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ố 11 kết quả

Đề tài: bài tập đệ quy

  1. #1
    Ngày gia nhập
    10 2008
    Nơi ở
    đại học vinh
    Bài viết
    283

    Wink bài tập đệ quy

    em có bài tập này nhờ mọi người giúp đở:
    viết thủ tục đệ quy in ra tất cả các hoán vị của n phần tưcuar một dãy số a={a1,a1,...,an}.
    ví dụ n=3,a1=1,a2=2,a3=3; thì in ra:
    1 2 3; 1 3 2 ; 2 1 3 ; 2 3 1 ; 3 1 2 ; 3 2 1 ;

  2. #2
    Ngày gia nhập
    11 2008
    Nơi ở
    Neverland
    Bài viết
    48

    C Code:
    1. #include <stdio.h>
    2.  
    3. int n,x[100],a[100],free[100];
    4.  
    5. void init() {
    6.     int i;
    7.     printf("Enter number :");
    8.     scanf("%d",&n);    
    9.     printf("Enter array:");
    10.     for (i = 1;i <= n;i++)
    11.         scanf("%d",&a[i]);
    12.     for (i = 0;i <= n;i++)
    13.         free[i] = 1;
    14. }
    15. void print(int x[]) {
    16.     int i;
    17.     for (i = 0;i < n;i++)
    18.         printf("%4d",a[x[i]]);
    19.     putchar('\n');
    20. }
    21. void comp(int i) {
    22.     int j;
    23.     for (j = 1;j <= n;j++)
    24.         if (free[j]) {
    25.             free[j] = 0;
    26.             x[i] = j;
    27.             if (i == n - 1) print(x);
    28.             else comp(i+1);
    29.             free[j] = 1;                   
    30.         }
    31. }
    32. int main() {
    33.     init();
    34.     comp(0);
    35. }
    I'm superman

  3. #3
    Ngày gia nhập
    10 2007
    Bài viết
    43

    @trung_dk: theo tớ nghĩ thì u nên để cho bạn ấy tìm hiểu rồi viết code thì hay hơn
    cũng phải để bạn ấ tự làm và khi ko đúng mình mới sửa chứ

    @nguyen my: nếu bạn ko tự tìm hiểu về đệ quy thì bạn sẽ ko thấy cái hay của thuật toán đệ quy đâu.
    Tên chính xác của bài toán này là đệ quy quay lui, nếu bạn chỉ copy code của ng` ta cho thì bạn mãi mãi ko hiểu đc cái hay của thuật toán đâu
    Đã được chỉnh sửa lần cuối bởi boy_popping : 25-12-2008 lúc 09:44 AM.

  4. #4
    Ngày gia nhập
    12 2008
    Bài viết
    0

    chào mấy bạn.cho minh hỏi làm sao hiểu đựoc đệ quy một bài toán?em đang học phần này mà kô sao hiểu đựoc, thấy khó.mấy anh giải thích dùm em với?
    ví dụ ; viết hàm đệ quy để tính X mũ N

  5. #5
    Ngày gia nhập
    04 2008
    Nơi ở
    HCMC
    Bài viết
    251

    Cứ đọc đệ quy đi đã.
    X mũ N = X mũ (N-1) * X
    X mũ (N-1) = X mũ (N-2)*X
    ...
    xem VD ở dưới nhé
    C++ Code:
    1. #include<iostream.h>
    2. int tinhGiaiThua (int n);
    3. int main()
    4. {
    5.     cout<<tinhGiaiThua(5);
    6.     return 0;
    7. }
    8. int tinhGiaiThua (int n)
    9. {
    10.    
    11.     if(n == 1)
    12.         return 1;
    13.     else
    14.         return tinhGiaiThua(n-1)*n;
    15. }
    C++ Code:
    1. for(;;){cout<<"Busy"<<endl;}
    2. system("cls");
    Hãy ủng hộ cho quỹ phát triển cộng đồng C Việt
    http://congdongcviet.com/quyphattrien-congdongcviet.cpp

  6. #6
    Ngày gia nhập
    11 2008
    Nơi ở
    Neverland
    Bài viết
    48

    Mặc định bài tập đệ quy

    Cách đệ quy khác xem sao :
    -N = 1 thì X mũ 1 = X
    -X mũ N = (X mũ N/2) * (X mũ N/2) nếu N chẵn
    -X mũ N = (X mũ N - 1) * X nếu N lẻ
    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3.  
    4. double Pow(float x,int n) {
    5.     if (n == 0) return 1;
    6.     if (n == 1) return x;
    7.     if (n % 2 == 0 ) return Pow(x,n/2) * Pow(x,n/2);
    8.     else return Pow(x,n-1) * x;
    9. }
    10.  
    11. int main() {
    12.     double x = 3.14;
    13.     int n = 3;
    14.     printf("Pow(%.3lf,%d) = %.3lf",x,n,Pow(x,n));
    15.     getch();
    16.     return 0;
    17. }
    Đã được chỉnh sửa lần cuối bởi trung_dk070384 : 23-12-2008 lúc 06:54 PM.
    I'm superman

  7. #7
    Ngày gia nhập
    12 2008
    Bài viết
    0

    cám ơn mấy anh nhiều,mấy anh có video học c kô cho em xin??

  8. #8
    Ngày gia nhập
    10 2008
    Nơi ở
    Q6, TP.HCM
    Bài viết
    5

    vậy ĐQ ở bài hoán vị trên có phải là :
    Hoán vị 5 phần tử, là xài 5 số ở phần tử thứ nhất, và hoán vị 4 phần tử còn lại ko

  9. #9
    Ngày gia nhập
    05 2008
    Bài viết
    224

    mình không hiểu bạn heotatoo183 nói gì , nhưng chỉ nhắc nhở mấy bạn mới học đệ quy quay lui : bài hoán vị là bài đơn giản nhất để tìm hiểu về đệ quy quay lui , nhung sẽ tạo cho các bạn một thắc mắc mà các bạn vẫn tưởng nhầm là quy tắc nó thế :
    Code:
    void comp(int i) {
        int j;
        for (j = 1;j <= n;j++)        if (free[j]) {
                free[j] = 0;
                x[i] = j;
                if (i == n - 1) print(x);
                else comp(i+1);
                free[j] = 1;                    
            }
    }
    các bạn chú ý odongf in đâmh gạch chân , do bài hoán vị sử dụng các số từ 1 -> n cho nên vòng lặp này lấy luôn giá trị j , chứ các bài khác vòng lặp này sẽ lấy phần tử của một mảng , trong khi giúp thầy giáo giảng về phần này mình thấy đa số các bạn hay nhầm chỗ này ( đó là suy nghĩ riêng của mình có thể sai với một số người =>mong thông cảm)
    Em có thấy nắng vàng kỷ niệm
    Hạ ngồi ru thanh thản những môi cười
    Thuở ngồi ngóng tay choàng tay nỗi nhớ
    Vin tay vào tháng năm chơi vơi...

  10. #10
    Ngày gia nhập
    11 2008
    Nơi ở
    Neverland
    Bài viết
    48

    Hoán vị chỉ số bạn ơi do cái bài của bạn nguyen my bắt hoán vị cái mảng gì đó a1 = 1 a2 = 2 a3 = 3 nên mình hoán vị chỉ số của mảng đó các chỉ số mảng 1 -> n --> in ra hoán vị mảng chứ không phải là hoán vị các số từ 1 -> n như bạn cafelanh nghĩ ( bạn hiểu nhầm thuật toán mình rồi ) :
    C Code:
    1. for (i = 0;i < n;i++)
    2.      printf("%4d",a[x[i]]);
    Đã được chỉnh sửa lần cuối bởi trung_dk070384 : 25-12-2008 lúc 10:06 AM.
    I'm superman

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