BÀI TOÁN THÁP HÀ NỘI - TOWER OF HANOI

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.


Cách giải Bài toán:

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) …

- 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. Còn về source code thì sao, xin xem phần sau cùng vì nếu viết ở đây sẽ có thể gây rối một vài bạn đọc không được học về lập trình.

- 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

Read More...

Phân loại thuật toán sắp xếp

Một số thuật toán sắp xếp


Sắp xếp ổn định

Một thuật toán sắp xếp được gọi là sắp xếp ổn định nếu sau khi tiến hành sắp xếp vị trí tương đối giữa các phần tử bằng nhau không bị thay đổi.

Sắp xếp so sánh

Một thuật toán sắp xếp được gọi là sắp xếp so sánh nếu trong quá trình thực hiện thuật toán ta tiến hành so sánh các khoá và đổi chỗ các phần tử cho nhau. Đa số các thuật toán sắp xếp dưới đây là sắp xếp so sánh, riêng sắp xếp đếm phân phối không phải là sắp xếp so sánh.

Sắp xếp nổi bọt

Sắp xếp nổi bọt (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường được dạy trong khoa học máy tính. Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp dữ liệu. Sau đó nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa.

Sắp xếp chèn

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp rất hiệu quả với các danh sách nhỏ. Nó lần lượt lấy các phần tử của danh sách chèn vào vị trí thích hợp trong một danh sách mới đã được sắp.


Sắp xếp chọn

Sắp xếp chọn (selectionÓ sort) là phương pháp sắp xếp bằng cách chọn phần tử bé nhất xếp vào vị trí thứ nhất, tương tự với các phần tử nhỏ t

Sắp xếp trộn

Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp xếp dựa vào tư tưởng "chia để trị" (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư...) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một.


Sắp xếp vun đống

Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).

Sắp xếp nhanh

Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để trị, nó dựa trên thủ tục phân chia như sau: để chia một dãy ta chọn một phần tử được gọi là "chốt" (pivot), chuyển tất cả các phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần tử lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời gian tuyến tính. Tiếp tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử.
Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định thứ tự được xác định khi "trộn", tức là trong khâu tổng hợp lời giải sau khi các bài toán con đã được giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con.
Ngoài ra còn nhiều giải thuật sắp xếp khác, trong đó nhiều giải thuật sắp xếp được cải tiến từ các giải thuật trên. Trong sau giải thuật liệt kê trên, ta thường coi các giải thuật chèn, chọn, nổi bọt là các giải thuật cơ bản, độ phức tạp trong trường hợp trung bình của chúng là O(n2). Ba giải thuật còn lại thường được coi là giải thuật cao cấp, độ phức tạp tính toán trung bình của chúng là n.lnn.

Sắp xếp theo cơ số

Sắp xếp theo cơ số (radix sort) dựa trên tính chất "số" của các khóa. Trong giải thuật sắp xếp theo cơ số, ta không chỉ so sánh giá trị của các khóa, mà so sánh các thành phần của khóa. Giả sử các khóa là các số biểu diễn theo hệ ghi số cơ số M. Khi đó sắp xếp theo cơ số sẽ so sánh từng ký số của nó.
Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ sơ đánh số bởi 3 chữ số thập phân. Đầu tiên ta chia các hồ sơ vào các đống có cùng chữ số *** trăm (đồng thới xếp các đống theo thứ tự của chữ số *** trăm), trong mỗi đống con lại phân chia theo chữ số *** chục, cuối cùng trong mỗi đống có cùng chữ số *** trăm và *** chục, sắp xếp theo thứ tự của chữ số *** đơn vị.
Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc cơ số là lũy thừa của 2 là thuận lợi nhất. Trong trường hợp cơ số 2, việc phân hoạch tương tự như phân hoạch trong Quick Sort, chỉ khác ở chỗ cách chọn phần tử chốtmn

Sắp xếp đếm phân phối

Sắp xếp đếm phân phối là phương pháp sắp xếp có độ phức tạp tuyến tính trong trường hợp các khóa nhận hữu hạn giá trị trong khoảng cho trước. Để đơn giản ta giả sử các phần tử của danh sách a[1..n] nhận các giá trị tự nhiên trong khoảng [1..M].
Sắp xếp đếm phân phối đầu tiên đếm các phần tử thuộc danh sách nhận giá trị k với . Các giá trị đếm được đươc ghi vào mảng Counter[1..M]. Sau đó khi duyệt theo k từ 1 đến M, ta lần lượt xếp Counter[k] phần tử của vào danh sách a[1..n].

* Một số code tham khảo ( Code C++ ):

Phương pháp Quickshort:

1. #include
2. #include
3. #include
4. float a[100];
5. int n;
6. void QuickSort(float a[],int l,int r)
7. {
8.  int i,j;
9.  int x;
10.  i=l;
11.  j=r;
12.  x=a[(l+r)/2];
13.  do
14.   {
15.    while (a[i]< span=""><>
16.    while(a[j]>x)j--;
17.    if(j<=j)
18.     {
19.      if(i< span=""><>
20.       {
21.        int temp=a[i];
22.        a[i]=a[j];
23.        a[j]=temp;
24.       }
25.    i++;
26.    j--;
27.      }
28.    }
29.    while(i< span=""><>
30.    if(l< span=""><>
31.    if(i< span=""><>
32. }
33. void input(float a[],int n)
34. {
35.  int i;
36.  for (i = 1; i <= n; i++)
37.   {
38.    cout<<"a["<<<"]= ";<="" span=""><<"]=>
39.    cin>>a[i];
40.   }
41. }
42. void output(float a[],int n)
43. {
44.   int i;
45.   for (i = 1; i <= n; i++)
46.       cout<<<"  ";<="" span=""><<" >
47. }
48. void main()
49. {
50. cout<<"Nhap n : ";cin>>n;
51.           if(n>0)
52.           {
53.           cout<<"Day ban dau: ";
54.           input(a,n);
55.           cout<< span=""><>
56.           cout<<"\nSap xep theo PP QuickSort:"<< span=""><>
57.           cout<< span=""><>
58.           QuickSort(a,1,n);
59.           output(a,n);
60.           }
61. getch();
62.  }

Phương pháp Bubble sort:

1. #include
2. #include
3. #include
4. float a[100];
5. int n;
6. void BubbleSort(float a[],int n)
7. {
8.  int temp;
9.  for(int i=1;i< span=""><>
10.  for(int j=n;j>i;j--)
11.  if(a[j]< span=""><>
12.   {
13.    temp=a[j];
14.    a[j]=a[j-1];
15.    a[j-1]=temp;
16.   }
17. }
18. void input(float a[],int n)
19. {
20.  int i;
21.  for (i = 1; i <= n; i++)
22.   {
23.    cout<<"a["<<<"]= ";<="" span=""><<"]=>
24.    cin>>a[i];
25.   }
26. }
27. void output(float a[],int n)
28. {
29.   int i;
30.   for (i = 1; i <= n; i++)
31.       cout<<<"  ";<="" span=""><<" >
32. }
33. void main()
34. {
35. cout<<"Nhap n : ";cin>>n;
36.           if(n>0)
37.           {
38.           cout<<"Day ban dau: ";
39.           input(a,n);
40.           cout<< span=""><>
41.           cout<<"\nSap xep theo PP Bubble sort:"<< span=""><>
42.           cout<< span=""><>
43.           BubbleSort(a,n);
44.           output(a,n);
45.           }
46. getch();
47.  }

Phương pháp Insertion sort: 

1. #include
2. #include
3. #include
4. float a[100];
5. int n;
6. void InsertionSort(float a[],int n)
7. {
8. float temp;
9. for(int i=2;i<=n;i++)
10.   {
11.    temp=a[i];
12. int vt=i;
13. while ((a[vt-1]>temp)&&(vt>1))
14.     {
15.   a[vt]=a[vt-1];
16.   vt=vt-1;
17.     }
18. a[vt]=temp;
19.   }
20. }
21. void input(float a[],int n)
22. {
23. int i;
24. for (i = 1; i <= n; i++)
25.   {
26. cout<<"a["<<<"]= ";<="" span=""><<"]=>
27. cin>>a[i];
28.   }
29. }
30. void output(float a[],int n)
31. {
32.   int i;
33.   for (i = 1; i <= n; i++)
34. cout<<<"  ";<="" span=""><<" >
35. }
36. void main()
37. {
38. cout<<"Nhap n : ";cin>>n;
39. if(n>0)
40. {
41. cout<<"Day ban dau: ";
42. input(a,n);
43. cout<< span=""><>
44. cout<<"\nSap xep theo PP insertion sort:"<< span=""><>
45. cout<< span=""><>
46. InsertionSort(a,n);
47. output(a,n);
48. }
49. getch();
50. }

Phương pháp selection sort:

1. #include
2. #include
3. #include
4. float a[100];
5. int n;
6. void SelectionSort(float a[], int n)
7. {
8. int min_pos;
9.     for (int i = 1; i < n; i++) {
10.         min_pos = i+1;
11.         for (int j = i + 2; j < n; j++)
12.             if (a[j] < a[min_pos])
13.                 min_pos = j;
14.                 if (a[min_pos]< span=""><>
15.                 {
16.         int temp = a[i];
17.         a[i] = a[min_pos];
18.         a[min_pos] = temp;
19.         }
20.     }
21. }
22. void input(float a[],int n)
23. {
24. int i;
25. for (i = 1; i <= n; i++)
26.   {
27. cout<<"a["<<<"]= ";<="" span=""><<"]=>
28. cin>>a[i];
29.   }
30. }
31. void output(float a[],int n)
32. {
33.   int i;
34.   for (i = 1; i <= n; i++)
35. cout<<<"  ";<="" span=""><<" >
36. }
37. void main()
38. {
39. cout<<"Nhap n : ";cin>>n;
40. if(n>0)
41. {
42. cout<<"Day ban dau: ";
43. input(a,n);
44. cout<< span=""><>
45. cout<<"\nSap xep theo PP Selection Sort:"<< span=""><>
46. cout<< span=""><>
47. SelectionSort(a,n);
48. output(a,n);
49. }
50. }

Read More...