Файл: Think likea programmer.pdf

Истинные головоломки 61
Табл. 2.3. Режим декодирования пунктуации
),“%
q,"%
1
!
2
?
3
,
4 5
(пробел)
6
;
7
"
8
'
Как и в случае с проверочной формулой Луна, мы познакомимся с конкретным примером, чтобы убедиться в том, что разобрались во всех шагах. На рис. 2.4 показан образец декодирования. Исходный поток ввода показан в верхней части рисунка. Этапы обработки ука- заны сверху вниз. В колонке (а) показано текущее число на вводе.
В колонке (б) показан текущий режим, принимающий циклически одно из трех состояний: верхний регистр (U), нижний регистр (L) и пунктуация (P). В колонке (в) приводится делитель для текущего режима. В колонке (г) показан остаток от деления текущего ввода из колонки (а) на текущий делитель в колонке (в). Результат показан в колонке (д), и это либо символ, либо, если результат в колонке (г) ра- вен 0, то переключение к следующему по порядку режиму.
Рис. 2.4. Образец процессинга для задачи «Декодирование сообщения»

62 Глава 2
Как и в случае с предыдущей проблемой, мы можем начать с яв- ного рассмотрения того, какие навыки потребуются для разработ- ки решения. Нам нужно считать строку символов до тех пор, пока не достигнем конца строки. Символы представляют последователь- ность целых чисел, поэтому нам нужно считать символы цифр и кон- вертировать их в целые числа для последующей обработки. Получив целые числа, мы должны конвертировать целое число в один сим- вол для вывода. Наконец, нам нужен некий способ для отслеживания режима декодирования, чтобы мы могли знать, должно ли текущее целое быть декодировано символ нижнего регистра, символ верхне- го регистра или же в знак пунктуации. Давайте преобразуем выше- сказанное в формальный список.
yСчитывать символ за символом до достижения конца строки.
y
Преобразовать последовательность символов, представля- ющие цифры, в целое число.
y
Преобразовать целое число в диапазоне 1 — 26 в символ верх- него регистра.
y
Преобразовать целое число в диапазоне 1 — 26 в символ ниж- него регистра.
y
Преобразовать целое число в диапазоне 1 — 8 в пунктуацион- ный символ, в соответствии с табл. 2.3.
yОтслеживать режим декодирования.
Решить первый пункт мы можем благодаря предыдущей задаче.
Более того, несмотря на то, что при решении задачи с проверочной формулой Луна мы только работали с отдельными цифрами, я подо- зреваю, что наши действия для решения задачи будут полезны и для второго элемента списка. Окончательный код алгоритма Луна еще, возможно, свеж в вашей памяти, но если между тем кодом и решени- ем этой задачи вы отложите чтение книги, то по продолжении вам понадобится вернуться и перечитать код предыдущей задачи. Обыч- но, если описание текущей проблемы вызывает у вас дежа-вю, вы за- хотите найти похожий код в своих архивах для изучения.
Давайте займемся оставшимися элементами списка. Должно быть, вы заметили, что в списке каждое из преобразований вынесе- но отдельным элементом. Я подозреваю, что преобразование числа в букву нижнего регистра будет очень сильно походить на преобра- зование числа в букву верхнего регистра, однако, возможно, пре- образование в пунктуационный символ потребует несколько иного подхода. В любом случае, нет ничего плохого в разбиении списка на такие детальные подпункты, это лишь означает, что вы сможете вы- черкивать элементы чаще.

Истинные головоломки 63
*+- . - %/ 0 %3456 0 7 + 6
0 %8 -/
Сходства между элементами этой и предыдущей задач показывают важность от- дельного сохранения исходного кода в виде, удобном для последующего повторно- го использования. Разработчики программного обеспечения очень много говорят о
повторном использовании кода, которое происходит, когда вы используете участки старого программного обеспечения для создания нового. Зачастую это подразу- мевает использование инкапсулированного компонента или непосредственное по- вторное использование исходного кода. Однако очень важно иметь легкий доступ к ранее написанным решениям. Даже если вы не копируете старый код напрямую, это позволит вам повторно использовать уже приобретенные навыки и приемы без необходимости изобретать велосипед повторно. Для максимизации этого преиму- щества, старайтесь сохранять весь исходный код, который вы пишете (конечно же, не забывая о соглашениях по интеллектуальной собственности, возможно, заклю- ченных между вами и вашими работодателями или клиентами).
Сможете ли вы использовать преимущества уже написанных программ, по боль- шей части, зависит от того, с какой скрупулезностью вы сохраняете их: код, ко- торый вы не можете найти — это код, который вы не можете использовать. Если вы используете пошаговый подход и пишите отдельные программы для проверки своих идей, прежде, чем интегрировать эти отдельные программы в целое ре- шение, обязательно сохраняйте и эти промежуточные программы. Позже, когда сходство программы, над которой вы работаете в данный момент, и старой про- граммы будет находиться в сфере, для которой вы уже писали тестовую програм- му, вы найдете такой подход очень удобным.
Давайте начнем с преобразований целых чисел в символы. Из программы с формулой Луна мы знаем код, который требуется для считывания символьной цифры в диапазоне 0 — 9 и конвертации его в целое число в диапазоне от 0 до 9. Как мы можем расширить этот метод для работы с многозначными числами? Давайте рассмотрим простейший случай — двузначные числа. Это выглядит вполне по- нятно: в двузначном числе первая цифра представляет десятки, сле- довательно, нужно умножить эту цифру на 10, а затем прибавить зна- чение второй цифры. Например, если бы число было 35, то после чтения отдельных составляющих цифр как символов 3 и 5 и преоб- разования этих символов в целые числа 3 и 5, выполнив выражение
3 * 10 + 5, мы получили бы нужное целое число. Давайте подтвердим это предположение с помощью кода:
cout << "Enter a two-digit number: ";
char digitChar1 = cin.get();
char digitChar2 = cin.get();
int digit1 = digitChar1 — '0';
int digit2 = digitChar2 — '0';
int overallNumber = digit1 * 10 + digit2;
cout << "That number as an integer: " << overallNumber << "\n";
Работает! Программа выводит то же самое двузначное число, что мы ввели. Однако мы сталкиваемся с проблемой, когда пыта- емся расширить этот метод. Эта программа использует две разные

64 Глава 2
переменные для хранения двух введенных символов, и, хотя это не вызывает никаких проблем, мы конечно же не хотим использовать этот подход как общее решение. А если бы захотели, то нам пона- добилось бы столько переменных, сколько цифр составляет введен- ное число. Это приведет к беспорядку, кроме того, такую программу было бы трудно изменить, если диапазон возможных чисел во вход- ном потоке изменился. Нам нужно более общее решение этой подза- дачи преобразования символов в целые числа. Первый шаг к поиску этого общего решения заключается в сокращении предыдущего кода до двух переменных: одной char и одной int:
cout << "Enter a two-digit number: ";
X char digitChar = cin.get();
Y int overallNumber = (digitChar — '0') * 10;
Z digitChar = cin.get();
[ overallNumber += (digitChar — '0');
cout << "That number as an integer: " << overallNumber << "\n";
Мы достигаем этого за счет выполнения всех вычислений, касаю щихся первой цифры еще до считывания второй цифры.
После считывания первого цифрового символа в первом шаге
X
, мы преобразуем его в целое число, умножаем на 10 и сохраняем результат во втором шаге
Y
. После считывания второй цифры
Z
мы прибавляем ее целочисленное значение к общему значению
[
Эти шаги аналогичны предыдущему коду, только в этот раз мы ис- пользуем лишь две переменных: одну для последнего прочитанно- го символа и еще одну для общего значения целого числа. Следую- щий шаг — рассмотреть расширение этого метода для трехзначных чисел. Как только мы сделаем это, скорее всего, мы увидим законо- мерность, которая позволит нам создать общее решение для любо- го количества цифр.
Однако когда мы попытаемся реализовать этот план, то столкнем- ся с проблемой. С двузначными числами мы умножали левую цифру на 10, потому что левая цифра была в позиции разряда десятков, од- нако в случае с трехзначными числами самая левая цифра будет на- ходиться в позиции разряда сотен, а значит, нам потребовалось бы умножить эту цифру на 100. После этого мы могли бы считать сред- нюю цифру, умножить ее на 10, прибавить к общему значению, а затем считать последнюю цифру и также прибавить ее к общему значению.
Это должно сработать, однако такой подход не приближает нас к соз- данию общего решения. Вы видите проблему? Задумайтесь о вышеска- занном: cамая левая цифра будет находиться в позиции разряда сотен. В случае с общим решением мы не будем знать, из скольких цифр состо- ит число до тех пор, пока не достигнем следующей запятой. Самой ле- вой цифре числа с неизвестным количеством цифр нельзя присвоить позицию сотен или вообще какую-либо другую позицию. Так каким же образом мы узнаем, какой множитель нам использовать с каждой циф- рой прежде, чем прибавлять ее к общему значению? Или, может, нам нужен абсолютно иной подход?

Истинные головоломки 65
Как всегда, зайдя в тупик, хорошей идеей будет создать упрощен- ную задачу и поработать над ней. Сложность здесь в том, что мы не знаем, из скольких цифр будет состоять число. Самая простая зада- ча, в которой преодолевается та же самая сложность, будет предпо- лагать работу с одним из двух возможных количеств цифр.
: 9 - # 9
Напишите программу, которая считывала бы число символ за символом и преобра- зовывала бы его в целое число, используя только одну переменную типа char и одну переменную типа int. Число может быть либо трехзначным, либо четырехзначным.
Проблема незнания общего количества символов до самого кон- ца, но потребности в общем количестве с самого начала аналогична проблеме с формулой Луна. В том случае мы не знали, состоит ли идентификационный номер из четного или нечетного количества символов. В том случае наше решение состояло в одновременном подсчете результата двумя способами и использовании подходяще- го результата в конце. Можем ли мы сделать что-то похожее и здесь?
Если число состоит либо из трех, либо из четырех цифр, то существу- ет лишь два варианта. Если число трехзначное, то самая левая цифра соответствует количеству сотен. Если же число четырехзначное, то самая левая цифра означает количество тысяч. Мы могли бы произ- вести вычисления одновременно, как будто бы перед нами трехзнач- ное число и четырехзначное, а в конце выбрать подходящее число, однако условие задачи позволяет нам иметь только одну числовую переменную. Поэтому чтобы продвинуться в решении большой за- дачи, давайте ослабим это ограничение.
: 9 - # 9 ,
$ !
Напишите программу, которая считывала бы число символ за символом и преобра- зовывала бы его в целое число, используя только одну переменную типа char и две переменные типа int. Число может быть либо трехзначным, либо четырехзначным.
Теперь мы можем применить метод «подсчет двумя способами».
Мы обработаем первые три цифры двумя способами, а затем посмо- трим, есть ли еще и четвертая цифра:
cout << "Enter a three-digit or four-digit number: ";
char digitChar = cin.get();
X int threeDigitNumber = (digitChar — '0') * 100;
Y int fourDigitNumber = (digitChar — '0') * 1000;
digitChar = cin.get();
threeDigitNumber += (digitChar — '0') * 10;
fourDigitNumber += (digitChar — '0') * 100;
digitChar = cin.get();
threeDigitNumber += (digitChar — '0');
fourDigitNumber += (digitChar — '0') * 10;
digitChar = cin.get();

66 Глава 2
if
Z (digitChar == 10) {
cout << "Number entered: " << threeDigitNumber << "\n";
} else {
[ fourDigitNumber += (digitChar — '0');
cout << "Number entered: " << fourDigitNumber << "\n";
}
После считывания крайней левой цифры мы умножаем целочис- ленное значение на 100 и сохраняем результат в трехзначной пере- менной
X
. Мы также умножаем целочисленное значение на 1000 и сохраняем результат в четырехзначной переменной
Y
. Эта же схема повторяется и для следующих двух цифр. Вторая цифра обрабатыва- ется и как показатель десятков в трехзначном числе, и как сотен — в четырехзначном. Третья цифра обрабатывается и как показатель десятков, и как единиц. После считывания четвертого символа мы проверяем, является ли он символом конца строки, сравнив его с числом 10
Z
(как и в предыдущей задаче, это значение может отли- чаться в зависимости от операционной системы). Если перед нами символ конца строки, а значит, было введено трехзначное число, в противном случае нам все еще нужно прибавить значение единиц к общему значению
[
Теперь нам нужно придумать способ, как избавиться от одной лишней целочисленной переменной. Предположим, мы полно- стью убрали переменную fourDigitNumber. Значение переменной threeDigitNumber как и прежде будет присвоено корректно, но когда мы дойдем до момента, где потребуется переменная fourDigitNumber, в нашем распоряжении ее просто не будет. Существует ли какой-либо способ определить значение, которое было бы присвоено переменной fourDigitNumber
, используя значение переменной threeDigitNumber?
Предположим, пользователь ввел 1234. После считывания трех пер- вых цифр, значение переменной threeDigitNumber будет равно 123.
Значение, которое было бы записано в переменную fourDigitNumber — это 1230. Так как множители для переменной fourDigitNumber в 10 раз больше множителей для threeDigitNumber, первая переменная всегда будет в 10 раз больше второй. Таким образом, нам нужна только одна целочисленная переменная, так как вторая переменная может быть просто при необходимости умножена на 10:
cout << "Enter a three-digit or four-digit number: ";
char digitChar = cin.get();
int number = (digitChar — '0') * 100;
digitChar = cin.get();
number += (digitChar — '0') * 10;
digitChar = cin.get();
number += (digitChar — '0');
digitChar = cin.get();
if (digitChar == 10) {
cout << "Number entered: " << number << "\n";
} else {
number = number * 10 + (digitChar — '0');
cout << "Number entered: " << number << "\n";
}

Истинные головоломки 67
Теперь у нас есть пригодный для использования шаблон. Рассмо- трите расширение этого кода для обработки пятизначных чисел. По- сле вычисления значения первых четырех цифр мы повторим тот же процесс, который использовали для вычисления четвертой цифры, вместо отображения результата, а именно: прочитаем пятый символ, проверим, является ли этот символ символом конца строки, и если так, то отобразим вычисленное значение, а в противном случае выполним умножение на 10 и прибавим цифровое значение текущего символа:
cout << "Enter a number with three, four, or ve digits: ";
char digitChar = cin.get();
int number = (digitChar — '0') * 100;
digitChar = cin.get();
number += (digitChar — '0') * 10;
digitChar = cin.get();
number += (digitChar — '0');
digitChar = cin.get();
if (digitChar == 10) {
cout << "Number entered: " << number << "\n";
} else {
number = number * 10 + (digitChar — '0');
digitChar = cin.get();
if (digitChar == 10) {
cout << "Number entered: " << number << "\n";
} else {
number = number * 10 + (digitChar — '0');
cout << "Number entered: " << number << "\n";
}
}
На данном этапе мы запросто смогли бы расширить этот код для обработки шестизначных чисел или чисел с меньшим количеством знаков. Шаблон вполне ясен: если следующий символ — это еще одна цифра, то умножить текущее общее значение на 10 и прибавить це- лочисленное цифровое значение этого символа. Поняв эту логику, мы можем написать цикл для обработки числа любой длины:
cout << "Enter a number with as many digits as you like: ";
X char digitChar = cin.get();
Y int number = (digitChar — '0');
Z digitChar = cin.get();
while
[ (digitChar != 10) {
\ number = number * 10 + (digitChar — '0');
] digitChar = cin.get();
}
^ cout << "Number entered: " << number << "\n";
Здесь мы считываем первый символ
X
и определяем его цифро- вое значение
Y
. Затем мы считываем второй символ
Z
и попадаем в цикл, в котором проверяем, не является ли только что прочитанный символ символом конца строки
[
. Если не является, мы умножаем текущее общее значение в цикле на 10 и добавляем цифровое значе- ние
\
текущего символа перед считыванием следующего символа
]
Когда достигается конца строки, переменная number уже содержит значение, которое мы можем распечатать на экране
^