۰۪۪۫۫●۪۫۰-SolitaryWolf--IT--Let's share together-۰۪۪۫۫●۪۫۰

The place for everyone to discuss anything that you like..specially for Information Technology... Software,Hardware,Program C,C++,C# and more...

 Bao gồm các phần lý thuyết hay đc mình tổng hợp từ nhiều sách và do mình tự viết theo những cái mình hiểu.Được chia làm 2 phần đó là lý thuyết và bt mình tự giải(phần bonus í).Bạn nào không hiểu gì hay cần code của bài toán nào cứ post lên mình sẽ giúp (nếu có thể:D)...


Chương I. Khái niệm đệ quy
Một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc qua một đối tượng khác cùng dạng với nó bằng quy nạp.
Nếu lời giải của một bài toán P 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. Nói cách khác, đệ quy trong tin học là dạng hồi quy trong toán học.
Một thủ tục (hàm) đệ quy gồm 2 phần:
- Phần neo (điều kiện dừng): phần nay thực hiện khi công việc đơn giản, có thể giải trực tiếp được.
- Phần đệ quy (lời gọi đệ quy): trong trường hợp bài toán chưa giải được bằng phần neo, ta xác định các bài toán con và gọi lại chính thủ tục (hàm) của nó với tham số khác để giải những các bài toán con đó.
Phần đệ quy thể hiện tính hồi quy của lời giải. Trong một thủ tục (hàm) đệ quy phải có đủ hai phần trên. Nếu không có phần neo thì thủ tục (hàm) sẽ thực hiện vô hạn. Vì vậy, nó rất quan trọng trong việc xác định tính hữu hạn của lời giải. 
1. Phân loại đệ quy
a. Đệ quy tuyến tính
Đệ quy tuyến tính là loại đệ quy đơn giản và có độ phức tạp dạng đa thức.
Cú pháp:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>) {
   if (<Điều kiện dừng>) 

   {
      …
      return <Giá trị trả về>;
   } 

   else 
   {
      …
      …TênHàm(<Danh sách tham số>); /*lời gọi chính nó 1 lần*/
      …
   }
}

Ví dụ: Tính n! được định nghĩa đệ quy như sau:  
C Code :
int Factorial(int n)
{
    if(n==1)return 1;
    else return n*Factorial(n-1);
}
b. Đệ quy nhị phân
Dạng đệ quy này cũng đơn giản và có độ phức tạp dạng đa thức. Sự phân cấp biến nhớ trong quá trình xử lý phát triển theo dạng cây nhị phân.
Cú pháp:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>) {
   if (<Điều kiện dừng>) 

   {
   …
   return <Giá trị trả về>;
   } 

   else //chứa lời gọi chính nó những 2 lần
   {
      …
      …TênHàm(<Danh sách tham số>);
      …
      …TênHàm(<Danh sách tham số>);
      …
   }
}

Ví dụ:  
C Code:
int RecursionF(int n)
{
    if(n==0)return 0;
    else if(n==1||n==2)return 1;
    else return RecursionF(n-1)+RecursionF(n-2);
}
c. Đệ quy phi tuyến
Chương trình con đệ quy phi tuyến là chương trình con đệ quy trực tiếp mà lời gọi đệ quy được thực hiện bên trong vòng lặp .Dạng đệ quy này tương đối phức tạp và thường được sử dụng trong thuật toán quay lui vét cạn. Tùy theo độ khó của bài toán mà ta xác định độ phức tạp của chương trình, hầu hết dạng đệ quy này có độ phức tạp dạng hàm mũ.
Cú pháp 1:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>)
{
   for (int i=1; i<=n; i++) 

   {
      …
      if(<Điều kiện dừng>)

      {
         …
      }
      else 

      {
         …
         TênHàm(<Danh sách tham số>);
         …
      }
   }
}

Cú pháp 2:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>)
{
   if(<Điều kiện dừng>){
      …
   }else {
      for (int i=1; i<=n; i++) {
         …
         TênHàm(<Danh sách tham số>);
         …
      }
   }
}
Ví dụ:
Tìm số hạng thứ n của dãy:
x(n)=n^2*x(0)+(n-1)^2*x(0)+(n-2)^2*x(0)+ +2^2*x(n-2)+1^2*x(n-1) với x(0)=0
C Code:
 long int TinhXn  (int n) 
{
 if(n==0)return1;
  long int s=0; 
 for(int i=1; i<=n; i++)
          s+=i*i*TinhXn(n-i);
 return s; 
}
d. Đệ quy hỗ tương
Dạng đệ quy này khá thú vị, thể hiện tính tương tác đệ quy giữa các đối tuợng cùng xử lý một bài toán với những trường hợp riêng. Tùy thuộc vào dạng toán xử lý ta tính được độ phức tạp của bài toán.
Cú pháp:
Code:
Kiểu_dữ_liệu TênHàm2(<Danh sách tham số>);
Kiểu_dữ_liệu TênHàm1(<Danh sách tham số>) {
   …
   TênHàm2(<Danh sách tham số>);
   …    
}
Kiểu_dữ_liệu TênHàm2(<Danh sách tham số>) {
   …
   TênHàm1(<Danh sách tham số>);
   …    
}

Ví dụ:  


Tìm số hạng thứ n của dãy sau:

x(0)=1y(0)=0x(n)=x(n-1)+y(n-1)khi n>0

y(n)=3*x(n-1)-2*y(n-1)khi n>0

C Code:




long int TinhYn(int n);
long int TinhXn(int n)
{
     if(n==0)return 1;
     return TinhXn(n-1)+TinhYn(n-1);
}
long int TinhYn (int n)
{
     if(n==0)return 0;
     return 3*TinhXn(n-1)-2*TinhYn(n-1);
}
2.Chú ý khi viết hàm đệ quy
Hàm đệ quy phải có 2 phần:
Phần dừng hay phải có trường hợp nguyên tố. Trong ví dụ ở trên thìtrường hợp n=0 là trường hợp nguyên tố.
Phần đệ quy: là phần có gọi lại hàm đang được định nghĩa. Trong vídụ trên thì phần đệ quy là n>0 thì n! = n * (n-1)!Sử dụng hàm đệ quy trong chương trình sẽ làm chương trình dễ đọc, dễ hiểu và vấn đề được nêu bật rõ ràng hơn. Tuy nhiên trong đa số trườnghợp thì hàm đệ quy tốn bộ nhớ nhiều hơn và tốc độ thực hiện chươngtrình chậm hơn không đệ quy.Tùy từng bài có cụ thể mà người lập trình quyết định có nên dùng đệquy hay không (có những trường hợp không dùng đệ quy thì không giải quyết được bài toán).

Bonus :
 1.In ra dãy fibonacci theo 3 cách:mảng,đệ quy,biến bình thường.
C Code:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define size 100
int main()
{
    int f[size],i,n;
    f[0]=0;
    f[1]=1;
    do
    {
        printf("input the ordinal number of the element(s) in Fibonacy Series :");      //Dùng mảng
        scanf("%d",&n);
        if(n<0)printf("the ordinal number of element(s) in Fibonacci Series must be greater than or equal to 0,input again\n");
    }
    while(n<0);
    if(n==1||n==2)printf("F%d is 1\n",n);
    else if(n==0)printf("F%d is 0\n",n);
    else
    {
        for(i=2;i<=n;i++)
            f[i]=f[i-1]+f[i-2];
        i--;
        printf("F%d is %d\n",n,f[i]);
    }
    system("pause");
    return 0;
}
/*int main()
{
    int first=0,next=1,result,n;
    do
    {
        printf("input the ordinal number of the element(s) in Fibonacy Series :");      //Dùng biến bình thường
        scanf("%d",&n);
        if(n<0)printf("the ordinal number of element(s) in Fibonacci Series must be greater than or equal to 0,input again\n");
    }
    while(n<0);
    for(int i=2;i<=n;i++)
    {
        result=first+next;
        first=next;
        next=result;
    }
    if(n==0)printf("F%d is 0\n",0);
    else if(n==1||n==2)printf("F%d is 1\n",n);
    else printf("F%d is %d\n",n,result);
    system("pause");
    return 0;
}*/
/*int RecursionF(int n);
int main()
{
    int n;
    do
    {
        printf("input the ordinal number of the element(s) in Fibonacy Series :");      //Dùng đệ quy
        scanf("%d",&n);
        if(n<0)printf("the ordinal number of element(s) in Fibonacci Series must be greater than or equal to 0,input again\n");
    }
    while(n<0);
    printf("F%d is %d\n",n,RecursionF(n));
    system("pause");
    return 0;
}
int RecursionF(int n)
{
    if(n==0)return 0;
    else if(n==1||n==2)return 1;
    else return RecursionF(n-1)+RecursionF(n-2);
}*/
2.Tính tổng các ước của 1 số:
C Code:

#include "stdio.h"
#include "stdlib.h"
int main()
{
    int n,s=0;
    printf("enter a positive integer :N=");
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        if(n%i==0)s+=i;
    printf("Sum of divisors is %d\n",s);
    system("pause");
    return 0;
}

3.Đổi từ hệ 16 sang hệ 10:
C Code:
#include "stdio.h"
#include "stdlib.h"
int main()
{
    int n;
    printf("nhap vao so he 10 :");
    scanf("%d",&n);
    printf("so do sang he 16 la%x\n",n);
    systen("pause");
    return 0;
}
4.Bảng bình phương các số từ 1 đến n:
C Code:
#include "stdio.h"
#include "stdlib.h"
int main()
{
    int n,i;
    printf("nhap vao 1 so n");
    scanf("%d",&n);
    printf("bang binh phuong cac so tu 1 den n\n");
    for(i=1;i<=n;i++)
        printf("so %d binh phuong la%d\n",i,i*i);
    system("pause");
    return 0;
}
5.Chèn 1 mảng vào 1 mảng đã sắp tăng sao cho mảng đó vẫn tăng:
C Code:
#include "stdio.h"
#include "stdlib.h"
#define size 40
void input(int n,int c[],int b[],int m);
void output(int n,int c[]);
void insertdirectly(int a[],int b,int pos,int &n);
void insertbtoc(int b[],int m,int c[],int &n);
int main()
{
    int b[size],c[size],m,n;
    printf("input the number of element of array B and array C");
    scanf("%d%d",&m,&n);
    input(n,c,b,m);
    insertbtoc(b,m,c,n);
    output(n,c);
    system("pause");
    return 0;
}
void input(int n,int c[],int b[],int m)
{
    for(int i=0;i<m;i++)
    {
        printf("b[%d]",i);
        scanf("%d",&b[i]);
    }
    for(int j=0;j<n;j++)
    {
        printf("c[%d]",j);
        scanf("%d",&c[j]);
    }
}
void output(int n,int c[])
{
    for(int i=0;i<n;i++)
        printf("%d ",c[i]);
}
void insertdirectly(int c[],int x,int pos,int &n)
{
    for(int j=n;j>pos;j--)
        c[j]=c[j-1];
    c[pos]=x;
    n++;
}
void insertbtoc(int b[],int m,int c[],int &n)
{
    int j,k;
    for(int i=0;i<m;i++)   
    {
        for(k=0;k<n;k++)
            if(b[i]<c[k])     
            {
                for(j=0;b[i]>c[j];j++);
                insertdirectly(c,b[i],j,n);
                break;
            }
            if(k==n)insertdirectly(c,b[i],k,n); 
    }
}
6.Chèn 1 phần tử vào 1 mảng 1 chiều:
C Code:

#include "stdio.h"
#include "stdlib.h"
void nhap(int n,int a[]);
void chen1phantu(int a[],int x,int &n,int y);
void xuat(int n,int a[]);
int main()
{
    int a[200],n,x,y;
    do
    {
        printf("nhap so phan tu mang");
        scanf("%d",&n);
        if(n<=0)printf("nhap sai,nhap lai\n");
    }
    while(n<=0);
    nhap(n,a);
    printf("nhap vi tri can chen va so can chen");
    scanf("%d%d",&x,&y);
    chen1phantu(a,x,n,y);
    printf("mang sau khi chen la");
    xuat(n,a);
    system("pause");
    return 0;
}
void nhap(int n,int a[])
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("a[%d]",i);
        scanf("%d",&a[i]);
    }
}
/*void chen1phantu(int a[],int x,int &n,int y)
{
    int i;
    for(i=n;i>x;i--)
        a[i]=a[i-1];
    a[x]=y;
    n++;
}*/
void chen1phantu(int a[],int x,int &n,int y)
{
    int i;
    n++;
    for(i=n-1;i>x;i--)a[i]=a[i-1];
    a[x]=y;
}
void xuat(int n,int a[])
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
}
7.Chèn kí tự vào 1 chuỗi:
C Code:

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "string.h"
void insert(char ch,char* st,int pos,int len);
int main()
{
    char *st,ch;
    int pos;
    st=new char[20];
    printf("type a random string");
    fflush(stdin);
    gets(st);
    int len=strlen(st);
    do
    {
        printf("tell me the position u want to insert character ch ");
        scanf("%d",&pos);
        if(pos<0||pos>len)printf("Have mistake during input process,please input again\n");
    }
    while(pos<0||pos>len);
    printf("tell me the character u want to insert ");
    fflush(stdin);
    ch=getchar();
    insert(ch,st,pos,len);
    printf("the string after u inserted ");
    puts(st);
    system("pause");
    return 0;
}
void insert(char ch,char* st,int pos,int len)
{
    for(int i=len+1;i>pos;i--)
        st[i]=st[i-1];
    st[pos]=ch;
}
8.Chèn số 0 trước phần tử lẻ trong mảng 1 chiều:
C Code:

#include "stdio.h"
#include "stdlib.h"
void nhap(int n,int a[]);
void chenso0vaole(int &n,int a[]);
void xuat(int n,int a[]);
int main()
{
    int a[200],n;
    do
    {
        printf("nhap so phan tu mang");
        scanf("%d",&n);
        if(n<=0)printf("nhap sai,nhap lai\n");
    }
    while(n<=0);
    nhap(n,a);
    printf("mang sau khi them 0 vao so le la");
    chenso0vaole(n,a);
    xuat(n,a);
    system("pause");
    return 0;
}
void nhap(int n,int a[])
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("a[%d]",i);
        scanf("%d",&a[i]);
    }
}
void chenso0vaole(int &n,int a[])
{
    int i,j;
    for(i=0;i<n;i++)
    {
        if(a[i]%2!=0)
        {
            for(j=n;j>i;j--)
            {
                a[j]=a[j-1];
            }
            a[i]=0;
            n++;
            i++;
        }
    }
}
void xuat(int n,int a[])
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
}

1 comments:

Hello there! This is my first visit to your blog! We are a team of volunteers and starting a new
project in a community in the same niche. Your blog provided us valuable information to work on.
You have done a wonderful job!
Stop by my blog post ... cialis 20mg

Post a Comment

Followers!

About this blog

When you're sad and have sorrow just visit me...^^

Total Pageviews

Most Viewer