Tổng Hợp Các Bài Toán Về đệ Quy Trong C - Học 3 Giây

Trang chủ » đệ Quy Mảng » Tổng Hợp Các Bài Toán Về đệ Quy Trong C - Học 3 Giây

Có thể bạn quan tâm

Hàm gọi lại chính nó được gọi là đệ quy. Hàm đề quy có 4 loại bao gồm:

  1. Đệ quy tuyến tính => Thân hàm gọi 1 lần chính nó
  2. Đệ quy nhị phân => Thân hàm gọi 2 lần chính nó
  3. Đệ quy phi tuyến => Thân hàm lặp gọi 1 số lần chính nó
  4. Đệ quy hỗ tương => 2 hàm đệ quy gọi nhau

Sau đây chúng ta cũng tìm hiểu những dạng bài nào được viết dạng đệ quy.

Tổng hợp các bài toán về đệ quy trong C

1. Hàm nhập, xuất mảng đệ quy

void nhapmang(int a[], int n){ if(n==0) return; nhapmang(a, n-1); printf(“\nNhap phan tu %d: “,n-1); scanf(“%d”,&a[n-1]); }void xuatmang(int a[], int n){ if(n == 0) return; xuatmang(a, n-1); printf(“%4d”,a[n-1]); }

2. Hàm xuất mảng ngược

Vd: Mảng a[5]={2, 4, 5, 3, 9} thì ta có mảng ngược là a[5]={9, 3, 5, 4, 2}

void xuatmangnguoc(int a[], int n){ if(n == 0) return; printf(“%4d”,a[n-1]); xuatmangnguoc(a, n-1); }

3. Tính tổng n

Vd: n = 5 thì ta có S = 1 + 2 + 3 + 4 + 5

//Dung de quy long tong(int n){ if(n==0) return 0; return n + tong(n-1); }

4. Đếm mảng các số chẵn

Chú thích: Chúng ta sẽ đếm những số chẵn có trong mảng có bao nhiêu số.

int demchan(int a[], int n){ if(n == 0) return 0; if(n % 2 == 0) return 1 + demchan(a,n-1); return demchan(a,n-1); }

5. Đếm mảng các số nguyên tố

bool ktnt(int n){ int d=0; for(int i=1; i< n; i++){ if(n%i==0) d=d+1; } if(d==1) return true; return false; } int demsonguyento(int a[], int n){ if(n==0) return 0; if(ktnt(a[n-1])) return 1 + demsonguyento(a, n-1); return demsonguyento(a, n-1); }

6. Hàm tổng mảng

long tongmang(int a[], int n){ if(n==0) return 0; return a[n-1] + tongmang(a,n-1); }

7. Hàm tổng mảng chẵn

long tongmangchan(int a[], int n){ if(n==0) return 0; if(a[n-1] % 2 == 0) return a[n-1] + tongmangchan(a, n-1); return tongmangchan(a, n-1); }

8. Hàm tính tổng các giá trị lớn hơn giá trị đứng trước nó.

Vd: 5, 6, 9, 1, 2 thì ta có S= 6 + 9 + 2 vì 5 < 6 ta lấy 6, 6 < 9 ta lấy 9…

long tonglhdt(int a[], int n){ if(n==0) return 0; if(a[n-1] > a[n]) return a[n-1] + tonglhdt(a,n-1); return tonglhdt(a, n-1); }

9. Kiểm tra mảng toàn chẵn

bool kttoanchan(int a[], int n){ if(n==0) return true; if(a[n-1] % 2 != 0) return false; return kttoanchan(a, n-1); }

10. Hàm tìm max trong mảng

int timmax(int a[], int n){ if(n==1) return a[0]; if(a[n-1] > timmax(a,n-1)) return a[n-1]; return timmax(a,n-1); }

11. Tìm vị trí max trong mảng

int timvitrimax(int a[], int n){ if(n==1) return 0; if(a[n-1] > a[timmax(a,n-1)]) return n-1; return timmax(a,n-1); }

12. Hàm xếp tăng mảng

void sapxeptang(int a[], int n){ if(n==1) return; for(int i=0;i<n;i++){ if(a[i] > a[n-1]){ int tam = a[i]; a[i]=a[n-1]; a[n-1]=tam; } } sapxeptang(a,n-1); }

13. Giả xử x1=1, x2 =1, xn=x(n-1) + (n-1)*x(n-2) 

Viết hàm tính xn bằng đệ quy.

long tinhdequy(int n){ if(n==1 || n==2) return 1; return tinhdequy(n-1) + (n-1)*tinhdequy(n-2); }

14. Tính số hạng n của dãy Fibonacci sau.

f1=1

f2=1

fn=fn-1 + fn-2, n>=3

long Fibonaci(int n){ if(n==1 || n==2) return 1; return Fibonaci(n-1) + Fibonaci(n-2); }

15. Tìm UCLN của 2 số nguyên dương

int UCLN(int c, int b){ if (c == b) return c; if (c > b) return UCLN(c – b, b); else return UCLN(c, b – c); }

Từ khóa » đệ Quy Mảng