Tháp Hà Nội

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

Ko ai thử bài này à ^^.

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ử.

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.

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.

Đâ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. ^^

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

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à.

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.