Программирование игр и головоломок
Шрифт:
*** Головоломка 28. Песенка спета.
На этот раз дело идет именно об игре Армана Жаммо. Вам надлежит гадать вашему компьютеру шесть шашек, взятых среди 24; а именно, в набор входят:
по два раза — шашки от 1 до 10,
один раз — шашки 25, 50, 75, 100.
Затем вы задаете искомое число, скажем n, обязательно трехзначное. Требуется соединить значения шашек между собой с помощью четырех операций: сложения, вычитания, умножения и деления — чтобы получить число n. Не обязательно использовать все 6 шашек.
Если число n получить нельзя, то телевизионная игра допускает и числа, близкие к n,
Теоретически эта программа не должна быть трудной. Есть ограниченное число возможных комбинаций:
— есть 15 способов взять две шашки среди 6 и, самое большее, 4 способа соединить их между собой, следовательно, самое большое 60 комбинаций с двумя шашками. Но их уже гораздо больше для трех шашек. Испытать все комбинации за разумное время не представляется возможным.
Когда вы излагаете решение, вы берете две шашки из 6, соединяете их между собой одной из четырех операций (на самом деле можно считать, что только тремя, начинать с деления — это исключение). Есть 60 (или, скорее, 45) способов это сделать. После этого задача сводится к задаче с 5 шашками. При таком подходе решение кажется более достижимым.
Следовательно, попробуем. Самые большие упрощения возникают, если вы не ищете для данного числа приближенных значений. Компьютер выводит результат, если он его находит; в противном случае он сообщает, что он решения не нашел. Вы сами можете систематически проводить одну попытку за другой. Пусть pi, pj, pk обозначают три из 6 шашек. Вы можете искать решение в виде
pi * комбинация из 5 оставшихся шашек = n,
pj + pi * комбинация из 4 оставшихся шашек = n,
– pj + pi * комбинация из 4 оставшихся шашек = n,
±(pj o pk) + pi * комбинация из 3 оставшихся шашек = n,
где o означает одну из четырех разрешенных операций. Удивительным образом все это очень быстро и очень часто приводит к точному ответу. Никто на запрещает вам попробовать что-то лучшее…
В соответствии с заглавием примера попытайтесь поэтому для 6 шашек 10, 10, 25, 50, 75, 100 найти 370, 369, 368…
7. Обо всем понемногу
В этом разделе я объединил различные задачи, среди которых далеко не все являются головоломками, по той причине, что опыт показывает: средний программист в них достигает цели не бее труда. Для некоторых из них в различных книгах можно найти многочисленные решения, не всегда правильные, или — во всяком случае — не всегда хорошие, или слишком плохо объясненные. Условия этих задач могут показаться мало привлекательными. Но если в программировании вы любите именно трудности, не поддавайтесь первому впечатлению.
* Головоломка 29. Дихотомический поиск.
Это — совершенно известная задача. Вам предлагается упорядоченная таблица попарно различных элементов; например, в порядке возрастания. Вам предлагается, кроме того, другой элемент: его нужно разместить в таблицу.
Следовало бы уточнить (хоть это и не в моих правилах: обычно я предоставляю вам заботу об уточнении. В этой книге вовсе не
a[i] < a[i + 1] для 1 < i <= n,
и x — элемент, который нужно разместить. Его место
0, если x <= a[1],
i, если a[i] < x <= a[i + 1],
n, если a[n] < x.
Один сотрудник факультета Нотр-Дам де ла Пэ в Намюре изучил 18 программ, опубликованных различными авторами по всему свету и в каждой нашел хоть что-то, за что можно упрекнуть. Всякий раз, когда я получаю новую книгу по программированию (к счастью, я получаю не все), я смотрю, нет ли там случайно исследования этой задачи. Почти во всех случаях это так. Настоящий «ослиный мост» [16] информатики…
* Головоломка 30. Равенство «с точностью до пробелов».
16
«Ослиным мостом», дальше которого учащегося сдвинуть трудно, считалась в XII–XIII вв. в Парижском университете либо теорема о равенстве углов при основании равнобедренного треугольника, либо геометрическое доказательство теоремы Пифагора. — Примеч. пер.
Пусть даны две буквенные цепочки: a и b. Составьте программу, которая может сказать, совпадают ли эти цепочки с точностью до пробелов. Внимание: вы не имеете права изменять цепочки a и b, вы не имеете права порождать новые цепочки. Это запрещает вам удалить пробелы из обеих цепочек или копировать их, удаляя пробелы. Под равенством с точностью до пробелов нужно понимать, что обе цепочки должны быть образованы одними и теми же буквами в одном и том же порядке, если не учитывать пробелы. Такая задача встречается в системах, связанных с практической работой, с программами, потому что пробелы чаще всего рассматриваются в операторах и командах как незначащие.
Если вы находите это совершенно элементарным, вы можете изучить, являются ли данные цепочки обращениями друг друга с точностью до пробелов. Вы можете также увидеть, является ли цепочка палиндромом (т. е. совпадает со своим обращением) с точностью до пробелов, Так, палиндромами являются
А РОЗА УПАЛА НА ЛАПУ АЗОРА
АРГЕНТИНА МАНИТ НЕГРА
Попытайтесь получить правильную (это уж как минимум) и элегантную программу.
Головоломка 31. Анаграмма.
Еще одна головоломка, вопреки ее внешнему виду, Дело в том, чтобы сказать, являются ли две цепочки букв анаграммами друг друга (т. е. получаются ли они друг из друга перестановками букв). Эта задача имеет совершенно различный вид в зависимости от того, разрешите ли вы себе изменять обе цепочки или порождать новые цепочки, или нет. Выбор я предоставляю вам… Может быть, вы заметите, что различные решения следует оценивать в зависимости от соотношения между размерами цепочек и используемого алфавита. Подумайте о крайних случаях: алфавит из 26 букв и цепочка из 1000 символов; алфавит из 1000 символов (это вроде китайского…) и цепочка из 10 символов.