Bạn đang xem bài viết Bài 4: Bài Toán Và Thuật Toán được cập nhật mới nhất trên website Ictu-hanoi.edu.vn. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất.
Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán đó.Trả lời
Ví dụ bài toán tính diện tích tam giác
Phát biểu bài toán:
Cho ba cạnh của tam giác ABC là: x, y, z. Hãy tính diện tích tam giác ABC.
– Input: Ba cạnh tam giác X, y, X.
– Output: Diện tích tam giác.
Câu 2 trang 44 SGK Tin học 10 Dãy các thao tác sau:
Bước 1. Xoá bảng;
Bước 2. Vẽ đường tròn;
Bước 3. Quay lại bước 1; có phải là thuật toán không? Tại sao?
Hãy mô tả thuật toán giải các bài toán sau bàng cách liệt kê hoặc bằng sơ đồ khối.
Trả lời
Dãy các thao tác sau:
Bước I. Xoá bàng;
Bước 2. Vẽ dường tròn;
Bước 3. Quay lại bước 1;
Đây không phải là thuật toán, vì không thoả mãn tính chất dừng: đến bước 3 lại quay lại bước 1, nó tạo thành vòng lặp vô hạn không có điều kiện kết thúc.
Câu 3 trang 44 SGK Tin học 10 Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.
Trả lời:
Thuật toán tìm kiếm tuần tự:
Bước 1. Nhập N, các số hạng a,…a 2,…a N và khoá k
Bước 2. i
Bước 3. Nếu a i= k thì thông báo chỉ số i, rồi kết thúc;
Bước 4. i
Bước 6. Quay lại bước 3.
Tính dùng cùa thuật toán tìm kiếm tuần tự: nghĩa là thuật toán phải kết thúc sau một số hữu hạn lần bước tính.
Thuật toán chia làm hai trường hợp
– Nếu tìm thấy giá trị cần tìm trong dãy A (a i= k) thì thông báo chỉ số i (vị trí tìm thấy khoá k trong dãy A), rồi kết thúc.
Câu 4 trang 44 SGK Tin học 10 Cho N và dãy số a1….aN, hãy tìm giá trị nhỏ nhất (Min) của dãy đó.
Trả lời:
– Xác định bài toán:
Output: Giá trị nhỏ nhất (Min) của dãy số.
– Ý tưởng:
Khởi tạo giá trị Min = a1.
Lần lượt nhận giá trị /i từ 2 đến N, so sánh giá trị số hạng a1 với giá trị Min, nếu ai < Min thì Min nhận giá trị mới ai
– Thuật toán:
Mô tả thuật toán theo cách liệt kê:
Bước 2. Mini, i
Bước 4.
Bước 4.1: Nếu a i < Min thì Mini
Bước 4.2: i
Câu 6 trang 44 SGK Tin học 10 Cho N và dãy số a1… aN, hãy sắp xếp dãy số đó thành dãy số không tăng (số hạng trước lớn hơn hay bằng số hạng sau).
Trả lời:
Xác điịnh bài toán
– Output: Dãy A được sắp xếp lại thành dãy không tăng:
Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước nhỏ hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
Thuật toán Cách liệt kê:
Bước 1. Nhập N, các số hạng a,,a 2…, a N;
Bước 2: M
Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4: M
Bước 5: i
Bước 7: Nếu a i < a i+1thì tráo đổi a i và a i+1 cho nhau
Bước 8: Quay lại bước 5
Sơ đồ khối:
Câu 7 trang 44 SGK Tin học 10 Cho N và dãy số a1….aN hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0.
Trả lời:
– Output: Số số hạng trong dãy A có giá trị bằng 0.
– Thuật toán
Cách liệt kê
Bước 2. i
Bước 3. Nếu a i= 0 thì k
Bước 4. i
Bước 6. Quay lại bước 3.
Sơ đồ khối
Câu 5 trang 44 SGK Tin học 10
Mô tả thuật toán tìm nghiệm của phương trình bậc hai tổng quát bằng cách liệt kê hoặc bằng sơ đồ khối.
Trả lời:
– Input: Các số thực a, h, c (a≠0).
– Output: Các số thực X thoả mãn ax 2 + bx + c = 0.
– Ý tưởng:
– Tính d = b 2 – 4ac.
– Lần lượt xét ba trường hợp cho giá trị d:
nếu d
nếu d = 0 thì kết luận phương trình có một nghiệm x =-b/2a
x – (-b± √ d ) / 2a.
Mô tả thuật toán bằng cách liệt kê:
Bước I. Nhập ba số a, b, c;
Bước 2. d 4-(b*b – 4*a*c);
Bước 3.
nếu d < 0 thì đưa ra thông báo phương trình vô nghiệm rồi kết thúc;
nếu d = 0 thì đưa ra thông báo phương trình có một nghiệm và tính nghiệm
x = -b/(2*a), rồi kết thúc;
Mô tả thuật toán theo sơ đồ khối:
chúng tôi
Thuật Toán Mã Hóa Và Giải Mã Des
Bài viết này giới thiệu về thuật toán mã hóa và giải mã dữ liệu DES (Data Encryption Standard). Đây là thuật toán mã hóa dữ liệu được công bố 25/10/1999 trong tài liệu về chuẩn xử lý thông tin liên bang Hoa Kỳ FIPS 46-3.1. Một số thuật ngữ sử dụng
Encipher – Bộ mã hóa
Decipher – Bộ giải mã
Plaintext – Bản rõ là dữ liệu gốc chưa được mã hóa
Ciphertext – Bản mã là dữ liệu đã dược mã hóa
Key – khóa mã là một giá trị được sử dụng để mã hóa và giải mã
Round key – khóa vòng là những giá trị trung gian được tạo ra từ khóa mã trong suốt quá trình mã hóa và giải mã
2. Thuật toán mã hóa dữ liệu DES – Encipher
2.1 Lưu đồ thuật toán mã hóa
Thuật toán DES được sử dụng để mã hóa và giải mã các block (khối) dữ liệu 64 bit dựa trên một key (khóa mã) 64 bit. Chú ý, các block được đánh số thứ tự bit từ trái sang phải và bắt đầu từ 1, bit đầu tiên bên trái là bit số 1 và bit cuối cùng bên phải là bit số 64. Quá trình giải mã và mã hóa sử dụng cùng một key nhưng thứ tự phân phối các giá trị các bit key của quá trình giải mã ngược với quá trình mã hóa.
Một block dữ liệu sẽ được hoán vị khởi tạo (Initial Permutation) IP trước khi thực hiện tính toán mã hóa với key. Cuối cùng, kết quả tính toán với key sẽ được hoán vị lần nữa để tạo ra , đây là hoán vị đảo của hoán vị khởi tạo gọi là (Inverse Initial Permutation) IP-1. Việc tính toán dựa trên key được định nghĩa đơn giản trong một hàm f, gọi là hàm mã hóa, và một hàm KS, gọi là hàm phân phối key (key schedule). Hàm KS là hàm tạo ra các khóa vòng (round key) cho các lần lặp mã hóa. Có tất cả 16 khóa vòng từ K1 đến K16.2.2 Hoán vị khởi tạo – IP
Hoán vị là thay đổi ví trí các bit trong một chuỗi giá trị nhưng không làm thay đổi giá trị của các bit này. Đây là bước đầu tiên trong quy trình mã hóa dữ liệu. 64 bit dữ liệu đầu vào, gọi là plaintext, sẽ được hoán vị theo bảng mô tả sau đây. Chuỗi bit đầu vào được đánh số từ 1 đến 64 (tính từ trái qua phải). Sau đó, các bit này được thay đổi vị trí như sơ đồ IP, bit số 58 được đặt vào vị trí đầu tiên, bit số 50 được đặt vào vị trí thứ 2. Cứ như vậy, bit thứ 7 được đặt vào vị trí cuối cùng.
Sau hoán vị, chuỗi bit mới được phân ra làm hai đoạn, mỗi đoạn 32 bit để bắt đầu vào quy trình tính toán mã hóa với key. Đoạn bên trái ký hiệu là L, đoạn bên phải ký hiệu là R. Đoạn L gồm các bit từ bit số 1 đến bit số 32, đoạn R gồm các bit từ bit số 33 đến bit số 64. Đoạn L của lần tính toán sau sẽ chính là đoạn R của lần tính toán trước. Đoạn R của lần tính toán sau sẽ được tính từ đoạn R trước đó qua hàm mã hóa f(R, K) rồi XOR với đoạn L của lần tính trước đó.
2.3 Hàm mã hóa f(R,K) Đầu tiên, 32 bit của đoạn R được đánh số từ 1 đến 32 theo thứ tự từ trái qua phải. Giá trị này sẽ được chuyển đổi thông qua bảng tra E để tạo thành một giá trị 48 bit. Bit đầu tiên trong chuỗi giá trị 48 bit là bit số 32 của R, bit thứ 2 là bit số 1 của R, bit thứ 3 là bit số 2 của R và bit cuối cùng là bit số 1 của R. Sau khi tra bảng E, giá trị 48 bit được XOR với 48 bit của khóa vòng (cách tạo ra khóa vòng 48 bit sẽ được trình bày sau). Kết quả phép XOR được chia làm 8 block được đánh số từ 1 đến 8 theo thứ tự từ trái qua phải, mỗi block 6 bit. Mỗi block sẽ được biến đổi thông qua các hàm lựa chọn riêng biệt. Tương ứng với 8 block sẽ có 8 hàm chuyển đổi (selection function) riêng biệt là S1, S2, S3, S4, S5, S6, S7 và S8. Việc chuyển đổi giá trị của các hàm S1, S2, …, S8 được thực hiện bằng cách tách block 6 bit thành hai phần. Phần thứ nhất là tổ hợp của bit đầu tiên và bit cuối cùng của block để tạo thành 2 bit chọn hàng của bảng S, bảng S có 4 hàng được đánh số từ 0 đến 3 theo thứ tự từ trên xuống. Phần thứ 2 là 4 bit còn lại dùng để chọn cột của bảng S, bảng S có 16 cột được đánh số từ 0 đến 15 theo thứ tự từ trái qua phải. Như vậy, với mỗi block 8 bit ta chọn được 1 giá trị trong bảng S. Giá trị này nằm trong khoảng từ 0 đến 15 sẽ được quy đổi thành chuỗi nhị phân 4 bit tương ứng. Các chuỗi nhị phân có được sau khi chuyển đổi từ S1 đến S8 sẽ được ghép lại theo thứ tự từ trái qua phải để tạo thành một giá trị 32 bit.
Qua bước chuyển đổi với các hàm lựa chọn S, kết quả thu được là một giá trị 32 bit. Giá trị này được đưa qua một hàm hoán vị P để tạo ra giá trị hàm f. Giá trị 32 bit thu được từ các chuyển đổi với hàm lựa chọn S sẽ được đánh số từ 1 đến 32 theo thứ tự từ trái qua phải.
Theo bảng hoán vị P, bit đầu tiên sau hoán vị sẽ là bit số 16, bit thứ 2 sẽ là bit số 7 và bit cuối cùng sẽ là bit số 25. Hàm tính toán mã hóa f(R, K) được định nghĩa như sau:
P(): là phép hoán vị P
Sn: là phép chuyển đổi block n (n chạy từ 1 đến 8) với hàm lựa chọn S
Bn: là block 6 bit thứ n (n chạy từ 1 đến 8). Block này lấy từ phép toán XOR giữa khóa vòng K và giá trị hàm E(R)
E(R): là hàm chuyển đổi giá trị R 32 bit thành giá trị 48 bit
Một key có 64 bit nhưng chỉ có 56 bit được sử dụng để thực hiện tính toán giá trị khóa vòng. Key được chia làm 8 byte. Các bit ở vị trí 8, 16, 32, 40, 48, 56 và 64 là các bit parity được sử dụng để kiểm tra độ chính xác của key theo từng byte vì khi key được phân phối trên đường truyền đến bộ mã hóa giải mã thì có thể xảy ra lỗi. Parity được sử dụng là parity lẻ (odd parity). Key gốc sẽ được thực hiện hoán vị lựa chọn PC-1. Key được đánh số từ 1 đến 64 theo thứ tự từ trái qua phải. Bảng hoán vị lựa chọn PC-1 có hai phần. Phần đầu dùng để xác định giá trị C0 và phần sau dùng để xác định giá trị D0. Theo bảng trên thì C0 là chuỗi bit có thứ tự là 57, 49, 41, …, 36 lấy từ key gốc, D0 là chuỗi bit có thứ tự là 63, 55, 47, …, 4 lấy từ key gốc.
Sau khi xác định được giá trị ban đầu để tính key là C0 và D0 thì các khóa vòng Kn (với n từ 1 đến 16) sẽ được tính theo nguyên tắc giá trị của khóa vòng thứ n sẽ được tính từ giá trị khóa vòng thứ n-1.
Trong đó Cn và Dn được tạo từ Cn-1 và Dn-1 bằng cách dịch trái các giá trị này với số bit được quy định trong bảng sau đây: Ví dụ, theo bảng trên, C3 và D3 có được từ C2 và D2 bằng cách dịch trái 2 bit. Hay C16 và D16 có được từ C15 và D15 bằng cách dịch trái 1 bit. Dịch trái ở đây được hiểu là quay trái như minh họa sau đây:
Sau khi tính được Cn và Dn thì chuỗi CnDn sẽ được đánh số từ 1 đến 56 theo thứ tự từ trái sang phải và được hoán vị lựa chọn lần 2 theo bảng hoán vị PC-2. Như vậy bit đầu tiên của khóa vòng Kn là bit số 14 của chuỗi CnDn, bit thứ 2 là bit số 17 của chuỗi CnDn và bit cuối cùng là bit số 32 của chuỗi CnDn.
2.5 Hoán vị khởi tạo đảo IP-1
Đây là bước cuối cùng để tạo ra giá trị mã hóa. Giá trị của lần lặp mã hóa cuối cùng sẽ được hoán vị khởi tạo đảo IP-1 và tạo ra giá trị mã hóa plaintext.2.6 Ví dụ về mã hóa DES
Giả sử ta có dữ liệu cần mã hóa và key là:
M = 00123456789abcde (Hex) = 0000 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1111
K = 0133457799bbcdff (Hex) = 0000 0001 0011 0011 0100 0101 0111 0111 1001 10001 1011 1011 1100 1100 1111 1111
Từ hai đầu vào này, giá trị của từng bước tính toán mã hóa DES sẽ được minh họa chi tiết sau đây.
2.6.1 Hoán vị khởi tạo – IP
Thông điệp M được đánh số vị trí bit từ trái qua phải như sau:
Sắp xếp lại thứ tự các bit của M theo bảng hoán vị IP, kết quả có được sau bước này là:
IP(M) = 98fecc00e054f0aa (Hex) = 1001 1000 1111 1110 1100 1100 0000 0000 1110 0000 0101 0100 1111 0000 1010 1010
2.6.2 Tính toán giá trị các khóa vòng – KS
Để tính toán hàm mã hóa f, chúng ta cần có giá trị khóa cho từng lần lặp mã hóa. Key ban đầu được đánh số thứ tự bit từ trái qua phải như sau:
Sau khi sắp xếp các bit theo bảng hoán vị PC-1 ở Hình 1‑8, kết quả thu được là hai giá trị đầu như sau:
C0 = f0ccaab (Hex) = 1111 0000 1100 1100 1010 1010 1011
D0 = aaccf0a (Hex) = 1010 1010 1100 1100 1111 0000 1010
Để tính khóa vòng đầu tiên K1 thì C0 và D0 sẽ được dịch (quay) trái 1 bit. Giá trị thu được sau khi dịch trái là:
C1 = e199557 (Hex) = 1110 0001 1001 1001 0101 0101 0111
D1 = 5599e15 (Hex) = 0101 0101 1001 1001 1110 0001 0101
Hai chuỗi C1 và D1 được ghép lài thành một chuỗi 56 bit là e1995575599e15. Chuỗi này được hoán vị bằng bảng PC-2 ở Hình 1‑11 để được giá trị khóa vòng 48 bit thứ nhất K1.
Để tính khóa vòng K2 thì lấy C1 và D1 dịch trái với số lượng bit theo bảng ở Hình 1‑9, rồi lấy kết quả hoán vị theo bảng PC-2. Quá trình cứ tiếp tục cho đến khóa vòng cuối cùng là K16. Kết quả các khóa vòng 48 bit thu được là:
K2 = 69aed925ae66 (Hex)
K3 = 55fc8ab4acd2
K4 = 72add2ad8657
K5 = 7cec071fe6c2
K6 = 63a51e3cc545
K7 = 6c84b78ae4c6
K8 = f7883aece781
K9 = c0dbeb27b839
K10 = b1f347631d76
K11 = 215fc30d89be
K12 = 7171f5455cd5
K13 = 95c5d14b80fd
K14 = 5743b783đ8d
K15 = bf91850a17b5 K16 = cb3d0bbc7072
2.6.3 Tính hàm mã hóa f(R,K)
Sau bước hoán vị khởi tạo IP, giá trị IP(M) sẽ được tách làm hai phần là:
R0 = e054f0aa (Hex) = 1110 0000 0101 0100 1111 0000 1010 1010
L0 = 98fecc00 (Hex) = 1001 1000 1111 1110 1100 1100 0000 0000
Giá trị 32 bit của R0 được tra qua bảng E để tạo ra một giá trị 48 bit.
Giá trị này được XOR với khóa vòng thứ nhất K1 và được kết quả
XOR(E(R0), K1) = 6b0046a15cf0 (Hex)
Giá trị trên được chia thành 8 nhóm theo thứ tự từ trái qua phải, mỗi nhóm 6 bit để đưa đến các bảng S. Các giá trị đầu ra sau bước tra các bảng S sẽ được ghép lại theo thứ tự từ S1 đến S8 để được 1 giá trị 32 bit.
S1()S2()S3()S4()S5()S6()S7()S8() = 10010101110100111010110101010000 = 95d3ad50 (Hex)
Giá trị này được hoán vị bằng bảng P để cho ra giá trị của hàm f.
f(R0,K1) = 97d1619a (Hex) = 1001 0111 1101 0001 0110 0001 1001 1010
Tương tự, ta có giá trị hàm f tại các vòng lặp mã hóa còn lại như sau:
f(R1,K2) = 88488d0b (Hex)
f(R2,K3) = da3b2692
f(R3,K4) = f44950b2
f(R4,K5) = d83237fd
f(R5,K6) = afc43b25
f(R6,K7) = 4e5123a2
f(R7,K8) = 6cfdecb8
f(R8,K9) = fb0600b1
f(R9,K10) = d51508e4
f(R10,K11) = fcf67146
f(R11,K12) = 704fa3a5
f(R12,K13) = 7bfe2806
f(R13,K14) = 65fc7a48
f(R14,K15) = 513f1d11 f(R15,K16) = cbf5252d
2.6.4 Giá trị tại mỗi vòng lặp mã hóa
Giá trị của hàm f(R,K) được sử dụng để tính giá trị Rn và Ln tại mỗi vòng lặp mã hóa theo công thức:
Thay vào công thức trên ta có các kết quả như sau:
2.6.5 Hoán vị khởi tạo đảo IP-1
Giá trị R16 và L16 của vòng lặp mã hóa cuối cùng sẽ được ghép lại thành một chuỗi 64 bit để thực hiện hoán vị theo bảng IP-1.
Kết quả của phép hoán vị này chính là giá trị mã hóa (ciphertext) cần tính.
IP-1(R16, L16) = 1abff69d5a93e80b (Hex) = 0001 1010 1011 1111 1111 0110 1001 1101 0101 1010 1001 0011 1110 1000 0000 1011
3. Thuật toán giải mã dữ liệu DES
Các bước của quá trình giải mã dữ liệu được thực hiện tương tự như quá trình mã hóa dữ liệu. Trong quá trình giải mã có một số thay đổi như sau:
Đầu vào lúc này là dữ liệu cần giải mã (ciphertext) và đầu ra là kết quả giải mã được (plaintext).
Khóa vòng sử dụng trong các vòng lặp giải mã có thứ tự ngược với quá trình mã hóa. Nghĩa là, tại vòng lặp giải mã đầu tiên, khóa vòng được sử dụng là K16. Tại vòng lặp giải mã thứ 2, khóa vòng được sử dụng là K15, và tại vòng lặp giải mã cuối cùng thì khóa vòng được sử dụng là K1.
Giải Thuật Và Lập Trình: §3. Đệ Quy Và Giải Thuật Đệ Quy
KHÁI NIỆM VỀ ĐỆ QUY
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó bằng quy nạp.
Ví dụ: Đặt hai chiếc gương cầu đối diện nhau. Trong chiếc gương thứ nhất chứa hình chiếc gương thứ hai. Chiếc gương thứ hai lại chứa hình chiếc gương thứ nhất nên tất nhiên nó chứa lại hình ảnh của chính nó trong chiếc gương thứ nhất… Ở một góc nhìn hợp lý, ta có thể thấy một dãy ảnh vô hạn của cả hai chiếc gương.
Một ví dụ khác là nếu người ta phát hình trực tiếp phát thanh viên ngồi bên máy vô tuyến truyền hình, trên màn hình của máy này lại có chính hình ảnh của phát thanh viên đó ngồi bên máy vô tuyến truyền hình và cứ như thế…
Trong toán học, ta cũng hay gặp các định nghĩa đệ quy:
GIẢI THUẬT ĐỆ QUY
Nếu lời giải của một bài toán P được thực hiện bằng lời giải của bài toán P’ có dạng giống như P thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy. Mới nghe thì có vẻ hơi lạ nhưng điểm mấu chốt cần lưu ý là: P’ tuy có dạng giống như P, nhưng theo một nghĩa nào đó, nó phải “nhỏ” hơn P, dễ giải hơn P và việc giải nó không cần dùng đến P.
Trong Pascal, ta đã thấy nhiều ví dụ của các hàm và thủ tục có chứa lời gọi đệ quy tới chính nó, bây giờ, ta tóm tắt lại các phép đệ quy trực tiếp và tương hỗ được viết như thế nào:
Định nghĩa một hàm đệ quy hay thủ tục đệ quy gồm hai phần:
Phần neo (anchor): Phần này được thực hiện khi mà công việc quá đơn giản, có thể giải trực tiếp chứ không cần phải nhờ đến một bài toán con nào cả.
Phần đệ quy: Trong trường hợp bài toán chưa thể giải được bằng phần neo, ta xác định những bài toán con và gọi đệ quy giải những bài toán con đó. Khi đã có lời giải (đáp số) của những bài toán con rồi thì phối hợp chúng lại để giải bài toán đang quan tâm.
Phần đệ quy thể hiện tính “quy nạp” của lời giải. Phần neo cũng rất quan trọng bởi nó quyết
định tới tính hữu hạn dừng của lời giải.
VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUY
Hàm tính giai thừa
function Factorial(n: Integer): Integer; {Nhận vào số tự nhiên n và trả về n!}
begin
if n = 0 then Factorial := 1 {Phần neo}
else Factorial := n * Factorial(n – 1); {Phần đệ quy}
end;
Ví dụ: Dùng hàm này để tính 3!, trước hết nó phải đi tính 2! bởi 3! được tính bằng tích của 3 * 2!. Tương tự để tính 2!, nó lại đi tính 1! bởi 2! được tính bằng 2 * 1!. Áp dụng bước quy nạp này thêm một lần nữa, 1! = 1 * 0!, và ta đạt tới trường hợp của phần neo, đến đây từ giá trị 1 của 0!, nó tính được 1! = 1*1 = 1; từ giá trị của 1! nó tính được 2!; từ giá trị của 2! nó tính được 3!; cuối cùng cho kết quả là 6:
3! = 3 * 2! ↓ 2! = 2 * 1! ↓ 1! = 1 * 0! ↓ 0! = 1
Dãy số Fibonacci
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán đặt ra như sau:
Các con thỏ không bao giờ chết
Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp. Ví dụ, n = 5, ta thấy:
Giữa tháng thứ 1:1 cặp (ab) (cặp ban đầu)
Giữa tháng thứ 2:1 cặp (ab) (cặp ban đầu vẫn chưa đẻ)
Giữa tháng thứ 3:2 cặp (AB)(cd) (cặp ban đầu đẻ ra thêm 1 cặp con) Giữa tháng thứ 4:3 cặp (AB)(cd)(ef) (cặp ban đầu tiếp tục đẻ)
Giữa tháng thứ 5:5 cặp (AB)(CD)(ef)(gh)(ik) (cả cặp (AB) và (CD) cùng đẻ) Bây giờ, ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n)
Nếu mỗi cặp thỏ ở tháng thứ n – 1 đều sinh ra một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là:
F(n) = 2 * F(n – 1)
Nhưng vấn đề không phải như vậy, trong các cặp thỏ ở tháng thứ n – 1, chỉ có những cặp thỏ đã có ở tháng thứ n – 2 mới sinh con ở tháng thứ n được thôi. Do đó F(n) = F(n – 1) + F(n – 2) (= số cũ + số sinh ra). Vậy có thể tính được F(n) theo công thức sau:
F(n) = 1 nếu n ≤ 2
function F(n: Integer): Integer; {Tính số cặp thỏ ở tháng thứ n}
begin
if n £ 2 then F := 1 {Phần neo}
else F := F(n – 1) + F(n – 2); {Phần đệ quy}
end;
Giả thuyết của Collatz
Collatz đưa ra giả thuyết rằng: với một số nguyên dương X, nếu X chẵn thì ta gán X := X div 2; nếu X lẻ thì ta gán X := X * 3 + 1. Thì sau một số hữu hạn bước, ta sẽ có X = 1.
Ví dụ: X = 10, các bước tiến hành như sau:
1. X = 10 (chẵn)⇒X := 10 div 2;(5)Cứ cho giả thuyết Collatz là đúng đắn, vấn đề đặt ra là: Cho trước số 1 cùng với hai phép toán * 2 và div 3, hãy sử dụng một cách hợp lý hai phép toán đó để biến số 1 thành một giá trị nguyên dương X cho trước.
Ví dụ: X = 10 ta có 1 * 2 * 2 * 2 * 2 div 3 * 2 = 10.
Nếu X chẵn, thì ta tìm cách biểu diễn số X div 2 và viết thêm phép toán * 2 vào cuối Nếu X lẻ, thì ta tìm cách biểu diễn số X * 3 + 1 và viết thêm phép toán div 3 vào cuối
procedure Solve(X: Integer); {In ra cách biểu diễn số X}
begin
if X = 1 then Write(X) {Phần neo}
else {Phần đệ quy}
if X mod 2 = 0 then {X chẵn}
begin
Solve(X div 2); {Tìm cách biểu diễn số X div 2} Write(‘ * 2’); {Sau đó viết thêm phép toán * 2} end
else {X lẻ}
begin
Solve(X * 3 + 1); {Tìm cách biểu diễn số X * 3 + 1}
Write(‘ div 3’); {Sau đó viết thêm phép toán div 3}
end;
end;
procedure Solve(X: Integer); forward; {Thủ tục tìm cách biểu diễn số X: Khai báo trước, đặc tả sau}
begin
Solve(X * 3 + 1);
Write(‘ div 3’); end;
procedure SolveEven(X: Integer); {Thủ tục tìm cách biểu diễn số X trong trường hợp X chẵn}
begin
Solve(X div 2);
Write(‘ * 2’); end;
procedure Solve(X: Integer); {Phần đặc tả của thủ tục Solve đã khai báo trước ở trên}
begin
if X = 1 then Write(X) else
if X mod 2 = 1 then SolveOdd(X) else SolveEven(X);
end;
Trong cả hai cách viết, để tìm biểu diễn số X theo yêu cầu chỉ cần gọi Solve(X) là xong. Tuy nhiên trong cách viết đệ quy trực tiếp, thủ tục Solve có lời gọi tới chính nó, còn trong cách viết đệ quy tương hỗ, thủ tục Solve chứa lời gọi tới thủ tục SolveOdd và SolveEven, hai thủ tục này lại chứa trong nó lời gọi ngược về thủ tục Solve.
Đối với những bài toán nêu trên, việc thiết kế các giải thuật đệ quy tương ứng khá thuận lợi vì cả hai đều thuộc dạng tính giá trị hàm mà định nghĩa quy nạp của hàm đó được xác định dễ dàng.
Nhưng không phải lúc nào phép giải đệ quy cũng có thể nhìn nhận và thiết kế dễ dàng như vậy. Thế thì vấn đề gì cần lưu tâm trong phép giải đệ quy?. Có thể tìm thấy câu trả lời qua việc giải đáp các câu hỏi sau:
Có thể định nghĩa được bài toán dưới dạng phối hợp của những bài toán cùng loại nhưng nhỏ hơn hay không ? Khái niệm “nhỏ hơn” là thế nào ?
Trường hợp đặc biệt nào của bài toán sẽ được coi là trường hợp tầm thường và có thể giải ngay được để đưa vào phần neo của phép giải đệ quy
Bài toán Tháp Hà Nội
Đây là một bài toán mang tính chất một trò chơi, tương truyền rằng tại ngôi đền Benares có ba cái cọc kim cương. Khi khai sinh ra thế giới, thượng đế đặt n cái đĩa bằng vàng chồng lên nhau theo thứ tự giảm dần của đường kính tính từ dưới lên, đĩa to nhất được đặt trên một chiếc cọc.
Tháp Hà Nội
Các nhà sư lần lượt chuyển các đĩa sang cọc khác theo luật:
Khi di chuyển một đĩa, phải đặt nó vào một trong ba cọc đã cho
Mỗi lần chỉ có thể chuyển một đĩa và phải là đĩa ở trên cùng
Tại một vị trí, đĩa nào mới chuyển đến sẽ phải đặt lên trên cùng
Đĩa lớn hơn không bao giờ được phép đặt lên trên đĩa nhỏ hơn (hay nói cách khác: một đĩa chỉ được đặt trên cọc hoặc đặt trên một đĩa lớn hơn).
Ngày tận thế sẽ đến khi toàn bộ chồng đĩa được chuyển sang một cọc khác.
Trong trường hợp có 2 đĩa, cách làm có thể mô tả như sau:
Chuyển đĩa nhỏ sang cọc 3, đĩa lớn sang cọc 2 rồi chuyển đĩa nhỏ từ cọc 3 sang cọc 2.
Những người mới bắt đầu có thể giải quyết bài toán một cách dễ dàng khi số đĩa là ít, nhưng họ sẽ gặp rất nhiều khó khăn khi số các đĩa nhiều hơn. Tuy nhiên, với tư duy quy nạp toán học và một máy tính thì công việc trở nên khá dễ dàng:
Có n đĩa.
Nếu n = 1 thì ta chuyển đĩa duy nhất đó từ cọc 1 sang cọc 2 là xong.
Giả sử rằng ta có phương pháp chuyển được n – 1 đĩa từ cọc 1 sang cọc 2, thì cách chuyển n – 1 đĩa từ cọc x sang cọc y (1 ≤ x, y ≤ 3) cũng tương tự.
Giả sử ràng ta có phương pháp chuyển được n – 1 đĩa giữa hai cọc bất kỳ. Để chuyển n đĩa từ cọc x sang cọc y, ta gọi cọc còn lại là z (=6 – x – y). Coi đĩa to nhất là … cọc, chuyển n – 1 đĩa còn lại từ cọc x sang cọc z, sau đó chuyển đĩa to nhất đó sang cọc y và cuối cùng lại coi đĩa to nhất đó là cọc, chuyển n – 1 đĩa còn lại đang ở cọc z sang cọc y chồng lên đĩa to nhất.
procedure Move(n, x, y: Integer); {Thủ tục chuyển n đĩa từ cọc x sang cọc y}
begin
if n = 1 then WriteLn(‘Chuyển 1 đĩa từ ‘, x, ‘ sang ‘, y)
begin
Move(n – 1, x, 6 – x – y); {Chuyển n – 1 đĩa từ cọc x sang cọc trung gian}
Move(1, x, y); {Chuyển đĩa to nhất từ x sang y}
Move(n – 1, 6 – x – y, y); {Chuyển n – 1 đĩa từ cọc trung gian sang cọc y}
end;
end;
Chương trình chính rất đơn giản, chỉ gồm có 2 việc: Nhập vào số n và gọi Move(n, 1, 2).
HIỆU LỰC CỦA ĐỆ QUY
Qua các ví dụ trên, ta có thể thấy đệ quy là một công cụ mạnh để giải các bài toán. Có những bài toán mà bên cạnh giải thuật đệ quy vẫn có những giải thuật lặp khá đơn giản và hữu hiệu. Chẳng hạn bài toán tính giai thừa hay tính số Fibonacci. Tuy vậy, đệ quy vẫn có vai trò xứng đáng của nó, có nhiều bài toán mà việc thiết kế giải thuật đệ quy đơn giản hơn nhiều so với lời giải lặp và trong một số trường hợp chương trình đệ quy hoạt động nhanh hơn chương trình viết không có đệ quy. Giải thuật cho bài Tháp Hà Nội và thuật toán sắp xếp kiểu phân đoạn (QuickSort) mà ta sẽ nói tới trong các bài sau là những ví dụ.
Có một mối quan hệ khăng khít giữa đệ quy và quy nạp toán học. Cách giải đệ quy cho một bài toán dựa trên việc định rõ lời giải cho trường hợp suy biến (neo) rồi thiết kế làm sao để lời giải của bài toán được suy ra từ lời giải của bài toán nhỏ hơn cùng loại như thế. Tương tự như vậy, quy nạp toán học chứng minh một tính chất nào đó ứng với số tự nhiên cũng bằng cách chứng minh tính chất đó đúng với một số trường hợp cơ sở (thường người ta chứng minh nó đúng với 0 hay đúng với 1) và sau đó chứng minh tính chất đó sẽ đúng với n bất kỳ nếu nó đã đúng với mọi số tự nhiên nhỏ hơn n.
Rõ ràng là tính chất này đúng với n = 1, bởi ta cần 2 1 – 1 = 1 lần chuyển đĩa để thực hiện yêu cầu.
Vậy thì công thức này sẽ đúng với mọi n.
Thật đáng tiếc nếu như chúng ta phải lập trình với một công cụ không cho phép đệ quy, nhưng như vậy không có nghĩa là ta bó tay trước một bài toán mang tính đệ quy. Mọi giải thuật đệ quy đều có cách thay thế bằng một giải thuật không đệ quy (khử đệ quy), có thể nói được như vậy bởi tất cả các chương trình con đệ quy sẽ đều được trình dịch chuyển thành những mã lệnh không đệ quy trước khi giao cho máy tính thực hiện.
Việc tìm hiểu cách khử đệ quy một cách “máy móc” như các chương trình dịch thì chỉ cần hiểu rõ cơ chế xếp chồng của các thủ tục trong một dây chuyền gọi đệ quy là có thể làm được. Nhưng muốn khử đệ quy một cách tinh tế thì phải tuỳ thuộc vào từng bài toán mà khử đệ quy cho khéo. Không phải tìm đâu xa, những kỹ thuật giải công thức truy hồi bằng quy hoạch động là ví dụ cho thấy tính nghệ thuật trong những cách tiếp cận bài toán mang bản chất đệ quy để tìm ra một giải thuật không đệ quy đầy hiệu quả.
Bài tập
Bài 1
Viết một hàm đệ quy tính ước số chung lớn nhất của hai số tự nhiên a, b không đồng thời bằng 0, chỉ rõ đâu là phần neo, đâu là phần đệ quy.
Bài 2
Viết một hàm đệ quy tính C k theo công thức truy hồi sau:
Chứng minh rằng hàm đó cho ra đúng giá trị:
C nk = n! / k!(n – k)!
Bài 3
Nêu rõ các bước thực hiện của giải thuật cho bài Tháp Hà Nội trong trường hợp n = 3. Viết chương trình giải bài toán Tháp Hà Nội không đệ quy.
Giải Bài Tập Trang 11, 12 Sgk Toán 4: Hàng Và Lớp Giải Bài Tập Toán Lớp 4
Giải bài tập trang 11, 12 SGK Toán 4: Hàng và lớp Giải bài tập Toán lớp 4
Giải bài tập 1, 2, 3, 4, 5 trang 11, 12 SGK Toán 4: Hàng và lớp
Hướng dẫn giải bài HÀNG NGHÌN VÀ LỚP (bài 1, 2, 3, 4, 5 SGK Toán lớp 4 trang 10, 12)
BÀI 1. (Hướng dẫn giải bài tập số 1 trang 11/SGK Toán 4)
Viết theo mẫu:
BÀI 2. (Hướng dẫn giải bài tập số 2 trang 11/SGK Toán 4)
a) Đọc các số sau và cho biết chữ số 3 ở mỗi số đó thuộc hàng nào lớp nào:
46 307 ; 56 032 ; 123 517 ; 305 804 ; 960 783.
b) Ghi giá trị của chữ số 7 trong mỗi số ở bảng sau:
a) 46 307 đọc là: Bốn mươi sáu nghìn ba trăm linh bảy. Chữ số 3 trong số 46 307 thuộc hàng trăm lớp đơn vị.
56 032 đọc là: Năm mươi sáu nghìn không trăm ba mươi hai. Chữ số 3 trong số 56 032 thuộc hàng chục lớp đơn vị.
123 517 đọc là: Một trăm hai mươi ba nghìn năm trăm mười bày. Chữ số 3 trong số 123 517 thuộc hàng nghìn lớp nghìn.
305 804 đọc là: Ba trăm linh lăm nghìn tám trăm linh bốn. Chữ số 3 trong số 305 804 thuộc hàng trăm nghìn lớp nghìn.
BÀI 3. (Hướng dẫn giải bài tập số 3 trang 12/SGK Toán 4)
960 783 đọc là: Chín trăm sáu mươi nghìn bảy trăm tám mươi ba. Chữ số 3 trong số 960 783 thuộc hàng đơn vị lớp đơn vị.
b)
Viết mỗi số sau thành tổng (theo mẫu):
52 314 ; 503 060 ; 83 760 ; 176 091.
Mẫu: 52314 = 50000 + 2000 + 300 + 10 + 4.
503 060 = 500 000 + 3 000 + 60.
BÀI 4. (Hướng dẫn giải bài tập số 4 trang 12/SGK Toán 4)
83 760 = 80 000 + 3000 + 700 + 60.
176 091 = 100 000 + 70 000 + 6000 + 90 + 1.
Viết số, biết số đó gồm:
a) 5 trăm nghìn, 7 trăm, 3 chục và 5 đơn vị;
b) 3 trăm nghìn, 4 trăm và 2 đơn vị;
c) 2 trăm nghìn, 4 nghìn và 6 chục;
d) 8 chục nghìn và 2 đơn vị.
a) 5 trăm nghìn, 7 trăm, 3 chục và 5 đơn vị = 500 735
b) 3 trăm nghìn, 4 trăm và 2 đơn vị = 300 402
BÀI 5. (Hướng dẫn giải bài tập số 5 trang 12/SGK Toán 4)
c) 2 trăm nghìn, 4 nghìn và 6 chục = 204 060
d) 8 chục nghìn và 2 đơn vị = 80 002.
Viết số thích hợp vào chỗ chấm (theo mẫu):
Mẫu: Lớp nghìn của số 832 573 gồm các chữ số: 8 ; 3 ; 2.
a) Lớp nghìn của số 603 786 gồm các chữ số: … ; … ; ….
b) Lớp đơn vị của số 603 785 gồm các chữ số: … ; … ; ….
c) Lớp đơn vị của số 532 004 gồm các chữ số: … ; … ; ….
a) Lớp nghìn của số 603 786 gồm các chữ số: 6 ; 0 ; 3.
b) Lớp đơn vị của số 603 785 gồm các chữ số: 7 ; 8 ; 5.
c) Lớp đơn vị của số 532 004 gồm các chữ số: 0 ; 0 ; 4.
Cập nhật thông tin chi tiết về Bài 4: Bài Toán Và Thuật Toán trên website Ictu-hanoi.edu.vn. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Chúc bạn một ngày tốt lành!