Trang 2 trên tổng số 5 Đầu tiênĐầu tiên 1234... Cuối cùngCuối cùng
Từ 11 tới 20 trên tổng số 43 kết quả

Đề tài: Bài toán Tháp Hà Nội | Tower of Hanoi

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

    Mặc định Bài toán Tháp Hà Nội | Tower of Hanoi

    Trích dẫn Nguyên bản được gửi bởi theanhkkt Xem bài viết
    Có ai biết độ phức tạp thuật toán này là cỡ nhiêu không?
    trong môn phân tích độ phức tạp của thuật toán - thì nó là cỡ O nào?
    mà theo mình biết thì bài toán này là do 1 người ấn độ nghĩ ra mà, tên là ha noi. đến việt nam sao đổi thành hà nội
    Bài toán này do các nhà chiêm tinh ở babylon nghĩ ra khi sắp xếp các tản đá với n = 64, tương truyền rằng khi giải xong bài toán này sẽ đến ngày tận thế.
    2^64-1 lần di chuyển, cứ tính mỗi lần di chuyển mất... 1s thì phải làm đến 5.8*10^11 lần =))

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

  2. #12
    Ngày gia nhập
    10 2010
    Bài viết
    2

    Trích dẫn Nguyên bản được gửi bởi goalball1 Xem bài viết
    em cũng xin góp 1 bài...cho thêm phần sinh động...
    C++ Code:
    1. #include<conio.h>
    2. #include<iostream.h>
    3. #include<process.h>
    4. void hn(int n,char a,char b,char c)
    5. {
    6.   if(n==1)
    7.     {
    8.     cout<<"\nchuyen 1 dia tu "<<a<<" sang "<<c;
    9.     cout<<"\n";
    10.     }
    11.   else
    12.      {
    13.        hn(n-1,a,c,b);
    14.        hn(1,a,b,c);
    15.        hn(n-1,b,a,c);
    16.      }
    17. }
    18. void main()
    19. {
    20.    int n;
    21.    clrscr();
    22.    cout<<"nhap vao so dia:";
    23.    cin>>n;
    24.    hn(n,'A','B','C');
    25.    getch();
    26. }
    thanks bạn nhé. mình thích dùng C++ hơn, bạn có thể gán A, B, C theo kiểu int mà, thế cho gọn

  3. #13
    Ngày gia nhập
    10 2010
    Bài viết
    1

    Trích dẫn Nguyên bản được gửi bởi goalball1 Xem bài viết
    em cũng xin góp 1 bài...cho thêm phần sinh động...
    C++ Code:
    1. #include<conio.h>
    2. #include<iostream.h>
    3. #include<process.h>
    4. void hn(int n,char a,char b,char c)
    5. {
    6.   if(n==1)
    7.     {
    8.     cout<<"\nchuyen 1 dia tu "<<a<<" sang "<<c;
    9.     cout<<"\n";
    10.     }
    11.   else
    12.      {
    13.        hn(n-1,a,c,b);
    14.        hn(1,a,b,c);
    15.        hn(n-1,b,a,c);
    16.      }
    17. }
    18. void main()
    19. {
    20.    int n;
    21.    clrscr();
    22.    cout<<"nhap vao so dia:";
    23.    cin>>n;
    24.    hn(n,'A','B','C');
    25.    getch();
    26. }
    mình gà có 1 vấn đề chưa hiểu lắm.Mọi người có thể cho mình biết cái n-1 và 1 có ý nghĩa gì ko.Nó đại diện cho cái gì trong bài toán

  4. #14
    Ngày gia nhập
    12 2010
    Bài viết
    1

    còn đối với bài tháp Hà Nội nhiều cọc thì sao
    tức là cho n cọc, m đĩa (m, n <=64)

  5. #15
    Ngày gia nhập
    02 2011
    Bài viết
    11

    Mặc định Tháp HN dùng C++ nè

    C++ Code:
    1. /* Bai toan thap HN */
    2. #include<iostream.h>
    3. #include<stdio.h>
    4. #include<conio.h>
    5.  
    6. void HANOI(int n, int c1, int c2,int c3)
    7. {
    8.  if(n==1)
    9.   cout<<c1<<"->"<<c3<<"\n";
    10.  else
    11.      {
    12.       HANOI(n-1,c1,c3,c2);
    13.       HANOI(1,c1,c2,c3);
    14.       HANOI(n-1,c2,c1,c3);
    15.      }
    16. }
    17.  
    18. void main()
    19.   {
    20.    int n,c1=1,c2=2,c3=3;
    21.    cout<<"\n nhap so dia can chuyen:";
    22.    cin>>n;
    23.    HANOI(n,c1,c2,c3);
    24.    getch();
    25.   }

  6. #16
    Ngày gia nhập
    10 2010
    Bài viết
    10

    Mặc định Bài toán Tháp Hà Nội | Tower of Hanoi

    Trích dẫn Nguyên bản được gửi bởi goalball1 Xem bài viết
    em cũng xin góp 1 bài...cho thêm phần sinh động...
    C++ Code:
    1. #include<conio.h>
    2. #include<iostream.h>
    3. #include<process.h>
    4. void hn(int n,char a,char b,char c)
    5. {
    6.   if(n==1)
    7.     {
    8.     cout<<"\nchuyen 1 dia tu "<<a<<" sang "<<c;
    9.     cout<<"\n";
    10.     }
    11.   else
    12.      {
    13.        hn(n-1,a,c,b);
    14.        hn(1,a,b,c);
    15.        hn(n-1,b,a,c);
    16.      }
    17. }
    18. void main()
    19. {
    20.    int n;
    21.    clrscr();
    22.    cout<<"nhap vao so dia:";
    23.    cin>>n;
    24.    hn(n,'A','B','C');
    25.    getch();
    26. }
    mình chạy thử cái chương trình này
    Đã được chỉnh sửa lần cuối bởi mrlamtb : 13-05-2011 lúc 10:14 AM.

  7. #17
    Ngày gia nhập
    03 2011
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi conrongchautien Xem bài viết
    Đóng góp code
    PHP Code:
    /* Bai toan thap HN */
    #include<stdio.h>
    #include<conio.h>

    void DICH_CHUYEN(int nint c1int c2,int c3)
    {
     if(
    n==1printf("\n\t%d ->%d",c1,c2);
     else
         {
          
    DICH_CHUYEN(n-1,c1,c3,c2);
         
    DICH_CHUYEN(1,c1,c2,c3);
         
    DICH_CHUYEN(n-1,c3,c2,c1);
        }
    }

    void main()
      {
       
    int n,c1=1,c2=2,c3=3;
       
    clrscr();
       
    printf("\ncho so dia can chuyen:");scanf("%d",&n);
       
    DICH_CHUYEN(n,c1,c2,c3);
       
    getch();
      } 
    code của bạn hơi nhầm chút, mình sửa lại thế này nè :
    Code:
    /* Bai toan thap HN */
    #include<stdio.h>
    #include<conio.h>
    
    void DICH_CHUYEN(int n, int c1, int c2,int c3)
    {
     if(n==1) printf("\n\t%d ->%d",c1,c3);
     else
    	  {
    	  DICH_CHUYEN(n-1,c1,c3,c2);
    	  DICH_CHUYEN(1,c1,c2,c3);
    	 DICH_CHUYEN(n-1,c2,c1,c3);
    	 }
    }
    
    void main()
      {
    	int n,c1=1,c2=2,c3=3;
    	clrscr();
    	printf("\ncho so dia can chuyen:");scanf("%d",&n);
    	DICH_CHUYEN(n,c1,c2,c3);
    	getch();
      }

  8. #18
    Ngày gia nhập
    05 2011
    Bài viết
    1

    Theo mình biết if else là nếu điều kiện if đúng thì nó ko thực hiện lệnh else đúng ko?cái n==1 là nghĩa thế nào?
    DICH_CHUYEN(n-1,c1,c3,c2);
    DICH_CHUYEN(1,c1,c2,c3);
    DICH_CHUYEN(n-1,c3,c2,c1);
    còn 3 dòng trong lệnh trong else ý nghĩa là gì?mình đã tìm ebook c++ đọc nhưng cũng ko hiểu

  9. #19
    Ngày gia nhập
    05 2011
    Nơi ở
    TP HCM
    Bài viết
    27

    Độ phức tạp O(2^n). Nếu chuyển n đĩa thì cần ít nhất 2^n-1 bước !

    @ntd2011: N==1 là còn 1 đĩa đó bạn ! Còn sau else, nếu n>1, thì chuyển n-1 đĩa (nhỏ hơn n) từ cột đầu sang cột trung gian, sau đó chuyển đĩa thứ n từ cột đầu sang cột đích, rồi lại chuyển n-1 đĩa kia từ cột trung gian qua cột đích ! Trong quá trình chuyển thì các cột (đầu, đích, trung gian) có thể thay đổi chức năng cho nhau tùy theo n (cột này là đầu với đĩa n nhưng có thể là đích với đĩa n-1 ... )

  10. #20
    Ngày gia nhập
    01 2011
    Bài viết
    35

    Theo mình: Với bài toán Tháp Hà Nội dạng tổng quát thế này (n Đĩa và m cột).
    Ta có thể đưa bài toán này trở về bài toán QHD có thể sẽ chạy nhanh hơn thuật đệ quy.
    - F[i,j] là số lần chuyển ít nhất để chuyển i đĩa sử dụng j cột.
    - Ta nhận thấy : Tại i , j (j > 3) thì ta cần chuyển k đĩa (1<=k<i) sang cột j1 (1<j1<j) , sau đó chuyển i-k đĩa còn lại sang cột thứ j và chuyển k đĩa đó sang lại cột thứ j. Vậy ta có công thức
    F[i,j] = Max(F[i,j] , F[k,j]*2 + F[i-k,j-1]) (với k = 1..i-1)
    - Ta có thể khơi tạo:
    F[i,1] = 0
    F[1,2] = F[2,2] = 1
    F[i,2] = +oo (i>2)
    F[i,3] = 2^i-1
    Đã được chỉnh sửa lần cuối bởi Coder_1340 : 03-06-2011 lúc 10:45 PM.

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

  1. Cho thuê Căn hộ 3pn,1000 USD, đủ đồ, Chung cư Keangnam HaNoi landmark Tower
    Gửi bởi kyucmotthoi999 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 22-11-2013, 10:45 AM
  2. Bán suất ngoại giao chung cư Indochina Plaza Hanoi Tower ( IPH )
    Gửi bởi hienviboss trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 23-07-2012, 03:52 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