книги / Технологии разработки объектно-ориентированных программ на язык C++. Основы структурного программирования на алгоритмическом языке C++
.pdfint Data(int i, int r) { return Data(i);
}
int Data(int i) { int h;
return Data(i, h);
}
Программист написал рекурсию, не осознавая того, что одну и ту же функциональность выполняют несколько перегруженных функций и одна вызывает другую.
11.5.Ханойская башня
Вданной задаче необходимо рекурсивно перенести все кольца (рис. 11.2) с одного стержня на другой, соблюдая строгие правила:
Рис. 11.2. Ханойская башня
изначально на стержне находится p колец разного размера, расположенных по убыванию радиуса колец;
за одну операцию перекладывать можно только одно кольцо
слюбого стержня на любой другой, соблюдая условие: на большее кольцо можно положить меньшее, но не наоборот;
101
в итоге нужно все кольца, лежащие на стержне 1, переместить на стержень 3, используя стержень 2 как вспомогательный.
Например, для трех колец результат будет в виде следующей последовательности перекладывания колец: 1 => 3 , 1 => 2 , 3 => 2, 1 => 3, 2 => 1, 2 => 3, 1 => 3.
Код программы:
#include <iostream> using namespace std;
void Hanoi(int p, int t, int f, int r) { /*
p - кол-во колец, f – номер стержня, на котором кольца находятся изначально, t – номер стержня, где в итоге должны оказаться кольца, r – номер промежуточного
стержня
*/
if (n != 0) { |
|
// условие выхода из рекурсии |
Towers(p |
– 1, |
f, r, t); |
// p – 1 |
колец перекладываются на промежуточный |
|
стержень |
cout |
<< " Снимаем " << n << "й диск с |
" << f << "го стержня и надеваем его на " << t << "й |
||
стержень" << endl; |
||
Towers(p – 1, |
r, t, f); |
|
/* |
|
|
p – 1 колец перекладываются с промежуточного стержня на нужный стержень
*/ |
|
} |
|
} |
|
int main() { |
|
setlocale(LC_ALL, "Russian"); |
// Подключение русского |
языка |
|
int p; |
// Количество колец |
cout << "Введите количество колец |
"; |
cin >> p; |
// Ввод количества |
колец |
|
Hanoi(p, 1, 3, 2); |
// Вызов рекурсии |
return 0; |
|
} |
|
102
Подробнее: чтобы перенести n колец с первого стержня на третий, необходимо p – 1 колец с первого стержня перенести на свободный стержень (1-й рекурсивный вызов), перенести последнее кольцо на третий стержень (вывод текста на экран), затем p – 1 колец со свободного стержня перенести на третий (2-й рекурсивный вызов). А так как при вызове назначения колец f, t, r меняются, то условие, что на меньшее кольцо нельзя положить меньшее, выполняется.
Пример работы:
Введите количество колец 3 Снимаем 1-й диск с 1-го стержня и надеваем его на 3-й стержень
Снимаем 2-й диск с 1-го стержня и надеваем его на 2-й стержень Снимаем 1-й диск с 3-го стержня и надеваем его на 2-й стержень Снимаем 3-й диск с 1-го стержня и надеваем его на 3-й стержень Снимаем 1-й диск с 2-го стержня и надеваем его на 1-й стержень Снимаем 2-й диск с 2-го стержня и надеваем его на 3-й стержень Снимаем 1-й диск с 1-го стержня и надеваем его на 3-й стержень
Задания для самостоятельной работы:
Написать программу, которая выводит все числа от 1 до n (задается пользователем), используя рекурсию.
Написать программу, которая выводит все числа от A до B (задаются пользователем) включительно в порядке возрастания, если A < B, или в порядке убывания в противном случае.
103
Глава 12. СТРУКТУРЫ ДАННЫХ
Структура – это объединение нескольких переменных разных типов, которому можно присвоить имя [5]. Например, можно объединить данные об объекте автомобиль: владелец автомобиля, номер, марка, цена и т.д. Для того чтобы реализовать данную структуру, необходимо описать новый тип данных (в конце описания ставится точка с запятой):
struct Avto { |
|
string fio; |
// ФИО владельца автомобиля |
string marka; |
// Марка автомобиля |
string nom; |
// Номер автомобиля |
int price; |
// Цена автомобиля |
}; |
|
Имя созданного типа – Avto. Переменная данного типа создается аналогично переменной встроенного типа:
Avto a; // Переменная типа Avto
Avto a[20]; // Массив структур
Также можно совместить описание структуры с описанием переменных:
struct Avto { } a, b[20];
Элементы структуры называют полями. Поля могут быть переменной любого встроенного типа, структурой, массивом или указателем. Чтобы обратиться к полю, необходимо использовать знак «–>» для указателя и знак «.» для переменной:
a.price = 2300000; // Цена автомобиля 2.300.000 руб a->price = 2300000; // Если price – указатель
(*a).price= 2300000; // Также можно использовать для указателя
104
Ввод и вывод структур осуществляются по полям, подобно тому, как в массиве по элементам:
getline(cin,a.fio);
cin >> a.marka >> a.nom >> a.price;
Также структуры можно инициализировать перечислением значений их элементов:
Avto a = {“Петров А.В.”,”LADA”,”к420ло”,285000};
Структуры одного типа можно присваивать друг другу, но сравнивать и вводить/выводить сразу все поля не получится.
12.1. Поиск в массиве структур
Пример:
В текстовом файле Avto.txt хранится 100 записей автомобилей. Запись содержит ФИО владельца автомобиля (гарантируется, что ФИО не совпадают), марку, номер и цену. Каждое поле записано в разные строки:
ФИО владельца Марка Номер Цена
Записи идут подряд без каких-либо разделительных символов или пробелов. Написать программу, которая по заданным ФИО выводит информацию о машине.
Подключаем необходимые библиотеки, описываем структуру и подключаем алфавит русского языка:
#include <iostream> |
|
|
#include <string> |
// |
Заголовок строк |
#include <fstream> |
// |
Работа с файлами |
#include <Windows.h> // |
Для русского языка |
|
using namespace std; |
|
|
struct Avto { |
|
|
string fio; |
// ФИО владельца автомобиля |
|
string marka; |
// Марка автомобиля |
105
string nom; // Номер автомобиля int price; // Цена автомобиля
};
int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); return 0;
}
Следующим |
шагом будет объявление нужных переменных |
и ввод ФИО: |
|
string fio; |
// ФИО, введенное пользователем |
getline(cin, fio); |
|
Avto mas[100]; |
// Массив структур |
bool flag = false; /* Флаг, отвечающий за поиск ФИО. Если найден, то flag = true, а если нет, то flag = false */
В цикле от 0 до 100 необходимо «пройти» по файлу и заполнить массив структур, одновременно сравнивая ФИО из файла и введенные ФИО. Если строки равны, то выводятся данные ячейки массива, а если нет, то сообщение об этом выводится на экран:
ifstream f("Avto.txt"); |
// Открываем поток |
|
вывода из файла |
for (int i = 0; i < 100; i++) { |
|
getline(f, mas[i].fio); |
// Ввод ФИО из файла |
getline(f, mas[i].marka); // Ввод марки из файла |
|
getline(f, mas[i].nom); |
// Ввод номера из файла |
string str; |
|
getline(f, str); |
// Ввод цены из файла |
mas[i].price = atoi(str.c_str());
// Преобразование string к int и присваивание к полю
if (fio == mas[i].fio) { // Если нашли элемент cout << "ФИО владельца: " << mas[i].fio << endl; cout << "Марка автомобиля: " << mas[i].marka << endl; cout << "Номер автомобиля: " << mas[i].nom << endl; cout << "Цена автомобиля: " << mas[i].price << endl;
106
flag = true;
break; // Выход из цикла
}
}
if (!flag) cout << "Информации об автомобиле данного владельца нет\n"; // Если элемент не найден
Пример выполнения программы:
Киселев Сергей Русланович ФИО владельца: Киселев Сергей Русланович Марка автомобиля: Ford
Номер автомобиля: с874ра Цена автомобиля: 535000
12.2. Структуры в динамической памяти
Структуры также можно размещать в динамической области памяти:
Avto *mas1 = new Avto; // Структура
Avto *mas2 = new Avto[size]; // Массив структур
Написать программу, в которой вводится size-записей автомобилей и затем массив структур сортируется по возрастанию цены.
Подключаем необходимые библиотеки, описываем структуру и подключаем алфавит русского языка:
#include <iostream> #include <string> #include <Windows.h> using namespace std; struct Avto {
string marka; // Марка автомобиля int price; // Цена автомобиля
};
int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251);
return 0;
}
107
Затем необходимо ввести значение количества записей n, выделить память для n записей и ввести структуры:
int size; // Количество записей cout << "Введите количество автомобилей: ";
cin >> size;
Avto *mas = new Avto[size]; // Выделение памяти для n
записей
for (int i = 0; i < n; i++) {
cout << "Автомобиль №" << i+1 << endl << "Введите марку: "; cin >> mas[i].marka;
cout << "Введите цену: "; cin >> mas[i].price;
}
Сортировка массива осуществляется по возрастанию цены автомобиля методом вставки. И последним шагом выводится отсортированный массив структур:
// Сортировка методом вставки |
|
for (int i = 1; i < size; i++) { |
|
int y = mas[i].price; |
/* Сохраняем цену |
|
автомобиля */ |
Avto g = mas[i]; |
// Сохраняем |
|
структуру |
for (int j = i – 1; j >= 0; j--) { |
|
if (mas[j].price > y) { |
|
mas[j + 1] = mas[j]; |
// Заменяем |
|
структуры |
mas[j] = g; |
// Заменяем |
|
структуры |
} |
|
} |
|
}
// Вывод отсортированного массива структур for (int i = 0; i < size; i++) {
cout << "*** Автомобиль №" << i + 1 << " ***" << endl
<<"Марка: " << mas[i].marka << endl
<<"Цена: " << mas[i].price << endl;
}
108
Пример выполнения программы:
Введите количество автомобилей: 3 Автомобиль №1
Введите марку: KIA Введите цену: 350000 Автомобиль №2 Введите марку: Toyota Введите цену: 1230000 Автомобиль №3 Введите марку: LADA Введите цену: 230000
Отсортированный массив:
***Автомобиль №1 ***
Марка: LADA Цена: 230000
***Автомобиль №2 ***
Марка: KIA Цена: 350000
***Автомобиль №3 ***
Марка: Toyota Цена: 1230000
Задание для самостоятельной работы:
Описать структуру Worker, которая содержит следующие поля: ФИО, возраст, название организации, зарплата. Написать программу, которая выполняет следующие действия: ввод с клавиатуры данных в массив, состоящий из N (вводится пользователем) структур типа Worker, отсортировать массив по возрастанию зарплаты, реализовать вывод данных работника при поиске по ФИО.
109
Глава 13. РАБОТА С ФАЙЛАМИ
Программа может получать данные не только с консоли. Основным местом для хранения большого количества данных являются файлы. Программа может взаимодействовать с ними. Для этого необходимо подключить библиотеку <fstream>.
Есть несколько операций, которые используются чаще всего:
операторы перенаправления ввода/вывода: <<, >>;
запись и чтение строк: getline(), get(), put();
потоковая запись и чтение: write(), read();
открытие и закрытие файлов: open(), close();
проверка, открыт ли файл: is_open();
проверка, достигнут ли конец файла: eof().
13.1. Открытие файла для записи. Работа с файлом в режиме записи
Это режим открытия файла, при котором в файл можно только записывать информацию. Для открытия файлов используется метод open(). Чтобы открыть файл для чтения, необходимо использовать класс ofstream.
Открытие файла выглядит следующим образом:
ofstream file (“C:\game\F1.txt”);
где сначала указывается тип открытия (для записи), потом имя объекта, через которое будем взаимодействовать с файлом (подобно переменной), и в скобках указывается полное имя файла.
Далее необходимо сделать проверку, открылся ли файл. Это делается с помощью метода is_open():
#include <iostream> #include <fstream> using namespace std;
110