Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 19 kết quả

Đề tài: Lý thuyết đệ quy cơ sở - Lý thuyết lập trình

  1. #1
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Mặc định Lý thuyết đệ quy cơ sở - Lý thuyết lập trình

    Dreaminess hiểu là thế này:

    - Trong thân của một hàm, nếu nó gọi tới chính hàm đó để xử lý bài toán thì gọi là hàm đệ quy (Tự mình bắt mình làm ấy mà). Có điểm giống với quy nạp toán học.

    Đặc điểm
    - Mỗi một lần hàm tự gọi đệ quy đến nó thì máy tính sẽ tự tạo ra một biến cục bộ mới.
    - Có bao nhiêu lần hàm gọi đệ quy thì sẽ có bấy nhiêu lần thoát ra khỏi hàm.(Kiểu như lặp hàm).
    - Khi thoát ra ngoài hàm đệ quy thì một loạt các biến cục bộ tạo ra do dùng đệ quy lúc này mới được giải phóng, và chúng sẽ giải phóng trước các biến cục bộ(sinh ra do đệ quy) tạo ra sau.

    - Sử dụng đệ quy là một phương pháp làm cho chương trình ngắn gọn, dễ hiểu nhưng nó sẽ làm tốn bộ nhớ và thời gian nếu như cấu trúc hàm đệ quy 'phức tạp'.

    Sử dụng đệ quy:

    - Chỉ sử dụng hàm đệ quy khi có suy biến.
    - Trong một trường hợp tổng quát bài toán có thể đưa về cùng dạng. Nhưng giá trị thay đổi, sau một loạt thay đổi nó phải đưa về trường hợp suy biến.

    Ví dụ:

    C Code:
    1. unsigned long fac(int n) // Hàm tính giai thừa
    2. {
    3.   if(n==0) return (1); // Trường hợp suy biến.
    4.   return (n*fac(n-1)); // Gọi đệ quy.
    5. }
    Bây giờ bạn liên tưởng hàm trên với hàm sau đây sẽ hiểu được phương pháp đệ quy.

    C Code:
    1. unsigned long fac(int n)
    2. {
    3.      int i, f=1;
    4.      if (n>0)
    5.      {
    6.           for(i=1;i<=n;i++) f = f*i;
    7.      }
    8.      return (f);
    9. }

    Một ví dụ khác:

    C1: Dùng đệ quy

    C Code:
    1. int USC(int x, int y)
    2. {
    3.    if(y==0) return(x); // Trường hợp suy biến
    4.    return (USC(y,x % y); // Gọi đệ quy
    5. }

    C2: Dùng lặp
    C Code:
    1. int USC(int x, int y)
    2. {
    3.    int m;
    4.    while(y!=0)
    5.    {
    6.       m=x % y;
    7.       x=y;
    8.       y=m;
    9.     }
    10.     return (x);
    11. }
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Bài này là bài tìm các số palidom, nội dung của bài toán là liệt kê tất cả các số palidom <=N cho trước là các số mà khi viết theo thứ tự ngược lại cũng bằng chính nó.
    Đây là code:
    C Code:
    1. void palidom()
    2.     {
    3.  
    4.     unsigned long n,i,j;
    5.     int dem;
    6.     char s[12];
    7.     dem=0;
    8.     printf("\nNhap N : ");
    9.     scanf("%ld",&n);
    10.     printf("Cac so palidrom nho hon %d la : ",n);
    11.     for(i=1;i<=n;i++)
    12.     {
    13.       ltoa(i,s,10);
    14.       strrev(s);
    15.       j=atol(s);
    16.       if(i==j)
    17.         {
    18.         printf("\n%d",i);
    19.         dem++;
    20.         if(dem%20==0)
    21.         getch();
    22.         }
    23.     }
    24.    }

  3. #3
    Ngày gia nhập
    03 2009
    Bài viết
    6

    Lý do lôi Topic lên, mọi người đều đã học qua và rất rành về đệ quy thì có thể giành vài phút phân tích cho mình hiểu rõ ưu và nhược điểm của thuật toán Đệ Quy được ko, mình đã tham khảo tài liệu nhưng kiến thức ko nhiều , ko rút ra được kết luận gì cả. Mong mọi người hồi âm.

  4. #4
    Ngày gia nhập
    03 2008
    Nơi ở
    Hồ chí minh
    Bài viết
    134

    umh,vấn đề đệ quy mình thấy đa số mọi người đều hiểu mơ hồ,nếu là những bài toán đơn giản thì không cần nói,nhưng một số bài toán phức tạp ngồi hình dung cũng nhức cả óc.
    ví du:
    C Code:
    1. int stack[max],index[max],d=0,num=0;
    2. chutrinh(int v)
    3. {
    4.    d++;
    5.   stack[d]=v;
    6.    num++;
    7.    index[v]=num;
    8.   for(int i=0;i<n;i++)
    9.   if(index[i]==0)
    10.            chutrinh(i);
    11.   else
    12.       if(i!=stack[d-1]&&index[v]>index[i])
    13.               .......
    14.   d--;
    15. }
    16. void main()
    17. {
    18.     for(int i=1;i<=a.n;i++)
    19.        index[i]=0;
    20.       for(int j=1;j<=a.n;j++)
    21.           chutrinh(j);
    22. }
    đây là thuật toán tìm chu trinh cơ bản của đô thị,mỗi vòng lặp for có nhiều lần gọi đệ quy.
    danh sách kề:
    Simu Code:
    1. 1:kề:2,7,3
    2. 2:kề:6,1;
    3. 3: kề 5,4,1
    4. 4:kề 3,5
    5. 5:3,4
    6. 6:8,97,2
    7. 7:6,9,1
    8. 8:6
    9. 9:7,6
    giờ mình sẽ thủ chạy tay:
    trong hàm main,vòng lặp for thứ 2 bắt đầu j =1;
    index[j]=0 (thỏa điều kiền)
    vào hàm chutrinh(j)//với j=1;
    d=1;
    num=1;
    stack[d]=stack[1]=1;
    index[1]=num=1;
    for(int i=1;i<n;i++)kề 1 là 2
    i=1(bỏ qua)
    i=2 thỏa điều kiện vì(index[2]==0)
    gọi đẹ quy chutrinh(2)//thêm 2 vào stack,kề 2 là 6
    index[2]=2;
    d=2;
    num=2;
    stack =2;
    for(int i=1;i<n;i++)//vòng for 1
    kề 2 là 6
    thêm 6 vào stack (gọi lại chutrinh(6)
    d=3;
    num=3;
    stack[3]=6;
    index[6]=3;
    for(int i=1;i<n;i++)//vòng for 2
    kề 6 là 8//index[8]==0,gọi lại chutrinh(8)
    d=4;
    num=4;
    index[8]=4;
    stack[4]=8;
    for(int i=1;i<n;i++)//vòng for 3
    kề 8 chỉ có 6 mà index[6]=3!=0
    d sẽ giảm bớt 1 còn 3;
    sau đó nó sẽ quay lên vòng for thứ 2 để xét tiếp những đỉnh kề với đỉnh 6.hết vòng lặp 2,lại quay lui lên thực hiện vòng lặp 1 để xét những đỉnh kề 1.
    Every step I'm taking
    Every move I make
    Feels lost with no direction
    My faith is shaking
    But I gotta keep trying.

  5. #5
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Trích dẫn Nguyên bản được gửi bởi clacaigi Xem bài viết
    Lý do lôi Topic lên, mọi người đều đã học qua và rất rành về đệ quy thì có thể giành vài phút phân tích cho mình hiểu rõ ưu và nhược điểm của thuật toán Đệ Quy được ko, mình đã tham khảo tài liệu nhưng kiến thức ko nhiều , ko rút ra được kết luận gì cả. Mong mọi người hồi âm.
    Ưu điểm : trong sáng dễ hiểu, viết ngắn gọn
    Nhược điểm : đa phần thì đệ quy có độ phức tạp lớn hơn cách duyệt và đặt cận thông thường

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  6. #6
    Ngày gia nhập
    12 2008
    Nơi ở
    Bình Dương
    Bài viết
    114

    Mặc định Lý thuyết đệ quy cơ sở - Lý thuyết lập trình

    Trích dẫn Nguyên bản được gửi bởi clacaigi Xem bài viết
    Lý do lôi Topic lên, mọi người đều đã học qua và rất rành về đệ quy thì có thể giành vài phút phân tích cho mình hiểu rõ ưu và nhược điểm của thuật toán Đệ Quy được ko, mình đã tham khảo tài liệu nhưng kiến thức ko nhiều , ko rút ra được kết luận gì cả. Mong mọi người hồi âm.
    1 nhược điểm nữa là, nếu bạn muốn viết được 1 chương trình theo kiểu đệ quy, thì bạn phải hôi tụ được những yếu tố nào? (nghe phong phanh đâu đó là phải có gì đó giống như quy nạp - nói chung là quên rồi, để về lục lại sách đã!). đâu phải bài nào cũng có thể dùng đệ quy, có bài thì có thể dùng đệ quy để giải quyết, nhưng liệu bạn có thể nghĩ ra hay không, và làm như thế nào? nói chung, người ta thường tránh dùng đệ quy để giải quyết bài toán, nếu như còn cách khác để giải quyết!

  7. #7
    Ngày gia nhập
    02 2009
    Bài viết
    35

    nếu hoàn toàn lĩnh hội đc đệ quy bạn sẽ thấy công lực tăng tiến rất nhiều đó
    sẽ càng thêm khâm phục trí tuệ loài người
    thương dân như con

  8. #8
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Đúng là lĩnh hội được đệ quy thì công lực thâm hậu hẳn, nếu không có đệ quy thì chả có QuickSort và MergeSort và HeapSort đâu các bạn ạ. Vì thế trước khi học được mấy cái Sort trên, đề nghị các bạn phải hiểu được đệ quy là gì và phương pháp thiết kế hàm đệ quy:
    Xin phép Kevin và các Mod cho được góp đôi lời, được nói rõ thêm ý mà Kevin nói ở chỗ này
    Trích dẫn Nguyên bản được gửi bởi Kevin Hoang
    Sử dụng đệ quy:

    - Chỉ sử dụng hàm đệ quy khi có suy biến.
    - Trong một trường hợp tổng quát bài toán có thể đưa về cùng dạng. Nhưng giá trị thay đổi, sau một loạt thay đổi nó phải đưa về trường hợp suy biến.
    - Để thiết kế được giải thuật đệ quy.Bạn phải nhận xét được mối quan hệ rằng buộc giữa bài toán cấp n với bài toán cấp nhỏ hơn nó là n-1. Cứ như vậy phân ra đến khi về một bài toán cấp của nó mà ta có lời giải luôn.
    - Ở bài toán mà ta có ngay lời giải, (không phải phân rã ra cấp nhỏ hơn nữa) thì đây chính là Điều Kiện Dừng của thuật toán đệ quy.

    Vậy ta phải làm được là:
    1.Ta phải thiết lập được hàm đệ quy (Chính là công thức truy hồi trong toán 11)
    2.Điều kiện dừng của hàm đệ quy (Chính là điều kiện xuất phát trong của công thức truy hồi)

    Xin ví dụ việc tìm min trong một dãy số có n phần tử.

    Ký hiệu Min(1,n) là vị trí của phần tử min trong dãy có n phần tử bắt đầu từ phần tử 1 đến phần tử n.
    Ký hiệu Min2(i,j) là vị trí của phần tử min trong dãy có chỉ số lần lượt là là i,j. Chú ý là hàm này trả về vị trí của phần tử min trong dãy có n phần tử nhé.
    C Code:
    1. int Min2(int i, int j)
    2. {
    3.  if (A[i]<A[j]) return i;
    4.  else
    5.  return j;
    6. }
    Ta có công thức đệ quy sau:
    Nếu n==2 thì:
    Min(1,2)=Min2(1,2); Đây là điều kiện xuất phát, hay là điều kiện dừng trong hàm đệ quy
    Ngược lại n>2 thì:
    Min(1,n)=min2(min(1,n-1), n);

    Từ đó xin được code giải thuật đệ quy sơ xài như sau:
    C++ Code:
    1. #include <iostream>
    2. #include <ctime>
    3. using namespace std;
    4. int A[10];
    5. int n=10;
    6.  
    7.  //Hàm int min2(int i,int j) trả về vị trí của phần tử nhỏ nhất giữa A[i] và A[j].
    8.  int min2(int i,int j)
    9.  {
    10.   if (A[i]<A[j]) return i;
    11.   else return j;
    12.  }
    13.  
    14. //Hàm tìm vị trí của phần tử min trong dãy có n phần tử sử dụng đệ quy, chú ý là sau khi
    15. //truyền thì giá trị của l luôn bằng 1 nhé.Làm vậy cho khớp với thiết kế ở trên
    16.  int Min(int l,int r)
    17.  {
    18.   if (r-l==1) //Nếu khoảng cách giữa đoạn l đến r có 2 phần tử
    19.     return min2(l,r); //Trả về min2. Đây là điều điện dừng của hàm đệ quy
    20.  else
    21.    if (r-l>1)
    22.    // return Min(  min2(  Min(l,r-1), r )     ); Xin được sửa sai chỗ này
    23.    return min2(Min(l,r-1),r);
    24.  }
    25.  
    26. void main()
    27. {
    28.  //Sinh ra dãy ngẫu nhiên
    29.  srand(time(NULL));
    30.  for (int i=0;i<n;i++)
    31.   {
    32.    A[i]=rand()%100;
    33.    cout<<A[i]<<"  ";
    34.   }
    35.  
    36.  //Tìm kiếm vị trí của phần tử nhỏ nhất trong dãy
    37.  int minPos=Min(0,n-1);
    38.  cout<<endl<<"Vi tri Min = "<<minPos<<" , gia tri = "<<A[minPos]<<endl;
    39.  system("pause");
    40. }
    Đã được chỉnh sửa lần cuối bởi Tadius : 20-04-2010 lúc 10:53 PM. Lý do: Sai lầm cơ bản có chết người không?

  9. #9
    Ngày gia nhập
    02 2009
    Bài viết
    35

    C++ Code:
    1.     return Min(  min2(  Min(l,r-1), r )     );

    code sai rồi kìa zzzz
    thương dân như con

  10. #10
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi takiemtam Xem bài viết
    C++ Code:
    1.     return Min(  min2(  Min(l,r-1), r )     );

    code sai rồi kìa zzzz
    Đâu có chạy bình thường . Viết thế để các bạn đỡ bị loạn bởi các dấu ngoặc.

Các đề tài tương tự

  1. Thuyết Trình Ext Js for asp.net
    Gửi bởi bigs1993 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 07-12-2013, 11:06 PM
  2. bài tập lý thuyết đồ thị
    Gửi bởi canhocthem trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 11-10-2010, 11:39 PM
  3. lý thuyết tô màu cho đồ thị
    Gửi bởi #include# trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2008, 04:11 PM
  4. Lý thuyết đồ thị với C++
    Gửi bởi CuongNH trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 15-04-2008, 09:39 AM
  5. [Phụ lục C] - Dành cho tra cứu lý thuyết C
    Gửi bởi Kevin Hoang trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 22-08-2006, 11:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn