Trong hướng dẫn này, bạn sẽ học cách viết các chức năng đệ quy trong lập trình C với sự trợ giúp của một ví dụ.
Video: C đệ quy
Một hàm tự gọi được gọi là hàm đệ quy. Và, kỹ thuật này được gọi là đệ quy.
Làm thế nào đệ quy hoạt động?
void recurse[]
{
... .. ...
recurse[];
... .. ...
}
int main[]
{
... .. ...
recurse[];
... .. ...
} làm việc đệ quyViệc đệ quy tiếp tục cho đến khi một số điều kiện được đáp ứng để ngăn chặn nó.
Để ngăn chặn đệ quy vô hạn, nếu ... tuyên bố khác [hoặc cách tiếp cận tương tự] có thể được sử dụng khi một nhánh thực hiện cuộc gọi đệ quy và những cái khác thì không.
Ví dụ: tổng số tự nhiên bằng cách sử dụng đệ quy
#include
int sum[int n];
int main[] {
int number, result;
printf["Enter a positive integer: "];
scanf["%d", &number];
result = sum[number];
printf["sum = %d", result];
return 0;
}
int sum[int n] {
if [n != 0]
// sum[] function calls itself
return n + sum[n-1];
else
return n;
}
Đầu ra
Enter a positive integer:3 sum = 6
Ban đầu,
factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
3 được gọi từ hàm factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
4 có số được truyền dưới dạng đối số.Giả sử, giá trị của n bên trong
factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
3 ban đầu là 3. Trong cuộc gọi chức năng tiếp theo, 2 được chuyển đến hàm factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
3. Quá trình này tiếp tục cho đến khi N bằng 0.Khi N bằng 0, điều kiện
factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
7 không thành công và phần factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
8 được thực thi trả lại tổng số nguyên cuối cùng cho hàm factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
4.Ưu điểm và bất lợi của đệ quy
Đệ quy làm cho chương trình thanh lịch. Tuy nhiên, nếu hiệu suất là quan trọng, thay vào đó hãy sử dụng các vòng vì đệ quy thường chậm hơn nhiều.
Điều đó đang được nói, đệ quy là một khái niệm quan trọng. Nó thường được sử dụng trong cấu trúc dữ liệu và thuật toán. Ví dụ, thông thường sử dụng đệ quy trong các vấn đề như truyền tải cây.
2.3 & nbsp; Đệ quy - Đệ QUY
Ý tưởng gọi một han từ bên trong một haH kác lập tức gợi đến Khả năng một ha Cơ chế ha Ệ quy là một kĩ thuật lập trì , Cho Đến Phương Pháp Xử Lý Tín Hiệu Số Biến đổi Fourier nhanh để xử lý tín hiệu [Chương 9].
Chương trình Đệ QUY ĐầU Tin.
Chương trình
Chào thế giớiCho Đệ QUY Là HÀM TínH GIIA THừ
N! = N × [n-1] × [n-2] × ... × 2 × 1
Ta thoại thể dễ dàng tính n! bằng một vngng
for, NHưng Cách Đó vẫn Chưa Đơn Giản
public static int factorial[int N] { if [N == 1] return 1; return N * factorial[N-1]; }
Bạn bạn thể tự chứng Minhng ha
factorial[]TRả Về 1 = 1! Khi
Nbằng 1 và nếu nó tính đếm
[N-1]! = [N-1] × [n-2] × ... × 2 × 1
thì nó cũng tính đaog giá trị
N! = N × [N-1]! = N × [n-1] × [n-2] × ... × 2 × 1
Ta đó là thể lần bước quá trình tính toán đó
factorial[5]
factorial[4]
factorial[3]
factorial[2]
factorial[1]
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
CÀi ĐặT HO không []
- Trường hợp cơ bản [trường hợp cơ sở] trả về Trường hợp cơ bản áp dụng cho một hoặc vào giá tr Factorial [], trường hợp cơ bản là khi sử dụng n = 1.
- BướC Đệ QUY [Bước giảm] Nó mô tả mối Quan hệ giữa ha với một [hoặc nhiều] input hiện tại với ha thó khi NGOÀi RA, Chuỗi Các Giá trị Tham Số Phải Hội Tụ về Trường Hợp Cơ Bản. Với factorial [], bước Đệ QUY lÀ n * FACTORAL [N-1] VÀ N GIảM ĐI 1 VớI MỗI LầN GọI HÀM
QUY Nạp Toán Học.
Lập trình đệ quy đó quan hệ trực tiếp với quy nạp toán học, một kĩ thul Việc Dùng QUY NạP Để Chứng MIH MộT Phát Biểu Về Một
- Trường hợp cơ bản là Chứng
- BướC QUY NạP Là Phần Trung tâm của Chứng Minh. V í dụ, ta thường gi ả thiết rằng pháti biểu màyng với mọi
Một chứng MINH NH N.
Thuật Toán Euclid.
Ước Số Chung lớn NHất - Ưu điểm chung lớn nhất [GCD] Ví dụ, ucln của 102 vào
Taó thể tính ucln - gcd một cách rất hiệu quảu sử dụng tính chất Sau đó
Nếu p > q, thì UCLN[p,q] = UCLN[q, p % q].
Phương thức static gcd[] trong Euclid.java là một hàm đệ quy ngắn gọn với bước đệ quy dựa vào tính chất trên.
gcd[1440, 408]
gcd[408, 216]
gcd[216, 192]
gcd[192, 24]
gcd[24, 0]
return 24
return 24
return 24
return 24
return 24
Bài toán Tháp Hà Nội.
Một bài giảng về đệ quy không thể hoàn chỉnh nếu không nhăc đến bài toán cổ Tháp Hà Nội. Ta có ba cột và n đĩa có thể xếp lồng vào các cột đó. Các cái đĩa đó có kích thước khác nhau và ban đầu được xếp vào một cột trong số đó, theo thứ tự đĩa lớn bên dưới, đĩa nhỏ bên trên [đĩa n nằm dưới đáy và đĩa 1 trên đỉnh]. Nhiệm vụ là di chuyển chồng đĩa sang một cột khác, tuân thủ các quy tắc sau:
- Mỗi lần chỉ được di chuyển một đĩa.
- Không bao giờ đặt một đĩa lên trên một đĩa nhỏ hơn.
Để giải bài toán, mục tiêu của ta là tạo ra một chuỗi lệnh di chuyển đĩa. Giả sử các cột được xếp thành hàng, mỗi lệnh di chuyển đĩa quy định 2 thông tin: số hiệu đĩa cần di chuyển và hướng di chuyển [trái hay phải]. Với một đĩa nằm trên cột bên trái, lệnh chuyển sang trái có tác dụng xoay vòng chuyển nó sang cột bên phải; với một đĩa nằm trên cột phải, lệnh di chuyển sang phải sẽ xoay vòng chuyển nó sang cột bên trái.
Exponential time - thời gian chạy lũy thừa.
Một truyền thuyết nói rằng trong một ngôi đền có một nhóm các nhà sư ngồi giải bài toán Tháp Hà Nội với 64 cái đĩa bằng vàng trên ba chiếc kim bằng kim cương. Khi các nhà sư này giải xong thì ngày đó sẽ là ngày tận thế. Ta có thể ước lượng thời gian cho đến ngày tận thế đó [giả sử truyền thuyết kia đúng]. Nếu ta định nghĩa hàm T[n] là số lệnh di chuyển mà chương trình TowersOfHanoi.java sinh ra để di chuyển n đĩa từ một cột sang một cột khác, thì hàm đệ quy cho thấy T[n] phải thỏa mãn hệ phương trình sau:
T[n] = 2 T[n - 1] + 1 với n > 1, và T[1] = 1
Một hệ phương trình như vậy trong toán rời rạc được gọi là một quan hệ đệ quy - recurrence relation. Ta thường dùng chúng để rút ra một biểu thức dạng đóng là công thức cho một đại lượng quan tâm. Chẳng hạn, T[1] = 1, T[2] = 3, T[3] = 7, and T[4] = 15. Tổng quát, T[n] = 2^n - 1.
Khi biết giá trị của T[n], ta có thể ước lượng thời gian cần thiết để thực hiện tất cả các bước di chuyển. Nếu cứ mỗi giây, các nhà sư lại chuyển được một đĩa, họ sẽ cần 1 tuần để giải xong bài toán 20 đĩa, hơn 31 năm cho bài toán 30 đĩa, và hơn 348 thế kỉ cho một bài toán 40 đĩa [giả thiết rằng họ không di chuyển nhầm bước nào]. Bài toán 64 đĩa sẽ cần đến hơn 5,8 tỷ thế kỷ.
Gray code - Mã Gray.
Nhà biên kịch Samuel Beckett đã viết một vở kịch có tên Quad với tính chất sau: Mở màn là một sân khấu trống rỗng, mỗi thời điểm chỉ có nhiều nhất 01 nhân vật vào hoặc ra sân khấu. Nhưng mỗi nhóm nhân vật xuất hiện trên sân khấu đúng 01 lần. Vở kịch có bốn nhân vật. Do đó có 2^4 = 16 nhóm nhân vật khác nhau, nghĩa là 16 tập con của tập hợp gồm 4 phần tử; Cái tên của vở kịch xuất phát từ đó. Hỏi Beckett làm thế nào để tạo ra hướng dẫn vào ra cho vở kịch này. Nếu số nhân vật là 5 hoặc nhiều hơn thì ta làm cách nào? [enter: ra sân khấu, exit: vào bên trong cánh gà - ra khỏi sân khấu].
Mã Gray n-bit là một danh sách gồm 2^n số nhị phân n-bit khác nhau sao cho mỗi số trong danh sách đều khác số liền trước nó đúng 01 bit. Mã Gray áp dụng trực tiếp cho bài toán của Beckett vì ta có thể coi mỗi số nhị phân trong dãy đại diện cho một tập con của n phần tử, với mỗi bit đại diện cho việc số tự nhiên tương ứng với vị trí của bit đó có nằm trong tập con đó hay không. Việc thay đổi giá trị của một bit từ 0 đến 1 tương ứng với việc một số nguyên được đưa vào tập con; thay đổi từ 1 về 0 ứng với việc một số tự nhiên ra khỏi tập con.
Ta sinh mã Gray bằng cách nào? Một kế hoạch đệ quy khá tương tự với thuật toán đã dùng cho bài Tháp Hà Nội. Bộ số nhị phân n bit biểu diễn mã Gray được định nghĩa một cách đệ quy như sau:
- bộ mã n-1 bit, gắn thêm một bit 0 ở trước mỗi từ, tiếp theo là
- bộ mã n-1 bit, gắn thêm một bit 1 ở trước mỗi từ.
Bộ mã 0-bit được định nghĩa là dãy rỗng, Bộ mã 1-bit gồm 2 từ: 0 và 1. Sau khi nghĩ cẩn thận một chút, ta sẽ thấy định nghĩa đệ quy dẫn đến cài đặt tại Beckett.java cho chương trình in ra hướng dẫn sân khấu của Beckett.
Recursive graphics - Đồ họa đệ quy.
Một thuật toán vẽ đệ quy đơn giản có thể đem lại một hình ảnh rất phức tạp. Ví dụ, một hình H-tree bậc n được định nghĩa như sau: Trường hợp cơ bản, n = 0, là hình rỗng không. Bước đệ quy là vẽ ba đoạn thẳng tạo thành hình chữ H trong phạm vi hình vuông đơn vị, và bốn hình H-tree bậc n-1 tại bốn đầu mút của chữ H vừa vẽ. Điều kiện bổ sung là các hình H-tree bậc n-1 nằm tại tâm của bốn mảng 1/4 của hình vuông nói trên, với kích thước giảm còn một nửa. Chương trình Htree.java nhận n là tham số dòng lệnh và vẽ một hình H-tree bậc n bằng thư viện StdDraw.
Brownian bridge - Cầu Brown.
H-tree là một ví dụ đơn giản của fractal: một hình hình học có thể chia thành các phần mà mỗi phần là [xấp xỉ] một bản sao thu nhỏ của hình ban đầu. Nghiên cứu về fractals đóng một vai trò quan trọng và dài lâu trong nghệ thuật, phân tích kinh tế, và các phát kiến khoa học. Các nghệ sỹ và nhà khoa học sử dụng fractal để xây dựng các mô hình xúc tích của các hình dạng phức tạp xuất hiện trong tự nhiên mà hình học truyền thống không thể mô tả được, chẳng hạn như mây, thực vật, núi, lưu vực sông, da người, và nhiều thứ khác. Các nhà kinh tế học cũng dùng fractal để mô hình hóa các đồ thị hàm số của các chỉ số kinh tế.
Chương trình Brownian.java tạo một đồ thị hàm số xấp xỉ một ví dụ đơn giản được gọi là cây cầu Brown [Brownian bridge] và các hàm liên quan. Bạn có thể coi đồ thị này như là một đường nối ngẫu nhiên giữa hai điểm, từ [x0, y0] tới [x1, y1], được điều khiển bởi một số tham số. Cài đặt này dựa trên phương pháp thay điểm giữa [midpoint displacement method], đó là một thuật toán đệ quy cho việc vẽ đồ thị trong khoảng [x0, x1]. Trường hợp cơ bản [khi độ dài của khoảng nhỏ hơn một ngưỡng chấp nhận cho trước] là vẽ một đoạn thẳng nối hai điểm. Bước đệ quy là chia khoảng quan tâm làm đôi, quy trình như sau:
- tính trung điểm [xm, ym] của khoảng đang xét.
- Cộng vào tọa độ y của trung điểm một giá trị ngẫu nhiên δ, lấy từ phân bố Gauss với kì vọng bằng 0 và một variance cho trước.
- Đệ quy cho các đoạn con, chia variance theo một hệ số tỷ lệ s cho trước .
Đường cong được điều khiển bởi hai tham số: volatility [giá trị ban đầu của variance] điều khiển khoảng cách tối đa của đồ thị tới đường thẳng nối hai điểm, và Hurst exponent điều khiển độ mịn của đường cong. Ta kí hiệu Hurst exponent bằng H và chia variance cho 2^[2H] tại mỗi tầng đệ quy. Khi H bằng 1/2 [nghĩa là chia đôi ở mỗi tầng] độ lệch chuẩn sẽ là một hằng số đối với toàn bộ đường cong: trong trường hợp này, đường cong là một đường dạng cầu Brown.
Các lỗi thường gặp khi dùng đệ quy.
Với đệ quy, bạn có thể viết những chương trình đẹp và ngắn gọn mà khi chạy nó lại thất bại thảm hại.
- Thiếu trường hợp cơ bản. Hàm đệ quy trong NoBaseCase.java có nhiệm vu tính các số điều hòa [Harmonic], nhưng nó thiếu một trường hợp cơ bản:
Khi bạn gọi hàm này, nó sẽ gọi đi gọi lại chính nó và không bao giờ trả về.public static double H[int N] { return H[N-1] + 1.0/N; } - Không đảm bảo hội tụ. Một lỗi khác là đặt vào trong hàm đệ quy một lời gọi đệ quy cho một bài toán con không giảm kích thước. Hàm đệ quy trong NoConvergence.java sẽ lặp vô tận nếu nó được gọi với một tham số khác 1:
public static double H[int N] { if [N == 1] return 1.0; return H[N] + 1.0/N; } - Quá tốn bộ nhớ. Mỗi lời gọi hàm cần được lưu lại dấu vết trong bộ nhớ [ngăn xếp các lời gọi hàm - function call stack], các lời gọi hàm đệ quy không phải ngoại lệ. Nếu một hàm gọi chính nó quá nhiều lần trước khi trả về, không gian bộ nhớ cần thiết cho việc lưu lại các lời gọi hàm đó có thể vượt quá lượng bộ nhớ cho phép. Hàm đệ quy trong ExcessiveSpace.java tính đúng số harmonic thứ N. Tuy nhiên, ta không thể dùng hàm đó cho các giá trị N lớn, vì độ sâu đệ quy tỷ lệ thuận với N, và khi N đạt giá trị 5000, chương trình sẽ gây lỗi StackOverflowError - tràn bộ nhớ stack.
public static double H[int N] { if [N == 0] return 0.0; return H[N-1] + 1.0/N; } - Tính đi tính lại quá nhiều. Khi viết một chương trình đệ quy đơn giản, cần cẩn thận lưu ý rằng một chương trình đơn giản có thể đòi hỏi thời gian chạy cấp lũy thừa [một cách không cần thiết] do việc tính đi tính lại quá nhiều. Ví dụ, chuỗi Fibonacci
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
được định nghĩa bằng công thức Fn = Fn-1 + Fn-2 với n ≥ 2 và F0 = 0 và F1 = 1. Một lập trình viên thiếu kinh nghiệm có thể cài hàm đệ quy sau để tính các số trong một chuỗi Fibonacci, như trong Fibonacci.java:
Tuy nhiên, chương trình trên cực kì không hiệu quả! Để thấy vì sao làm như trên lại không hiệu quả, hãy xét cách hàm trên tính F[8] = 21. Đầu tiên, nó tính F[7] = 13 và F[6] = 8. Để tính F[7], nó gọi đệ quy tính F[6] = 8 một lần nữa và F[5] = 5. Tình hình nhanh chóng trở nên ngày càng tồi tệ, vì trong cả hai lần tính F[6] nó đều bỏ qua thực tế là F[5] đã được tính rồi, và cứ như vậy. Khi tính F[n], số lần chương trình này tính F[1] chính bằng Fn. Lỗi tính đi tính lại này tăng lên theo cấp lũy thừa. Không có một cái máy tính nào, kể cả viễn tưởng, có thể tính được nhiều như vậy.public static long F[int n] { if [n == 0] return 0; if [n == 1] return 1; return F[n-1] + F[n-2]; }
Q + A
Q. Có khi nào vòng lặp là cách duy nhất để giải một bài toán? Có khi nào vòng lặp là cách duy nhất để giải một bài toán?
A. Không, bất cứ vòng lặp nào cũng có thể thay thế bằng một hàm đệ quy, tuy nhiên phiên bản đệ quy có thể đòi hỏi quá nhiều bộ nhớ. Không, bất cứ vòng lặp nào cũng có thể thay thế bằng một hàm đệ quy, tuy nhiên phiên bản đệ quy có thể đòi hỏi quá nhiều bộ nhớ.
Q. Có khi nào đệ quy là cách duy nhất để giải một bài toán? Có khi nào đệ quy là cách duy nhất để giải một bài toán?
A. Không, hàm đệ quy bất kì đều có thể thay thế bằng một phiên bản dùng vòng lặp. Ở mục 4.3, ta sẽ thấy cách trình biên dịch sinh mã cho các lời gọi hàm bằng cách sử dụng một cấu trúc dữ liệu gọi là stack. Không, hàm đệ quy bất kì đều có thể thay thế bằng một phiên bản dùng vòng lặp. Ở mục 4.3, ta sẽ thấy cách trình biên dịch sinh mã cho các lời gọi hàm bằng cách sử dụng một cấu trúc dữ liệu gọi là stack.
Q. Tôi nên ưu tiên chọn cái gì hơn, đệ quy hay vòng lặp? Tôi nên ưu tiên chọn cái gì hơn, đệ quy hay vòng lặp?
A. Hãy chọn cách nào cho bạn code đơn giản dễ hiểu hơn, hoặc hiệu quả hơn. Hãy chọn cách nào cho bạn code đơn giản dễ hiểu hơn, hoặc hiệu quả hơn.
Q. Tôi lo ngại về việc mã đệ quy dùng quá nhiều bộ nhớ và tính toán lại quá nhiều lần. Ngoài ra còn nên để ý những vấn đề gì nữa không? Tôi lo ngại về việc mã đệ quy dùng quá nhiều bộ nhớ và tính toán lại quá nhiều lần. Ngoài ra còn nên để ý những vấn đề gì nữa không?
A. Cực kì cẩn trọng trong việc tạo mảng trong mã đệ quy. Lượng bộ nhớ sử dụng có thể tăng lên rất rất nhanh, cũng như thời gian tiêu tốn cho việc quản lý phần bộ nhớ đó. Cực kì cẩn trọng trong việc tạo mảng trong mã đệ quy. Lượng bộ nhớ sử dụng có thể tăng lên rất rất nhanh, cũng như thời gian tiêu tốn cho việc quản lý phần bộ nhớ đó.
Bài tập
- Chuyện gì xảy ra nếu bạn chạy factorial[] với giá trị n âm? với giá trị lớn, chẳng hạn 35?
- Viết một chương trình đệ quy tính giá trị ln[N!].
- Tìm dãy số nguyên in ra bởi lời gọi hàm ex233[6]:
0#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Tìm giá trị trả về của hàm ex234[6]:
1#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Phân tích nhược điểm của hàm đệ quy:
2#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Cho bốn số nguyên dương a, b, c, và d, giải thích giá trị kết quả của lời gọi gcd[gcd[a, b], gcd[c, d]].
- Giải thích hoạt động của hàm tựa Euclid sau bằng các khái niệm số nguyên và ước số.
3#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; }Lời giải. Kiểm tra xem p và q có nguyên tố cùng nhau hay không.
- Xét hàm đệ quy sau.
4#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; }mystery[2, 25] và mystery[3, 11] trả về kết quả gì? Cho các số nguyên dương a và b, hàm mystery[a, b] tính cái gì? Câu hỏi tương tự, nhưng thay + bằng * và thay return 0 bằng return 1.
Đáp án. 50 và 33. Nó tính a*b. Nếu thay + bằng *, thì nó tính a^b.
- Viết chương trình đệ quy Ruler.java với nhiệm vụ vẽ các vạch chia của một thước kẻ, sử dụng thư viện StdDraw.
- Solve the following recurrence relations, all with T[1] = 1. Assume N is a power of two.
- T[N] = T[N/2] + 1
- T[N] = 2T[N/2] + 1
- T[N] = 2T[N/2] + N
- T[N] = 4T[N/2] + 3
- Dùng quy nạp chứng minh rằng lời giải đệ quy của ta cho kết quả là số lệnh di chuyển tối thiểu.
- Prove by induction that the recursive program given in the text makes exactly F[n] recursive calls to F[1] when computing F[N].
- Chứng minh rằng cứ sau 2 lời gọi đệ quy thì đối số thứ hai của gcd[] giảm ít nhất một nửa. Sau đó, chứng minh rằng gcd[p, q] dùng tối đa log2 N lời gọi đệ quy, với N là giá trị lớn hơn trong hai giá trị p và q.
- Viết chương trình AnimatedHtree.java vẽ hoạt hình xây dựng hình H-tree.
Sau đó, sắp xếp lại trật tự của các lời gọi đệ quy [và trường hợp cơ bản], xem kết quả hoạt hình sau đó, và giải thích kết quả.
Creative Exercises
- Binary representation. Biểu diễn nhị phân Viết chương trình IntegerToBinary.java lấy tham số dòng lệnh là số nguyên dương N [hệ thập phân] và in ra biểu diễn nhị phân của nó. Thay vì dùng phương pháp tách dần các lũy thừa của 2. Ta hãy dùng cách đơn giản hơn: chia N cho 2 lấy phần dư và in ngược thứ tự. Đầu tiên hãy thử dùng một vòng while để thực hiện tính toán và in các bit ra - sẽ là thứ tự ngược. Sau đó sửa lại, dùng đệ quy để in các bit đó theo đúng thứ tự. Viết chương trình IntegerToBinary.java lấy tham số dòng lệnh là số nguyên dương N [hệ thập phân] và in ra biểu diễn nhị phân của nó. Thay vì dùng phương pháp tách dần các lũy thừa của 2. Ta hãy dùng cách đơn giản hơn: chia N cho 2 lấy phần dư và in ngược thứ tự. Đầu tiên hãy thử dùng một vòng while để thực hiện tính toán và in các bit ra - sẽ là thứ tự ngược. Sau đó sửa lại, dùng đệ quy để in các bit đó theo đúng thứ tự.
- A4 paper. Tỷ lệ chiều rộng-chiều cao của trang giấy theo chuẩn ISO là 1 trên căn 2. Định dạng A0 có diện tích 1 m vuông. A1 là A0 chia đôi bằng một đường thẳng, A2 là A1 chia đôi bằng một đường thẳng, cứ như vậy. Hãy viết một chương trình nhận n là tham số dòng lệnh và dùng thư viện StdDraw để thể hiện cách cắt một tờ giấy khổ A0 thành 2^n mảnh. Đây là một minh họa về các khổ giấy loại A. Tỷ lệ chiều rộng-chiều cao của trang giấy theo chuẩn ISO là 1 trên căn 2. Định dạng A0 có diện tích 1 m vuông. A1 là A0 chia đôi bằng một đường thẳng, A2 là A1 chia đôi bằng một đường thẳng, cứ như vậy. Hãy viết một chương trình nhận n là tham số dòng lệnh và dùng thư viện StdDraw để thể hiện cách cắt một tờ giấy khổ A0 thành 2^n mảnh. Đây là một minh họa về các khổ giấy loại A.
- Permutations. - Hoán vị Viết một chương trình Permutations.java lấy một tham số dòng lệnh n và in ra tất cả n! hoán vị của n chữ cái bắt đầu từ a [giả sử n không lớn hơn 26]. Một hoán vị của n phần tử là một trong n! thứ tự có thể có của các phần tử đó. Ví dụ, với n = 3, bạn cần ra được output sau: không cần quan tâm thứ tự liên kê các hoán vị đó. Viết một chương trình Permutations.java lấy một tham số dòng lệnh n và in ra tất cả n!
hoán vị của n chữ cái bắt đầu từ a [giả sử n không lớn hơn 26]. Một hoán vị của n phần tử là một trong n! thứ tự có thể có của các phần tử đó. Ví dụ, với n = 3, bạn cần ra được output sau: không cần quan tâm thứ tự liên kê các hoán vị đó.
5#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Các hoán vị độ dài k. Sửa Permutations.java thành PermutationsK.java sao cho chương trình mới lấy hai tham số dòng lệnh n và k, và in ra tất cả P[n, k] = n! / [n-k]! hoán vị chứa đúng k trong n phần tử. Dưới đây là output khi k = 2 và n = 4. Bạn có thể in ra theo thứ tự bất kì. Sửa Permutations.java thành PermutationsK.java sao cho chương trình mới lấy hai tham số dòng lệnh n và k, và in ra tất cả P[n, k] = n! / [n-k]! hoán vị chứa đúng k trong n phần tử. Dưới đây là output
khi k = 2 và n = 4. Bạn có thể in ra theo thứ tự bất kì.
6#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Combinations - tổ hợp. Viết chương trình Combinations.java that takes one command-line argument n and prints out all 2^n combinations of any size. A combination is a subset of the n elements, independent of order. As an example, when n = 3 you should get the following output. Viết chương trình Combinations.java that takes one command-line argument n and prints out all 2^n combinations of any size. A combination is a subset of the n elements, independent of order. As an example, when n = 3 you should get the following output. Note that the first element printed is the empty string [subset of size 0].
- Combinations of size k. Modify Combinations.java to CombinationsK.java so that it takes two command-line arguments n and k, and prints out all C[n, k] = n! / [k! * [n-k]!] combinations of size k. For example, when n = 5 and k = 3 you should get the following output. Modify Combinations.java to CombinationsK.java so that it takes two command-line arguments n and
k, and prints out all C[n, k] = n! / [k! * [n-k]!] combinations of size k. For example, when n = 5 and k = 3 you should get the following output.
Giải pháp thay thế sử dụng mảng thay vì chuỗi: Comb2.java.
7#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Khoảng cách hamming. Khoảng cách Hamming giữa hai chuỗi bit có chiều dài n bằng với số lượng bit trong đó hai chuỗi khác nhau. Viết một chương trình đọc trong một số nguyên k và một chuỗi bi bit từ dòng lệnh và in ra tất cả các chuỗi bit có khoảng cách Hamming nhiều nhất là từ s. Ví dụ: nếu k là 2 và s là 0000 thì chương trình của bạn sẽ in ra The Hamming distance between two bit strings of length n is equal to the number of bits in which the two
strings differ. Write a program that reads in an integer k and a bit string s from the command line, and prints out all bit strings that have Hamming distance at most k from s. For example if k is 2 and s is 0000 then your program should print out
Gợi ý: Chọn k của n bit trong s để lật.
8#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Hình vuông đệ quy. Viết một chương trình để tạo ra từng mẫu đệ quy sau đây. Tỷ lệ kích thước của hình vuông là 2,2. Để vẽ một hình vuông bóng mờ, vẽ một hình vuông màu xám đầy, sau đó là một hình vuông màu đen không được lấp đầy. Write a program to produce each of the following recursive patterns. The ratio of the sizes of the
squares is 2.2. To draw a shaded square, draw a filled gray square, then an unfilled black square.
- & nbsp;
- & nbsp;
- & nbsp;
- & nbsp;
Recursivesquares.java đưa ra một giải pháp cho phần a.
- Bánh kếp lật. Bạn có một chồng n pancakes có kích thước khác nhau trên vỉ nướng. Mục tiêu của bạn là sắp xếp lại ngăn xếp theo thứ tự giảm dần để bánh kếp lớn nhất ở phía dưới và mục tiêu nhỏ nhất nằm trên đầu. Bạn chỉ được phép lật bánh kếp k hàng đầu, do đó đảo ngược đơn đặt hàng của họ. Xuất phát một sơ đồ để sắp xếp bánh kếp theo đúng thứ tự bằng cách sử dụng nhiều nhất là 2n - 3 lần lật. Gợi ý: Bạn có thể thử các chiến lược ở đây. You have a stack of N pancakes of varying sizes on a griddle. Your goal is to re-arrange the stack in descending order so that the largest pancake is on the bottom and the smallest one is on top. You are only permitted to flip the top k pancakes, thereby reversing their order. Devise a scheme to arrange the pancakes in the proper order by using at most 2N - 3 flips. Hint: you can try out strategies here.
- Mã màu xám. Sửa đổi Beckett.java để in ra mã màu xám [không chỉ là chuỗi các vị trí bit thay đổi]. Modify
Beckett.java to print out the Gray code [not just the sequence of bit positions that change].
Dung dịch. Graycode.java sử dụng kiểu dữ liệu chuỗi của Java; GrayCodeArray.java sử dụng một mảng boolean.
- Tháp biến thể Hà Nội. Hãy xem xét các biến thể sau đây của các tòa tháp của vấn đề Hà Nội. Có 2n đĩa tăng kích thước được lưu trữ trên ba cực. Ban đầu, tất cả các đĩa có kích thước lẻ [1, 3, ..., 2N-1] được chất đống ở cực bên trái từ trên xuống dưới theo thứ tự tăng kích thước; Tất cả các đĩa có kích thước chẵn [2, 4, ..., 2n] được chất đống trên cực bên phải. Viết một chương trình để cung cấp hướng dẫn di chuyển các đĩa lẻ sang cực bên phải và các đĩa thậm chí sang cực bên trái, tuân theo các quy tắc tương tự như đối với các tòa tháp của Hà Nội. Consider the following variant of the towers of Hanoi problem. There are 2N discs of increasing size stored on three poles. Initially all of the discs with odd size [1, 3, ..., 2N-1] are piled on the left pole from top to bottom in increasing order of size; all of the discs with even size [2, 4, ..., 2N] are piled on the right pole. Write a program to provide instructions for moving the odd discs to the right pole and the even discs to the left pole, obeying the same rules as for towers of Hanoi.
- Tháp hoạt hình của hoạt hình Hà Nội. Viết một chương trình AnimatedHanoi.java sử dụng STDDRAW để làm động một giải pháp cho các tòa tháp của vấn đề Hà Nội, di chuyển các đĩa với tốc độ xấp xỉ 1 mỗi giây. Write a program AnimatedHanoi.java that uses StdDraw to animate a solution to the towers of Hanoi problem, moving the discs at a rate of approximately 1 per second.
- Tam giác Sierpinski. Viết một chương trình đệ quy để vẽ miếng đệm Sierpinski. Như với HTREE, sử dụng đối số dòng lệnh để kiểm soát độ sâu của đệ quy. Write a recursive program to draw the Sierpinski gasket. As with Htree, use a command-line argument to control the depth of recursion.
- Phân phối nhị thức. Ước tính số lượng cuộc gọi đệ quy sẽ được sử dụng bởi mã Estimate the number of recursive calls that would be used by the code
Để tính toán nhị thức [100, 50]. Phát triển một triển khai tốt hơn dựa trên ghi nhớ. Gợi ý: Xem Bài tập 1.4.26.
9#include int sum[int n]; int main[] { int number, result; printf["Enter a positive integer: "]; scanf["%d", &number]; result = sum[number]; printf["sum = %d", result]; return 0; } int sum[int n] { if [n != 0] // sum[] function calls itself return n + sum[n-1]; else return n; } - Hàm collatz. Hãy xem xét các hàm đệ quy sau trong collatz.java, có liên quan đến một vấn đề chưa được giải quyết nổi tiếng trong lý thuyết số, được gọi là vấn đề Collatz hoặc vấn đề 3n + 1. Consider the
following recursive function in Collatz.java, which is related to a famous unsolved problem in number theory, known as the Collatz problem or the 3n + 1 problem.
Enter a positive integer:3 sum = 6
0Ví dụ: một cuộc gọi đến Collatz [7] in trình tự
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Do hậu quả của 17 cuộc gọi đệ quy. Viết một chương trình lấy đối số dòng lệnh n và trả về giá trị của n 0, đó là bộ chứa số nguyên von Neumann 0 đến I-1. The von Neumann integer i is defined as follows: for i = 0, it is the empty set; for i > 0, it is the set containing the von Neumann integers 0 to i-1.
Viết một chương trình ordinal.java với hàm đệ quy vonneumann [] có số nguyên không âm N và trả về một biểu diễn chuỗi của số nguyên von neumann N. Đây là một phương pháp để xác định các tác phẩm trong lý thuyết tập hợp.public static int factorial[int N] { if [N == 1] return 1; return N * factorial[N-1]; }7 - Trình độ của một chuỗi. Viết một chuỗi chương trình. Write a program Subsequence.java that takes a string command-line argument s and an integer command-line argument k and prints out all subsequences of s of length k.
public static int factorial[int N] { if [N == 1] return 1; return N * factorial[N-1]; }8 - Xen kẽ hai chuỗi. Cho hai chuỗi s và t của các ký tự riêng biệt, in ra tất cả [M+N]! / [M! N!] Interleaving, trong đó m và n là số lượng ký tự trong hai chuỗi. Ví dụ, nếu Given two strings s and t of distinct characters, print out all [M+N]! / [M! N!] interleavings, where M and N are the number of characters in the two strings. For example, if
public static int factorial[int N] { if [N == 1] return 1; return N * factorial[N-1]; }9 - Nhị phân GCD. Viết một chương trình Binarygcd.java tìm thấy ước số chung lớn nhất của hai số nguyên dương bằng thuật toán GCD nhị phân: GCD [P, Q] = = Write a program BinaryGCD.java that finds the greatest common divisor of two positive integers using the binary gcd algorithm: gcd[p, q] =
- p nếu q = 0
- q nếu p = 0
- 2 * gcd [p/2, q/2] nếu p và q chẵn
- gcd [p/2, q] nếu p chẵn và q là số lẻ
- gcd [p, q/2] nếu p là số lẻ và q chẵn
- gcd [[p-q]/2, q] nếu p và q là lẻ và p> = q
- gcd [p, [q-p]/2] nếu p và q là lẻ và p