Bài tập lớn môn toán rời tạc-Bài toán tháp hà nội

Sinh viên thực hiện:  Cao Xuân Sơn(1100804)

                                   Vũ Thị Lan Anh(1400006)
                                   Trần Văn Hậu(1400108)
                                                           

Giảng viên:              Ts. Trần Xuân Thanh

MỤC LỤC

MỤC LỤC.. 1

LỜI MỞ ĐẦU.. 2

Chương 1: Giới thiệu bài toán Tháp Hà Nội 3

Chương 2: Bài toán và cách giải bài toán Tháp Hà Nội 6

2.1 Phát biểu bài toán Tháp Hà Nội 6

2.2. Cách giải bài toán Tháp Hà Nội 6

Chương 3: Giải bài toán Tháp Hà Nội bằng thuật toán đệ quy(DevC++) 8

3.1. Thuật toán đệ quy giải bài toán. 8

3.2. Chương trình. 8

3.3. Kết quả chương trình. 9

KẾT LUẬN.. 12

TÀI LIỆU THAM KHẢO.. 13

LỜI MỞ ĐẦU

Trò chơi (Bài toán) Tháp Hà Nội được phổ biến rộng rãi ở Paris năm 1883 bởi nhà toán học Edouard Lucas, là một bài toán nổi tiếng thế giới, hiện nay đang được nghiên cứu bởi rất nhiều nhà toán học và khoa học máy tính, các chuyên gia giáo dục và y học, được đưa vào nhiều giáo trình tin học và sách về trò chơi toán học như một ví dụ điển hình về thuật toán đệ qui và lập trình căn bản, nhưng hình như chưa được chú ý nghiên cứu ở Việt Nam. Mặc dù trò chơi Tháp Hà Nội có mặt trên khá nhiều trang WEB và giáo trình tiếng Việt, số lượng bài viết tiếng Việt giới thiệu về trò chơi và bài toán Tháp Hà Nội trên các tạp chí là rất ít và còn rất sơ lược, hình như chưa có bài nghiên cứu tiếng Việt nào về bài toán Tháp Hà Nội, trong khi đó chỉ tính riêng số bài báo nghiên cứu về bài toán Tháp Hà Nội trong lĩnh vực Toán-Tin học đã có đến hơn 450 bài với khoảng 250 bài với đầu đề có cụm từ "The Tower of Hanoi", đăng trên hơn 100 tạp chí khoa học uy tín (trong thống kê số lượng bài báo khoa học viết về Tháp Hà Nội là 464 bài). Đó là chưa kể đến những bài viết về sử dụng bài toán Tháp Hà Nội trong khoa học giáo dục và y học. Trò chơi Tháp Hà Nội thú vị đến mức nó đã được dùng làm đề tài của một số luận án Tiến sĩ và luận văn cao học. Một hội thảo khoa học quốc tế  với tên gọi Workshop on the Tower of Hanoi and Related Problems đã được tổ chức năm 2005.  Bài toán Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của Việt nam, mà nó hấp dẫn các nhà Toán-Tin học bởi nó liên quan đến nhiều vấn đề như giải thuật đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski, lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính toán,.... Bài toán Tháp Hà Nội gợi ý cho nhiều nghiên cứu trong khoa học máy tính và toán học.

Chương 1: Giới thiệu bài toán Tháp Hà Nội

Có thể còn ít người Việt Nam biết Tháp Hà Nội, nhưng rất nhiều thanh niên sinh viên trên toàn thế giới lại biết đến nó. Đó là vì, Tháp Hà Nội là tên một bài toán rất nổi tiếng trong Chương trình khoa học tính toán (Computing Science) dành cho sinh viên những năm đầu tại các trường đại học ở nhiều nơi trên thế giới.

Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho n cái đĩa (ngài không nói chính xác là bao nhiêu) và ba cái trục: A là trục nguồn, B là trục đích, và C là trục trung chuyển. Những cái đĩa có kích cỡ khác nhau và có lỗ ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục C được phép sử dụng làm trục trung chuyển? 

Vì địa vị quân sư được coi là vinh hiển nên có rất nhiều người dự thi. Từ vị học giả đến bác nông phu, họ đua nhau trình lên Hoàng đế lời giải của mình. Nhiều lời giải dài tới hàng nghìn bước, và nhiều lời giải có chữ "chuyển sang bước tiếp theo" (go to). Nhưng hoàng đế thấy mệt mỏi vì những lời giải đó, nên cuối cùng hạ chiếu: "Ta không hiểu những lời giải này. Phải có một cách giải nào khác dễ hiểu và nhanh chóng hơn". May mắn thay, cuối cùng đã có một cách giải như thế.

Thật vậy, ngay sau khi chiếu vua ban ra, một vị cao tăng trông bề ngoài giống như một kỳ nhân hạ sơn tới xin yết kiến hoàng đế. Vị cao tăng nói: "Thưa Bệ hạ, bài toán đố đó dễ quá, hầu như nó tự giải cho nó". Quan trùm cấm vệ đứng hầu ngay bên cạnh vua quắc mắt nhìn gã kỳ nhân, muốn quẳng gã ra ngoài, nhưng Hoàng đế vẫn kiên nhẫn tiếp tục lắng nghe. "Nếu chỉ có 1 đĩa, thì...; nếu có nhiều hơn 1 đĩa (n>1), thì...", cứ thế vị cao tăng bình tĩnh giảng giải. Im lặng được một lát, cuối cùng Hoàng đế sốt ruột gắt: "Được, thế cao tăng có nói rõ cho ta lời giải hay không cơ chứ?". Thay vì giải thích tiếp, gã kỳ nhân mỉm cười thâm thúy rồi biến mất, bởi vì hoàng đế tuy giỏi giang nhưng rõ ràng là chưa hiểu ý nghĩa của phép truy hồi (recursion). Nhưng các bạn sinh viên ngày nay thì có thể thấy cách giải của vị cao tăng là hoàn toàn đúng.

Toàn bộ đoạn chữ nghiêng ở trên được trích nguyên văn từ cuốn sách giáo khoa dành cho sinh viên ngành thuật toán và lập trình - "giải toán nâng cao và cấu trúc dữ liệu" (intermediate problem solving and data structures) do Paul Henman và Robert Veroff, hai giáo sư Đại học New Mexico, cùng biên soạn với Frank Carrano, giáo sư Đại học Rhode Island (Mỹ).

Bạn nào chưa từng biết Tháp Hà Nội thì cũng nên "thử sức" một chút xem sao, vì đây là một trò chơi rất thú vị. Bạn có thể bắt đầu bằng bài toán 3 đĩa, rồi nâng lên 4 đĩa. Với 4 đĩa chắc bạn bắt đầu thấy rắc rối. Nâng tiếp lên 5 và cao hơn nữa, chẳng hạn n = 1 triệu, bài toán sẽ rắc rối đến mức không ai đủ kiên trì và đủ thì giờ để thử từng đĩa một. Vậy mà vị cao tăng dám nói là dễ quá! Xin tiết lộ, ấy là vì vị đó đã sử dụng phép truy hồi - một quy tắc toán học cho phép xác định số hạng thứ n từ số hạng đứng trước nó, tức số hạng thứ n-1. Cái giỏi của vị cao tăng là ông tìm ra một quy tắc chung, tức một thuật toán chung cho tất cả các bước chuyển đĩa. 

Vậy thay vì mô tả toàn bộ quá trình chuyển đĩa từng cái một như những thí sinh trước đó đã làm, vị cao tăng chỉ mô tả một quy tắc chung. Cứ làm theo quy tắc đó, lặp đi lặp lại chẳng cần suy nghĩ gì, rồi cuối cùng tự nhiên sẽ tới đích. Vì thế vị cao tăng nói rằng bài toán này "tự nó giải nó".

Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để lập trình. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Nếu số lần lặp lại lên đến con số hàng triệu hàng tỷ thì con người không đủ sức và thời gian để làm, nhưng máy tính thì có thể giải quyết trong chớp mắt. Điểm mạnh của computer là ở chỗ nó không hề biết e ngại và mệt mỏi trước những công việc lặp đi lặp lại lên đến hàng triệu hàng tỷ lần. Và vì thế, việc cộng tác giữa computer với con người là mô hình lý tưởng của lao động trí óc trong cuộc sống hiện đại.

Về mặt lịch sử, Tháp Hà Nội được E. Lucas phát hiện từ năm 1883, nhưng mãi đến gần đây người ta mới nhận ra ý nghĩa hiện đại của nó. Hiện vẫn chưa rõ vì sao Lucas lại gọi chồng đĩa trong bài toán là Tháp Hà Nội, mà không gọi là Tháp Bắc Kinh, hay Tháp Tokyo. 

Tháp Hà Nội đã mở tung cánh cửa cho tương lai khi nhiều nghiên cứu lấy Tháp Hà Nội làm điểm xuất phát đã đạt được thành tựu mới: 

(1) Nâng câu hỏi của Tháp Hà Nội lên một mức cao hơn, sao cho số lần chuyển đĩa là nhỏ nhất. Các nhà toán học đã phát hiện ra rằng Tháp Hà Nội có cùng bản chất với bài toán tìm Đường Hamilton (Hamilton Path) trên một hình giả phương cấp n (n-Hypercube), một bài toán cũng rất nổi tiếng. 

(2) Nhà toán học D.G. Poole đã sáng tạo ra Lược Đồ Hà Nội - một tam giác có các đỉnh tương ứng với các cách sắp xếp đĩa trong Tháp Hà Nội, từ đó tìm ra những liên hệ lý thú giữa Tam giác Pascal với Lược đồ Hà Nội. Liên hệ này đã được công bố trong một công trình mang một cái tên đầy liên tưởng: Pascal biết Hà Nội (Pascal knows Hanoi).

Hiện nay, tại một số đại học ở Australia, uy tín của sinh viên Việt Nam trong lĩnh vực lập trình được đánh giá ngang với sinh viên Ấn Độ - một cường quốc lập trình của thế giới, làm cho Tháp Hà Nội vốn đã nổi tiếng lại càng nổi tiếng hơn.

Chương 2: Bài toán và cách giải bài toán Tháp Hà Nội

2.1 Phát biểu bài toán Tháp Hà Nội

Có 3 cọc A,B,C. Trên cọc A có một chồng gồm n cái đĩa đường kính giảm dần từ dưới lên trên cân phải chuyển chồng đĩa từ cọc A sang cọc C tuân thủ quy tắc: mỗi lần chỉ được chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ hơn lên đĩa có đường kính lớn hơn. Trong quá trình chuyển được phép dùng cọc B làm cọc trung gian.

2.2. Cách giải bài toán Tháp Hà Nội

          Bài toán có 2 chiều, chiều nghịch dùng để phân tích bài toán và dùng để lập trình, chiều thuận để thực hiện trên mô hình. Ở đây nguyên lí thực hiện (tức là cách hiểu bài toán) nằm ở chiều nghịch, còn cách thực hiện nằm ở chiều thuận. Chiều nghịch dùng cho dân lập trình và chiều thuận dành cho dân toán. 

Chiều nghịch thì dân lập trình hay gọi là bài toán đệ qui. Bài toán này có ví dụ đơn giản như sau: giaithừa(n)=giaithừa(n-1)*n. Muốn tính giai thừa của n thì đơn giản, lấy n nhân với giai thừa của (n-1). Còn giai thừa của (n-1) thì tính sao? Đơn giản, cứ lấy (n-1) nhân với giai thừa của (n-2) …

2.2.1. Chiều nghịch (nguyên lí)

            Muốn đưa n khối tròn từ cột A (cột nguồn) sang cột C (cột đích) thông qua cột B (cột trung gian) thì chỉ cần đưa (n-1) khối tròn từ A qua B, rồi đưa 1 khối tròn từ A qua C và cuối cùng là đưa (n-1) khối tròn từ B qua C. Đã làm xong bài toán!!!

Còn (n-1) khối tròn từ A sang B thì làm sao mà đưa? Đơn giản, khi đó xem A là cột nguồn, B là cột đích và C là cột trung gian. Việc tiến hành tương tự, đưa (n-2) khối từ cột nguồn qua cột trung gian, 1 khối từ cột nguồn sang cột đích và cuối cùng là (n-2) khối từ cột trung gian sang cột đích. 

2.2.2. Chiều thuận

 Nói đơn giản để hiệu thì như chiều nghịch đã nói. Còn thực hiện (chiều thuận) thì làm sao? Khối tròn đầu tiên từ cột nguồn A thì chuyển vào đâu? Cột trung gian B hay cột đích C?

Với khối tròn đầu tiên thì chuyển về cột đích (với n là số lẻ) và cột trung gian (với n là số chẳn). Xếp được 1 khối tròn (khối nhỏ nhất) theo đúng yêu cầu thì tiếp theo là xếp 2 khối tròn theo đúng yêu cầu (2 khối nhỏ nhất và nhỏ nhì). Cứ xếp 2 khối đó vào cột còn lại so với lần đầu tiên và làm tiếp vớ 3, 4, … khối tròn. Điều vừa nói được diễn đạt như sau:

Với n lẻ: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….

• 1 khối nhỏ nhất qua C (cột đích)

• 2 khối nhỏ nhất qua B (cột trung gian)

• 3 khối nhỏ nhất qua C (cột đích)

• 4 khối nhỏ nhất qua B (cột trung gian)

• Tiếp tục như trên

Với n chẳn: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….

• 1 khối nhỏ nhất qua B (cột trung gian)

• 2 khối nhỏ nhất qua C (cột đích)

• 3 khối nhỏ nhất qua B (cột trung gian)

• 4 khối nhỏ nhất qua C (cột đích)

• Tiếp tục như trên

Phát triển của cách làm trên: Muốn chuyển n khối tròn từ cột nguồn sang cột đích thì làm như sau (ở đây ta phải hiểu rõ cột nguồn không nhất thiết là cột A, cột đích là C hay cột trung gian là B mà phải hiểu tổng quát, có thể cột nguồn là B chẳng hạn (trong phép chuyển (n-1) cột từ cột B sang cột C như trong cách làm ở phần nghịch)):

Với n lẻ: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….

• 1 khối nhỏ nhất qua cột đích

• 2 khối nhỏ nhất qua cột trung gian

• 3 khối nhỏ nhất qua cột đích

• 4 khối nhỏ nhất qua cột trung gian

• Tiếp tục như trên

Với n chẳn: cách xếp các khối như sau. Đầu tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài toán với n=2) ….

• 1 khối nhỏ nhất qua cột trung gian

• 2 khối nhỏ nhất qua cột đích

• 3 khối nhỏ nhất qua cột trung gian

• 4 khối nhỏ nhất qua cột đích

• Tiếp tục như trên

- Như vậy thì số lần chuyển cho bài toán là bao nhiêu? Với bài toán tháp Hà Nội chuyển n khối tròn từ cột nguồn A sang cột đích C thông qua cột trung gian B thì cần có 2^0 + 2^1 + 2^2 + … + 2^n lần chuyển

Chương 3: Giải bài toán Tháp Hà Nội bằng thuật toán đệ quy(DevC++)

3.1. Thuật toán đệ quy giải bài toán

3.2. Chương trình

                                                             

3.3. Kết quả chương trình

Kết quả chương trình với n=1.

Kết quả chương trình với n=2.

Kết quả chương trình với n=3.

Kết quả chương trình với n=4.

KẾT LUẬN

            Trong bài tập lớn này, chúng em đã trình bày được khái quát lịch sử của bài toán Tháp Hà Nội, thuật toán đệ quy của bài toán và mô phỏng chương trình. Bài làm còn sơ sài mong thầy và các bạn bỏ qua cho chúng em. Em xin chân thành cảm ơn!

                                                               

TÀI LIỆU THAM KHẢO

[1]  Phạm Trà Ân, Bài toán Tháp Hà Nội, Tạp chí Toán học và Tuổi trẻ, số 280, tháng 10.2000.

[2] Phạm Trà Ân, Bài toán Tháp Hà Nội-Cái nhìn từ lý thuyết Độ phức tạp tính toán, Tạp chí Thông tin Toán học, Tập 6 Số 2, tháng 8 năm 2002, trang 10-13.

[3] Vũ Đình Hòa, Bài toán Tháp Hà Nội, Tạp chí Toán Tuổi thơ 2, Số 68, tháng 10.2008.

[4]  Tạ Duy Phượng, Trò chơi Tháp Hà Nội-Lịch sử và bài toán tổng quát, Tạp chí Toán học và Tuổi trẻ, số 280, tháng 1.2010.

[5]  Tạ Duy Phượng, Trò chơi Tháp Hà Nội và những bài toán liên quan (Bản thảo), 150 trang.

[6]  Nguyễn Xuân Tấn, Bài toán “Tháp Hà Nội”-một bài toán hóc búa hơn một trăm năm nay, Tạp chí Thông tin Toán học, Tập 6 Số 1, tháng 3 năm 2002, trang 2-4.

[7] Các bài trên các trang WEB viết về trò chơi Tháp Hà Nội.

Download chương trình: https://drive.google.com/file/d/0B5fbXrMbFIyBeTFsalJEVUtzRlk/view?usp=sharing

Toán rời rạc- Buổi 2

#include<conio.h>
#include<iostream>
#include<math.h>
#include<cstdlib>

using namespace std;

void maxmin()
{
int mang[10],n,max,min;
cout<<"Nhap n: ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\nmang["<<i<<"]= ";
cin>>mang[i];
}
max=mang[0];
min=mang[0];
cout<<"\nCac so vua nhap la:\t";
for(int i=0;i<n;i++)
cout<<mang[i]<<"\t";
for(int i=1;i<n;i++)
{
if(min>mang[i])
min=mang[i];
if(max<mang[i])
max=mang[i];
}
cout<<"\nMax la: "<<max;
cout<<"\nMin la: "<<min;
}

void ptb1()
{
float a,b;
cout<<"Nhap a: ";
cin>>a;
cout<<"Nhap b: ";
cin>>b;
if(a==0)
{
if(b==0)
cout<<"Phuong trinh co vo so nghiem!";
else
cout<<"Phuong trinh vo nghiem!";
}
else
cout<<"Phuong trinh co nghiem x="<<-b/a;
}

void ptb2()
{
float a1,b1,c1,d1;
cout<<"Nhap a: ";
cin>>a1;
cout<<"Nhap b: ";
cin>>b1;
cout<<"Nhap c: ";
cin>>c1;
if(a1==0)
{
if(b1==0)
{
if(c1==0)
cout<<"Phuong trinh co vo so nghiem!";
else
cout<<"Phuong trinh vo nghiem!";
}
else
cout<<"Phuong trinh co nghiem x="<<-c1/b1;
}
else
{
d1=b1*b1-4*a1*c1;
if(d1<0)
cout<<"Phuong trinh vo nghiem!";
else
{
if(d1>0)
{
cout<<"\nPhuong trinh co nghiem x1="<<(-b1+sqrt(d1))/(2*a1);
cout<<"\nPhuong trinh co nghiem x2="<<(-b1-sqrt(d1))/(2*a1);
}
else
cout<<"\nPhuong trinh co nghiem kep x="<<-b1/(2*a1);
}
}
}

void diem()
{
float diem;
cout<<"\nNhap diem toan roi rac: ";
cin>>diem;
if(diem>=8.5)
cout<<"\nDiem chu la: "<<"A";
else
{
if(diem>=7)
cout<<"\nDiem chu la: "<<"B";
else
if(diem>=5.5)
cout<<"\nDiem chu la: "<<"C";
else
if(diem>=4)
cout<<"\nDiem chu la: "<<"D";
else
cout<<"\nDiem chu la: "<<"F";
}

}

int main()
{
char t;
maxmin();
cout<<"\n\n---------------------------------\n";
ptb1();
cout<<"\n\n---------------------------------\n";
ptb2();
cout<<"\n\n---------------------------------\n";
diem();
cout<<"\n\nBan muon thoat khong? (y/n)\n";
cin>>t;
if(t=='y'||t=='Y')
getch();
else
{
main();
}
}

Bài toán tháp Hà Nội

Bài toán tháp Hà Nội

Mục đích của bài toán là thực hiện được yêu cầu của trò chơi. Dạng bài toán thông dụng nhất là: "Người chơi được cho ba cái cọc và một số đĩa có kích thước khác nhau có thể cho vào các cọc này. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau: một lần chỉ được di chuyển một đĩa một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)". Bài toán này có lời giải chính xác. Tuy nhiên các mở rộng cho trường hợp có nhiều hơn ba cọc cho đến nay vẫn chưa được giải cặn kẽ. Đa số các trò chơi dạng này có 8 đĩa. Đối với người mới chơi thì có vẻ khó nhưng thật rathuật giải của nó hết sức đơn giản: Thuật giải đệ quy đặt tên các cọc là A, B, C -- những tên này có thể chuyển ở các bước khác nhau (ở đây: A = Cọc Nguồn, B = Cọc Đích, C = Cọc Trung Gian) gọi n là tổng số đĩa đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng) Để chuyển n đĩa từ cọc A sang cọc B thì cần: chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A chuyển đĩa #n từ A sang B chuyển n-1 đĩa từ C sang B cho chúng nằm trên đĩa #n Phương pháp trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho n-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho n = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc C. Ngôn ngữ Pascal biểu diễn giải thuật trên là: VAR n: Integer; Procedure chuyen(sodia: Integer; CotNguon: Char; CotDich: Char; CotTG: Char);    Begin         If sodia>0 then begin            chuyen(sodia-1, CotNguon, CotTG, CotDich);            Writeln(CotNguon,`->`,CotDich); { Dia lon nhat hien tai }            chuyen(sodia-1, CotTG, CotDich, CotNguon)         End;    End; BEGIN      Write(`Hay nhap so dia: `); Readln(n);      chuyen(n,`A`,`C`,`B`);//Thực hiện chuyển từ cột A sang cột C với cột B làm trung gian      Readln; END. Giải thích thuật giải (Trên) Lời giải cho 3 đĩa. (Dưới) Lời giải cho 4 đĩa. Tái tạo lại trang trong phần này để xem sự tương quan giữa hai lời giải. Sau đây là dạng dễ xem hơn của thuật giải này: chuyển đĩa 1 sang cọc C chuyển đĩa 2 sang cọc B chuyển đĩa 1 từ C sang B sao cho nó nằm lên 2 Vậy ta hiện có 2 đĩa đã nằm trên cọc B, cọc C hiện thời trống chuyển đĩa 3 sang cọc C lặp lại 3 bước trên để chuyển 1 & 2 cho nằm lên 3 Mỗi lần dựng xong tháp từ đĩa i đến 1, chuyển đĩa i+1 từ cọc A là cọc xuất phát, rồi lại di chuyển tháp đã dựng lên đĩa i+1. Giải thuật bằng biểu diễn nhị phân Các vị trí đĩa có thể xác định được trực tiếp từ biểu diễn nhị phân của số thứ tự di chuyển (cơ số 2 với một chữ số cho mỗi đĩa) trong đó các dãy 1 và các dãy 0 tượng trưng cho các dãy các đĩa liền nhau trên cùng cọc, và mỗi khi chữ số có thay đổi thì đĩa kế tiếp sẽ dời sang trái hay phải một cọc (hay chuyển sang cọc ngoài cùng phía đối diện). Chữ số ở đầu đại diện cho đĩa lớn nhất và nếu là chữ số 0 thì có nghĩa là đĩa lớn nhất không dời khỏi cọc xuất phát và ngược lại. Đặt các chữ số 1 và 0 luân phiên bên dưới các chữ số của một bước chuyển cho phép biết được di chuyển theo một chiều khi nó hợp với chữ số của bước chuyển tại nơi chữ số thay đổi và theo chiều kia khi nó không hợp. Do đó bước chuyển 00000000... có nghĩa là đặt 8 đĩa lớn nhất lên cọc ban đầu, bước chuyển 11111111... có nghĩa là đặt chúng lên cọc cuối cùng, và bước chuyển 11011000... có hai đĩa lớn nhất trên cọc đích, đĩa tiếp theo trên cọc xuất phát, hai đĩa tiếp theo ở cọc trung gian, và ba đĩa tiếp theo nữa trên cọc xuất phát, bất kể có thêm bao nhiêu chữ số đại diện các đĩa nhỏ hơn. Ta có thể dễ dàng tính được các vị trí của các đĩa trong một bộ tám mươi đĩa sau một số các bước tiến, nếu giới hạn đủ lớn để chứa nó. Việc dùng phương pháp đệ quy cho trường hợp tám mươi đĩa như thế này có thể không thực tế. Ứng dụng Tháp Hà Nội là một bài toán thường được dùng để dạy về lập trình cơ bản. Một phiên bản bằng hình của bài toán này được lập trình trong chương trình soạn thảo emacs, có thể truy cập được bằng cách gõ M-x hanoi. Ngoài ra cũng có một thuật giải mẫu viết bằng ngôn ngữProlog. Bài toán Tháp Hà Nội thường được dùng trong nghiên cứu tâm lý về cách giải quyết vấn đề. Cũng có những biến thể khác của bài toán này gọi là Tháp Luân Đôn dùng trong chuẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành. Trường hợp bốn cọc trở lên Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó. Mặc dù không biết được chính xác cần bao nhiêu lần di chuyển, có thể có một vài kết quả tiệm cận. Có một "lời giải được coi như tối ưu" có thể áp dụng một cách đệ quy để tìm một lời giải–xem giải thích cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer (tiếng Anh). Mặc dù với số đĩa nhỏ thử nghiệm trên máy tính thì "lời giải được coi như tối ưu" này là thực sự tối ưu, nhưng nó vẫn chưa có một chứng minh tổng quát để coi là thực sự tối ưu. Tuy nhiên, những kết quả nghiên cứu trong năm 2004 (tiếng Anh) đã cho thấy lời giải được coi như tối ưu phải nằm trong cùng độ lớn với lời giải tối ưu. CXT (st)

Giới thiệu trường Đại học Thành Đô

Đại học Thành Đô chào đón bạn    Chào mừng bạn đến với trường Đại học Thành Đô, ngôi trường tư thục đầu tiên đào tạo ở bậc đại học của Việt Nam, có trụ sở duy nhất tại Kim Chung, Hoài Đức, Hà Nội. Trường đào tạo đa ngành trình độ kỹ sư, cử nhân đại học, cao đẳng chính quy và đào tạo nghề các cấp.

Tại sao chọn học ở Đại học Thành Đô?

  Được thành lập ngày 30/11/2004, tính đến nay trường đã đào tạo và cấp bằng tốt nghiệp cho hàng ngàn sinh viên. Chương trình đào tạo linh hoạt với hệ thống giáo trình được chọn lựa kỹ càng. Nhà trường tuyển sinh theo điểm chuẩn của Bộ Giáo dục và Đào tạo, thủ tục đơn giản, thuận tiện. Đại học Thành Đô cam kết cung cấp một dịch vụ đào tạo chất lượng với mức chi phí trung bình, hợp lý.

  Đặc điểm nổi bật của nhà trường là hệ thống dịch vụ chăm sóc người học chu đáo. Các tân sinh viên đến trường đều được các cố vân học tập hỗ trợ thường xuyên thông qua thư điện tử, điện thoại … Nhà trường đặc biệt chú trọng chương trình định hướng nghề nghiệp nhằm giúp sinh viên chọn lựa được ngành nghề phù hợp với năng lực chuyên môn, đáp ứng nhu cầu của thị trường lao động.

 Sứ mạng của Đại học Thành Đô

  Sứ mạng của Đại học Thành Đô là đào tạo những sinh viên có phẩm chất đạo đức chính trị, có trình độ chuyên môn nghiệp vụ chất lượng cao đáp ứng nhu cầu của người học và của thị trường lao động trong thời đại mới của nền kinh tế tri thức.

    Để hiện thực hóa sứ mạng này, nhà trường cam kết cung cấp một môi trường học tập sáng tạo, linh hoạt, phát huy năng lực của người học và sự chuyên nghiệp, tâm huyết của đội ngũ giảng viên, cán bộ quản lý.

  Vị trí pháp lý

   Đại học Thành Đô là đại học tư thục, thuộc hệ thống giáo dục đại học Việt Nam. Trường có tư cách pháp nhân, có con dấu riêng, đáp ứng chuẩn Quốc gia về đào tạo bậc đại học.

Bằng do trường Đại học Thành Đô cấp có giá trị như các trường đại học khác trong hệ thống giáo dục đại học Việt Nam và được các doanh nghiệp, các đơn vị sử dụng lao động công nhận. Sinh viên tốt nghiệp Đại học Thành Đô hoàn toàn có thể tiếp tục theo học ở các cấp học cao hơn

  Đội ngũ cán bộ quản lý - giảng viên nhà trường

 Đại học Thành Đô tự hào có đội ngũ giảng viên danh giá đã từng tham gia giảng dạy tại rất nhiều các trường đại học trong nước và quốc tế. Họ tự nguyện đến với nhà trường, đem kiến thức, nghiệp vụ, kinh nghiệm đã tích lũy được của mình truyền đạt cho sinh viên với tâm nguyện hiện thực hóa sứ mệnh của nhà trường.

  Các giảng viên luôn đánh giá, cho điểm kết quả học tập của sinh viên một cách công bằng, khuyến khích sinh viên bước đầu tham gia nghiên cứu khoa học thông qua các bài tập lớn, tiểu luận, đồ án, khóa luận.     

  

Hướng đến một trường đại học đẳng cấp quốc tế    Đại học Thành Đô đang tìm kiếm cơ hội hợp tác quốc tế, nhất là với những trường đại học uy tín, chất lượng nhằm đẩy mạnh và nâng cao vị thế nhà trường. Để đạt mục tiêu này cần xây dựng một kế hoạch rõ ràng phù hợp với điều kiện phát triển Việt Nam, cụ thể là:   - Thu hút lực lượng sinh viên ưu tú - Tận dụng nguồn lực quốc tế, cung cấp dịch vụ đào tạo đáp ứng nhu cầu - Chuyên môn hóa nhằm khai thác triệt để đội ngũ giảng viên danh giá - Khuyến khích hoạt động nghiên cứu khoa học - Tăng cường hợp tác với các doanh nghiệp - Tổ chức lại hệ thống đào tạo - Xây dựng hệ thống đào tạo đa phương tiện, tạo môi trường nghiên cứu trong thời đại thông tin, kỹ thuật số - Xây dựng cơ sở vật chất đạt chuẩn quốc tế - Củng cố hoạt động tài chính hiệu quả - Xây dựng hệ thống quản lý nhà trường chất lượng, hiệu quả