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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
peace_of_deth
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 11
#1

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

29.03.2013, 12:45. Просмотров 1155. Ответов 12
Метки нет (Все метки)

Переместить 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++
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем...

Ханойская башня - C++
Легенда гласит, что, в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены...

Ханойская башня - C++
23. Написать программу, которая печатает последовательность действий (в виде «перенести диск с q на r», где q и r – это А,В или С),...

Ханойская башня еще раз - C++
Ну ни как не могу понять.Объясните как тут рекурсия работает. #include <iostream> using namespace std; void...

Задача Ханойская башня. Написать порядок действий в графической интерпритации - C++
День добрый! Учусь на 1 курсе ИВТ. Препод по программированию дал для общего развития написать прогу по ханойской башне в консоли. Но нужно...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Van111
кодер с++
208 / 187 / 4
Регистрация: 03.08.2011
Сообщений: 2,597
Записей в блоге: 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
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 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
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 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,597
Записей в блоге: 12
29.03.2013, 14:19     Ханойская башня- тесты #8
Цитата Сообщение от peace_of_deth Посмотреть сообщение
...Выполнить отчет с результатами тестирования.
может вам надо будет определить на сколько допустим за 1000 ходов операция перекладывания дисков завершилась?
Kastaneda
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 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
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 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++
Нужна рабочая программа &quot;Ханойская башня&quot; в консоле: Вводишь количество колец, и выводит все ходы перемещения колец. Если таковой...

Рекурсия (нужны комментарии) "Ханойская башня" - C++
Помогите пожалуйста, обьясните написание программы, какие переменные и зачем используются, буду очень благодарна)) #include &lt;iostream&gt;...

Ханойская башня и "любимая" рекурсия - C++
Здравствуйте. Нашёл здесь на форуме код, для решения данной задачи, но самому мало понятно, что и как, может кто подробно разъяснить? ...

Тесты - C++
1. Функция активизируется с помощью: 1) вызова прототипа 2) вызова функции 3) команды return 4) команды extern 2. Число,...

Тесты - C++
Привет всем к вам просьба кто может вот вопрос 7 Вопрос 7 Когда происходит динамическое связывания ответ а во время...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru