ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 433
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
54 Глава 2
Табл. 2.2. Коды символов и требуемые целочисленные значения
q,"%
j% “,"%=
Š!K3% %
p=ƒ…, =
0 48 0
48 1
49 1
48 2
50 2
48 3
51 3
48 4
52 4
48 5
53 5
48 6
54 6
48 7
55 7
48 8
56 8
48 9
57 9
48
Разница между кодом символа и требуемым целым числом всег- да 48, следовательно, нам нужно вычесть это значение. Вы, возмож- но, обратили внимание, что это код символа — 0. Это всегда будет так, потому, что все системы кодировки символов всегда хранят сим- волы цифр в порядке возрастания, начиная с 0. Таким образом, мы можем создать более общее и более удобочитаемое решение, вычи- тая символ 0, а не используя некое предустановленное значение, ка- ковым является 48:
char digit;
cout << "Enter a one-digit number: ";
cin >> digit;
int sum = digit — '0';
cout << "Is the sum of digits " << sum << "? \n";
Теперь мы можем перейти дальше к выяснению, какие именно цифры нужно умножить на 2. Эта часть проблемы может потребо- вать несколько шагов, прежде чем мы решим ее. Поэтому давайте попробуем упростить проблему. Что если бы мы изначально огра- ничили себя номером фиксированной длины? Это помогло бы под- твердить наше понимание общей формулы и продвинуться к окон- чательной цели. Давайте попробуем ограничить длину до шести, это достаточно длинный номер, который позволит представить общую сложность задачи.
: $ " " # % ,
'
Напишите программу, которая принимала бы идентификационный номер (и его прове- рочную цифру) длиной шесть цифр и определяла бы по формуле Луна, действителен ли номер. Программа должна обрабатывать каждый символ перед чтением следующего.
Как и прежде, мы можем еще упростить задачу, чтобы облег- чить начало работы настолько, насколько это вообще возможно.
Что если мы изменим формулу так, что ни одна из цифр не удваи- вается? Тогда программе остается лишь считывать цифры и сумми- ровать их.
Истинные головоломки 55
: $ $ " " # ,
'
Напишите программу, которая принимала бы идентификационный номер (и его прове- рочную цифру) длиной шесть цифр и определяла бы по простой формуле, где значения всех цифр суммируются, а результат подвергается проверке на делимость на 10, что- бы сказать, действителен ли номер. Программа должна обрабатывать каждый символ перед чтением следующего.
Поскольку мы знаем, как считывать отдельные цифры в виде сим- волов, то можем довольно легко решить эту задачу с простой контроль- ной суммой и числом фиксированной длины. Нам нужно лишь считать шесть цифр, сложить их и определить, делится ли сумма на 10.
char digit;
int checksum = 0;
cout << "Enter a six-digit number: ";
for (int position = 1; position <= 6; position ++) {
cin >> digit;
checksum += digit — '0';
}
cout << "Checksum is " << checksum << ". \n";
if (checksum % 10 == 0) {
cout << "Checksum is divisible by 10. Valid. \n";
} else {
cout << "Checksum is not divisible by 10. Invalid. \n";
}
На этом этапе нам нужно добавить программную логику, которая бы действительно проверяла формулу Луна, что значит умножение на 2 каждой второй цифры, начиная со второй цифры справа. Так как в настоящий момент мы ограничили себя шестизначными номе- рами, нам нужно удвоить цифры в позициях один, три и пять, считая слева. Иными словами, мы умножаем цифру на 2, если находится в нечетной позиции. Мы можем различить четные и нечетные пози- ции с помощью оператора деления с остатком (%), поскольку число считается по определению четным, если делится на два без остатка.
Таким образом, если результат выражения position % 2 равен 1, значит, position — нечетное число — и мы должны его удвоить. Сле- дует помнить, что в данном контексте удвоить значит не только ум- ножение цифры на два, но и сложение цифр получившегося числа, если это число больше или равно 10. В этом нам поможет предыду- щая функция. Когда по формуле Луна нужно удвоить цифру, мы про- сто передаем эту цифру нашей функции и пользуемся возвращенным результатом. Обобщив все вышесказанное, нам остается лишь изме- нить код цикла for из предыдущего листинга:
for (int position = 1; position <= 6; position ++) {
cin >> digit;
if (position % 2 == 0) checksum += digit — '0';
else checksum += doubleDigitValue(digit — '0');
}
56 Глава 2
К этому моменту мы многого достигли на пути решения этой за- дачи, но предстоит сделать еще пару шагов, прежде чем мы сможем написать код для идентификационных номеров произвольной дли- ны. Чтобы окончательно решить эту проблему, мы должны последо- вать правилу «разделяй и властвуй». Предположим, я попросил вас изменить код выше для работы с номерами длиной 10 или 16 цифр.
Эта задача была бы тривиальной: вам понадобилось бы лишь заме- нить число 6, использованное в качестве верхнего предела цикла, на другое значение. Но предположим, что я попросил вас проверить семизначные номера. Это потребовало бы некоторого дополнитель- ного изменения, так как если количество цифр нечетное и мы удва- иваем каждую вторую цифру, начиная со второй цифры справа, то первая цифра слева уже не будет удваиваться. В этом случае вам нуж- но удвоить четные позиции: 2, 4, 6 и так далее. Отложив ненадолго этот вопрос, давайте разберемся, каким образом нам обрабатывать номера четной длины.
Первая сложность, с которой мы сталкиваемся, — это определе- ние того, что мы достигли конца номера. Если пользователь вводит многозначное число и нажимает клавишу Enter, а мы считываем ввод цифра за цифрой, какой символ считывается после последней цифры? На самом деле это зависит от операционной системы, но мы лишь напишем экспериментальный код:
cout << "Enter a number: ";
char digit;
while (true) {
digit = cin.get();
cout << int(digit) << " ";
}
Цикл выполняется бесконечно, но делает свою работу. Я ввел но- мер 1234 и нажал клавишу Enter. Результатом было 49 50 51 52 10
(на основе ASCII, это будет зависеть от операционной системы). Та- ким образом, 10 — это то, что я ищу. Вооружившись этой информаци- ей, мы можем заменить цикл for в предыдущем коде на цикл while:
char digit;
int checksum = 0;
X int position = 1;
cout << "Enter a number with an even number of digits: ";
Y digit = cin.get();
while
Z(digit != 10) {
[ if (position % 2 == 0) checksum += digit — '0';
else checksum += doubledDigitValue(digit — '0');
\ digit = cin.get();
] position++;
}
cout << "Checksum is " << checksum << ". \n";
if (checksum % 10 == 0) {
cout << "Checksum is divisible by 10. Valid. \n";
} else {
cout << "Checksum is not divisible by 10. Invalid. \n";
}
Истинные головоломки 57
В этом коде position больше не является управляющей перемен- ной цикла for, значит, мы должны отдельно ее инициализировать
X
и постепенно увеличивать
]
. Теперь циклом управляет условное выражение
Z
, сверяющее ввод с кодом символа конца строки. Так как мы имеем значение для проверки при первом проходе по циклу, то считываем первое значение перед началом цикла
Y
и затем каж- дое последующее значение внутри цикла
\
, после обрабатывающего кода.
Повторюсь, этот код обработает номер любой четной длины.
Для обработки номера нечетной длины нам потребовалось бы толь- ко изменить обрабатывающий код, обратив логику условия инструк- ции if
[
, чтобы удваивать числа в четных позициях, а не в нечетных.
Это наконец охватывает все возможности. Длина идентификаци- онного номера может быть либо четной, либо нечетной. Если бы мы заранее знали длину номера, то знали бы, удваивать ли нам четные или нечетные позиции числа. Однако у нас нет такой информации до тех пор, пока мы не достигли конца числа. Неужели, учитывая все ограничения, решение проблемы невозможно? Если мы знаем, как решить эту проблему для нечетного количества цифр и для четного, но не знаем количество цифр в номере до тех пор, пока полностью не прочитаем число, как мы можем решить эту проблему?
Возможно, вы уже видите ответ для этой задачи. Если нет, то это не потому, что ответ сложен, а потому, что он спрятан в деталях. Чем мы могли бы воспользоваться здесь, так это аналогия, но мы еще не сталкивались с аналогичными ситуациями. Вместо этого мы созда- дим собственную аналогию. Давайте сформулируем задачу, явно по- священную этой самой ситуации, и посмотрим, будет ли нам полезно взглянуть проблеме прямо в глаза. Отчистите свое сознание от кон- цепций, сложившихся у вас на основе проведенной работы, и прочи- тайте условие следующей задачи.
: &
Напишите программу, которая считывала бы 10 целых чисел пользователя. По окон- чании ввода всех чисел пользователь может попросить отобразить количество положи- тельных и количество отрицательных чисел.
Это простая задача, которая, кажется, не должна вызывать ка- ких-либо сложностей. Нам понадобится лишь две переменных: одна для подсчета положительных чисел и еще одна для подсчета отри- цательных чисел. Когда пользователь уточняет запрос в конце про- граммы, то для ответа на этот запрос нужно лишь воспользоваться соответствующей переменной:
int number;
int positiveCount = 0;
int negativeCount = 0;
for (int i = 1; i <= 10; i++) {
58 Глава 2
cin >> number;
if (number > 0) positiveCount++;
if (number < 0) negativeCount++;
}
char response;
cout << "Do you want the (p)ositive or (n)egative count? ";
cin >> response;
if (response == 'p')
cout << "Positive count is " << positiveCount << "\n";
if (response == 'n')
cout << "Negative count is " << negativeCount << "\n";
Пример демонстрирует метод, который нам необходимо исполь- зовать для решения проблемы контрольной суммы Луна: одновре- менно отслеживать увеличивающуюся контрольную сумму обоими способами, как будто бы введенный номер имеет нечетную длину и одновременно четную. Когда мы дойдем до конца числа и узнаем действительную длину, у нас будет правильная контрольная сумма в одной или другой переменной.
Соберем все детали вместе
Мы уже поставили галочки напротив всех пунктов нашего изначаль- ного списка задач. Теперь пришло время собрать все вместе и ре- шить эту задачу. Так как мы уже по отдельности решили все подза- дачи и знаем точно, что нужно делать, то можем использовать для справки предыдущие программы для быстрого достижения конеч- ного результата:
char digit;
int oddLengthChecksum = 0;
int evenLengthChecksum = 0;
int position = 1;
cout << "Enter a number: ";
digit = cin.get();
while (digit != 10) {
if (position % 2 == 0) {
oddLengthChecksum += doubleDigitValue(digit — '0');
evenLengthChecksum += digit — '0';
} else {
oddLengthChecksum += digit — '0';
evenLengthChecksum += doubleDigitValue(digit — '0');
}
digit = cin.get();
position++;
}
int checksum;
X if ((position — 1) % 2 == 0) checksum = evenLengthChecksum;
else checksum = oddLengthChecksum;
cout << "Checksum is " << checksum << ". \n";
if (checksum % 10 == 0) {
cout << "Checksum is divisible by 10. Valid. \n";
} else {
cout << "Checksum is not divisible by 10. Invalid. \n";
}
Обратите внимание, что при проверке четности или нечетности длины введенного номера
X
мы вычитаем 1 из position. Делаем мы
Истинные головоломки 59
это потому, что последний считываемый символ в цикле — это сим- вол конца строки, а не последняя цифра номера. Мы также могли бы написать такое проверочное выражение — (position % 2 == 1), но оно сложнее для восприятия. Иными словами, проще сказать «если position — 1
— четное число, использовать четную контрольную сум- му», нежели сказав «если position — нечетное число, использовать четную контрольную сумму», помнить, почему это правильно.
Пока что это самый длинный из всех листингов, которые мы с вами видели, но у меня нет необходимости делать аннотации ко всем участком кода и описывать, как работает каждый блок, так как вы уже видели работу этих блоков по отдельности. И в этом большой плюс плана. Впрочем, следует отметить, что мой план необязательно будет вашим. Вероятно, те сложности, что я увидел в условии исход- ной задачи, и шаги, которые я предпринял, чтобы решить эту задачу, отличаются от того, что бы увидели и сделали вы. Ваш программист- ский опыт и те проблемы, которые вы успешно решили, определя- ют, какие из частей этой задачи для вас тривиальны, а какие сложны, а следовательно и то, какие шаги вам нужно предпринять для реше- ния этой задачи. В предыдущем разделе мог быть такой момент, ког- да шаг, предпринятый мною, казался вам лишним отклонением для выяснения чего-то, что уже очевидно для вас. И наоборот, возможно был такой момент, когда я в спешке пропустил что-то сложное для вас. Кроме того, если бы вы решали эту задачу самостоятельно, воз- можно, ваша программа была бы столь же успешной, но значитель- но отличающейся от моей. Нет «правильных» решений проблемы, если любая программа, соответствующая ограничениям, считается решением, а для каждого решения отсутствует «правильный» путь достижения.
Просмотрев все шаги для решения задачи и учитывая относи- тельную краткость кода, вы, возможно, захотите редуцировать ка- кие-либо шаги в собственном процессе решения проблем. Я бы предупредил вас об опасности этого позыва. Всегда лучше сделать больше шагов, чем пытаться сделать слишком многое за один шаг, даже если какие-то из шагов кажутся чересчур тривиальными. Пом- ните о целях решения проблем. Главная цель, разумеется, — найти программное решение, которое решало бы поставленную задачу и соответствовало бы всем ограничениям. Второстепенная цель — найти такое программное решение за кратчайшее время. Минимиза- ция количества шагов не является целью, и никто не должен знать, сколько шагов вы сделали. Представьте, что вам нужно подняться на вершину крутого холма, и к этой вершине есть пологая, но длинная и извилистая тропа. Невнимание к тропе и восхождение на склон напрямую с подножья формально потребует меньше шагов, чем путь по тропе, но будет ли такое восхождение более быстрым? Наиболее вероятный результат такого прямого восхождения — вы просто упа- дете и сдадитесь.
1 2 3 4 5 6 7 8 9 10 ... 34
60 Глава 2
Также вспомните последнее из моих правил решения проблем: не
расстраивайтесь. Чем больше вы пытаетесь сделать за один шаг, тем на- стойчивее вы приглашаете в гости потенциальное расстройство. Даже если вы отступитесь от сложного шага и разобьете его на несколько подшагов, вред все равно будет нанесен, так как психологически вы бу- дете ощущать, что движетесь назад, вместо того, чтобы двигаться впе- ред. Когда я обучаю начинающих программистов пошаговому подходу, иногда находится студент, который жалуется: «Эй, этот шаг слишком прост», на что я отвечаю: «На что ты жалуешься?» Если изначально за- дача выглядела сложной, но вы разбили ее на несколько частей, так, что каждая часть кажется легко решаемой, я скажу вам: «Мои поздрав- ления! Это именно то, на что вы должны надеяться».
Отслеживание состояния
Последняя задача, которую мы рассмотрим в этой главе, также и са- мая сложная. Эта задача состоит из большого количества различных частей и имеет запутанное описание, что проиллюстрирует важ- ность разбиения сложной проблемы.
: !
Некое сообщение было закодировано в виде текстового потока, который должен быть прочитан символ за символом. Поток содержит последовательность целых чисел, раз- деленных запятыми. Каждое из этих чисел — положительное целое, которое может быть представлено типом int языка С++. Однако то, какой символ, представлен тем или иным целым числом, зависит от текущего режима декодирования. Всего существу- ет три режима: верхний регистр, нижний регистр и пунктуация.
В режиме верхнего регистра каждое целое число представляет прописную букву: целое число, взятое по модулю 27, означает букву алфавита (где 1 = A и так далее). Таким образом, введенное значение 143 в режиме верхнего регистра будет означать букву
H, так как 143 по модулю 27 равняется 8, а H — восьмая буква латинского алфавита.
Режим нижнего регистра работает аналогичным образом, но со строчными буквами: оста- ток от деления целого числа на 27 представляет строчную букву (где 1 = a и так далее).
Таким образом, введенное значение 56 в режиме верхнего регистра будет означать букву b, так как 56 по модулю 27 равняется 2, а b — вторая буква латинского алфавита.
В режиме пунктуации целое число уже берется по модулю 9 и согласно интерпретации в приведенной ниже табл. 2.3. Таким образом, 19 по модулю 9 будет означать вос- клицательный знак, так как 19 по модулю 9 равняется 1.