Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Tháp Hà Nội

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Tháp Hà Nội   Thu 13 May 2010, 11:33

Chắc có lẽ ai cũng biết bài tháp Hà Nội rồi. Bài này có cách giải đệ quy khá đặc trưng. Nhắc lại bài tháp Hà Nội tí xíu. Có một số đĩa ở trong cột 1. Trong đó, dĩa to hơn luôn ở dưới. Ta cần chuyển hết tất cả các đĩa này sang cột 3, ta được dùng cột 2 làm trung gian. Mỗi lần chuyển chỉ được phép bốc 1 dĩa từ cột này sang cột khác và phải luôn đảm bảo ở mọi lúc, phải đảm bảo ko được phép có 1 đĩa to hơn nằm trên 1 đĩa nhỏ hơn. Tử dưới lên trên, các đĩa xếp theo thứ tự nhỏ dần.

Bài này theo ý tưởng đệ quy là ta sẽ làm theo 3 bước:
bước 1: chuyển n-1 đĩa ở trên sang cột 2
bước 2: chuyển đĩa thứ n sang cột 3
bước 3: chuyển n-1 đĩa ở trên sang cột 3.

Bây giờ bài toán của chúng ta sẽ ko phải là nêu ra các bước nữa. Yêu cầu là nhập hai số n và k (n<=200; k<=2^n-1) . Hãy cho biết ở lần chuyển thứ k thì đĩa nào sẽ được chuyển từ cột nào sang cột nào.

ví dụ
n=4 k=6 => đĩa thứ 2 từ cột 3 sang cột 2
n=4 k=12 => đĩa thứ 3 từ cột 2 sang cột 3
n=20 k=1000000 => dĩa thứ 7 từ cột 1 sang cột 2
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Tháp Hà Nội   Sat 15 May 2010, 19:41

Ko ai thử bài này à ^^.
Về Đầu Trang Go down
hcungphuc
Gà con


Tổng số bài gửi : 11
Join date : 13/05/2010

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 17 May 2010, 20:30

Ha ha, bài này vui đó. Mấy bài khác ít nhiều cũng gặp đề rồi, bài này thì lạ. Không ai xử bài này thì để mình xử.
Về Đầu Trang Go down
hcungphuc
Gà con


Tổng số bài gửi : 11
Join date : 13/05/2010

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 17 May 2010, 20:43

Uhm, bài này mà đệ quy chay thì đừng nói với n=200, chỉ cần n=20, k=2^n-1 thì đã điếc máy tính rồi ^^

Mình có phân tích thế này, litlelee xem thử. Ta có với n đĩa thì tất cả các lần cộng lại sẽ có 2^n-1 lần, trong đó bước đầu tiên có 2^(n-1)-1 lần, bước 2 có 1 lần, bước 3 có 2^(n-1)-1 lần. Như vậy nếu k<=2^(n-1)-1 thì kết quả sẽ nằm trong bước 1, nếu k=2^(n-1) thì kết quả thuộc bước 2, mà bước 2 chỉ có 1 lần nên ta có luôn kết quả. Nếu k>2^(n-1) thì nằm trong bước 3. Như vậy nếu k nằm trong bước 1 hoặc 3 thì ta gọi đệ quy tương ứng. Littlelee nghĩ xem mình nghĩ có đúng ko.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 17 May 2010, 20:47

Phúc cứ đùa hoài. Nghĩ vậy thì đúng chắc rồi chứ hỏi gì ^^. Mình cũng làm theo ý tưởng đó.

Code cụ thể nè
Code:
program thap_ha_noi;
uses crt;
var n,j,x,y,dia:integer;
    k,l:longint; ok:boolean;
procedure nhap;
 begin
  clrscr;
  write('nhap so dia: ');readln(n);
  write('nhap so buoc: ');readln(k);
 end;

function mu(x,y:integer):longint;
 var z:integer; kq:longint;
 begin
  kq:=1;
  for z:=1 to y do kq:=kq*x;
  mu:=kq;
 end;

procedure hanoi(n:integer;k:longint;d,c,t:integer);
 begin
  if ok then
  begin
    l:=mu(2,n-1);
    if l>k then hanoi(n-1,k,d,t,c)
    else
    begin
      k:=k-l;
      if k=0 then
      begin
        ok:=false;
        x:=d; y:=c; dia:=n;
      end;
      hanoi(n-1,k,t,c,d);
    end;
  end;
 end;

procedure tinh;
 begin
  ok:=true;
  hanoi(n,k,1,3,2);
 end;

procedure xuat;
 begin
  writeln(dia,' ',x,' ',y); readln;
 end;

begin
 nhap;
 tinh;
 xuat;
end.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 17 May 2010, 20:57

Đây là làm hoàn toàn theo ý tưởng trên, chứ thức ra nó có khuyết điểm và chính cũng vì nó nên code này chưa thực sự đáp ứng đề đâu. Khuyết điểm đó là mặc dù ta đã biết nên làm gì tiếp theo và ta đã làm tiếp (gọi đệ quy) nhưng lần đệ quy hiện tại vẫn tồn tại, mặc dù nó ko còn lệnh nào nữa, nói đúng hơn là ko cần nữa. Việc tồn tại đó dẫn đến tràn stack. Mình ko nhớ rõ, code trên hình như chạy n với vài chục đã tràn stack rồi. Tuy nhiên code trên rất rõ ràng về ý tương của bài này.

Ta có thể cải tiến thành ko dugnf đệ quy vẫn có thể giải bình thường, chỉ hơi mất công tí thôi. ^^
Về Đầu Trang Go down
hcungphuc
Gà con


Tổng số bài gửi : 11
Join date : 13/05/2010

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 17 May 2010, 21:01

Hình như bài này ta có thể kết hợp thêm quy luật. Mà thôi, rắc rối, cứ để bình thường chạy cũng đâu có mất công, với 200 thì vẫn nhanh như thường thôi.

Littlelee siêng đánh code thật
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 17 May 2010, 21:18

Uhm, bài này thật ra cả đống quy luật ý chứ. Nhưng nếu n lên đến vài chục ngàn thì mới cần. Chứ 200 thì cho dù vognf lặp vô ích thì tối đa cũng chỉ 200 lần->ko si nhê. ^^

Code này mình đánh lâu rồi mà.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Tháp Hà Nội   Mon 26 Jul 2010, 22:41

Bài này mình làm ngắn hơn:
Code:

Var                      N:integer;
Procedure            Chuyen(A,B,C:integer):integer;
Begin
                          If A=1 then writeln(B,'->',C)
                          Else
                          Begin
                                        Chuyen(A-1,B,6-B-C);
                                        Chuyen(1,B,C);
                                        Chuyen(A-1,6-B-C,C);
                          End;
End;
BEGIN
                          Readln(N);
                          Chuyen(N,1,2);
END.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Tháp Hà Nội   Today at 21:31

Về Đầu Trang Go down
 
Tháp Hà Nội
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến