Ханойская башня количество комбинаций?
Недавно я проходил собеседование по позиции C ++ Develpoer, и меня попросили написать программу, которая решает головоломку Ханойской башни с 3 колонками и 1000000 дисками, программа должна записать вывод ходов на диск («1-> 3», «1-> 2», … и т. Д.), Я сказал им, что это будет очень большой файл для решения, потому что минимальное количество ходов для Ханойской башни равно 2 степени n — 1, а для 1000000 это будет очень большое число, которое не подходит ни к одному жесткому диску, говорят, что классический алгоритм неверен, и есть алгоритм, который решает эту загадку даже для 1000000 дисков с лихорадочными движениями. Я хочу знать, существует ли такой алгоритм или они просто лгут мне?
Спасибо, Тимур.
Решение
Выходные данные действительно будут слишком большими (экспоненциальный размер входных данных, как вы сказали), но алгоритм довольно прост для записи рекурсивным способом. Возможно, это то, что они имели в виду.
Я мог бы предоставить алгоритм, если хотите.
РЕДАКТИРОВАТЬ: просто ради полноты я бы предоставить алгоритм (его на Python, но реализация в C ++ будет в значительной степени то же самое):
n = 3
# using 4 elements just so we're 1-based with three towers
towers = [ [], range(n, 0, -1), [], [] ]
def move (orig, dest, n):
if n == 1:
elem = towers[orig].pop()
print 'moving %d from %d to %d' % (elem, orig, dest)
towers[dest].append(elem)
else:
through = dest ^ orig
move(orig, through, n-1)
move(orig, dest, 1)
move(through, dest, n-1)
move(1, 3, n)
Другие решения
Вот код, который я обещал для nhahtdh.
#include <iostream>
#include <conio.h>
#include <math.h>
#include <iomanip>
using namespace std;
char disc[2000000]={0};
int n;
bool validate(int num,int target){
int t=num+1;
while(t<n){
if ((disc[num]==disc[t])||(disc[t]==target))return false;
t++;
};
return true;
};
int main()
{
__int64 k=0;
cout<<"Enter number of discs:";cin>>n;
cout<<"This would be a "<<setprecision(1000)<<pow(2,n)-1<<" combinations !"<<endl;
cout<<"To START press a key!"<<endl;
_getch();
int num=0,cur=0,t=0,nn=0;
while(num<n){
t=2;nn=num;
while(nn<n){
if(disc[nn]==t){nn++;continue;}
if(validate(nn,t)){
if(nn==num)num++;
k++;cout<<disc[nn]+1<<"->"<<t+1<<":"<<k<<" move"<<endl;
disc[nn]=t;
nn++;
continue;
}
if((disc[nn]==0)&&(t==2)){nn++;t=1;continue;}
if((disc[nn]==0)&&(t==1)){nn++;t=2;continue;}
if((disc[nn]==1)&&(t==2)){nn++;t=0;continue;}
if((disc[nn]==1)&&(t==0)){nn++;t=2;continue;}
if((disc[nn]==2)&&(t==1)){nn++;t=0;continue;}
if((disc[nn]==2)&&(t==0)){nn++;t=1;continue;}
};
};
return 0;
}
Я надеюсь, что вы можете понять, но если нет, напишите мне по электронной почте [email protected], я могу объяснить более подробно.