Читайте также:
|
i j
i j i j
4 3 1 6 8 9 7
j i
Пример. Ханойские башни
sour middle dest
Сведем задачу с n дисками к задаче с n – 1 дисками (фактически, применим метод математической индукции по числу дисков). Пусть нам требуется переложить пирамиду из дисков со штыря с номером 1 (sour) на штырь с номером 3 (dest), используя штырь 2(work) в качестве вспомогательного. Для этого необходимо сначала переложить пирамиду из n – 1 диска со штыря 1 на штырь 2, используя штырь 3 в качестве вспомогательного. Затем переместить оставшийся диск со штыря 1 на штырь 3 и, наконец, переложить пирамиду из n – 1 диска со штыря 2 на штырь 3 используя штырь 1 в качестве вспомогательного.
//hanoy.cpp
#include <fstream>
#include <iostream>
Using namespace std;
Ofstream fout;
Int i;
Void Hanoy(int n, int sour, int dest)
{if (n>0)
{int middle=6-sour-dest;
Hanoy(n-1,sour,middle);
i++;
fout<<i<<". disk "<<n<<" "<<sour<<"-->"<<dest<<endl;
Hanoy(n-1,middle,dest);
}
}
Int main ()
{
Int n;
fout.open("rez.txt");
If (fout.fail())
{cout<<"error open file rez.txt "<<endl; return 1;}
cout<<"--> n ";
cin>>n;
fout<<"n="<<n<<endl;
i=0;
Hanoy(n, 1, 3);
Fout.close();
Return 0;
}
Rez.txt
n=5
1. disk 1 1-->3
2. disk 2 1-->2
3. disk 1 3-->2
4. disk 3 1-->3
5. disk 1 2-->1
6. disk 2 2-->3
7. disk 1 1-->3
8. disk 4 1-->2
9. disk 1 3-->2
10. disk 2 3-->1
11. disk 1 2-->1
12. disk 3 3-->2
13. disk 1 1-->3
14. disk 2 1-->2
15. disk 1 3-->2
16. disk 5 1-->3
17. disk 1 2-->1
18. disk 2 2-->3
19. disk 1 1-->3
20. disk 3 2-->1
21. disk 1 3-->2
22. disk 2 3-->1
23. disk 1 2-->1
24. disk 4 2-->3
25. disk 1 1-->3
26. disk 2 1-->2
27. disk 1 3-->2
28. disk 3 1-->3
29. disk 1 2-->1
30. disk 2 2-->3
31. disk 1 1-->3
Дата добавления: 2014-12-20; просмотров: 93 | Поможем написать вашу работу | Нарушение авторских прав |