Các thuật toán trong toán rời rạc

Chia sẻ: Chao Hello | Ngày: | Loại File: DOC | Số trang:5

Thêm vào BST

Báo xấu

382
lượt xem 106
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo về các thuật toán trong môn học toán rời rạc. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các thuật toán trong toán rời rạc

Các thuật toán trong toán rời rạc 1.Thuật toán tính nghiệm của phương trình bậc hai: ax2 + bx + c = 0 khi biết 3 hệ số a, b, c (a ? 0). Bước 1: Tính giá trị ∆ theo công thức ∆ = b2 - 4ac Bước 2: Xét dấu ∆ , ta có kết quả tùy thuộc một trong 3 trường hợp sau đây: Trường hợp ∆ > 0: Phương trình có 2 nghiệm được tính theo công thức x= Trường hợp ∆ = 0: Phương trình có nghiệm kép được tính theo công thức x= Trường hợp ∆ < 0: Phương trình vô nghiệm. 2. Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên: Nhập: dãy số a1, a2, . . ., an Xuất: max là giá trị lớn nhất trong dãy số đã cho trong input. Thuật toán: 1. max := a1 2. for i := 2 to n do if max < a1 then max := a1 3. max là giá trị lớn nhất trong dãy số. 3. Thuật toán giải phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0): Nhập : 3 hệ số a, b, c Ðiều kiện : a ≠ 0
Xuất : nghiệm của phương trình Thuật toán: 1. delta := b2 - 4*a*c 2. if delta > 0 then begin x1 := (-b - sqrt(delta)) / (2*a); x2 := (-b+sqrt(delta)) / (2*a); Xuất kết quả: phương trình có hai nghiệm là x1 và x2; end 3. esle if delta = 0 then Xuất kết quả: phương trình có nghiệm kép là -b / (2*a) 4. else { trường hợp delta < 0} Xuất kết quả: phương trình vô nghiệm; (Trong thuật toán nầy, ký hiệu sqrt(delta) dùng để chỉ căn bậc hai dương của delta) 4. Thuật toán Tìm kiếm tuyến tính (hay tuần tự) Nhập : dãy a1, a2, . . ., an, và phần tử x. Xuất : vị trí của x trong dãy (chỉ số của phần tử trong dãy bằng với x), hoặc 0 Thuật toán: 1. i := 1 2. while ( i ≤ n and x ≠ ai ) do i := i + 1; 3. if i ≤ n then location := i else location := 0
4. location là một lời giải (ví trí cần tìm). Trong thuật toán nầy từ "location" là một biến nguyên. 5. Thuật toán kiểm tra tính đối xứng của một ma trận. Nhập : ma trận M cấp n. Xuất : Yes nếu ma trận M là ma trận đối xứng. No nếu M không đối xứng. Thuật toán: 1. for i := 1 to n-1 do 2. for j := i + 1 to n do 3. if Mij ≠ Mij then Kết xuất "No", và dừng thuật toán. 4. Kết xuất "Yes". 6. Thuật toán đệ quy tính giai thừa của một số tự nhiên. Input : số tự nhiên n. Output : F (n) bằng n!. Thuật toán : 1. F := 1 2. if n > 0 then F := F(n-1) * n; { Tính (n-1)! rồi nhân với n sẽ được giá trị F} 3. Output F. 7. Thuật toán đệ quy tính số hạng thứ n của dãy số Fibonacci. Input : số nguyên dương n. Output : F (n) bằng số hạng thứ n của dãy Fibonacci. Thuật toán :
1. if n=0 or n=1 then F := 1; 2. if n > 1 then F := F(n-1) + F(n-2) { tức là tính F(n-1) và F(n-2) rồi tính tổng số của các giá trị nầy để gán cho F} 3. Output F. 8. Thuật toán lặp tính số hạng thứ n của dãy số Fibonacci. Input : số nguyên dương n. Output : F (n) bằng số hạng thứ n của dãy Fibonacci. Thuật toán : 1. a := 1 2. F := 1 3. for i:=3 to n do begin temp := a + F; a := F; F := temp; end; 4. Output F. 9. Thuật toán lặp tính giai thừa của một số tự nhiên. Input : số tự nhiên n. Output : F (n) bằng n!. Thuật toán :
1. F := 1 2. for i := 2 to n do F := F * i 3. Output F. 10. Thuật toán tính tổ hợp n chọn k: Tohop(n,k) If (k = 0) or (k = n) then Tohop := 1; If (0 < k) and (k < n) then Tohop := Tohop(n-1, k) + Tohop(n-1, k-1); 11. Thuật toán tính USCLN của a và b: USCLN(a,b) If (a = 0) or (b = 0) then USCLN := a+b; Else If (a > b) then USCLN := USCLN(a-b, b); Else USCLN := USCLN(a, b -a);