Bài giảng Kỹ thuật lập trình - Chương 7: Lập trình đệ quy - Trần Minh Thái

Bài tập 1. Tính n! 2. In ra các ước số của số nguyên dương 3. Đếm số lượng ước số của số nguyên dương 4. Tìm ước số chung lớn nhất của 2 số nguyên dương 5. Kiểm tra số nguyên dương n có phải là số nguyên tố? 6. Nhập vào mảng 1 chiều số nguyên a, kích thước n 7. Xuất mảng 1 chiều số nguyên a, kích thước n 8. Tìm phần tử có giá trị x trong mảng số nguyên a, kích thước n

pdf13 trang | Chia sẻ: thanhle95 | Lượt xem: 465 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Bài giảng Kỹ thuật lập trình - Chương 7: Lập trình đệ quy - Trần Minh Thái, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Trần Minh Thái minhthai@itc.edu.vn * 1 * *Môṭ ham̀ được goị co ́ tińh đệqui nêú trong thân cuả ham̀ đo ́co ́lêṇh goị laị chińh no ́môṭ caćh tường minh hay tiêm̀ ân̉. *Phân loaị đệqui *Đệ qui tuyêń tińh. *Đệqui nhịphân. *Đệqui phi tuyêń. *Đệqui hô t̃ương. 2 * •Trong thân ham̀ có duy nhât́ môṭ lời goị ham̀ goị laị chińh nómôṭ caćh tường minh. TenHam (́) { if (điêù kiêṇ dừng) { . . . //Trảvềgia ́trịhay kêt́ thuć công viêc̣ } //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ . . . TenHam (́); //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ } 3 Vi ́du:̣ Tińh - Điêù kiêṇ dừng: S(0) = 0. - Qui tăć (công thức) tińh: S(n) = S(n-1) + n. int TongS (int n) { if(n==0) return 0; return ( TongS(n-1) + n ); } nnS ++++= L321)( 4 * 1. Tính n! 2. In ra các ước số của số nguyên dương 3. Đếm số lượng ước số của số nguyên dương 4. Tìm ước số chung lớn nhất của 2 số nguyên dương 5. Kiểm tra số nguyên dương n có phải là số nguyên tố? 6. Nhập vào mảng 1 chiều số nguyên a, kích thước n 7. Xuất mảng 1 chiều số nguyên a, kích thước n 8. Tìm phần tử có giá trị x trong mảng số nguyên a, kích thước n 5 * Trong thân cuả ham̀ cóhai lời goị ham̀ goị laị chińh nómôṭ caćh tường minh. TenHam (́) { if (điêù kiêṇ dừng) { . . . //Trảvềgia ́trịhay kêt́ thuć công viêc̣ } //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ . . .TenHam (́); //Giaỉ quyêt́ vâń đềnhỏhơn //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ . . . TenHam (́); //Giaỉ quyêt́ vâń đềcoǹ laị //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ } 6 Vi ́du:̣ Tińh sốhaṇg thứn cuả daỹ Fibonaci được điṇh nghiã như sau: f1 = f0 =1 ; fn = fn-1 + fn-2 ; (n>1) Điêù kiêṇ dừng: f(0) = f(1) = 1. long Fibonaci (int n) { if(n==0 || n==1) return 1; return Fibonaci(n-1) + Fibonaci(n-2); } 7 * *Trong thân cuả ham̀ co ́lời goị ham̀ goị laị chińh no ́được đăṭ bên trong voǹg lăp̣. TenHam (́) { for (int i = 1; i<=n; i++) { //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ if (điêù kiêṇ dừng) { . . . //Tra ̉vê ̀gia ́trịhay kêt́ thuć công viêc̣ } else { //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ TenHam (́); } } } 8 Vi ́du:̣ Tińh sốhaṇg thứn cuả daỹ {Xn} được điṇh nghiã như sau: X0 =1 ; Xn = n2X0 + (n-1)2X1 + + 12Xn-1 ; (n≥1) Điêù kiêṇ dừng:X(0) = 1. long TinhXn (int n) { if(n==0) return 1; long s = 0; for (int i=1; i<=n; i++) s = s + i * i * TinhXn(n-i); return s; } 9 * *Trong thân cuả ham̀ naỳ co ́ lời goị ham̀ đêń ham̀ kia vàtrong thân cuả ham̀ kia co ́ lời goị ham̀ tới ham̀ naỳ. 10 TenHam2 (́); TenHam1 (́) { //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ TenHam2 (́); //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ } TenHam2 (́) { //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ TenHam1 (́); //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́ } 11 Vi ́du:̣ Tińh sốhaṇg thứn cuả hai daỹ {Xn}, {Yn} được điṇh nghiã như sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; (n>0) Yn = n2Xn-1 + Yn-1; (n>0) - Điêù kiêṇ dưǹg:X(0) = Y(0) = 1. long TinhYn(int n); long TinhXn (int n) { if(n==0) return 1; return TinhXn(n-1) + TinhYn(n-1); } long TinhYn (int n) { if(n==0) return 1; return n*n*TinhXn(n-1) + TinhYn(n-1); } 12 * *Ví dụ tính n! với n=5 13