Алгоритм Towers of Hanoi, ничего не печатая в окне терминала

Типичные решения проблем Ханойской башни:

void hanoi(int diskNumber , int start, int temp, int finish)
{
if(diskNumber == 1)
{
cout<< " Move Disk " << diskNumber<<" from " << start <<" to "<< finish<<endl;
}
else
{
hanoi(diskNumber-1,start,temp,finish);
cout<<"Move Disk from " << start <<" to "<<finish<<endl;
hanoi(diskNumber - 1,temp,start,finish);
}
}

Но я хочу рассчитать время выполнения алгоритма. таким образом:

int main
{
//Hanoi:
cout<<"Hanoi Tower Problem:"<<endl;
//3 Disks:
clock_t htimer3 = clock();
hanoi(3, 1,2,3);
cout<<"CPU Time for n = 3 is: "<<clock() - htimer3/CLOCKS_PER_SEC<<endl;
//6 Disks:
clock_t htimer6 = clock();
hanoi(6, 1,2,3);
cout<<"CPU Time for n = 6 is: "<<clock() - htimer6/CLOCKS_PER_SEC<<endl;
//9 Disks:
clock_t htimer9 = clock();
hanoi(9, 1,2,3);
cout<<"CPU Time for n = 9 is: "<<clock() - htimer9/CLOCKS_PER_SEC<<endl;
//12 Disks:
clock_t htimer12 = clock();
hanoi(12, 1,2,3);
cout<<"CPU Time for n = 12 is: "<<clock() - htimer12/CLOCKS_PER_SEC<<endl;
//15 Disks:
clock_t htimer15 = clock();
hanoi(15, 1,2,3);
cout<<"CPU Time for n = 15 is: "<<clock() - htimer15/CLOCKS_PER_SEC<<endl;
//End of Hanoi Tower Problem
return 0;
}

проблема здесь в том, что, например, если я установлю diskNumber = 15, код будет выполняться 32767 раз, что заполнит окно терминала, и я потеряю сгенерированные строки, которые предшествуют ему (мне нужно вычислить некоторые другие алгоритмы, такие как bubble сортировка, быстрая сортировка и т. д. Я собираюсь использовать числа, чтобы нарисовать диаграмму позже, чтобы представить их Big O, то есть: алгоритм Big O of Towers of Hanoi равен 2 ^ n).
Чтобы решить эту проблему, я изменил код:

void hanoi(int diskSize, int start, int finish, int temp)
{
if(diskSize == 1)
{
return;
}
else
{
hanoi(diskSize - 1, start, temp, finish);
hanoi(diskSize - 1, temp, finish, start);
}
}

Мой главный вопрос: занимает ли модифицированный код такое же время выполнения, как если бы это был оригинальный алгоритм? если нет, что делать? какие-либо предложения?

1

Решение

Да, временная сложность вашего измененного кода такая же, как и предыдущий cout занимает постоянное время. Таким образом, ваше время выполнения не будет сильно затронуто (степень детализации будет порядка наносекунд), учитывая поток, в который вы пишете.

Я бы порекомендовал перенаправить вывод в файл.
Например:

./executable > FileName
0

Другие решения


По вопросам рекламы [email protected]