Жак Арсак - Программирование игр и головоломок

по два раза — шашки от 1 до 10,

один раз — шашки 25, 50, 75, 100.

Затем вы задаете искомое число, скажем n , обязательно трехзначное. Требуется соединить значения шашек между собой с помощью четырех операций: сложения, вычитания, умножения и деления — чтобы получить число n . Не обязательно использовать все 6 шашек.

Если число n получить нельзя, то телевизионная игра допускает и числа, близкие к n , и тот, чье число ближе всего к n , и становится победителем.

Теоретически эта программа не должна быть трудной. Есть ограниченное число возможных комбинаций:

— есть 15 способов взять две шашки среди 6 и, самое большее, 4 способа соединить их между собой, следовательно, самое большое 60 комбинаций с двумя шашками. Но их уже гораздо больше для трех шашек. Испытать все комбинации за разумное время не представляется возможным.

Когда вы излагаете решение, вы берете две шашки из 6, соединяете их между собой одной из четырех операций (на самом деле можно считать, что только тремя, начинать с деления — это исключение). Есть 60 (или, скорее, 45) способов это сделать. После этого задача сводится к задаче с 5 шашками. При таком подходе решение кажется более достижимым.

Следовательно, попробуем. Самые большие упрощения возникают, если вы не ищете для данного числа приближенных значений. Компьютер выводит результат, если он его находит; в противном случае он сообщает, что он решения не нашел. Вы сами можете систематически проводить одну попытку за другой. Пусть p i , p j , p k обозначают три из 6 шашек. Вы можете искать решение в виде

p i * комбинация из 5 оставшихся шашек = n ,

p j + p i * комбинация из 4 оставшихся шашек = n ,

− p j + p i * комбинация из 4 оставшихся шашек = n ,

±( p j ◦ p k ) + p i * комбинация из 3 оставшихся шашек = n ,

где ◦ означает одну из четырех разрешенных операций. Удивительным образом все это очень быстро и очень часто приводит к точному ответу. Никто на запрещает вам попробовать что-то лучшее…

В соответствии с заглавием примера попытайтесь поэтому для 6 шашек 10, 10, 25, 50, 75, 100 найти 370, 369, 368…

В этом разделе я объединил различные задачи, среди которых далеко не все являются головоломками, по той причине, что опыт показывает: средний программист в них достигает цели не бее труда. Для некоторых из них в различных книгах можно найти многочисленные решения, не всегда правильные, или — во всяком случае — не всегда хорошие, или слишком плохо объясненные. Условия этих задач могут показаться мало привлекательными. Но если в программировании вы любите именно трудности, не поддавайтесь первому впечатлению.

* Головоломка 29.Дихотомический поиск.

Это — совершенно известная задача. Вам предлагается упорядоченная таблица попарно различных элементов; например, в порядке возрастания. Вам предлагается, кроме того, другой элемент: его нужно разместить в таблицу.

Следовало бы уточнить (хоть это и не в моих правилах: обычно я предоставляю вам заботу об уточнении. В этой книге вовсе не я тот человек, который должен аккуратно работать…). Пусть a — таблица с n элементами, упорядоченная так, что

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] «Ослиным мостом», дальше которого учащегося сдвинуть трудно, считалась в XII–XIII вв. в Парижском университете либо теорема о равенстве углов при основании равнобедренного треугольника, либо геометрическое доказательство теоремы Пифагора. — Примеч. пер. информатики…

* Головоломка 30.Равенство «с точностью до пробелов».

Пусть даны две буквенные цепочки: a и b . Составьте программу, которая может сказать, совпадают ли эти цепочки с точностью до пробелов. Внимание: вы не имеете права изменять цепочки a и b , вы не имеете права порождать новые цепочки. Это запрещает вам удалить пробелы из обеих цепочек или копировать их, удаляя пробелы. Под равенством с точностью до пробелов нужно понимать, что обе цепочки должны быть образованы одними и теми же буквами в одном и том же порядке, если не учитывать пробелы. Такая задача встречается в системах, связанных с практической работой, с программами, потому что пробелы чаще всего рассматриваются в операторах и командах как незначащие.