Г л а в а 2
Алгоритмы обработки строковых величин
§ 6. Основные алгоритмические конструкции и типы данных
6.1. Основные алгоритмические конструкции
Напомним некоторые определения, известные вам из курсов 7-го и 8-го классов.
Алгоритм — конечная последовательность команд, формальное выполнение которых позволяет получить решение задачи для любого допустимого набора исходных данных. Все команды делят на группы:
1. Команды, которые непосредственно выполняются в программе.
2. Команды, изменяющие порядок выполнения других команд.
Любой алгоритм может быть записан с использованием базовых алгоритмических конструкций, а именно: следование, цикл и ветвление (пример 6.1).
 |
|
  |
 |
Программа представляет собой запись на некотором формальном языке — языке программирования.
Командами в языке программирования считают:
- операторы (оператор присваивания, оператор ветвления, оператор цикла и др.);
- вызовы вспомогательных алгоритмов (встроенных в библиотеки и созданных пользователем).
Команды цикла и ветвления управляют порядком выполнения других команд в программе и относятся к командам управления (управляющим конструкциям) (пример 6.2).
Пример 6.2. Запись операторов ветвления и цикла на языке С++.
Ветвление в полной форме:
{ команды 1; }
else { команды 2; }
Ветвление в сокращенной форме:
if (условие) { команды; }
Цикл с предусловием:
{
тело цикла;
}
Цикл с параметром: N1 < N2
Параметр увеличивается:
for ( i = N1; i < N2; i++) { тело цикла; }
Параметр уменьшается:
for ( i = N2; i > N1; i--) { тело цикла; }
Обычно счёт начинается с 0. На это нужно обращать внимание при решении задач.
Оператор ветвления — команда, реализующая алгоритмическую конструкцию ветвление на языке программирования.
Оператор цикла — команда, реализующая алгоритмическую конструкцию повторение на языке программирования.
В С++ существуют различные возможности управлять тем, сколько раз будет повторяться тело цикла.
Может быть задано условие продолжения или окончания работы цикла, а также число повторений тела цикла.
Цикл с предусловием используется в том случае, когда известно условие продолжения работы.
Цикл с параметром используется тогда, когда известно количество повторений.
6.2. Вспомогательные алгоритмы
Вспомогательный алгоритм — алгоритм, который можно использовать в других алгоритмах, указав его имя и, если необходимо, значения параметров.
В языке С++ используются вспомогательные алгоритмы — функции. Они могут быть с параметрами или без параметров (пример 6.3).
Описание функций повторяет структуру программы на языке С++. Внутри функции можно описывать переменные, которые будут использоваться только внутри данной функции. Вы уже использовали встроенные функции из определённых модулей:
Circle(250, 125, 30); //для рисования окружности в графическом режиме
вызов функций для вычисления квадратного корня и синуса: d = sqrt(2) * sin(x);
6.3. Типы данных
В языке С++ используются разные типы данных. Они нужны для выполнения различных операций — с каждым типом данных связан свой набор операций.
Для хранения различных типов данных в памяти компьютера отводится разное количество памяти. Вы уже использовали типы данных, которые называют простыми. В таблице примера 6.5 приведены целочисленные типы данных, используемые в С++.
Пример 6.5. Целочисленные типы данных в С++
Все целочисленные типы данных, представленные в таблице, можно разделить на две группы:
- знаковые (диапазон значений которых содержит как положительные, так и отрицательные числа);
- беззнаковые (диапазон значений содержит только неотрицательные числа).
Для каждого знакового типа есть беззнаковый, занимающий столько же памяти.
Вещественные типы данных позволяют хранить число, представленное в стандартном виде:
a E n (например, 1,23E+10) или a · 10n, где 1≤ a ≤ 10, и n (целое) есть порядок числа, записанного в стандартном виде (пример 6.6).
Пример 6.6. Вещественные типы данных в С++
Значения типа bool, который называют логическим, занимают 1 байт и принимают одно из двух значений, задаваемых константами true (истина) и false (ложь).
Данные в программу пользователь может вводить с помощью команды cin. Для вывода данных используется команда cout.
Оператор присваивания используется для того, чтобы задавать значения переменным и вычислять значение выражения.
При использовании в одном операторе присваивания данных разных типов нужно помнить об их совместимости:
переменной целочисленного типа нельзя присвоить вещественное значение;
для данных вещественных типов определены операции «+», «–», «*», «/»;
для данных целочисленных типов определены операции «+», «–», «*», «/» (только целая часть), «%».
Целочисленные типы могут быть преобразованы к вещественным, но не наоборот (пример 6.7).
Пример 6.7. Приведение типов.
int x, y, z;
a = 1; b = 3; x = 6; y = 4;
//вычисления с вещественным типом
c = a / b; cout << c; //будет выведено 0.333333
//преобразование к целому
c = int (a / b); cout << c; //будет выведено 0
//вычисления с целым типом
c = x / y; cout << c; //будет выведена целая часть от деления целых чисел: 6 на 4, то есть 1
z = x % y; cout << z; //будет выведено 2 - остаток от деления 6 на 4
//преобразование к вещественному
c = x / (y*1.0); cout << c; // для получения дробного результата, одно из чисел нужно привести к дробному типу, например, путём умножения на 1.0
Все простые типы, кроме вещественного, называются порядковыми.
Для порядковых типов используются команды + + и - - (пример 6.8 и пример 6.9).
Пример 6.8. Процедуры и функции для работы с порядковыми типами.
Команда i++ увеличивает значение переменной i на 1
Команда i-- уменьшает значение переменной i на 1
Пример 6.9. Фрагмент программы для работы с порядковыми типами.
using namespace std;
int main()
{
char a, b, c;
a = 'b'; b = 'k';
a++;
cout << a << endl; //будет выведено с - следующий символ
cout <<int (a) << endl; //будет выведено 99 - код с в кодировочной таблице
cout << b << endl; //будет выведено j - предыдущий символ
cout <<int (b); //будет выведено 106 - код j в кодировочной таблице
}
если нужно символ цифры преобразовать в числовой тип, то можно найти разницу между символом нужной цифрой и символом '0':
b = '9';
cout << b - '0' << endl; // будет выведено число 9
6.4. Примеры задач
Отличительной особенностью переменных является то, что мы можем многократно в течение работы программы изменять их значение. Но кроме переменных в языке программирования C++ можно определять константы. Их значение устанавливается один раз и впоследствии мы его не можем изменить. Константа определяется практически так же, как и переменная за тем исключением, что в начале определения константы идет ключевое слово const. Например:
// или
// const int n = 22;
Пример 6.10. Описать слово «Pascal» как константу. Вывести слово на экран.
Этапы выполнения задания
I—II. Результат работы не зависит от исходных данных.
III. Алгоритм решения задачи.
1. Записать слово в переменную char как константу.
2. Вывести константу.
IV. В программе нет переменных.
V. Программа:
using namespace std;
int main()
{
const char* a="Pascal";
cout << a;
return 0;
}
VI. Тестирование.
Запустить программу. Проверить результат.
Пример 6.11. Написать программу, которая выведет заданное слово на экран n раз. Значение n вводится.
I. Исходные данные: переменная n.
II. Результат: n слов.
III. Алгоритм решения задачи.
1. Опиcываем слово как константу.
2. Вводим значения n.
3. Воспользуемся циклом for для вывода слова n раз.
4. Выводим слова в цикле.
IV. Описание переменных: n — int.
V. Программа:
using namespace std;
int main()
{
const char* sl="Programming";
int n;
cin >> n;
for (int i=0; i<n; i++)
cout << sl << endl;
return 0;
}
VI. Тестирование. Результат при n = 5:
Programming
Programming
Programming
Programming
Пример 6.12. Написать программу, которая выведет на экран n раз одно из двух слов. Выбор слова осуществляется случайным образом. Значение n вводится. Посчитайте, сколько раз было выведено каждое слово.
Этапы выполнения задания
I. Исходные данные: переменная n.
II. Результат: n раз выведено одно из двух слов и сообщение о том, сколько раз выведено каждое из слов.
III. Алгоритм решения задачи.
2. Вводим значения n.
3. Инициализируем нулем переменные k1 и k2, которые будут подсчитывать, сколько раз выведено каждое слово.
4. Для вывода слов используем цикл for.
4.1. Сгенерируем случайное число x на промежутке [0; 2).
4.2. Если x = 0, то выведем первое слово и увеличим значение переменной k1 на 1.
4.3. Иначе выведем второе слово и увеличим значение переменной k2 на 1.
5. Выводим сообщения о количестве слов.
IV. Описание переменных: n, k1, k2, x — int.
V. Программа:
using namespace std;
int main()
{
const char* sl1="Programming";
const char* sl2="Python";
int n, k1, k2, x;
cin >> n;
k1=0; k2=0;
for (int i=0; i<n; i++) {
x= rand() % 3;
if (x==0)
{
cout << sl1 << endl;
k1++;
}
else
{
cout << sl2 << endl;
k2++;
}
}
cout << sl1 << " - "<< k1 << endl;
cout << sl2 << " - "<< k2 << endl;
return 0;
}
VI. Тестирование. Запустить программу. Результат при n = 5:
Python
Programming
Python
Python
Programming - 1
Python - 4
Вопросы:
2. Назовите основные алгоритмические конструкции.
3. Что понимают под вспомогательным алгоритмом?
4. Чем отличаются различные целочисленные типы данных друг от друга?
5. Что нужно помнить о совместимости типов данных?
6. Какие арифметические операции определены для целочисленных типов данных? Для вещественных типов данных?
Упражнения
1. Измените константу в программе примера 6.10 на свое имя. Используя команды графической библиотеки для работы с текстом, измените шрифт, размер символов, фон, начертание букв.
2. Запустите программу из примера 6.12 несколько раз. Какие результаты получили? Измените программу из примера 6.12 так, чтобы случайным образом выбиралось одно из трех слов.
§ 7. Строковые величины
В первых языках программирования строкового типа данных не было; программист должен был сам строить функции для работы со строками.
В 1962 г. был разработан язык SNOBOL (StriNg Oriented symBOlicLanguage), ориентированный на работу со строками. В конце 60-х гг. ХХ в. строковые типы данных появились в языках Algol и Fortran.
Две строки, в отличие от двух чисел, нельзя прочитать с помощью одной команды cin, поскольку пробел для строк - это разделитель, то есть первая строка будет считываться до первого пробела, вторая строка - до следующего пробела (или, если его нет, то до конца строки). Если же в строке должен участвовать пробел, то ввод данных будет осуществляться другой командой.
7.1. Ввод, вывод, присваивание строковых величин
Современные компьютеры способны обрабатывать данные, представленные различными способами: числа, тексты, графику, звуки. Вы уже знаете, как на языке программирования С++ можно работать с целыми и вещественными числами, выполнять простейшие графические построения.
Обработка текстовых данных является сегодня наиболее актуальной — это обработка различных поисковых запросов в Интернете, перевод текстов с одного языка на другой, озвучивание компьютером печатного текста и др.
В языке С++ для работы с текстовыми данными используется тип string (строка). Строки состоят из набора последовательно расположенных символов и используются для хранения текста. Они могут иметь произвольную длину. Строка, в которой нет ни одного символа, называется пустой.
Строка описывается следующим образом:
string <имя строки>;
Например, string str;
Давать значение строке (инициализировать) можно стразу при описании строки:
string s1("I like infomatiks"), s2("And you?");
Если в выражении встречается одиночный символ, он должен быть заключен в одинарные кавычки. При использовании в выражениях строка заключается в двойные кавычки.
Для ввода строки с клавиатуры используются другая команда, чем для вывода чисел:
getline(cin, s1);
Ввод данных всегда заканчивается нажатием клавиши Enter, которой соответствует специальный символ: ¶. Признаком конца строки является нулевой символ \0.
Переменной строкового типа можно присвоить значение с помощью команды присваивания.
Пустая строка задается следующим образом: s := "";
К символам в строке можно обращаться, используя индекс. Нумерация символов начинается с нуля, s[i] соответствует (i + 1)-му символу в строке s (пример 7.2).
Над строками типа string определенны следующие операции:
- присваивания, например s1 = s2;
- объединения строк (s1+=s2 или s1=s1+s2) — добавляет к строке s1 строку s2, результат храниться в строке s1, пример объединения строк. В примере к содержимому строки a в конце "приклеивается" содержимое строки b, результат записывается в а:
Этапы выполнения задания
II. Результат: строка с приветствием.
III. Алгоритм решения задачи.
1. Ввод имени.
2. Вывод строки с приветствием.
IV. Описание переменных: imja — string.
Пример 7.1. Введем строку s и выведем ее значение.
#include <string>
using namespace std;
int main()
{
string s;
cout<<"Input string: "; getline(cin, s);
cout<<"Output string: ";
cout<< s <<endl;
return 0;
}
Результат работы:
Output string: Primer
Пример 7.2. Вывести третий символ строки «Информатика».
#include <string>
using namespace std;
int main()
{
string s;
cout<<"Input string: "; getline(cin, s);
cout<<"3 simbol: ";
cout<< s[2] <<endl;
return 0;
}
Результат работы:
3 simbol: h
Пример 7.3.
V. Программа:
#include <string>
using namespace std;
int main()
{
string imja;
cout<<"What's your name? "; getline(cin, imja);
cout<<"Hi, ";
cout<< imja <<endl;
return 0;
}
VI. Тестирование.
Запустить программу и ввести значение «Sveta». Результат:
What's your name? Sveta
Hi, Sveta
7.2. Сравнение и сложение строковых величин
Так же как и для других типов данных, для строк определены свои операции — действия, которые можно выполнять с данными типа string. Для строкового типа такими операциями являются сравнение и сложение.
Для сравнения строк нужно уметь сравнивать символы. Все символы записаны в таблице символов (в документе Word эту таблицу вы использовали для вставки символа, отсутствующего на клавиатуре). Каждый символ в таблице имеет свой код (номер), и при сравнении символов сравниваются их коды — номера в таблице символов.
В таблице символов, которую использует C++, 65536 символов (стандарт Юникод — англ. Unicod: https://ru.wikipedia.org/wiki/Юникод (дата доступа: 05.01.2019)). Запомнить, в каком порядке записаны символы, невозможно. Достаточно знать, как расположены группы наиболее часто употребляемых символов. В примере 7.4 приведены некоторые группы символов в порядке их расположения в таблице.
Строки сравниваются посимвольно. Сначала сравниваются первые символы двух строк. Если символы различны, то больше та строка, символ которой имеет больший номер. Если символы одинаковые, то переходят к сравнению следующих символов. Сравнение заканчивается, когда найдены различные символы или в одной из строк закончились символы — в этом случае больше та строка, в которой символы остались. Если при сравнении символов различия не найдены и строки закончились одновременно, то они равны (пример 7.5). Порядок, в котором меньшая строка предшествует большей, называют лексикографическим. Это название он получил по аналогии с размещением по алфавиту в словаре.
При сравнении строк следует помнить, что заглавные и строчные буквы — это разные буквы, поскольку имеют различные номера в таблице символов. Поэтому строки 'мама' и 'Мама' будут различными, а неравенство 'мама' > 'Мама' будет верным (у буквы 'м' код 236, а у 'М' — 204).
Для проверки правильности сравнения строк можно воспользоваться программой из примера 7.6.
Пример 7.6. Сравнение двух строк
#include <string>
using namespace std;
int main()
{
string s1, s2;
cout << "First string: ";
getline(cin, s1);
cout << "Second string: ";
getline(cin, s2);
if (s1 > s2)
cout<<"s1 > s2";
else if (s1 < s2)
cout<<"s1 < s2";
else cout<<"s1 = s2";
return 0;
}
Столица государства ... — город ... .
Вместо многоточия должны быть выведены соответствующие значения.
Этапы выполнения задания
II. Результат: переменная s (итоговая строка).
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. Создание итоговой строки.
3. Вывод строки.
IV. Описание переменных: str, gor, s — string.
#include <string>
using namespace std;
int main()
{
string str, gor, s;
cout << "The name of the country? ";
getline(cin, str);
cout << "The name of the capital? ";
getline(cin, gor);
s = "The capital of " + str + " is the city of " + gor;
cout << s << endl;
return 0;
}
8.1. Поиск в строке
Современные компьютерные устройства позволяют достаточно быстро осуществлять поиск в тексте, используя для этого различные алгоритмы. Языки программирования предоставляют широкий набор функций для работы с текстом. Некоторые функции языка программирования С++ для поиска подстроки (части строки) в другой строке представлены в таблице.
https://kvodo.ru/urok-11-stroki.html?utm_referrer=https%3A%2F%2Fwww.google.com%2F
Комментариев нет:
Отправить комментарий