THINK
LIKE
A PROGRAMMER
AN INTRODUCTION TO CREATIVE PROBLEM SOLVING
АНТОН СПРОЛ
ДУМАЙ
КАК
ПРОГРАММИСТ
КРЕАТИВНЫЙ ПОДХОД К СОЗДАНИЮ КОДА
004.4
32.973.26-018
74
V. Anton Spraul
THINK LIKE A PROGRAMMER
Copyright 2012 by V. Anton Spraul. Title of English-language original: Think Like
a Programmer, ISBN 978-1-59327-424-5, published by No Starch Press. Russian-language
edition copyright 2018 by EKSMO Publishing House. All rights reserved.
Âñå ïðàâà çàùèùåíû. Êíèãà èëè ëþáàÿ åå ÷àñòü íå ìîæåò áûòü ñêîïèðîâàíà, âîñïðîèçâåäåíà â
ýëåêòðîííîé èëè ìåõàíè÷åñêîé ôîðìå, â âèäå ôîòîêîïèè, çàïèñè â ïàìÿòü ÝÂÌ, ðåïðîäóêöèè
èëè êàêèì-ëèáî èíûì ñïîñîáîì, à òàêæå èñïîëüçîâàíà â ëþáîé èíôîðìàöèîííîé ñèñòåìå áåç
ïîëó÷åíèÿ ðàçðåøåíèÿ îò èçäàòåëÿ. Êîïèðîâàíèå, âîñïðîèçâåäåíèå è èíîå èñïîëüçîâàíèå
êíèãè èëè åå ÷àñòè áåç ñîãëàñèÿ èçäàòåëÿ ÿâëÿåòñÿ íåçàêîííûì è âëå÷åò óãîëîâíóþ,
àäìèíèñòðàòèâíóþ è ãðàæäàíñêóþ îòâåòñòâåííîñòü.
Íàó÷íî-ïîïóëÿðíîå èçäàíèå
ÌÈÐÎÂÎÉ ÊÎÌÏÜÞÒÅÐÍÛÉ ÁÅÑÒÑÅËËÅÐ
Àíòîí Ñïðîë
ÄÓÌÀÉ ÊÀÊ ÏÐÎÃÐÀÌÌÈÑÒ
ÊÐÅÀÒÈÂÍÛÉ ÏÎÄÕÎÄ Ê ÑÎÇÄÀÍÈÞ ÊÎÄÀ
C++ ÂÅÐÑÈß
Äèðåêòîð ðåäàêöèè Å. Êàïü¸â. Îòâåòñòâåííûé ðåäàêòîð Å. Èñòîìèíà
Ìëàäøèé ðåäàêòîð Å. Ìèíèíà. Õóäîæåñòâåííûé ðåäàêòîð À. Ãóñåâ
ООО «Издательство «Эксмо»
123308, Москва, ул. Зорге, д. 1. Тел.: 8 (495) 411-68-86.
Home page: www.eksmo.ru E-mail: info@eksmo.ru
ндіруші: «ЭКСМО» А*Б Баспасы, 123308, М7скеу, Ресей, Зорге к;шесі, 1 right == NULL && root->left == NULL)
return root->data;
Z int leftMax = maxValue(root->left);
[ int rightMax = maxValue(root->right);
\ int maxNum = root->data;
if (leftMax > maxNum) maxNum = leftMax;
if (rightMax > maxNum) maxNum = rightMax;
return maxNum;
}
Обратите внимание на то, что минимальное дерево для этой задачи представляет собой единственный узел Y (хотя случай с пустым
деревом учитывается по соображениям безопасности X). Это связано с тем, что на вопрос, который мы задаем, можно дать осмысленный ответ с помощью минимум одного значения. Рассмотрим практическую проблему, когда базовым случаем является пустое дерево.
Какое значение мы могли бы вернуть? Если мы возвращаем ноль, мы
неявно требуем наличия в этом дереве нескольких положительных
значений; если все значения в дереве отрицательные, то ноль будет
ошибочно возвращен как наибольшее значение в дереве. Мы могли бы решить эту проблему, возвращая наименьшее (самое отрицательное) целое число, но в этом случае нам бы пришлось осторожно
адаптировать код для других числовых типов. Сделав базовым случаем единственный узел, мы полностью избегаем необходимости принятия этого решения.
Остальная часть кода проста. Мы используем рекурсию для нахождения максимальных значений в левом Z и правом поддере-
194
Глава 6
вьях [. Затем мы находим наибольшее из трех значений (значение
в корневом узле, наибольшее значение в левом поддереве, наибольшее значение в правом поддереве), используя вариант алгоритма
«Царь горы», который мы использовали на протяжении всей этой
книги \.
Функции-обертки
В предыдущих примерах в этой главе мы обсуждали только саму рекурсивную функцию. Однако в некоторых случаях эту рекурсивную
функцию требуется «настраивать» с помощью второй функции.
Чаще всего это происходит, когда мы пишем рекурсивные функции
внутри структур классов. Это может привести к несоответствию
между параметрами, необходимыми для рекурсивной функции, и параметрами, необходимыми для общедоступного метода класса. Поскольку классы обычно обеспечивают сокрытие информации, код
клиента класса может не иметь доступа к данным или типам, который требуется рекурсивной функции. Эта проблема и ее решение
показаны в следующем примере.
:
9
"
Для класса, реализующего двоичное дерево, добавьте общедоступный метод, который возвращает количество листьев (узлов без дочерних элементов) в дереве. Подсчет
листьев должен выполняться с использованием рекурсии.
Давайте обрисуем схему того, как мог бы выглядеть этот класс,
прежде чем мы попытаемся реализовать решение этой задачи. Для
простоты мы будем включать только соответствующие части класса,
игнорируя конструкторы, деструктор и даже методы, которые позволили бы нам построить дерево, чтобы сосредоточиться на нашем
рекурсивном методе.
class binaryTree {
public:
X int leafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
};
Обратите внимание на то, что наша функция для подсчета листьев не принимает параметров X. С точки зрения интерфейса это
корректно. Рассмотрим образец вызова для ранее построенного
объекта binaryTree bt:
Решение задач с помощью рекурсии
195
int numLeaves = bt.leafCount();
В конце концов, если мы спрашиваем у дерева, сколько у него листьев, то какую информацию мы могли бы предоставить этому объекту, которую он еще о себе не знает? Так же, как это является правильным для интерфейса, это не является правильным для рекурсивной
реализации. Если не существует параметра, что же меняется от одного рекурсивного вызова к другому? В этом случае ничто не может измениться, кроме как благодаря глобальным переменным, использования которых, как говорилось ранее, следует избегать. Если ничего
не изменяется, то для прогресса или прекращения рекурсии нет возможности.
Чтобы обойти эту проблему, нужно сначала написать рекурсивную функцию, концептуализируя ее как функцию вне класса. Другими словами, мы напишем эту функцию для подсчета листьев в
двоичном дереве в том же стиле, который мы использовали при написании функции для нахождения наибольшего значения в двоичном дереве. Единственным параметром, который нам необходимо
передать, является указатель на нашу структуру узла.
Это дает нам еще одну возможность использовать БРИ. В чем заключается вопрос Q в данном случае? Сколько листьев в дереве? Применение общего плана рекурсивной обработки двоичных деревьев к
этой конкретной задаче приводит к следующей последовательности
шагов.
1.
Если корень дерева не имеет дочерних элементов, то дерево
имеет только один узел. Этот узел является листом по определению, поэтому возвратите 1. В противном случае...
2.
Сделайте рекурсивный вызов для подсчета листьев в левом поддереве.
3.
Сделайте рекурсивный вызов для подсчета листьев в правом поддереве.
4.
В данном случае нет необходимости проверять корневой узел,
поскольку, если мы добрались до этого этапа, значит, корневой
узел не может быть листом. Поэтому...
5.
Возвратите сумму значений, полученных на этапах 2 и 3.
Переведя этот план в код, мы получим следующее:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
int leafCount(treePtr rootPtr) {
if (rootPtr == NULL) return 0;
if (rootPtr->right == NULL && rootPtr->left == NULL)
return 1;
int leftCount = leafCount(rootPtr->left);
196
Глава 6
int rightCount = leafCount(rootPtr->right);
return leftCount + rightCount;
}
Как вы можете видеть, код представляет собой прямой перевод плана. Вопрос в том, как мы переходим от этой независимой функции к
тому, что мы можем использовать в классе? Именно здесь неосторожный программист может легко попасть в неприятности, посчитав, что
нам нужно использовать глобальную переменную или сделать корневой
указатель общедоступным. Нам не нужно этого делать; мы можем оставить все внутри класса. Трюк заключается в использовании функцииобертки. Сначала мы помещаем независимую функцию с параметром
treePtr в приватный раздел нашего класса. Затем мы пишем публичную
функцию, которая будет служить «функцией-оберткой» для приватной
функции. Поскольку публичная функция имеет доступ к приватному
элементу данных _root, она может передать его рекурсивной функции,
а затем возвратить клиенту результаты следующим образом:
class binaryTree {
public:
int publicLeafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
int privateLeafCount(treePtr rootPtr);
};
X int binaryTree::privateLeafCount(treePtr rootPtr) {
if (rootPtr == NULL) return 0;
if (rootPtr->right == NULL && rootPtr->left == NULL)
return 1;
int leftCount = privateLeafCount(rootPtr->left);
int rightCount = privateLeafCount(rootPtr->right);
return leftCount + rightCount;
}
Y int binaryTree::publicLeafCount() {
Z return privateLeafCount(_root);
}
Несмотря на то, что язык C++ позволяет обеим функциям иметь
одно и то же имя, для ясности я использовал разные имена, чтобы различать публичную и приватную функции для «подсчета листьев». Код
в функции privateLeafCount X точно повторяет код в нашей предыдущей, независимой функции leafCount. Функция-обертка publicLeafCount Y проста. Она вызывает функцию privateLeafCount, передавая
приватный элемент данных _root, и возвращает результат Z. По сути,
она стимулирует рекурсивный процесс. Функции-обертки очень полезны при написании рекурсивных функций внутри классов, однако
их можно использовать в любое время при несоответствии между списком параметров, которые требуются функции, и желаемым списком
параметров вызывающей функции.
Решение задач с помощью рекурсии
197
В каких случаях использовать рекурсию
Начинающие программисты часто задаются вопросом, зачем использовать рекурсию. Возможно, они уже узнали, что любую программу можно создать, используя базовые управляющие структуры,
такие как выбор (утверждения if) и итерация (циклы for и while).
Если рекурсию использовать труднее, чем базовые управляющие
структуры, и она не является необходимой, возможно, ее следует
просто игнорировать.
На этого существует несколько возражений. Во-первых, рекурсивное программирование помогает программистам думать рекурсивно,
а рекурсивное мышление применяется повсюду в мире информатики
в таких областях, как проектирование компилятора. Во-вторых, некоторые языки просто требуют использования рекурсии, поскольку
в них отсутствуют некоторые элементарные управляющие структуры.
Чистые версии языка Lisp, например, требуют рекурсии почти в каждой нетривиальной функции.
Тем не менее остается вопрос: если программист изучил рекурсию
достаточно для того, чтобы ее понять, и использует такой полнофункциональный язык, как C++, Java или Python, следует ли ему применять
рекурсию? Имеет ли рекурсия практическую ценность в таких языках,
или это просто упражнение для ума?
Аргументы против рекурсии
Чтобы изучить этот вопрос, давайте перечислим недостатки рекурсии.
Концептуальная сложность
В большинстве случаев среднему программисту бывает сложнее
решить задачу с помощью рекурсии. Даже если вы понимаете
Большую Рекурсивную Идею, в большинстве ситуаций будет проще написать код с использованием циклов.
Производительность
Вызовы функций очень требовательны к ресурсам компьютера.
Рекурсия предусматривает множество вызовов функций и, следовательно, может приводить к замедлению работы системы.
Требования к пространству
Рекурсия не просто предусматривает много вызовов функций;
она также вкладывает их один в другой. То есть в итоге вы можете получить длинную цепочку вызовов функций, ожидающих
завершения других вызовов. Каждый вызов функции, который
начался, но еще не закончился, занимает дополнительное пространство в системном стеке.
На первый взгляд этот список свойств представляет собой сильное обвинение против рекурсии, характеризуя ее как сложный, медленный и требовательный к пространству метод. Тем не менее эти
аргументы работают не во всех случаях. Поэтому самым базовым
198
Глава 6
правилом для выбора между рекурсией и итерацией является следующее: выбирайте рекурсию, когда эти аргументы не работают.
Рассмотрим нашу функцию, которая подсчитывает количество
листьев в двоичном дереве. Как бы вы решили эту задачу без рекурсии? Это возможно, но вам бы понадобился явный механизм для поддержания «тропы из хлебных крошек» для обозначения узлов, дочерние элементы которых в левом поддереве уже были посещены,
а в правом — нет. К этим узлам пришлось бы вернуться в какой-то
момент, чтобы иметь возможность посетить дочерние элементы в
правом поддереве. Вы могли бы хранить эти узлы в такой динамической структуре, как стек. Для сравнения далее приведена реализация
функции, которая использует класс stack из стандартной библиотеки шаблонов C++:
int binaryTree::stackBasedCountLeaves() {
if (_root == NULL) return 0;
int leafCount = 0;
Xstack< YbinaryTreeNode *> nodes;
Znodes.push(_root);
while ([!nodes.empty()) {
treePtr currentNode = \nodes.top();
]nodes.pop();
if (currentNode->left == NULL && currentNode->right == NULL)
leafCount++;
else {
if (currentNode->right != NULL) wnodes.push(currentNode->right);
if (currentNode->left != NULL) wnodes.push(currentNode->left);
}
}
return leafCount;
}
Этот код следует той же схеме, что и оригинал, однако, если
вы никогда раньше не использовали класс stack, здесь будут уместны некоторые комментарии. Класс stack работает как системный
стек, который мы обсуждали в главе 3; вы можете добавлять и удалять элементы только на вершине. Обратите внимание на то, что
мы могли бы выполнить операцию подсчета листьев, используя любую структуру данных, которая не имеет фиксированного размера.
Например, мы могли бы использовать вектор, однако использование стека лучше всего отражает исходный код. Когда мы объявляем стек X, то указываем тип элементов, которые собираемся в нем
хранить. В данном случае мы будем хранить указатели на структуру
binaryTreeNode Y. В этом коде мы будем использовать четыре метода класса stack. Метод push Z помещает элемент (в данном случае
указатель на узел) на вершину стека. Метод empty [ говорит нам,
остались ли в стеке какие-либо элементы. Метод top \ предоставляет нам копию элемента на вершине стека, а метод pop ] удаляет
верхний элемент из стека.
Данный код решает задачу, помещая на стек указатель на первый узел, а затем последовательно удаляя из стека указатель на узел,
Решение задач с помощью рекурсии
199
проверяя, является ли он листом, увеличивая счетчик на 1, если это
так, и помещая на стек указатели на дочерние узлы, если они существуют. Таким образом, стек отслеживает узлы, которые мы обнаружили, но еще не обработали, так же, как цепочка рекурсивных вызовов в рекурсивной версии отслеживает узлы, которые мы должны
повторно посетить. Сравнивая эту итеративную версию с рекурсивной, мы видим, что ни одно из стандартных возражений против рекурсии не имеет в данном случае достаточной силы. Во-первых, этот
код длиннее и сложнее, чем его рекурсивная версия, поэтому против рекурсивной версии нельзя выдвинуть аргумент, связанный с
концептуальной сложностью. Во-вторых, посмотрите, сколько вызовов функций совершает stackBasedCountLeaves — на каждое посещение внутреннего узла (то есть узла, который не является листом)
эта функция совершает до пяти вызовов функций: по одному для методов empty, top и pop и один или два для метода push. Рекурсивная
версия совершает только два рекурсивных вызова для каждого внутреннего узла. (Обратите внимание на то, что мы можем избежать
вызовов функцией объекта стека, включив в функцию логику стека.
Однако это еще больше увеличит сложность функции.) В-третьих,
хотя эта итеративная версия не использует дополнительное пространство системного стека, она явно использует приватный стек.
Справедливости ради следует сказать, что при этом расход пространства меньше, чем расход пространства системного стека при рекурсивных вызовах, однако это по-прежнему расходование системной
памяти, пропорциональное максимальной глубине двоичного дерева, которое мы обходим.
Поскольку в данной ситуации возражения против рекурсии
смягчаются или сводятся к минимуму, рекурсия — хороший выбор для решения этой задачи. В общем случае, если задачу легко
решить итеративно, то итерация должна быть вашим первым выбором. Рекурсию следует использовать, когда решение с помощью
итерации представляется сложным. Часто это требует использования описанного здесь механизма создания «тропы из хлебных крошек». Обход ветвящихся структур, таких как деревья и графы, по
своей сути рекурсивен. Обработка линейных структур, таких как
массивы и связные списки, обычно не требует рекурсии, однако существуют исключения. Вы никогда не ошибетесь, если начнете решать задачу с помощью итерации и посмотрите, как далеко вас это
заведет. В качестве последних примеров рассмотрим следующие задачи со связными списками.
:
D "
""
Напишите функцию, которой передается указатель на головной элемент односвязного
списка, где типом данных каждого узла является целое число, и которая отображает
эти целые числа по одному на строке в порядке их следования в списке.
200
Глава 6
:
D "
"
Напишите функцию, которой передается указатель на головной элемент односвязного
списка, где типом данных каждого узла является целое число, и которая отображает эти
целые числа по одному на строке в порядке, обратном порядку их следования в списке.
Поскольку эти задачи являются зеркальными версиями друг
друга, естественно предположить, что их решения также будут зеркальными. Это действительно так в случае рекурсивных реализаций. Далее приведены рекурсивные функции для решения обеих
этих задач с использованием приведенных ранее типов listNode и
listPtr:
void displayListForwardsRecursion(listPtr head) {
if (head != NULL) {
X cout data next);
}
}
void displayListBackwardsRecursion(listPtr head) {
if (head != NULL) {
Z displayListBackwardsRecursion(head->next);
[ cout data next)
cout data next)
nodes.push(current);
[ while (!nodes.empty()) {
\ nodePtr current = nodes.top();
] nodes.pop();
^ cout data 0) {
total += array[i];
positiveCount++;
}
}
X return total / (double) positiveCount;
}
Думайте как программист
235
На первый взгляд эта функция выглядит нормально, но при ближайшем рассмотрении в ней обнаруживается проблема. Если в этом
массиве нет положительных чисел, тогда значение переменной positiveCount будет равно нулю, когда цикл завершится, и это приведет
к делению на ноль в конце функции X. Поскольку это деление с плавающей точкой, в программе может произойти не сбой, а скорее она
продемонстрирует странное поведение в зависимости от того, как
значение этой функции используется всей программой.
Если вы хотите быстро запустить свой код, то, обнаружив эту
проблему, можете добавить код для обработки случая, когда значение переменной positiveCount равно нулю, и двигаться дальше. Но
если вы хотите расти как программист, вы должны спросить себя,
какую ошибку вы совершили. Разумеется, конкретная проблема заключается в том, что вы не учли возможности деления на ноль. Тем
не менее, если ваш анализ ограничится этим, то в будущем вам это не
поможет. Конечно, вы можете столкнуться с другой ситуацией, когда
делитель может оказаться равным нулю, однако это бывает нечасто.
Вместо этого мы должны спросить, какой общий принцип был нарушен. Ответ: мы всегда должны искать специальные случаи, которые
могут нарушить работоспособность кода.
Если мы учтем этот общий принцип, мы с большей вероятностью заметим в наших ошибках закономерности и, следовательно,
с большей вероятностью отследим эти ошибки в будущем. Вопрос:
«Есть ли здесь возможность деления на ноль?» — не так полезен, как
вопрос: «Каковы специальные случаи для этих данных?» Постановка
более широкого вопроса будет напоминать не только о возможном
делении на ноль, но и о пустых наборах данных, о данных вне ожидаемого диапазона и т.д.
Планирование с учетом недостатков дизайна
Чтобы справиться с недостатками дизайна, требуются другие подходы. Тем не менее первый шаг тот же: вы должны обнаружить эти недостатки. У многих людей возникают проблемы на этом этапе, поскольку
они не любят смотреть на себя столь критично. Мы приучены скрывать
личные недостатки. Это похоже на то, когда на собеседовании при приеме на работу вас спрашивают о вашем самом большом недостатке, и
в ответ вы говорите какую-то глупость о том, что вы слишком сильно
переживаете о качестве своей работы, вместо того, чтобы рассказать о
настоящем недостатке. Однако так же, как у Супермена есть свой криптонит, даже лучшие программисты имеют свои слабые стороны.
Вот примерный (разумеется, не исчерпывающий) список недостатков программистов. Посмотрите, узнаете ли вы себя в любом из
этих описаний.
Замысловатый дизайн
Программист с таким недостатком создает программы, которые
имеют слишком много частей или слишком много шагов. Несмо236
Глава 8
тря на то, что программы работают, они не внушают доверия —
как изношенная одежда, которая выглядит так, будто готова развалиться, стоит потянуть за нитку, кроме того, эти программы
явно неэффективны.
Сложности с началом работы
Этот программист имеет высокую степень инерции. Либо из-за
недостатка уверенности в своих навыках решения задач, либо изза банальной прокрастинации, этот программист ждет слишком
долго, прежде чем приступить к делу.
Отсутствие тестирования
Этот программист не любит формально тестировать код. Часто
код подходит для общих случаев, но не справляется со специальными случаями. В других ситуациях код работает нормально,
но не «масштабируется» для более крупных задач, которые этот
программист не тестировал.
Чрезмерная уверенность
Уверенность в себе — это прекрасная вещь, данная книга призвана повысить уверенность читателей, однако слишком большая уверенность иногда может быть такой же проблемой, как
слишком маленькая. Чрезмерная уверенность проявляется поразному. Чрезмерно уверенный в себе программист может попытаться реализовать более сложное решение, чем нужно, или
выделить слишком мало времени на завершение проекта, в результате чего получается недоработанная и полная ошибок программа.
Слабость в определенной области
Эта категория охватывает множество разнообразных проблем.
Работа некоторых программистов протекает достаточно гладко,
пока они не столкнуться с определенными концепциями. Возьмем темы, обсуждавшиеся в предыдущих главах этой книги. Даже
после выполнения упражнений большинство программистов будут ориентироваться в некоторых областях лучше, чем в других.
Например, возможно, программист теряется при работе с указателями или у него голова идет кругом из-за рекурсии. Может
быть, у программиста проблемы с разработкой сложных классов.
Дело не в том, что программист не может разобраться и решить
задачу, а в том, что это требует тяжелой работы и напоминает
езду по грязи.
Существуют разные способы противостоять своим крупным недостаткам, и как только вы их осознаете, вы легко сможете спланировать свою работу с их учетом. Например, если вы программист, который часто пропускает этап тестирования, сделайте тестирование
неотъемлемым пунктом своего плана написания каждого модуля и не
переходите к следующему модулю, пока не поставите галочку в соответствующем месте. Кроме того, вы можете рассмотреть парадигму
Думайте как программист
237
под названием «разработка через тестирование», в рамках которой сначала пишется тестовый код, а затем код для прохождения этого теста. Если у вас возникают проблемы с началом работы, используйте
принципы деления или уменьшения задач и начинайте писать код,
как можно быстрее, понимая, что позднее вам, возможно, придется его переписать. Если ваши проекты часто оказываются слишком
сложными, добавьте специальный этап рефакторинга в свой мастерплан. Суть в том, что, какие бы недостатки как у программиста у вас
ни были, если вы их осознаете, вы можете спланировать свою работу с их учетом. В этом случае ваши слабости больше не будут являться
слабостями, а будут просто препятствиями на пути, которые вы будете объезжать, двигаясь к успешному завершению проекта.
Планирование с учетом ваших сильных сторон
Планирование с учетом слабых сторон в значительной степени направлено на избегание ошибок. Однако хорошее планирование заключается не только в том, чтобы не допустить ошибку. Смысл в том,
чтобы достичь наилучшего из возможных результатов, учитывая существующие способности и любые ограничения, в которых вам приходится работать. Это означает, что вы также должны включить в
мастер-план свои сильные стороны.
Вы можете подумать, что этот раздел не про вас или, по крайней мере, пока не про вас. В конце концов, если вы читаете эту книгу, вы все еще находитесь на этапе становления программистом. Вы
можете усомниться в наличии у себя каких-либо сильных сторон на
данном этапе своего развития. Я утверждаю, что у вас есть сильные
стороны, даже если вы о них еще не знаете. Далее приведен список
распространенных сильных сторон программистов, который ни в
коем случае не является исчерпывающим, с описаниями каждой из
них и подсказками, помогающими вам понять, насколько тот или
иной пункт относится к вам.
Зоркий глаз на детали
Такой программист может предвидеть специальные случаи,
предвосхищать потенциальные проблемы в плане производительности и никогда не позволяет общей картине заслонить
важные детали, которые необходимо учесть, чтобы программа
представляла собой завершенное и корректное решение. Программисты с такой сильной стороной обычно проверяют свои
планы на бумаге перед кодированием, пишут код медленно и часто его тестируют.
Быстрое обучение
Такой программист быстро осваивает новые навыки, независимо от того, изучает ли он новую технику на уже известном языке
или работает с новым каркасом приложений. Он получает удовольствие от изучения нового и может выбирать проекты, исходя из этого предпочтения.
238
Глава 8
Быстрое кодирование
Такому программисту не требуется много времени изучать справочник, чтобы создать функцию. Когда приходит время набирать текст, код течет из-под кончиков пальцев такого кодера без
особых усилий и с малым количеством синтаксических ошибок.
Упорство
Некоторые программисты воспринимают досадную ошибку как
личное оскорбление, которое нельзя игнорировать. Это похоже на то, что программа ударила программиста по лицу кожаной
перчаткой, и ему необходимо ответить на вызов. Кажется, что
такой программист всегда остается уравновешенным, решительным и никогда сильно не расстраивается, будучи уверенным в
том, что при достаточных усилиях победа будет гарантирована.
Превосходные навыки решения задач
Вероятно, когда вы купили эту книгу, вы еще не были мастером
решения задач, но теперь, после изучения этого руководства,
вам многое может начать казаться более легким. Программист с
этой чертой начинает предполагать потенциальные решения задачи еще во время чтения ее условия.
Энтузиазм
Для такого программиста рабочая программа похожа на удивительный ящик с игрушками. Энтузиаст очень любит, когда компьютер выполняет его или ее приказы, и обожает ставить перед
машиной все новые задачи. Это может выражаться в добавлении
в рабочую программу все большего количества функций — симптом, известный под названием ползучий «улучшизм». Кроме того,
такой программист может многократно подвергать программу
рефакторингу для повышения ее производительности или дорабатывать ее так, чтобы она просто казалась программисту или
пользователю более красивой.
Не у многих программистов проявляется сразу более двух из
перечисленных сильных сторон, на самом деле, некоторые из них,
как правило, отменяют друг друга. Однако у каждого программиста
есть свои сильные стороны. Если вы не узнали себя ни в одном из
приведенных описаний, это просто означает, что вы еще недостаточно себя знаете или ваши сильные стороны просто не вписываются ни в одну из выделенных мной категорий.
Как только вы определите свои сильные стороны, вам нужно будет учесть их в своем мастер-плане. Предположим, вы быстро пишете код. Очевидно, что это поможет довести любой проект до завершения, однако как вы можете использовать эту сильную сторону
систематически? В области формальной разработки программного обеспечения существует подход, называемый быстрым прототипированием, в рамках которого программа сначала пишется, минуя
этап подробного планирования, а затем улучшается с помощьюДумайте как программист
239
последовательных итераций до тех пор, пока результаты не начинают удовлетворять требованиям задачи. Если вы быстро пишете код,
вы можете попробовать использовать этот метод, приступая к кодированию, как только у вас появится основная идея, и руководствуясь
в процессе создания дизайна и разработки окончательного кода программы своим черновым прототипом.
Если вы быстро учитесь, возможно, вам следует начинать каждый проект с освоения новых ресурсов или методов, способных помочь вам в решении текущей задачи. Если вы являетесь программистом, который учится не очень быстро, но не расстраивается из-за
неудач, возможно, вам следует начать проект с тех областей, которые кажутся вам самыми трудными, чтобы уделить достаточно времени каждой из них.
Таким образом, какими бы ни были ваши сильные стороны, убедитесь в том, что вы используете их в процессе своей работы. Составьте свой мастер-план так, чтобы как можно больше времени тратилось на то, что вы делаете лучше всего. Так вы получите не только
наилучшие результаты, но и удовольствие от своей работы.
Составление мастер-плана
Давайте рассмотрим пример составления мастер-плана. Его составными частями являются все разработанные нами методы решения
задач, а также анализ наших сильных и слабых сторон. В этом примере я буду использовать свои сильные и слабые стороны.
Что касается методов решения задач, то я использую все методы, которые я описал в этой книге, но особенно мне нравится техника «уменьшения задачи», поскольку ее использование позволяет
мне ощутить конкретный прогресс в достижении своей цели. Если
я в настоящее время не могу найти способ написания кода, который
соответствует всей спецификации, я просто отбрасываю часть этой
спецификации, пока не наберу скорость.
Моим самым большим недостатком в кодировании является
чрезмерное рвение. Я люблю программировать, потому что мне нравится видеть, что компьютеры следуют моим инструкциям. Иногда
это заставляет меня думать: «Попробую-ка я сделать это и посмотрю,
что произойдет», — когда мне следует анализировать правильность
того, что я только что написал. Опасность здесь заключается не в
том, что в программе произойдет сбой, а в том, что программа либо
покажется успешной, но не охватит все специальные случаи, либо,
несмотря на свою эффективность, окажется не лучшим из возможных решений.
Мне нравятся элегантные дизайны программ, которые легко
расширять и повторно использовать. Часто, когда я создаю код для
крупных проектов, я трачу много времени на разработку альтернативных версий дизайна. В целом, это хорошая черта, но иногда
это приводит к тому, что я трачу слишком много времени на этапе
240
Глава 8
проектирования, что не оставляет достаточно времени на фактическую реализацию выбранного дизайна. Кроме того, иногда из-за
этого решение получается чрезмерно разработанным. То есть иногда решение оказывается более элегантным, расширяемым и надежным, чем необходимо. Поскольку каждый проект ограничен в плане
времени и денег, лучшее решение должно сбалансировать стремление к высокому качеству программного обеспечения с необходимостью экономии ресурсов.
Я считаю, что моя самая сильная сторона в программировании
заключается в том, что я хорошо усваиваю новые концепции и люблю учиться. В то время как некоторым программистам нравится снова и снова использовать одни и те же навыки, мне нравится работать
над проектом, на котором я могу научиться чему-то новому, и я всегда
с радостью принимаю вызов.
Далее представлен мой мастер-план для нового проекта, учитывающий мои сильные и слабые стороны.
Чтобы справиться со своей основной слабой стороной в области
дизайна, я строго ограничу свое время на этапе проектирования или
ограничу количество различных версий дизайна, которые я буду рассматривать, прежде чем двигаться дальше. Некоторым читателям
это может показаться опасной идеей. Разве мы не должны потратить
максимально возможное количество времени на этапе проектирования, прежде чем переходить к кодированию? Разве не правда, что
большинство проектов терпят неудачу из-за того, что на начальных
этапах было потрачено недостаточно времени, что привело к необходимости многочисленных компромиссов в конце? Это правомерные опасения, однако помните, что моей целью не являлось создание общего справочника по разработке программного обеспечения.
Я создаю свой личный мастер-план для решения проблем программирования. Моя слабая сторона заключается в чрезмерной, а не в недостаточной разработке, поэтому правило, ограничивающее время
на этапе проектирования, является для меня актуальным. Для другого программиста такое правило может оказаться катастрофическим,
а некоторым программистам может понадобиться правило, заставляющее их тратить больше времени на разработку.
После завершения своего первоначального анализа я собираюсь
посмотреть, предоставляет ли проект возможность для изучения новых методов, библиотек и т.д. Если да, я собираюсь написать небольшую пробную версию программы, чтобы опробовать эти новые навыки, прежде чем пытаться включить их в разрабатываемое мною
решение.
Чтобы справиться с чрезмерным рвением, я мог бы включить
небольшой этап для обзора кода после завершения этапа кодирования каждого модуля. Тем не менее это потребует от меня применения силы воли — после завершения модуля мне захочется опробовать его. Просто надеяться на то, что я смогу всякий раз себя
Думайте как программист
241
уговорить, — это все равно, что оставить открытый пакет с картофельными чипсами рядом с голодным человеком и удивиться, когда
пакет опустеет. Лучше попытаться справиться со слабыми сторонами с помощью плана, который не требует от программиста борьбы
с собственными инстинктами. Итак, что, если я создам две версии
проекта: приблизительную версию, с которой можно делать все что
угодно, и отшлифованную версию, которую можно сдать заказчику?
Если я позволю себе поиграть с первой версией по своему усмотрению, но не позволю себе включать код в отшлифованную версию до
тех пор, пока он не будет полностью проверен, я с большей вероятностью преодолею свой недостаток.
Решение любой задачи
Теперь, когда у нас есть мастер-план, мы готовы ко всему. В конечном счете, суть этой книги сводится к следующему: начните с задачи,
с любой задачи, и найдите способ ее решения. Во всех предыдущих
главах описания задач подталкивали нас в определенном направлении, однако в реальном мире большинство задач не подразумевает требований, связанных с использованием массива или рекурсии
или инкапсуляцией части функций программы в класс. Эти решения
принимает программист по ходу рабочего процесса.
Поначалу может показаться, что меньшее количество требований делает задачу более простой. В конце концов, требование к
дизайну является ограничением, а разве ограничения не затрудняют решение задачи? Хотя это верно, верно и то, что все задачи подразумевают ограничения, просто в некоторых случаях они изложены более четко, чем в других. Например, если вам не было сказано,
что конкретная задача требует динамически выделяемой структуры,
не означает, что это решение является бесполезным. Более общим
ограничениям задачи, касаются ли они производительности, модифицируемости, скорости разработки или чего-то еще, может быть
сложнее или вообще невозможно удовлетворить, если мы сделаем
неправильный выбор в плане дизайна.
Представьте, что группа друзей попросила вас выбрать фильм
для совместного просмотра. Если один из друзей определенно хочет
посмотреть комедию, другой не любит старые фильмы, а третий перечисляет пять фильмов, которые он недавно видел, поэтому не хочет смотреть их снова, то эти ограничения затруднят выбор. Однако
если ни у кого нет никаких пожеланий, кроме «просто какого-нибудь
хорошего фильма», ваша задача становится еще более сложной, и
вы, скорее всего, выберете то, что вообще не понравится по крайней мере одному человеку из группы.
Поэтому крупные, пространно определенные, слабо ограниченные задачи являются самыми трудными из всех. Тем не менее к ним
применимы рассмотренные в этой книге методы; их решение про-
242
Глава 8
сто требует чуть большего количества времени. Знания этих методов и ваш мастер-план помогут вам решить любую задачу.
Чтобы продемонстрировать суть того, о чем я говорю, я проведу вас по первым этапам программы, которая играет в классическую
детскую игру «Виселица», но с подвохом.
Прежде чем перейти к описанию задачи, давайте рассмотрим
основные правила этой игры. Первый игрок выбирает слово и говорит второму игроку, сколько в этом слове букв. Второй игрок пытается угадать букву. Если названная буква присутствует в слове, первый игрок показывает, в каком месте слова эта буква находится; если
эта буква встречается в слове более одного раза, указываются все ее
положения. Если названная буква в слове отсутствует, первый игрок
добавляет фрагмент к рисунку повешенного. Если второй игрок угадывает все буквы в слове, то он побеждает, если первый игрок завершает рисунок, то побеждает он. Существуют разные правила
относительно количества фрагментов, составляющих рисунок повешенного, поэтому в общем случае мы можем сказать, что игроки заранее договариваются о том, сколько «промахов» должен допустить
второй игрок, чтобы первый выиграл.
Теперь, когда мы обговорили основные правила, давайте рассмотрим конкретную задачу, включая подвох.
:
« & »
Напишите программу, которая будет Игроком 1 в текстовой версии игры «Виселица»
(то есть на самом деле вам не нужно рисовать повешенного, нужно только отслеживать
количество неправильных догадок). Игрок 2 будет задавать уровень сложности игры,
указывая длину слова, которое требуется угадать, а также количество неправильных
догадок, которые приведут к проигрышу.
Подвох заключается в том, что программа будет жульничать. Вместо того чтобы выбирать слово в начале игры, программа может избегать выбора слова так, что, когда
Игрок 2 проиграет, программа отобразит слово, соответствующее всей информации,
предоставленной Игроку 2. Правильно угаданные буквы должны указываться в соответствующих им положениях, а неправильно угаданные буквы вообще не могут появиться в этом слове. Когда игра закончится, Игрок 1 (программа) сообщит Игроку 2
слово, которое было выбрано. Поэтому Игрок 2 никогда не сможет доказать, что игра
его обманывает; просто вероятность выигрыша для Игрока 2 низкая.
Это не слишком крупная задача по стандартам реального мира,
однако она достаточно велика, чтобы на ее примере можно было
продемонстрировать проблемы, с которыми мы сталкиваемся при
решении задачи программирования, которая обозначает результаты, но не содержит никакой методологии. Основываясь на описании задачи, вы можете запустить свою среду разработки и начать писать код с любого места. Это, конечно, было бы ошибкой, потому
что нам всегда следует создавать код по плану, поэтому я собираюсь
применить свой мастер-план к этой конкретной ситуации.
Думайте как программист
243
Первая часть моего мастер-плана ограничивает количество времени, которое я трачу на этапе проектирования. Чтобы реализовать
это, мне нужно тщательно продумать дизайн, прежде чем приступать
к созданию кода. Тем не менее я считаю, что в данном случае для нахождения решения этой задачи мне понадобится провести несколько экспериментов. Мой мастер-план также позволяет мне создать
два проекта — грубый прототип и окончательное отшлифованное
решение. Поэтому я позволю себе начать кодирование прототипа в
любое время до начала реальной работы над дизайном, но не приступлю к кодированию итогового решения, пока не удостоверюсь в
том, что дизайн разработан так, как нужно. Это не гарантирует того,
что я буду полностью удовлетворен дизайном второго проекта, но
максимизирует вероятность этого.
Теперь пришло время разделить задачу на части. В предыдущих
главах мы иногда перечисляли все подзадачи, необходимые для итогового решения задачи, поэтому я хотел бы провести инвентаризацию подзадач. Тем не менее на данном этапе это было бы сложно
сделать, поскольку я не знаю, что программа сделает на самом деле,
чтобы обмануть второго игрока. Мне нужно более подробно исследовать этот вопрос.
Нахождение возможности для жульничества
Обман в игре «Виселица» достаточно специфичен, поэтому я не
ожидаю найти какое-либо руководство в обычных источниках с компонентами; там вряд ли есть шаблон под названием БесчестнаяСтратегия. На данном этапе у меня есть лишь смутное представление о
том, как можно сжульничать в этой игре. Я думаю, что загадаю исходное слово и буду придерживаться его, пока Игрок 2 выбирает буквы,
которые отсутствуют в этом слове. Как только Игрок 2 назовет букву, которая на самом деле есть в этом слове, я выберу другое слово,
если можно будет найти такое, в котором нет ни одной из названных
до сих пор букв. Другими словами, я буду стараться как можно дольше отказывать Игроку 2 в правильности его догадки. Это идея, но
мне нужно нечто большее, чем идея, — мне нужно что-то, что я могу
реализовать.
Чтобы развить свои идеи, я разберу пример на бумаге, взяв на
себя роль Игрока 1 и работая со списком слов. Чтобы не усложнять,
я предположу, что Игрок 2 запросил слово, состоящее из трех букв, и
что полный список известных мне трехбуквенных слов представлен
в первом столбце табл. 8.1. Я предполагаю, что первым загаданным
мной словом является первое слово в списке — bat. Если Игрок 2 назовет любую букву, кроме b, a или t, я скажу «нет», и мы подойдем на один
шаг ближе к завершению рисунка повешенного. Если Игрок 2 угадает
букву в слове, то я выберу другое слово, которое не содержит эту букву.
Тем не менее, глядя на свой список, я не уверен, что эта стратегия является лучшей. В некоторых ситуациях она, вероятно, име244
Глава 8
ет смысл. Предположим, что Игрок 2 называет букву b. Ни одно из
оставшихся в списке слов не содержит букву b, поэтому я могу выбрать в качестве загаданного слова любое из них. Это также означает, что я минимизировал ущерб; я исключил из своего списка только
одно возможное слово. Но что, если Игрок 2назовет букву a? Если
я просто скажу «нет», мне придется исключить все слова, содержащие букву a, при этом останется только три слова во втором столбце
табл. 8.1, из которых я смогу выбрать. Если бы вместо этого я решил
признать наличие буквы a в загаданном слове, у меня осталось бы
пять слов на выбор, как показано в третьем столбце. Однако заметьте, что этот расширенный выбор существует только потому, что все
пять слов содержат букву a в одном и том же положении. Как только
я признаю догадку правильной, я должен буду точно указать, где в
слове находится буква. Я буду чувствовать себя гораздо спокойнее,
если у меня будет больше вариантов слов, среди которых я могу сделать выбор в ответ на будущие догадки.
Табл. 8.1. Образец списка слов
“ “%"=
q%"= Kƒ K3"/ a
q%"= K3"%L a
bat
car
dot
eat
pit
saw
tap
top
dot
pit
top
bat
car
eat
saw
tap
Кроме того, даже если мне удастся избежать раскрытия букв в начале игры, мне следует ожидать того, что Игрок 2 в конечном итоге сделает правильное предположение. Например, Игрок 2 может начать с
перечисления всех гласных. Поэтому в какой-то момент мне нужно будет решить, что делать, когда буква будет открыта, и, судя по моему эксперименту с образцом списка, мне нужно будет найти местоположение
(или местоположения), в которых эта буква появляется чаще всего. Это
наблюдение заставило меня понять, что я неправильно подошел к обдумыванию возможного обмана. Мне никогда не следует загадывать слово, даже на время, мне нужно просто отслеживать все возможные слова, из которых при необходимости я мог бы выбрать одно.
Имея в виду эту идею, я могу теперь по-другому определить способ обмана: следует хранить как можно больше слов в списке словкандидатов. При каждой высказанной Игроком 2 догадке программа
должна принять решение. Признает ли она догадку правильной или
не правильной? Если догадка правильная, то, в каком месте слова находится угаданная буква? Я сделаю так, что моя программа будет постоянно сокращать список слов-кандидатов и после каждой высказанной догадки принимать решение, при котором в этом списке
остается максимальное количество слов.
Думайте как программист
245
Необходимые операции для обмана в игре «Виселица»
Теперь я понимаю задачу достаточно хорошо, чтобы создать список
подзадач. В случае проблемы такого размера существует довольно
большая вероятность того, что список, составленный на раннем этапе, позволит обойтись без некоторых операций. Это нормально, поскольку мой мастер-план предусматривает возможность того, что я
не создам идеальный дизайн с первого раза.
Сохранение и поддержание списка слов
Эта программа должна содержать список допустимых английских слов. Поэтому программе необходимо будет прочитать список слов из файла и сохранить его внутри в каком-то формате.
Во время игры, когда программа будет обманывать игрока, этот
список будет уменьшаться или из него будут извлекаться слова.
Создание подсписка слов определенной длины
Учитывая мое намерение поддерживать список слов, которые
могут быть загаданы (список слов-кандидатов), я должен начать
игру со списком слов указанной Игроком 2 длины.
Отслеживание выбранных букв
Программа должна будет помнить, какие буквы были названы
Игроком 2, сколькие из них были неправильными, а также в каком месте загаданного слова находятся буквы, которые были сочтены правильными.
Подсчет слов, в которых отсутствует названная буква
Чтобы облегчить обман Игрока 2, мне нужно знать, сколько слов
в списке не содержит последней названной буквы. Помните, что
программа решит, присутствует ли последняя названная Игроком 2 буква в загаданном слове, руководствуясь целью оставить в
списке слов-кандидатов максимальное количество слов.
Определение наибольшего количества слов, исходя из буквы
и положения
Эта операция кажется самой сложной. Предположим, что
Игрок 2 только что угадал букву d, а загаданное в текущей игре
слово состоит из трех букв. Возможно, текущий список словкандидатов содержит всего 10 слов, включающих букву d, но это
не важно, поскольку программе нужно будет указать, в каком
месте загаданного слова находится эта буква. Давайте назовем
расположение букв в слове шаблоном. Таким образом, d?? — это
трехбуквенный шаблон, который указывает, что первой буквой
в слове является d, а двумя другими — буквы отличные от d. Рассмотрим табл. 8.2. Предположим, что список в первом столбце
содержит все трехбуквенные слова с буквой d, известные программе. Остальные столбцы разбивают этот список согласно
шаблону. Наиболее часто встречается шаблон ??d — в 17 словах.
Это число, 17, будет сравниваться с количеством слов в списке
246
Глава 8
слов-кандидатов, которые не содержат буквы d, чтобы решить,
как следует оценивать догадку — как промах или как попадание.
Создание подсписка слов, соответствующих шаблону
Когда программа сообщает, что Игрок 2 угадал букву, она создает новый список слов-кандидатов, содержащий только те слова,
которые соответствуют выбранному буквенному шаблону. В предыдущем примере, если мы объявили, что буква d угадана правильно, то третий столбец в табл. 8.2 становится новым списком
слов-кандидатов.
Игра до конца
После разработки всех остальных операций мне нужно будет написать код, объединяющий все вместе и фактически играющий
в игру. Программа должна многократно запрашивать у Игрока 2 (пользователя) букву, определять, станет ли список словкандидатов более длинным, если догадка будет отклонена или
признана правильной, соответственно уменьшать список слов, а
затем отображать получившееся загаданное слово с открытыми
правильно угаданными буквами, наряду с перечислением всех названных ранее букв. Этот процесс будет продолжаться до окончания игры, пока не выиграет один из игроков, условия чего мне
еще предстоит сформулировать.
Табл. 8.2. Слова, состоящие из трех букв
“ “%"=
?dd
??d
d??
d?d
add
aid
and
bad
bed
bid
day
did
die
doe
dog
dry
due
end
fed
had
hid
kid
led
mad
mod
odd
old
red
rid
sad
add
odd
aid
and
bad
bed
bid
end
fed
had
hid
kid
led
mad
mod
old
red
rid
sad
day
die
doe
dog
dry
due
did
Думайте как программист
247
Исходный дизайн
Хотя может показаться, что в предыдущем списке необходимых операций перечислены просто сырые факты, мы принимаем решения,
касающиеся дизайна. Рассмотрим операцию «Создание подсписка
слов, соответствующих шаблону». Эта операция будет иметь место в
моем решении или по крайней мере в его первоначальной версии, однако, строго говоря, эта операция вовсе не является обязательной. Это
же касается операции «Создание подсписка слов определенной длины». Вместо поддержания постепенно уменьшающегося списка словкандидатов я мог бы на протяжении всей игры хранить исходный главный список слов. Тем не менее это усложнило бы большинство других
операций. Операция «Подсчет слов, в которых отсутствует буква» не
может подразумевать простой перебор списка слов-кандидатов и подсчет слов, не содержащих указанную букву. Поскольку она осуществляла бы поиск в основном списке, ей также пришлось бы проверять длину каждого слова и то, соответствует ли это слово открытым до сих
пор буквам. Я считаю, что выбранный мной путь в целом более прост,
однако я должен знать, что решения, принятые даже на этих ранних
этапах, влияют на итоговый дизайн.
Тем не менее кроме первоначального разбиения задачи на подзадачи, мне предстоит принять и другие решения.
Хранение списков слов
Основной структурой данных программы будет список слов, который программа будет уменьшать на протяжении всей игры.
Выбирая структуру, я сделал следующие наблюдения. Во-первых,
я не думаю, что мне потребуется произвольный доступ к словам в
списке, вместо этого я всегда буду обрабатывать список целиком,
от начала до конца. Во-вторых, мне не известен размер нужного мне исходного списка. В-третьих, мне предстоит часто сокращать список. Наконец, в-четвертых, вероятно, в этой программе
пригодятся методы стандартного класса string. На основе всех
этих наблюдений я принимаю решение, что моим первоначальным выбором для этой структуры будет стандартный шаблонный
класс list с типом элемента string.
Отслеживание отгаданных букв
Концептуально выбранные буквы представляют собой набор,
то есть буква либо выбрана, либо нет, ни одна буква не может
быть выбрана более одного раза. Таким образом, вопрос сводится к тому, является ли конкретная буква алфавита частью набора
«выбранных букв». Поэтому я собираюсь представить выбранные буквы в виде массива типа bool размером 26. Если массив называется guessedLetters, то guessedLetters[0] имеет значение
true, если буква а была угадана ранее, в противном случае значением будет false; guessedLetters[1] соответствует букву b и т.д.
Я буду использовать методы преобразования диапазона, кото-
248
Глава 8
рые мы уже обсуждали в этой книге, чтобы обеспечить преобразование между буквой в нижнем регистре и соответствующей ей
позицией в массиве. Если letter — это символ, представляющий
букву в нижнем регистре, то guessedLetters[letter — 'a'] — это
соответствующее ей место.
Хранение шаблонов
В одной из операций, код для которых мне предстоит написать,
«Создание подсписка слов, соответствующих шаблону», будет использоваться шаблон положений буквы в слове. Этот шаблон будет создаваться операцией «Определение наибольшего количества
слов, исходя из буквы и положения». Какой формат я буду использовать для этих данных? Шаблон представляет собой ряд чисел, соответствующих местоположению конкретной буквы. Существует
множество способов для хранения этих чисел, но для простоты я
буду использовать другой список list с типом элемента int.
Пишу ли я класс?
Поскольку я кодирую эту программу на языке C++, я могу использовать или не использовать объектно ориентированное программирование по своему усмотрению. Моя первая мысль заключается в
том, что многие из операций в моем списке можно естественным
образом объединить в класс под названием wordList, возможно, с
методами, позволяющими удалять слова на основе заданных критериев (то есть длины и шаблона). Однако, поскольку сейчас я пытаюсь избежать принятия решений, касающихся дизайна, которые
мне придется в дальнейшем отменить, я собираюсь сделать свою
первую, черновую программу полностью процедурной. Когда я разработаю все сложные аспекты программы и фактически напишу
код для всех операций в своем списке, я смогу принять решение относительно применимости принципов объектно-ориентированного программирования к окончательной версии программы.
Первичное кодирование
Теперь начинается самое интересное. Я запускаю свою среду разработки и берусь за дело. В этой программе будет использоваться несколько классов из стандартной библиотеки, поэтому для ясности
позвольте мне сначала установить их все.
#include
using std::cin;
using std::cout;
using std::ios;
#include
using std::ifstream;
#include
using std::string;
#include
using std::list;
using std::iterator;
#include
Думайте как программист
249
Теперь я готов начать кодирование операций из моего списка.
В какой-то мере я мог бы кодировать операции в любом порядке,
однако я собираюсь начать с написания функции для чтения простого текстового файла со словами в выбранную мною структуру
list. На данном этапе я понимаю, что мне нужно найти существующий мастер-файл со словами — я не хочу набирать его самостоятельно. К счастью, на поисковый запрос word list система Google
выдает ряд сайтов, содержащих списки английских слов в текстовом
формате, по одному слову на строку файла. Я уже знаком с чтением текстовых файлов средствами языка C++, но если бы это было не
так, я сначала написал бы небольшую тестовую программу, чтобы освоить этот навык, прежде чем интегрировать эту способность в программу, которая обманывает игрока в игре «Виселица». Эта практика обсуждается далее в главе.
Теперь, когда у меня есть файл, я могу написать функцию:
list readWordFile(char * lename) {
list wordList;
X ifstream wordFile(lename, ios::in);
Y if (wordFile == NULL) {
cout > currentWord) {
[ if (strchr(currentWord, '\'') == 0) {
string temp(currentWord);
wordList.push_back(temp);
}
}
return wordList;
}
Эта функция проста, поэтому я сделаю всего несколько коротких комментариев. Если вы никогда не встречали его раньше, объект ifstream X представляет собой входной поток, который работает так же, как cin, за исключением того, что данные считываются из
файла, а не из стандартного потока ввода. Если конструктор не может открыть файл (обычно это означает, что файл не найден), объект будет иметь значение NULL, что я явно проверяю Y. Если файл
существует, то он обрабатывается в цикле Z, который считывает
каждую строку файла в массив символов, преобразует массив в объект string и добавляет его в список list. Выбранный мной файл с
английскими словами содержит слова с апострофами, которые недопустимы в нашей игре, поэтому я явно исключаю их [.
Далее я пишу функцию для отображения всех слов в моем списке list. Это не входит в мой требуемый список операций,
и я бы не использовал ее в игре (в конце концов, это бы только помогло Игроку 2, которого я пытаюсь обмануть), однако это хороший способ проверить, правильно ли работает моя функция readWordFile:
250
Глава 8
void displayList(Xconst list & wordList) {
Y list::const_iterator iter;
iter = wordList.begin();
while (iter != wordList.end()) {
cout c_str() nd(letter) == string::npos) {
count++;
}
iter++;
}
return count;
}
Как видите, это тот же базовый цикл обхода. Внутри я вызываю
метод nd класса string X, который возвращает позицию своего параметра char в объекте string, возвращая специальное значение npos,
если символ не найден.
Я использую эту же базовую структуру для записи функции, которая
удаляет все слова из списка, которые не соответствуют указанной длине:
void removeWordsOfWrongLength(list & wordList, int acceptableLength)
{
list::iterator iter;
iter = wordList.begin();
while (iter != wordList.end()) {
if (iter->length() != acceptableLength) {
X iter = wordList.erase(iter);
} else {
Y iter++;
}
}
}
Думайте как программист
251
Эта функция является хорошим примером того, как каждая написанная вами программа позволяет углубить понимание принципов
своей работы. Мне было легко написать данную функцию, поскольку я понимал, что происходит «за кадром», благодаря написанным
мною ранее программам. В этой функции используется базовый
код обхода из предыдущих функций, однако внутри цикла код становится интереснее. Метод erase() удаляет элемент, указанный итератором iterator, из объекта list. Но из опыта реализации шаблона итератора для связного списка, описанного в главе 7, я знаю, что
iterator почти наверняка является указателем. Из опыта работы с
указателями, описанного в главе 4, я знаю, что указатель бесполезен и часто опасен, когда является висячей ссылкой на то, что было
удалено. Поэтому я знаю, что после этой операции мне необходимо
присвоить действительное значение iter. К счастью, разработчики
метода erase() предусмотрели возможность возникновения такой
проблемы и сделали так, чтобы этот метод возвращал новый iterator, который указывает на элемент, следующий за тем, который мы
только что стерли, поэтому я могу присвоить это значение iter X.
Также обратите внимание на то, что я явно продвигаю iter Y только тогда, когда текущая строка не удаляется из списка, потому что
присвоение erase()возвращенного значения фактически продвигает iterator, и я не хочу пропускать какие-либо элементы.
Теперь перейдем к трудной части — к поиску наиболее распространенного конкретного буквенного шаблона в списке оставшихся
слов. Это еще одна возможность для использования техники разделения задачи. Я знаю, что одной из подзадач этой операции является
определение того, соответствует ли конкретное слово определенному шаблону. Помните, что шаблон представляет собой list, причем каждый элемент int соответствует местоположению буквы в слове, а для того, чтобы слово соответствовало шаблону, буква не просто
должна находиться в указанных позициях в слове, но и не должна находиться больше нигде в слове. Учитывая это, я собираюсь проверить
строку на соответствие путем ее обхода. Для каждой позиции в строке, если указанная буква присутствует, я удостоверюсь, что эта позиция находится в шаблоне, а если там находится какая-то другая буква,
я удостоверюсь, что эта позиция в шаблоне отсутствует.
Упрощая еще больше, я сначала напишу отдельную функцию, чтобы проверить, отображается ли номер конкретной позиции в шаблоне:
bool numberInPattern(const list & pattern, int number) {
list::const_iterator iter;
iter = pattern.begin();
while (iter != pattern.end()) {
if (*iter == number) {
return true;
}
iter++;
}
return false;
}
252
Глава 8
Этот код было довольно просто написать, основываясь на предыдущих функциях. Я просто обхожу list в поисках number. Если я
нахожу его, то возвращаю значение true, а если добираюсь до конца
списка, то возвращаю false. Теперь я могу реализовать общий тест
на соответствие шаблону:
bool matchesPattern(string word, char letter, list pattern) {
for (int i = 0; i < word.length(); i++) {
if (word[i] == letter) {
if (!numberInPattern(pattern, i)) {
return false;
}
} else {
if (numberInPattern(pattern, i)) {
return false;
}
}
}
return true;
}
Как видите, эта функция соответствует описанному ранее плану.
Для каждого символа в строке, если он соответствует значению letter,
код проверяет, находится ли текущая позиция в шаблоне. Если символ
не соответствует значению letter, код производит проверку, чтобы
удостовериться в том, что позиция не находится в шаблоне. Если хотя
бы одна позиция не соответствует шаблону, слово отклоняется; в противном случае будет достигнут конец слова, и оно будет принято.
Сейчас мне кажется, что найти наиболее распространенный
шаблон будет проще, если каждое слово в списке содержит указанную букву. Поэтому я пишу быструю функцию для отбрасывания
слов, не содержащих эту букву:
void removeWordsWithoutLetter(list & wordList, char requiredLetter) {
list::iterator iter;
iter = wordList.begin();
while (iter != wordList.end()) {
if (iter->nd(requiredLetter) == string::npos) {
iter = wordList.erase(iter);
} else {
iter++;
}
}
}
Этот код представляет собой просто комбинацию идей, использованных в предыдущих функциях. Теперь, когда я думаю об этом,
мне понадобится и обратная функция, которая отбрасывает все слова, которые содержат указанную букву. Я буду использовать ее для
уменьшения списка слов-кандидатов, когда программа признает последнюю догадку промахом:
void removeWordsWithLetter(list & wordList, char forbiddenLetter) {
list::iterator iter;
iter = wordList.begin();
Думайте как программист
253
while (iter != wordList.end()) {
if (iter->nd(forbiddenLetter) != string::npos) {
iter = wordList.erase(iter);
} else {
iter++;
}
}
}
Теперь я готов найти наиболее распространенный шаблон в списке слов для данной буквы. Я рассмотрел ряд подходов и выбрал тот,
который, как мне кажется, я мог бы легче всего реализовать. Вопервых, я воспользуюсь вызовом вышеприведенной функции, чтобы удалить все слова, не содержащие указанную букву. Затем я возьму
первое слово в списке, определю его шаблон и подсчитаю количество других слов в списке, соответствующих этому же шаблону. Все
эти слова будут стираться из списка по мере их подсчета. Затем процесс повторится снова с любым словом, находящимся в начале списка, и так будет продолжаться, пока список не опустеет. Результат выглядит следующим образом:
void mostFreqPatternByLetter(X list wordList, char letter,
Y list & maxPattern,
Z int & maxPatternCount) {
[ removeWordsWithoutLetter(wordList, letter);
list::iterator iter;
maxPatternCount = 0;
\ while (wordList.size() > 0) {
iter = wordList.begin();
list currentPattern;
] for (int i = 0; i < iter->length(); i++) {
if ((*iter)[i] == letter) {
currentPattern.push_back(i);
}
}
int currentPatternCount = 1;
iter = wordList.erase(iter);
^ while (iter != wordList.end()) {
if (matchesPattern(*iter, letter, currentPattern)) {
currentPatternCount++;
iter = wordList.erase(iter);
} else {
iter++;
}
}
_ if (currentPatternCount > maxPatternCount) {
maxPatternCount = currentPatternCount;
maxPattern = currentPattern;
}
currentPattern.clear();
}
}
Список list представляет собой параметр типа значения X, поскольку в процессе обработки данная функция будет уменьшать список, пока в нем ничего не останется, и я не хочу влиять на параметр,
передающийся вызывающим кодом. Обратите внимание на то, что
maxPattern Y и maxPatternCount Z являются только исходящими па254
Глава 8
раметрами; они будут использоваться для отправки наиболее часто
встречающегося шаблона и количества случаев его появления обратно в вызывающий код. Я удаляю все слова, не содержащие значение
letter [. Затем я вхожу в основной цикл функции, который продолжается до тех пор, пока список не опустеет \. Код внутри цикла имеет три основных раздела. Во-первых, цикл for создает шаблон для
первого слова в списке ]. Затем цикл while подсчитывает, сколько
слов в списке соответствует этому шаблону ^. Наконец, мы проверяем, превышает ли это значение наибольшее из определенных до
сих пор значений, используя стратегию «Царь горы», описанную в
главе 3 _.
Последняя нужная мне служебная функция будет отображать все
отгаданные до сих пор буквы. Помните, что я храню их как массив
из 26 значений bool:
void displayGuessedLetters(bool letters[26]) {
cout
