Tài liệu Tổng hợp giải thuật hàm đệ quy

Chuyên mục 'Tài Liệu' bởi loveIT, 26 Tháng hai 2013.

  1. ĐỆ QUY
    Khái niệm :


    Một hàm được gọi là đệ qui nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó Phân loại đệ qui :

    Đệ quy thường gặp thuộc một trong bốn loại sau :

    Đệ qui tuyến tính
    Đê qui nhị phân
    Đệ qui phi tuyến
    Đệ qui hỗ tương

    Cấu trúc hàm đệ qui :

    Đệ qui nhị phân : Cũng giống như đệ qui tuyến tính nhưng bên trong thân hàm của nó có thêm một lời gọi lại chính nó

    Mã:
    KieuDuLieu TenHam(Thamso) 
    { 
                 if(Dieu Kieu Dung) 
                { 
                           ...; 
                           return Gia tri tra ve; 
                } 
                ...; 
                TenHam(Thamso); 
                ...; 
                ...; 
                TenHam(Thamso); 
                ...; 
                ...; 
    } 
    Đệ qui tương hỗ : Trong đệ qui tương hỗ thì thường có 2 hàm , và trong thân của hàm này có lời gọi của hàm kia , điều kiện dừng và giá tri tra về của cả hai hàm có thể giống nhau hoặc khác nhau

    Mã:
    KieuDuLieu TenHamX(Thamso) 
    { 
              if(Dieu Kieu Dung) 
              { 
                          ...; 
                          return Gia tri tra ve; 
              } 
              ...; 
              return TenHamX(Thamso) TenHamY(Thamso); 
    } 
    KieuDuLieu TenHamY(Thamso) 
    { 
            if(Dieu Kieu Dung)[INDENT]{[/INDENT]
    [INDENT=2]...;[/INDENT]
    [INDENT=2]return Gia tri tra ve;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]...;[/INDENT]
    [INDENT]return TenHamY(Thamso)TenHamX(Thamso);[/INDENT]
    }
    
    Đệ qui phi tuyến : Hàm được gọi là đệ qui phi tuyến nếu bên trong thân hàm có lời gọi lại chính nó được đặt bên trong thân của vòng lặp
    Mã:
    KieuDuLieu TenHam(Thamso) 
    { 
        if(Dieu Kieu Dung) 
        { 
            ...; 
            return Gia tri tra ve; 
        } 
        ...; 
        vonglap(dieu kieu lap) 
        { 
            ...TenHam(Thamso)...; 
        } 
        return Gia tri tra ve; } 
    
    Bài tập đệ qui :

    1/Đệ qui tuyến tính :

    Bài tập 730: Tính S(n) = 1 + 2 + 3 + ... + n - 1 + n
    Mã:
    int Tinh(int n) 
      { 
                      if (n==1) 
                            return 1; 
                      return Tinh(n-1) + n; 
      } 
    Bài tập 731 : Tính S(n) = 1^2 + 2^2 + 3^2 + ... + (n-1)^2 + n^2
    Mã:
    int Tinh(int n) 
      { 
                      if (n==1) 
                               return 1; 
                      return Tinh(n-1) + n*n; 
      } 
    
    Bài tập 732 : Tính S(n) = 1 + 1/2 + 1/3 + ... + 1/n

    Mã:
    float Tinh(float n) 
      { 
                      if (n==1) 
                                return 1; 
                      return Tinh(n-1) + 1/n; 
      } 
    
    Bài tập 733 : Tính S(n) = 1/2 + 1/4 + ... + 1/2n
    Mã:
    float Tinh(float n){[INDENT=4]if (n==1)[/INDENT]
    [INDENT=2]return 0.5;[/INDENT]
    [INDENT]return Tinh(n-1) + 1/(2*n);[/INDENT]
    }
    Bài tập 734 : Tính S(n) = 1 + 1/3 + 1/5 + ... + 1/(2n+1)
    Mã:
    float Tinh(float n) 
      { 
                      if (n==1)
                                       return 1; 
                      return Tinh(n-1) + 1/(2*n+1); 
      } 
    

    Bài tập 735: Tính S(n) = 1/(1*2) + 1/(2*3) + 1/( n(*n-1) )
    Mã:
    float Tinh(float n) 
      { 
                      if (n==1) 
                                      return 0.5;
                       return Tinh(n-1) + 1/(n*(n+1)); 
      } 


    Bài tập 736 : Tính S(n) = 1/2 + 2/3 + 3/4 + ... + n/(n+1)
    Mã:
    float Tinh(float n) 
      { 
                      if (n==1)
                                       return 0.5; 
                      return Tinh(n-1) + n/(n+1); 
      } 

    Bài tập 737 :Tính S(n) = 1/2 + 3/4 + 5/6 + ... + (2n+1)/(2n+2)
    Mã:
    float Tinh(float n) 
      { 
                      if (n==1) 
                                      return 0.5; 
                      return Tinh(n-1) + (2*n+1)/(2*n+2); 
      } 
    
    Bài tập 738 :Tính T(n) = 1*2*3*.....*n
    Mã:
    float Tinh(float n) 
      { 
                      if (n==1)
                                       return 1; 
                      return Tinh(n-1)*n; 
      } 
    
    Bài tập 739 :Tính T(x,n) = x^n
    Mã:
    float LuyThua(float x , int n)[INDENT]{[/INDENT]
    [INDENT]if(n == 0)[/INDENT]
    [INDENT=2]{[/INDENT]
    [INDENT=3]return 1;[/INDENT]
    [INDENT=2]}[/INDENT]
    [INDENT]if(n < 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return LuyThua(x,n+1) * 1/x;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return LuyThua(x,n-1) * x;[/INDENT]
    }
     
    Bài tập 740 :Tính S(n) = 1 + 1.2 + 1.2.3 + .... + 1.2.3....n
    Mã:
    long GiaiThua(int n) 
      {
             if(n==1) 
            {
                   return 1; 
            } 
            return GiaiThua(n-1)*n; 
      } 
        
      long Tong(int n) 
      {
             if(n == 1) 
            {
                   return 1; 
            } 
            return Tong(n-1) + GiaiThua(n-1)*n; 
      } 

    Bài tập 741 :Tính S(x,n) = x + x^2 + x^3 + ... + x^n
    Mã:
    float LuyThua(float x , int n) 
      {         if(n == 0) 
            {
                   return 1; 
            } 
            return LuyThua(x,n-1)*x; 
      } 
        
      float Tong(float x , int n) 
      { 
            if(n == 1) 
            { 
                  return x;  
            } 
            return Tong(x,n-1) + LuyThua(x,n-1)*x; 
      } 
     
    
    Bài tập 742 :Tính S(x,n) = x^2 + x^4 +.... + x^2n
    Mã:
    double bai742(int x, int n) 
      { 
                  if (n==1) 
                  { 
                              return pow(x,2*n); 
                  } 
                  return bai742(x,n-1) + pow(x,2*n); 
      } 
    
    Bài tập 743 :Tính S(x,n) = x + x^3 + x^5 +....+ x^(2n+1)

    Mã:
    {[INDENT]if (n==1){[/INDENT]
    [INDENT=2]return pow(x,n);[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return tinh(x,n-1) + pow(x,n+1);[/INDENT]
    }
    Bài tập 744 :Tính S(n) = 1 + 1/(1+2) + 1/(1+2+3) + ... + 1/(1+2+3+...+n)
    Mã:
    float Tong(float n) 
      { 
            if(n == 1) 
            { 
                  return (float)1; 
            } 
            return Tong(n-1) + n;  
      } 
        
      float TongChia(float n) 
      { 
            if(n == 1) 
            { 
                  return (float)1; 
            } 
            return TongChia(n-1) + 1/(Tong(n-1) + n);  
      } 
     
    
    Bài tập 745 :Tính S(x,n) = x + (x^2)/2! + (x^3)/3! + ... + (x^n)/n!
    Mã:
    float LuyThua(float x , float n) 
      { 
            if(n == 1) 
            { 
                  return x; 
            } 
            return LuyThua(x,n-1)*x; 
      } 
        
      float GiaiThua(float n) 
      { 
            if(n == 1) 
            { 
                  return (float)1; 
            } 
            return GiaiThua(n-1)*n; 
      } 
        
      float LTChiaGT(float x , float n) 
      {         if(n == 1) 
            { 
                  return x; 
            } 
            return LTChiaGT(x,n-1) + ((LuyThua(x,n-1)*x) / (GiaiThua(n-1)*n)); 
      } 
     
    
    Bài tập 746 :Tính S(x,n) = 1 + (x^2)/2! + (x^4)/4! + ... + (x^2n)/(2n)!

    Mã:
    float LuyThua(float x , float n){[INDENT]if(n == 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return (float)1;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return LuyThua(x,n-1) *x*x;[/INDENT]
    }
    float GiaiThua(float n)
    {[INDENT]if(n == 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return (float)1;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return GiaiThua(n-1)*n;[/INDENT]
    }
    
    float LTChiaGT(float x , float n)
    {[INDENT]if(n == 0)[/INDENT]
    [INDENT=2]{[/INDENT]
    [INDENT=3]return (float)1;[/INDENT]
    [INDENT=2]}[/INDENT]
    [INDENT]return LTChiaGT(x,n-1) + ( (LuyThua(x,n-1)*x*x) / ((GiaiThua (2*n - 1) *2*n)));[/INDENT]
    }
    Bài tập 747 :Tìm ước số lẻ lớn nhất của số nguyên dương n . Ví dụ : n = 100 ước lẻ lớn nhất của 100 là 25
    Mã:
    int UocLeMax(int n) 
      { 
            if(n % 2 == 1) 
            { 
                  return n; 
            } 
            return UocLeMax(n/2); 
      } 
    
    Bài tập 748 :Tính S(n) = sqrt(2 + sqrt (2 + ... sqrt ( 2 + sqrt(2) ) ) )
    Mã:
    #include 
      float Function(float n) 
      { 
                  if(n == 1) 
                  { 
                              return sqrt(2); 
                  } 
                  return sqrt(2 + Function(n-1)); 
      } 
    

    Bài tập 749 :Tính S(n) = sqrt(n + sqrt (n-1 + sqrt(n-2 + ...sqrt(2 + sqrt (1) ) ) ) )
    Mã:
    #include 
        long double Function(long double n) 
      { 
            if(n == 1) 
            { 
                  return 1; 
            } 
            return sqrt(n + Function(n-1)); 
      } 

    Bài tập 750 :Tính S(n) = sqrt(1 + sqrt(2 + sqrt (3 + ...sqrt (n-1 + sqrt (n)))))
    Mã:
    #include 
    float Function(float i, float n)    //bắt đầu: i=1
    {[INDENT]if(n == i)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return sqrt(n);[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return sqrt( i + Function(i+1,n));[/INDENT]
    }

    Bài tập 751 :S(n) = 1/(1 + 1/(1 + 1/(1 + 1/(... 1 /(1/(1 + 1/(1 + 1 )))))))

    Mã:
    long double Thuong(int n) 
      { 
            if(n == 1) 
            { 
                  return 1.0 / (1.0 + 1.0);  
            } 
            return  1 / (1 + Thuong(n-1));  
      } 
    
    Bài tập 752 :Hãy đếm số lượng chữ số của số nguyên dương n
    Mã:
    int DemSoLuongChuSo(int n) 
      { 
            if(n == 0) 
            {               return 0; 
            } 
            return DemSoLuongChuSo(n/10) + 1; 
      } 
    
    Bài tập 753 :Hãy tính tổng các chữ số của số nguyên dương n
    Mã:
    int TongChuSo(int n) 
      { 
            if(n == 0) 
            { 
                  return 0; 
            } 
            return TongChuSo(n/10) + n % 10;  
      } 

    Bài tập 754 :Hãy tính tích các chữ số của số nguyên dương n
    Mã:
    int Tich(int n) 
      {         if(n == 0) 
            { 
                  return 1; 
            } 
            return Tich(n/10) * (n%10); 
    }
    Bài tập 755 :Hãy đếm số lượng chữ số lẻ của số nguyên dương n
    Mã:
    int DemLe(int n) 
      { 
            if(n == 0) 
            { 
                  return 0; 
            } 
            if(n%2 == 1) 
            { 
                  return DemLe(n/10) + 1; 
            }
            return DemLe(n/10);  
      }  

    Bài tập 756 :Hãy tính tổng các chữ số chẵn của số nguyên dương n
    Mã:
    int TongChuSoChan(int n) 
      { 
            if(n == 0) 
            { 
                  return 0; 
            } 
            if(n%2 == 0) 
            { 
                  return TongChuSoChan(n/10) + (n%10); 
            } 
            return TongChuSoChan(n/10); 
      } 
    
    Bài tập 757 :Hãy tính tích các chữ số lẻ của số nguyên dương n
    Mã:
    int TichChuSoLe(int n) 
      { 
            if(n == 0) 
            { 
                  return 0; 
            } 
            if(n % 2 == 1) 
            { 
                  return TichChuSoLe(n/10) * (n%10); 
            } 
            return TichChuSoLe(n/10); 
      } 
    
    Bài tập 758 :Cho số nguyên dương n . Hãy tìm chữ số đầu tiên của n
    Mã:
    int ChuSoDauTien(int n) 
      { 
            if(n/10 == 0) 
            { 
                  return n; 
            } 
            return ChuSoDauTien(n/10); 
      } 
    
    Bài tập 759 :Hãy tìm chữ số đảo ngược của số nguyên dương n
    Mã:
    int DemSoLuongChuSo(int n)[INDENT]{[/INDENT]
    [INDENT]if(n == 0)[/INDENT]
    [INDENT=2]{[/INDENT]
    [INDENT=3]return 0;[/INDENT]
    [INDENT=2]}[/INDENT]
    [INDENT]return DemSoLuongChuSo(n/10)+1;[/INDENT]
    [INDENT]}[/INDENT]
    int DoiChuSo(int H , int Dem)[INDENT]{[/INDENT]
    [INDENT]if(Dem > 0)[/INDENT]
    [INDENT=2]{[/INDENT]
    [INDENT=3]return DoiChuSo(H*10,Dem-1);[/INDENT]
    [INDENT=2]}[/INDENT]
    [INDENT]return H;[/INDENT]
    }
    int ChuSoDaoNguoc(int n)
    {[INDENT]if(n == 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return 0;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]int Dem = DemSoLuongChuSo(n);[/INDENT]
    [INDENT]int H = n%10;[/INDENT]
    [INDENT]int T = DoiChuSo(H,Dem-1);[/INDENT]
    [INDENT]return ChuSoDaoNguoc(n/10) + T;[/INDENT]
    }
    Bài tập 760 :Tìm chữ số lớn nhất của số nguyên dương n
    Mã:
    int ChuSoLonNhat(int Max,int n)          //Max bắt đầu là n%10 
      { 
                  if (n%10==0) 
                  { 
                              return Max; 
                  } 
                  Max=(Max>n%10)?Max:n%10;               return ChuSoLonNhat(Max,n/10); 
      } 
    Bài tập 761 :Tìm chữ số nhỏ nhất của số nguyên dương n

    Mã:
    int ChuSoLonNhat(int Max,int n) //Max bắt đầu là n%10[INDENT]{[/INDENT]
    [INDENT]if (n%10==0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return Max;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]Max=(Max>n%10)?Max:n%10;[/INDENT]
    [INDENT]return ChuSoLonNhat(Max,n/10);[/INDENT]
    }
    
    Bài tập 761 :Tìm chữ số nhỏ nhất của số nguyên dương n
    Mã:
    int ChuSoNhoNhat(int Min,int n) //Min bắt đầu là n%10
    {[INDENT]if (n%10==0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return Min;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]Min=(Min<n%10) ? Min : n%10;[/INDENT]
    [INDENT]return ChuSoLonNhat(Min,n/10);[/INDENT]
    }
    
    Bài tập 762 :Hãy kiểm tra số nguyên dương n có toàn chữ số lẻ hay không ?
    Mã:
    int KTToanLe(int n)
    {[INDENT]if (n%2==0 && n!= 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return 0;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]if (n%2==1)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return KTToanLe(n/10);[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return 1;[/INDENT]
    }
    Bài tập 763 : Hãy kiểm tra số nguyên dương n có toàn chữ số chẵn hay không ?
    Mã:
    int KTToanChan(int n)
    {[INDENT]if(n == 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return 1;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]if(n % 2 == 1)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return 0;[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]if(n % 2 == 0)[/INDENT]
    [INDENT]{[/INDENT]
    [INDENT=2]return KTToanChan(n/10);[/INDENT]
    [INDENT]}[/INDENT]
    [INDENT]return 1;[/INDENT]
    }
    
    Làm thêm đệ qui cho mảng 1 chiều, ma trận nhé!
    --------Hết đệ qui------​