ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 437
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
68 Глава 2
Вышеприведенный код обрабатывает преобразование одного набора символов в соответствующие целочисленные эквиваленты.
В финальной версии программы мы будем считывать наборы чисел, разделенные запятыми. Каждое число должно быть отдельно счи- тано и обработано. Как всегда лучше всего начать с размышления о простой ситуации, которая позволяет продемонстрировать пробле- му. Давайте рассмотрим ввод 101,22[EOL], где [EOL] для большей яс- ности явно означает конец строки. Этого нам будет достаточно для изменения условия цикла для проверки ввода запятой или символа конца строки. Затем нам потребовалось бы поместить код, обраба- тывающий одно число внутрь большего цикла, повторяющегося до тех пор, пока не будут прочитаны все числа. Таким образом, выпол- нение внутреннего цикла должно прерываться запятой или [EOL], тогда как выполнение внешнего цикла — только [EOL]:
X char digitChar;
do {
digitChar = cin.get();
int number = (digitChar — '0');
digitChar = cin.get();
while ((digitChar != 10) && (digitChar != ',')) {
number = number * 10 + (digitChar — '0');
digitChar = cin.get();
}
cout << "Number entered: " << number << "\n";
} while
Y (digitChar != 10);
Это еще один замечательный пример того, как важны малень- кие шаги. Несмотря на то, что это лишь короткая программа, ее хи- тросплетенная природа со вложенным циклом сделала бы написа- ние такого кода довольно сложной задачей, попытайся мы написать эту программу с нуля. Впрочем, программа становится вполне пря- молинейной, когда мы приходим к этому коду, делая шаг вперед от предыдущей программы. Объявление переменной char digitChar
X
перенесено на отдельную строку, таким образом, что эта перемен- ная остается видимой для всех участков кода. Оставшаяся часть кода идентичная предыдущему листингу за тем лишь исключением, что этот код помещен внутрь цикла do-while, выполнение которого про- должается до тех пор, пока мы не достигаем конца строки
Y
Разобравшись с этой частью решения, мы можем сконцентриро- ваться на обработке отдельных чисел. Следующий элемент нашего списка — преобразование числа в диапазоне 1 — 26 в букву A-Z. Если вы попробуете решить эту задачу, то обнаружите, что этот процесс абсолютно противоположен тому процессу, который мы использо- вали для отдельных символов цифр в соответствующие целочислен- ные эквиваленты. Если мы можем извлечь код символа 0 для перево- да этого символа из символьного диапазона 0 — 9 в целочисленный диапазон 0 — 9, значит, мы сможем прибавить символьный код для перевода 1 — 26 в A-Z. Что произойдет, если мы прибавили 'A'? Ниже приведена эта попытка, а также пример ввода и вывода:
Истинные головоломки 69
cout << "Enter a number 1-26: ";
int number;
cin >> number;
char outputCharacter;
outputCharacter =
X number + 'A';
cout << "Equivalent symbol: " << outputCharacter << "\n";
Enter a number 1-26:
5
Equivalent letter:
F
Что-то пошло не так… Пятая буква латинского алфавита — E, а не F. Проблема в том, что мы прибавляем число из диапазона, на- чинающегося с 1. Когда мы совершали преобразования в обратном направлении, конвертируя символы цифр в целочисленные эквива- ленты, мы работали с диапазоном, начинающимся с 0. Мы можем это исправить, изменив арифметическое выражение
X
с number +
'A'
на number + 'A' — 1. Обратите внимание, что мы могли бы про- сто посмотреть код символа буквы А (в кодировке ASCII это 65) и использовать значение на один меньше (например, number + 64 в кодировке ASCII). Однако я предпочитаю первую версию, так как она более удобочитаема. Иными словами, если позже вы вернетесь и просмотрите этот код, то вы быстрее вспомните, что означает вы- ражение number + 'A' — 1, чем number + 64, так как присутствие символа 'A' в первом выражении напомнит вам о преобразовании в символы верхнего регистра.
Разобравшись в этом, мы запросто можем адаптировать эту идею для преобразования в символы нижнего регистра, изменив арифме- тическое выражение
X
на number + 'a'-1. Преобразование таблицы пунктуационных символов не столь же компактно, так как символы пунктуации не появляются в таком порядке ни в таблице ASCII, ни в любой другой системе кодировки символов. Поэтому нам придется решить этот вопрос в лоб:
cout << "Enter a number 1-8: ";
int number;
cin >> number;
char outputCharacter;
X switch (number) {
case 1: outputCharacter = '!'; break;
case 2: outputCharacter = '?'; break;
case 3: outputCharacter = ','; break;
case 4: outputCharacter = '.'; break;
case 5: outputCharacter = ' '; break;
case 6: outputCharacter = ';'; break;
case 7: outputCharacter = '"'; break;
case 8: outputCharacter =
Y '\''; break;
}
cout << "Equivalent symbol: " << outputCharacter << "\n";
Здесь мы используем инструкцию switch
X
для вывода коррект- ного знака пунктуации. Обратите внимание, что для отображения символа одинарной кавычки
Y
мы использовали обратный слеш в качестве знака перехода.
70 Глава 2
Перед тем как мы соберем все вместе, осталось решить лишь одну подзадачу: переключение между режимами каждый раз, ког- да последнее введенное значение декодируется в 0. Вспомните, что условие задачи требует, чтобы мы брали целочисленное значе- ние по модулю 27 (если программа в настоящий момент находит- ся в режиме верхнего или нижнего регистра) или 9 (если програм- ма в режиме пунктуации). Когда результат операции равен 0, мы переключаемся к следующему режиму. Что нам потребуется, так это переменная, которая будет хранить текущий режим, а также некую логику внутри цикла «чтение и обработка следующего зна- чения» для переключения режимов при необходимости. Перемен- ная, отслеживающая текущий режим, может быть простым целым числом, но если мы воспользуемся для этих целей перечислением, код будет более удобочитаемым. На заметку: если переменная ис- пользуется только для отслеживания состояния, и ни у одного из значений нет присущего смысла, то лучше использовать перечис- ление. В этом случае мы могли бы объявить переменную int mode, скажем, значение 1 которой означало бы верхний регистр, 2 — ниж- ний регистр, а 3 — режим пунктуации. Однако в том, почему имен- но эти значения были выбраны для этих режимов, нет никакого скрытого смысла. Когда мы вернемся к этому коду позже, нам при- дется вспомнить, что значат некоторые инструкции, например if
(mode==2)
. Если мы воспользуемся перечислением, как в инструк- ции (mode == LOWERCASE), то ничего не придется вспоминать, так как все и так написано. Далее приведен код, являющийся резуль- татом вышеприведенных рассуждений, а также образец общения пользователя с программой:
enum modeType {UPPERCASE, LOWERCASE, PUNCTUATION};
int number;
modeType mode = UPPERCASE;
cout << "Enter some numbers ending with -1: ";
do {
cin >> number;
cout << "Number read: " << number;
switch (mode) {
case UPPERCASE:
number = number % 27;
cout << ". Modulo 27: " << number << ". ";
if (number == 0) {
cout << "Switch to LOWERCASE";
mode = LOWERCASE;
}
break;
case LOWERCASE:
number = number % 27;
cout << ". Modulo 27: " << number << ". ";
if (number == 0) {
cout << "Switch to PUNCTUATION";
mode = PUNCTUATION;
}
break;
case PUNCTUATION:
Истинные головоломки 71
number = number % 9;
cout << ". Modulo 9: " << number << ". ";
if (number == 0) {
cout << "Switch to UPPERCASE";
mode = UPPERCASE;
}
break;
}
cout << "\n";
} while (number != -1);
Enter some numbers ending with -1:
2 1 0 52 53 54 55 6 7 8 9 10 -1
Number read: 2. Modulo 27: 2.
Number read: 1. Modulo 27: 1.
Number read: 0. Modulo 27: 0. Switch to LOWERCASE
Number read: 52. Modulo 27: 25.
Number read: 53. Modulo 27: 26.
Number read: 54. Modulo 27: 0. Switch to PUNCTUATION
Number read: 55. Modulo 9: 1.
Number read: 6. Modulo 9: 6.
Number read: 7. Modulo 9: 7.
Number read: 8. Modulo 9: 8.
Number read: 9. Modulo 9: 0. Switch to UPPERCASE
Number read: 10. Modulo 27: 10.
Number read: -1. Modulo 27: -1.
Мы вычеркнули все пункты нашего списка, поэтому настало время интегрировать эти отдельные листинги кода для создания решения всей программы. Мы могли бы подойти к такой интегра- ции по-разному. Мы могли бы совместить два фрагмента кода и по- строить решение на их основе. Например, можно объединить код для чтения и преобразования чисел, разделенных запятыми, с ко- дом для переключения режимов из крайнего листинга. После этого мы могли бы протестировать интеграцию и добавить код для пре- образования каждого числа в соответствующую букву. Или же мож- но пойти другим путем: превратить листинг с преобразованием чи- сел в символы в несколько функций, которые мы вызывали бы из главной программы. На этом этапе мы уже перешли от решения за- дачи к проблемам технологий разработки программного обеспече- ния, а это совсем другая тема. Мы создали несколько блоков, что было сложной частью, а сейчас нужно лишь собрать их, как пока- зано на рис. 2.5.
Практически каждая строка этой программы была взята из пре- дыдущих листингов, приведенных в этом разделе. Каркас кода X взята из программы, переключающей режимы. Центральный об- рабатывающий цикл Y позаимствован из нашего кода для считы- вания последовательности чисел, разделенных запятыми. Наконец вы узнаете код, преобразующий целые числа в буквы верхнего и нижнего регистра и знаки пунктуации [. Небольшое количество нового кода отмечено меткой Z. Инструкции continue переносят нас на следующую итерацию цикла, когда последний введенный символ был распознан как команда переключения режимов, пропу- ская строку cout << outputCharacter в конце цикла.
72 Глава 2
Рис. 2.5. Собранное решение задачи «Декодировать сообщение»
Истинные головоломки 73
Несмотря на то, что это «копипаста», это хорошая разновид- ность «копипасты»: вы повторно используете код, который на- писали сами, и поэтому полностью понимаете его. Как и раньше, подумайте о том, насколько легок был каждый шаг в процессе ре- шения задачи по сравнению с попыткой написать окончательный листинг сразу с нуля. Вне всяких сомнений, хороший програм- мист должен писать окончательный листинг без необходимости выполнения промежуточных шагов но в таком случае были бы неправильные шаги, иногда код выглядит уродливо, строки кода закомментированы, а потом возвращены в программу. Благодаря маленьким шагам, мы заранее выполняем всю грязную работу, а код никогда не выглядит уродливо, так как код, над которым мы работаем в настоящее время, никогда не будет слишком длинным или запутанным.
Заключение
В этой главе мы изучили три задачи. В некотором смысле нам по- требовалось пройти три разных пути для их решения. С другой точки зрения, мы проходили один и тот же маршрут каждый раз, потому что мы использовали одну и ту же базовую технику разби- ения проблемы на компоненты, написания кода для решения этих компонентов по отдельности, а затем использования знаний, по- лученных при написании программ, или даже прямого использо- вания строк кода из этих программ для решения исходной задачи.
В последующих главах мы не будем явно использовать этот метод при решении каждой задачи, но эта основная идея будет присут- ствовать всегда: разрубить задачу на куски, с которыми можно спра- виться.
В зависимости от вашего опыта эти задачи изначально могут показаться вам лежащими в любом участке диапазона сложности: от очень сложных до тривиальных. Вне зависимости от того, на- сколько сложной задача может показаться изначально, я бы реко- мендовал вам использовать эту технику с каждой задачей, с кото- рой вы сталкиваетесь. Не нужно дожидаться встречи с безнадежно сложной задачей, чтобы опробовать эту новую технику. Помните, что одна из целей этой книги — развить вас уверенность в своих способностях решить любую задачу. Попрактикуйтесь в использо- вании этих техник на «простых» задачах — и у вас будет много энер- гии, когда вы повстречаетесь со сложными.
Упражнения
Как и прежде, я настоятельно рекомендую вам сделать столько упражнений, сколько сможете. Теперь, когда мы полностью вовле- клись в настоящее программирование, проработка этих упражне- ний необходима вам для развития ваших навыков решения задач.
74 Глава 2
2.1.
Используя только инструкции вывода одного символа, которые выводят на экран символ #, пробел или конец строки, напишите программу, которая распечатывает следующую фигуру:
########
######
####
##
2.2.
Или как насчет такой?
##
####
######
########
########
######
####
##
2.3.
А вот особенно сложная:
# #
## ##
### ###
########
########
### ###
## ##
# #
2.4.
Создайте свою собственную фигуру: Придумайте свою собствен- ную симметричную фигуру из символов # и проверьте, сможете ли вы написать программу, которая следует правилам программ с фигурами.
2.5.
Если вам понравилась задача с формулой Луна, попробуйте на- писать программу для другой системы с проверочной цифрой, например для 13-значной системы ISBN. Программа должна принимать идентификационный номер и верифицировать его либо принимать номер без проверочной цифры и генерировать такую цифру.
2.6.
Если вы изучали двоичные числа и знаете, как преобразовывать десятичные числа в двоичные и наоборот, попробуйте написать программу для выполнения таких преобразований. При этом чис- ла должны быть неограниченной длины (но вы можете предполо- жить, что числа должны быть достаточно небольшими, чтобы их можно было сохранить в стандартной переменной int языка С++).
2.7.
Вы изучали шестнадцатеричные числа? Попробуйте написать программу, которая позволяет пользователю ввести двоичное, десятичное или шестнадцатеричное число и вывести все три ва- рианта.
2.8.
Хотите дополнительный вызов? Обобщите код предыдущего упражнения для создания программы, конвертирующей любое число с базисом 16 или меньше в число с любым другим базисом.
Так, например, программа должна смочь преобразовать число с базисом 9 в число с базисом 4.
2.9.
Напишите программу, которая считывала бы строку текста, под- считывая количество слов и вычисляя длину самого длинного слова, наибольшее количество гласных букв в слове и/или лю- бую другую статистику, какую вы можете себе представить.
76 Глава 3
В предыдущей главе мы ограничи- лись скалярными переменными , то есть переменными, которые могут одно- временно хранить только одно значение.
В этой главе мы рассмотрим задачи, в которых используется самый популярный агрегированный тип данных — массив. Несмотря на то, что массивы — это простые структуры с некоторыми фундаменталь- ными ограничениями, их использование значительно увеличивает мощь наших программ.
В этой главе мы в первую очередь будем иметь дело с истинными массивами, то есть массивами, объявляемыми с помощью встроен- ного синтаксиса языка С++, например так:
int tenIntegerArray[10];
Однако обсуждаемые техники также хорошо применимы и к структурам данных с подобными атрибутами. Наиболее часто встре-
+ " "
3
Решение задач с массивами 77
чающаяся разновидность таких структур данных — вектор. Термин
вектор зачастую используется в качестве синонима одномерного мас- сива, но мы будем использовать его более конкретно: для обозначе- ния структуры с атрибутами массива без указания максимального ко- личества элементов. Таким образом, в обсуждениях мы согласимся, что массив имеет фиксированный размер, тогда как размер вектора может увеличиваться или уменьшаться автоматически при необхо- димости. В каждой из обсуждаемых в этой главе задач будет некое ограничение, которое позволит использовать структуру с фиксиро- ванным количеством элементов. Задачи без таких ограничений мо- гут быть адаптированы для использования векторов.
Более того, техники, используемые для массивов, могут зачастую также использоваться для структур данных, не обладающих каждым из вышеперечисленных свойств. Так, например, некоторые техни- ки не требуют случайного доступа, то есть они могут использоваться применительно к таким структурам, как связанные списки. Массивы очень часто встречаются в программировании, и техники работы с ними используются и в других областях, поэтому это хороший тре- нировочный полигон для изучения решения задач со структурами данных.
Обзор основных свойств массивов
Вы уже должны знать, что такое массив, но давайте все же для боль- шей ясности пробежимся по его основным свойствам. Массив —это набор переменных одного типа, собранных под одним именем, где отдельные переменные обозначаются числом. Мы называем отдель- ные переменные элементами массива. В С++ и большинстве других языков первый элемент имеет порядковый номер 0, но в некоторых языках ситуация может быть иной.
Основные свойства массива следуют сразу из его определения.
Все значения, сохраненные в массиве, имеют один тип, тогда как агрегированные структуры данных могут хранить значения разных типов. Доступ к отдельному элементу осуществляется через порядко- вый номер, называемый индексом. В других разновидностях структур данных доступ к отдельному элементу может осуществляться по име- ни или ключевому значению.
Из этих основных свойств мы можем вывести несколько вторич- ных. Так как каждый элемент обозначается собственным порядко- вым номером, начиная с 0, мы можем с легкостью узнать все значе- ния, сохраненные в массиве. В структурах данных других типов это может быть сложно, неэффективно или даже невозможно. Кроме того, тогда как к элементам некоторых структур данных, например связанных списков, доступ может быть получен только последова- тельно, массивы предлагают случайный доступ, таким образом, мы можем получить доступ к любому элементу в любое время.
Вышеприведенный код обрабатывает преобразование одного набора символов в соответствующие целочисленные эквиваленты.
В финальной версии программы мы будем считывать наборы чисел, разделенные запятыми. Каждое число должно быть отдельно счи- тано и обработано. Как всегда лучше всего начать с размышления о простой ситуации, которая позволяет продемонстрировать пробле- му. Давайте рассмотрим ввод 101,22[EOL], где [EOL] для большей яс- ности явно означает конец строки. Этого нам будет достаточно для изменения условия цикла для проверки ввода запятой или символа конца строки. Затем нам потребовалось бы поместить код, обраба- тывающий одно число внутрь большего цикла, повторяющегося до тех пор, пока не будут прочитаны все числа. Таким образом, выпол- нение внутреннего цикла должно прерываться запятой или [EOL], тогда как выполнение внешнего цикла — только [EOL]:
X char digitChar;
do {
digitChar = cin.get();
int number = (digitChar — '0');
digitChar = cin.get();
while ((digitChar != 10) && (digitChar != ',')) {
number = number * 10 + (digitChar — '0');
digitChar = cin.get();
}
cout << "Number entered: " << number << "\n";
} while
Y (digitChar != 10);
Это еще один замечательный пример того, как важны малень- кие шаги. Несмотря на то, что это лишь короткая программа, ее хи- тросплетенная природа со вложенным циклом сделала бы написа- ние такого кода довольно сложной задачей, попытайся мы написать эту программу с нуля. Впрочем, программа становится вполне пря- молинейной, когда мы приходим к этому коду, делая шаг вперед от предыдущей программы. Объявление переменной char digitChar
X
перенесено на отдельную строку, таким образом, что эта перемен- ная остается видимой для всех участков кода. Оставшаяся часть кода идентичная предыдущему листингу за тем лишь исключением, что этот код помещен внутрь цикла do-while, выполнение которого про- должается до тех пор, пока мы не достигаем конца строки
Y
Разобравшись с этой частью решения, мы можем сконцентриро- ваться на обработке отдельных чисел. Следующий элемент нашего списка — преобразование числа в диапазоне 1 — 26 в букву A-Z. Если вы попробуете решить эту задачу, то обнаружите, что этот процесс абсолютно противоположен тому процессу, который мы использо- вали для отдельных символов цифр в соответствующие целочислен- ные эквиваленты. Если мы можем извлечь код символа 0 для перево- да этого символа из символьного диапазона 0 — 9 в целочисленный диапазон 0 — 9, значит, мы сможем прибавить символьный код для перевода 1 — 26 в A-Z. Что произойдет, если мы прибавили 'A'? Ниже приведена эта попытка, а также пример ввода и вывода:
Истинные головоломки 69
cout << "Enter a number 1-26: ";
int number;
cin >> number;
char outputCharacter;
outputCharacter =
X number + 'A';
cout << "Equivalent symbol: " << outputCharacter << "\n";
Enter a number 1-26:
5
Equivalent letter:
F
Что-то пошло не так… Пятая буква латинского алфавита — E, а не F. Проблема в том, что мы прибавляем число из диапазона, на- чинающегося с 1. Когда мы совершали преобразования в обратном направлении, конвертируя символы цифр в целочисленные эквива- ленты, мы работали с диапазоном, начинающимся с 0. Мы можем это исправить, изменив арифметическое выражение
X
с number +
'A'
на number + 'A' — 1. Обратите внимание, что мы могли бы про- сто посмотреть код символа буквы А (в кодировке ASCII это 65) и использовать значение на один меньше (например, number + 64 в кодировке ASCII). Однако я предпочитаю первую версию, так как она более удобочитаема. Иными словами, если позже вы вернетесь и просмотрите этот код, то вы быстрее вспомните, что означает вы- ражение number + 'A' — 1, чем number + 64, так как присутствие символа 'A' в первом выражении напомнит вам о преобразовании в символы верхнего регистра.
Разобравшись в этом, мы запросто можем адаптировать эту идею для преобразования в символы нижнего регистра, изменив арифме- тическое выражение
X
на number + 'a'-1. Преобразование таблицы пунктуационных символов не столь же компактно, так как символы пунктуации не появляются в таком порядке ни в таблице ASCII, ни в любой другой системе кодировки символов. Поэтому нам придется решить этот вопрос в лоб:
cout << "Enter a number 1-8: ";
int number;
cin >> number;
char outputCharacter;
X switch (number) {
case 1: outputCharacter = '!'; break;
case 2: outputCharacter = '?'; break;
case 3: outputCharacter = ','; break;
case 4: outputCharacter = '.'; break;
case 5: outputCharacter = ' '; break;
case 6: outputCharacter = ';'; break;
case 7: outputCharacter = '"'; break;
case 8: outputCharacter =
Y '\''; break;
}
cout << "Equivalent symbol: " << outputCharacter << "\n";
Здесь мы используем инструкцию switch
X
для вывода коррект- ного знака пунктуации. Обратите внимание, что для отображения символа одинарной кавычки
Y
мы использовали обратный слеш в качестве знака перехода.
70 Глава 2
Перед тем как мы соберем все вместе, осталось решить лишь одну подзадачу: переключение между режимами каждый раз, ког- да последнее введенное значение декодируется в 0. Вспомните, что условие задачи требует, чтобы мы брали целочисленное значе- ние по модулю 27 (если программа в настоящий момент находит- ся в режиме верхнего или нижнего регистра) или 9 (если програм- ма в режиме пунктуации). Когда результат операции равен 0, мы переключаемся к следующему режиму. Что нам потребуется, так это переменная, которая будет хранить текущий режим, а также некую логику внутри цикла «чтение и обработка следующего зна- чения» для переключения режимов при необходимости. Перемен- ная, отслеживающая текущий режим, может быть простым целым числом, но если мы воспользуемся для этих целей перечислением, код будет более удобочитаемым. На заметку: если переменная ис- пользуется только для отслеживания состояния, и ни у одного из значений нет присущего смысла, то лучше использовать перечис- ление. В этом случае мы могли бы объявить переменную int mode, скажем, значение 1 которой означало бы верхний регистр, 2 — ниж- ний регистр, а 3 — режим пунктуации. Однако в том, почему имен- но эти значения были выбраны для этих режимов, нет никакого скрытого смысла. Когда мы вернемся к этому коду позже, нам при- дется вспомнить, что значат некоторые инструкции, например if
(mode==2)
. Если мы воспользуемся перечислением, как в инструк- ции (mode == LOWERCASE), то ничего не придется вспоминать, так как все и так написано. Далее приведен код, являющийся резуль- татом вышеприведенных рассуждений, а также образец общения пользователя с программой:
enum modeType {UPPERCASE, LOWERCASE, PUNCTUATION};
int number;
modeType mode = UPPERCASE;
cout << "Enter some numbers ending with -1: ";
do {
cin >> number;
cout << "Number read: " << number;
switch (mode) {
case UPPERCASE:
number = number % 27;
cout << ". Modulo 27: " << number << ". ";
if (number == 0) {
cout << "Switch to LOWERCASE";
mode = LOWERCASE;
}
break;
case LOWERCASE:
number = number % 27;
cout << ". Modulo 27: " << number << ". ";
if (number == 0) {
cout << "Switch to PUNCTUATION";
mode = PUNCTUATION;
}
break;
case PUNCTUATION:
Истинные головоломки 71
number = number % 9;
cout << ". Modulo 9: " << number << ". ";
if (number == 0) {
cout << "Switch to UPPERCASE";
mode = UPPERCASE;
}
break;
}
cout << "\n";
} while (number != -1);
Enter some numbers ending with -1:
2 1 0 52 53 54 55 6 7 8 9 10 -1
Number read: 2. Modulo 27: 2.
Number read: 1. Modulo 27: 1.
Number read: 0. Modulo 27: 0. Switch to LOWERCASE
Number read: 52. Modulo 27: 25.
Number read: 53. Modulo 27: 26.
Number read: 54. Modulo 27: 0. Switch to PUNCTUATION
Number read: 55. Modulo 9: 1.
Number read: 6. Modulo 9: 6.
Number read: 7. Modulo 9: 7.
Number read: 8. Modulo 9: 8.
Number read: 9. Modulo 9: 0. Switch to UPPERCASE
Number read: 10. Modulo 27: 10.
Number read: -1. Modulo 27: -1.
Мы вычеркнули все пункты нашего списка, поэтому настало время интегрировать эти отдельные листинги кода для создания решения всей программы. Мы могли бы подойти к такой интегра- ции по-разному. Мы могли бы совместить два фрагмента кода и по- строить решение на их основе. Например, можно объединить код для чтения и преобразования чисел, разделенных запятыми, с ко- дом для переключения режимов из крайнего листинга. После этого мы могли бы протестировать интеграцию и добавить код для пре- образования каждого числа в соответствующую букву. Или же мож- но пойти другим путем: превратить листинг с преобразованием чи- сел в символы в несколько функций, которые мы вызывали бы из главной программы. На этом этапе мы уже перешли от решения за- дачи к проблемам технологий разработки программного обеспече- ния, а это совсем другая тема. Мы создали несколько блоков, что было сложной частью, а сейчас нужно лишь собрать их, как пока- зано на рис. 2.5.
Практически каждая строка этой программы была взята из пре- дыдущих листингов, приведенных в этом разделе. Каркас кода X взята из программы, переключающей режимы. Центральный об- рабатывающий цикл Y позаимствован из нашего кода для считы- вания последовательности чисел, разделенных запятыми. Наконец вы узнаете код, преобразующий целые числа в буквы верхнего и нижнего регистра и знаки пунктуации [. Небольшое количество нового кода отмечено меткой Z. Инструкции continue переносят нас на следующую итерацию цикла, когда последний введенный символ был распознан как команда переключения режимов, пропу- ская строку cout << outputCharacter в конце цикла.
72 Глава 2
Рис. 2.5. Собранное решение задачи «Декодировать сообщение»
Истинные головоломки 73
Несмотря на то, что это «копипаста», это хорошая разновид- ность «копипасты»: вы повторно используете код, который на- писали сами, и поэтому полностью понимаете его. Как и раньше, подумайте о том, насколько легок был каждый шаг в процессе ре- шения задачи по сравнению с попыткой написать окончательный листинг сразу с нуля. Вне всяких сомнений, хороший програм- мист должен писать окончательный листинг без необходимости выполнения промежуточных шагов но в таком случае были бы неправильные шаги, иногда код выглядит уродливо, строки кода закомментированы, а потом возвращены в программу. Благодаря маленьким шагам, мы заранее выполняем всю грязную работу, а код никогда не выглядит уродливо, так как код, над которым мы работаем в настоящее время, никогда не будет слишком длинным или запутанным.
Заключение
В этой главе мы изучили три задачи. В некотором смысле нам по- требовалось пройти три разных пути для их решения. С другой точки зрения, мы проходили один и тот же маршрут каждый раз, потому что мы использовали одну и ту же базовую технику разби- ения проблемы на компоненты, написания кода для решения этих компонентов по отдельности, а затем использования знаний, по- лученных при написании программ, или даже прямого использо- вания строк кода из этих программ для решения исходной задачи.
В последующих главах мы не будем явно использовать этот метод при решении каждой задачи, но эта основная идея будет присут- ствовать всегда: разрубить задачу на куски, с которыми можно спра- виться.
В зависимости от вашего опыта эти задачи изначально могут показаться вам лежащими в любом участке диапазона сложности: от очень сложных до тривиальных. Вне зависимости от того, на- сколько сложной задача может показаться изначально, я бы реко- мендовал вам использовать эту технику с каждой задачей, с кото- рой вы сталкиваетесь. Не нужно дожидаться встречи с безнадежно сложной задачей, чтобы опробовать эту новую технику. Помните, что одна из целей этой книги — развить вас уверенность в своих способностях решить любую задачу. Попрактикуйтесь в использо- вании этих техник на «простых» задачах — и у вас будет много энер- гии, когда вы повстречаетесь со сложными.
Упражнения
Как и прежде, я настоятельно рекомендую вам сделать столько упражнений, сколько сможете. Теперь, когда мы полностью вовле- клись в настоящее программирование, проработка этих упражне- ний необходима вам для развития ваших навыков решения задач.
74 Глава 2
2.1.
Используя только инструкции вывода одного символа, которые выводят на экран символ #, пробел или конец строки, напишите программу, которая распечатывает следующую фигуру:
########
######
####
##
2.2.
Или как насчет такой?
##
####
######
########
########
######
####
##
2.3.
А вот особенно сложная:
# #
## ##
### ###
########
########
### ###
## ##
# #
2.4.
Создайте свою собственную фигуру: Придумайте свою собствен- ную симметричную фигуру из символов # и проверьте, сможете ли вы написать программу, которая следует правилам программ с фигурами.
2.5.
Если вам понравилась задача с формулой Луна, попробуйте на- писать программу для другой системы с проверочной цифрой, например для 13-значной системы ISBN. Программа должна принимать идентификационный номер и верифицировать его либо принимать номер без проверочной цифры и генерировать такую цифру.
2.6.
Если вы изучали двоичные числа и знаете, как преобразовывать десятичные числа в двоичные и наоборот, попробуйте написать программу для выполнения таких преобразований. При этом чис- ла должны быть неограниченной длины (но вы можете предполо- жить, что числа должны быть достаточно небольшими, чтобы их можно было сохранить в стандартной переменной int языка С++).
2.7.
Вы изучали шестнадцатеричные числа? Попробуйте написать программу, которая позволяет пользователю ввести двоичное, десятичное или шестнадцатеричное число и вывести все три ва- рианта.
2.8.
Хотите дополнительный вызов? Обобщите код предыдущего упражнения для создания программы, конвертирующей любое число с базисом 16 или меньше в число с любым другим базисом.
Так, например, программа должна смочь преобразовать число с базисом 9 в число с базисом 4.
2.9.
Напишите программу, которая считывала бы строку текста, под- считывая количество слов и вычисляя длину самого длинного слова, наибольшее количество гласных букв в слове и/или лю- бую другую статистику, какую вы можете себе представить.
76 Глава 3
В предыдущей главе мы ограничи- лись скалярными переменными , то есть переменными, которые могут одно- временно хранить только одно значение.
В этой главе мы рассмотрим задачи, в которых используется самый популярный агрегированный тип данных — массив. Несмотря на то, что массивы — это простые структуры с некоторыми фундаменталь- ными ограничениями, их использование значительно увеличивает мощь наших программ.
В этой главе мы в первую очередь будем иметь дело с истинными массивами, то есть массивами, объявляемыми с помощью встроен- ного синтаксиса языка С++, например так:
int tenIntegerArray[10];
Однако обсуждаемые техники также хорошо применимы и к структурам данных с подобными атрибутами. Наиболее часто встре-
+ " "
3
Решение задач с массивами 77
чающаяся разновидность таких структур данных — вектор. Термин
вектор зачастую используется в качестве синонима одномерного мас- сива, но мы будем использовать его более конкретно: для обозначе- ния структуры с атрибутами массива без указания максимального ко- личества элементов. Таким образом, в обсуждениях мы согласимся, что массив имеет фиксированный размер, тогда как размер вектора может увеличиваться или уменьшаться автоматически при необхо- димости. В каждой из обсуждаемых в этой главе задач будет некое ограничение, которое позволит использовать структуру с фиксиро- ванным количеством элементов. Задачи без таких ограничений мо- гут быть адаптированы для использования векторов.
Более того, техники, используемые для массивов, могут зачастую также использоваться для структур данных, не обладающих каждым из вышеперечисленных свойств. Так, например, некоторые техни- ки не требуют случайного доступа, то есть они могут использоваться применительно к таким структурам, как связанные списки. Массивы очень часто встречаются в программировании, и техники работы с ними используются и в других областях, поэтому это хороший тре- нировочный полигон для изучения решения задач со структурами данных.
Обзор основных свойств массивов
Вы уже должны знать, что такое массив, но давайте все же для боль- шей ясности пробежимся по его основным свойствам. Массив —это набор переменных одного типа, собранных под одним именем, где отдельные переменные обозначаются числом. Мы называем отдель- ные переменные элементами массива. В С++ и большинстве других языков первый элемент имеет порядковый номер 0, но в некоторых языках ситуация может быть иной.
Основные свойства массива следуют сразу из его определения.
Все значения, сохраненные в массиве, имеют один тип, тогда как агрегированные структуры данных могут хранить значения разных типов. Доступ к отдельному элементу осуществляется через порядко- вый номер, называемый индексом. В других разновидностях структур данных доступ к отдельному элементу может осуществляться по име- ни или ключевому значению.
Из этих основных свойств мы можем вывести несколько вторич- ных. Так как каждый элемент обозначается собственным порядко- вым номером, начиная с 0, мы можем с легкостью узнать все значе- ния, сохраненные в массиве. В структурах данных других типов это может быть сложно, неэффективно или даже невозможно. Кроме того, тогда как к элементам некоторых структур данных, например связанных списков, доступ может быть получен только последова- тельно, массивы предлагают случайный доступ, таким образом, мы можем получить доступ к любому элементу в любое время.