2015-10-22
491
Вспомним, что четвертый шаг анализа решения задач Пойа включает в себя оценку точности работы программы (verification) и ее возможностей как инструмента для решения других задач. Важность первой части этого шага подтверждается при решении следующей задачи:
У путешественника есть золотая цепь, состоящая из семи колец. Он должен остановиться в гостинице на семь дней. Плата за сутки равна одному кольцу цепочки. Каково наименьшее число колец, которые нужно разрезать, чтобы платить за гостиницу по одному кольцу каждое утро, не платя за ночлег заранее?
Прежде всего, можно догадаться, что разрезать нужно не каждое кольцо цепочки. Если мы разрежем только второе кольцо, то освободятся и первое и второе. Следовательно, нужно разрезать только второе, четвертое и шестое кольцо, в результате чего освободятся все кольца (рис. 4.14). Более того, уменьшение числа разрезанных колец приводит к тому, что какие-либо два кольца остаются соединенными. Поэтому можно сделать вывод, что ответом нашей задачи является «три».
