Форум программистов, компьютерный форум CyberForum.ru

Ханойская башня- тесты - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
29.03.2013, 12:45     Ханойская башня- тесты #1
Переместить m дисков с одного из трех стержней на другой, соблюдая:
1) диски можно перемещать с одного стержня на другой только по одному;
2) нельзя класть больший диск на меньший.
Вход: текстовый файл, в котором записано число m.
Выход: текстовый файл, описывающий перемещения дисков.
Пример: in.txt: 2; out.txt: 1->2; 1->3; 2->3
Тестирование: протестировать программу на следующих данных
m 100 300 1000 10000 1000000
...Выполнить отчет с результатами тестирования.
Вообщем задача решена рекурсией и не составляет особой сложности, но тестирование, я с этим никогда не имел дело, мне нужно знать QA? Да и потом что тестировать, если изменяется только количество дисков, т.е. количество операций. ну и на последок количество операций расчитывается по формуле (2 в степени m )-1, т.е. уже для m=100 это уже будет 1 267 650 600 228 229 401 496 703 205 376 операций, если принимать во внимание, что 1 символ занимает 1 байт, то как вообще я должен провести хоть какое-то тестирование, если мне нужно будет только заполнять "пол года" этот файл... Вообщем я в растерянности.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2013, 12:45     Ханойская башня- тесты
Посмотрите здесь:

C++ Ханойская башня
Ханойская башня C++
C++ Ханойская башня
Ханойская башня еще раз C++
Ханойская башня C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Van111
кодер с++
208 / 187 / 4
Регистрация: 03.08.2011
Сообщений: 2,585
Записей в блоге: 12
29.03.2013, 13:44     Ханойская башня- тесты #2
peace_of_deth, полагаю вам нужно будет вывести количество операций для
Цитата Сообщение от peace_of_deth Посмотреть сообщение
m 100 300 1000 10000 1000000
и тут у вас загвоздка с большими числами. следовательно или создайте свой класс для работы с числами неограниченной длины ,либо используйте существующий.
так, как у вас будет только операция возведения в степень у вас не будет натуги с умножением или тому подобному, можете просто сделать большую битовую последовательность поставить в неё 1(bin) и начать толкать <<2 потом сделаете перевод в десятичную и отнимите один
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
29.03.2013, 13:52  [ТС]     Ханойская башня- тесты #3
Цитата Сообщение от Van111 Посмотреть сообщение
peace_of_deth, полагаю вам нужно будет вывести количество операций для

и тут у вас загвоздка с большими числами. следовательно или создайте свой класс для работы с числами неограниченной длины ,либо используйте существующий.
так, как у вас будет только операция возведения в степень у вас не будет натуги с умножением или тому подобному, можете просто сделать большую битовую последовательность поставить в неё 1(bin) и начать толкать <<2 потом сделаете перевод в десятичную и отнимите один
Вы немного не поняли нет проблемы с большими числами, проблема в том что в текстовый документ будет при каждой операции добавляться запись типа "1->2" и поэтому во первых файл будет очень много весить, а во вторых даже без операций записи это будет длиться ну очень долго.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
29.03.2013, 13:57     Ханойская башня- тесты #4
Думаю имелось ввиду как раз выполнить программу на этих данных. Хз, может задания составляли недумая.
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
29.03.2013, 14:01  [ТС]     Ханойская башня- тесты #5
Цитата Сообщение от Kastaneda Посмотреть сообщение
Думаю имелось ввиду как раз выполнить программу на этих данных. Хз, может задания составляли недумая.
Тестовое задание от работадателя. Сам алгоритм не составляет проблемы, составляет проблему длительность работы такой программы, неимоверный размеров файла и что собственно тестировать. если скорость и качество программы не будет зависеть от m.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
29.03.2013, 14:06     Ханойская башня- тесты #6
Цитата Сообщение от peace_of_deth Посмотреть сообщение
Тестовое задание от работадателя.
А, я думал задание для учебы. Тогда врядли тут ошибка, может нужно составить какой-то сверхбыстрый алгоритм для таких данных, хз, сложно сказать. Некоторые задания даются специально недосказаными, чтоб кандитат вопросы задавал. Только по вопросам уже можно определить уровень кандидата.
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
29.03.2013, 14:10  [ТС]     Ханойская башня- тесты #7
Цитата Сообщение от Kastaneda Посмотреть сообщение
А, я думал задание для учебы. Тогда врядли тут ошибка, может нужно составить какой-то сверхбыстрый алгоритм для таких данных, хз, сложно сказать. Некоторые задания даются специально недосказаными, чтоб кандитат вопросы задавал. Только по вопросам уже можно определить уровень кандидата.
В этом-то и соль, сами операции ввода/вывода не имеет смысла делать даже inline ф-циями, потому что они требуют большого затрата ресурсов времени. Так что любой самый быстрый алгоритм загрузнет на этом. Может я не знаю каких-то хитростей потому что мне задание абсурдным кажется, поэтому и сюда написал.
Van111
кодер с++
208 / 187 / 4
Регистрация: 03.08.2011
Сообщений: 2,585
Записей в блоге: 12
29.03.2013, 14:19     Ханойская башня- тесты #8
Цитата Сообщение от peace_of_deth Посмотреть сообщение
...Выполнить отчет с результатами тестирования.
может вам надо будет определить на сколько допустим за 1000 ходов операция перекладывания дисков завершилась?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
29.03.2013, 14:23     Ханойская башня- тесты #9
Я бы на твоем месте, если бы больше ничего не придумал, то сделал бы так - если на входе большое число, то выводить сообщение типа "Вычисление займет очень много времени, вы уверены, что хотите продолжить?" Ну и можно еще сделать функцию, которая будет вычислять примерное вермя расчета, чтоб вместо "очень много" выводить примерное время.
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
29.03.2013, 14:27  [ТС]     Ханойская башня- тесты #10
Тут можно на калькуляторе подсчитать, не думаю. Тестирование проводится с разным количеством дисков, 100 дисков ужасает, там в теме написано сколько операций, а что говорить о 10 000 дисках..в этом мне и кажется абсурд всего.

Добавлено через 3 минуты
Цитата Сообщение от Kastaneda Посмотреть сообщение
Я бы на твоем месте, если бы больше ничего не придумал, то сделал бы так - если на входе большое число, то выводить сообщение типа "Вычисление займет очень много времени, вы уверены, что хотите продолжить?" Ну и можно еще сделать функцию, которая будет вычислять примерное вермя расчета, чтоб вместо "очень много" выводить примерное время.
Да, возможно время и стоит подсчитать, сколько осталось до... Но зачем в файл это всё скидывать, пока место на жёстком не закончится? Да и потом, если ф-ция будет выводить время всех операций это бдет считаться как тест? Я просто не знаю как проводится тестирование.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
29.03.2013, 14:29     Ханойская башня- тесты #11
Цитата Сообщение от peace_of_deth Посмотреть сообщение
Я просто не знаю как проводится тестирование.
Я думаю в задании под словом "тестирование" подразумевалось просто проверка работоспособности программы с определенными входными данными.
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
29.03.2013, 15:45  [ТС]     Ханойская башня- тесты #12
Ну тогда проблемы нет 100 000 не такое большое число, чтобы оно куда-то не помещалось да и ничего не кешируется чтобы память забирать. Вообщем вопрос на дороботке, я переспрашиваю что тут имеется ввиду, как скоро отвятят знать не могу. Всем спасибо за дискуссию на этом этапе.

Добавлено через 35 минут
Получен ответ, не знаю как для кого, а для меня он стал неожиданным, читаем:
При больших наборах данных под прохождением теста понимается, что
программа запустилась и начала записывать правильные результаты в файл.
После принудительной остановки программы первые 100 записей в файле
сверяются с эталонными и делаются выводы.
Вопрос снят
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.03.2013, 16:33     Ханойская башня- тесты
Еще ссылки по теме:

C++ Ханойская башня
Задача Ханойская башня. Написать порядок действий в графической интерпритации C++
Нужна рабочая программа "Ханойская башня" в консоли C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
29.03.2013, 16:33     Ханойская башня- тесты #13
Цитата Сообщение от peace_of_deth Посмотреть сообщение
При больших наборах данных под прохождением теста понимается, что
программа запустилась и начала записывать правильные результаты в файл.
После принудительной остановки программы первые 100 записей в файле
сверяются с эталонными и делаются выводы.
Ну да, неожиданно. Я бы даже сказал нелогично исходя из первоначальной постановки задачи.
Yandex
Объявления
29.03.2013, 16:33     Ханойская башня- тесты
Ответ Создать тему
Опции темы

Текущее время: 17:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru