Лабораторный практикум по основам алгоритмизации в Visual Studio 2005

Саровский государственный
физико-технический институт
Факультет информационных
технологий и электроники
Кафедра вычислительной и информационной техники
Касаткин С.С., Раткевич И.С., Травова Н.Н.
Лабораторный практикум
по курсу “Основы алгоритмизации”
в среде Microsoft Visual Studio 2005
г. Саров
2008 г.
Саровский государственный
физико-технический институт
Факультет информационных
технологий и электроники
Кафедра вычислительной и информационной техники
Касаткин С.С.,Раткевич И.С., Травова Н.Н.
Лабораторный практикум
по курсу “Основы алгоритмизации”
в среде Microsoft Visual Studio 2005
Утверждено:
на заседании кафедры ВИТ
Научно методическим Советом СарФТИ
г. Саров
2008 г.
6
УДК 681.3
Т 65
Одобрено Научно-методическим
советом Саровского государственного
физико-технического института
Т 65 Касаткин Сергей Сергеевич, Раткевич Ирина
Сергеевна, Травова Надежда Николаевна
Лабораторный практикум по курсу “Основы алгоритмизации”
в среде Microsoft Visual Studio 2005
Данное пособие предназначено для студентов, изучающих курс “Основы алгоритмизации” и выполняющих практические задания, составляя программы, написанные
на языке С++. Среда программирования, на которую ориентирован практикум –
Microsoft Visual Studio 2005.
Практикум содержит множество примеров программ, решающих классические
учебные задачи и иллюстрирующих основные приемы программирования на языке
C++, и задания для самостоятельного выполнения. Программы сопровождаются необходимыми пояснениями, однако предполагается, что студенты параллельно слушают
курс лекций или изучают самостоятельно по учебнику основы программирования на
языке C++.
Рецензент: к.ф.-м.н. доцент Холушкин В.С.
Консультант Лебедев Петр Андреевич
Содержание
ТИПЫ ДАННЫХ С++
7
ЛАБОРАТОРНАЯ РАБОТА №1
9
Тема: “Программы, использующие команды ветвления. Отладка
программы“....................................................................................................................... 9
ОТЛАДКА ПРОГРАММЫ................................................................................................. 9
ЧАСТЬ 1 ...................................................................................................................... 10
Ветвление в программе с помощью вложенных конструкций if-else ............. 10
Задание .............................................................................................................. 10
Организация повторения программы ............................................................. 14
Выполнение программы в пошаговом режиме ............................................. 15
Задание для самостоятельного выполнения .................................................. 15
ЧАСТЬ 2 ...................................................................................................................... 16
Ветвление в программе с помощью оператора switch .................................... 16
Задание для самостоятельного выполнения .................................................. 17
ЛАБОРАТОРНАЯ РАБОТА №2
18
Тема: “Программы, использующие команды повторения (циклы).
Рекуррентные соотношения“ ....................................................................................... 18
ЧАСТЬ 1 ...................................................................................................................... 18
Программы, работающие с натуральными числами ....................................... 18
1. Программа, которая находит наибольший общий делитель двух
натуральных чисел m и n .............................................................................................. 18
2. Программа, которая проверяет, является ли число простым ..................... 19
3. Программа, которая проверяет, является ли число палиндромом ............ 20
ЧАСТЬ 2 ...................................................................................................................... 21
Программы, использующие рекуррентные соотношения ............................... 21
4. Программа, которая находит числа Фибоначчи в заданном диапазоне.... 21
5. Программа, которая находит значение квадратного корня из заданного

1 x
числа, используя рекуррентное соотношение: y i 1  y i    y i  ..................... 22
2  yi

x4 x6

 с
2! 3!
заданной точностью. ..................................................................................................... 23
7. Пример – программа, которая вычисляет сумму ряда
1 1 1
1
  1   
для заданного количества слагаемых. ............................. 25
1! 2! 3!
n!
Задания для самостоятельного выполнения ..................................................... 25
2
6. Программа, которая вычисляет сумму ряда  x  1  x 2 
ЛАБОРАТОРНАЯ РАБОТА № 3
28
Тема: “Программы, использующие вспомогательные функции”. .................. 28
1. Программа, которая считывает координаты вершин треугольника на
плоскости и находит все углы этого треугольника в градусах. ............................... 28
2. Программа, которая находит заданное количество чисел, содержащих
цифру 3 29
3. Программа, которая находит на заданном отрезке натуральные числа,
которые можно представить в виде суммы квадратов двух натуральных чисел. .. 30
4. Программа, которая находит первое автоморфное число справа от
заданного........................................................................................................................ 32
8
5. Программа находит точки пересечения линий y= ax+b и y = c/x +d ........ 33
6. Программа для вычисления биноминальных коэффициентов .................. 35
Задания для самостоятельного выполнения .................................................... 36
ЛАБОРАТОРНАЯ РАБОТА № 4
39
Тема: “Программы, использующие строки символов ”. ................................. 39
1. Программа, которая считывает строку символов и сортирует ее по
возрастанию кодов символов ...................................................................................... 41
2. Программа перевода числа из десятичной системы счисления в двоичную
42
3. Программа перевода числа из двоичной системы в десятичную .............. 44
4. Программа перевода числа из 16-ой системы счисления в 2-ую. ............ 45
5. Программа перевода числа из 2-ой системы счисления в 16-ую. ............ 47
6. Программа, которая выводит на экран треугольник Паскаля (треугольник
биноминальных коэффициентов) ............................................................................... 49
Задания для самостоятельного выполнения .................................................... 50
ЛАБОРАТОРНАЯ РАБОТА № 5
53
Тема: “Программы, использующие файлы ”. .................................................. 53
1. Программа, которая считывает имя файла, открывает его и подсчитывает
количество скобок каждого вида, содержащихся в файле. ...................................... 53
2. Программа, инвертирующая файл (переставляющая символы в обратном
порядке) ......................................................................................................................... 54
3. Программа выводит на экран n-ую строку файла....................................... 56
4. Программа, которая переписывает текст из одного файла в другой, удаляя
лишние пробелы между словами и делая ширину текста максимум 70 символов 57
5. Программа, которая считывает текст файла и создает новый файл,
заменив во всем тексте заданное слово на новое (не изменяя деление на строки и
количество пробелов между словами)........................................................................ 59
6. Программа, которая считывает данные для структуры Man из файла. .... 60
7. Программа создающая новый текстовый файл из двух данных, в котором
1-я строка –строка из первого файла, 2-я строка – строка из 2-го файла, 3-я строка
– содержит общие символы первых 2-х строк........................................................... 63
8. Программа создаёт из двух файлов третий, в котором содержатся
максимальные по длине слова из соответствующих строк исходных файлов,
причём все слова длиннее 5-ти символов заключаются в квадратные скобки. ..... 65
Задания для самостоятельного выполнения .................................................... 68
ЛАБОРАТОРНАЯ РАБОТА № 6
71
Тема: “Программы, использующие массивы ”. ................................................ 71
1. Программа заполняет массив A(50) случайными целыми числами из
диапазона [-20, 30] и упорядочивает его по возрастанию. Исходный и
упорядоченный массивы выводятся на экран дисплея. ............................................ 71
2. Программа, которая по заданным корням многочлена степени n
восстанавливает все коэффициенты многочлена. ..................................................... 72
3. Программа считывает линейный массив из файла, выводит его на экран, и
подсчитывает количество элементов массива, находит min и max элементы и их
индексы. ......................................................................................................................... 74
4. Программа заполняет массив A[5][5] случайными целыми числами из
диапазона [-3, 3] и находит произведение элементов, стоящих на побочной
диагонали....................................................................................................................... 76
5. Программа считывает матрицу из файла, выводит ee на экран, сортирует
элементы в каждом столбце и отсортированную матрицу записывает в файл. ..... 77
6. Программа, сортирующая файл по длине строки методом быстрой
сортировки. .................................................................................................................... 79
Задания для самостоятельного выполнения ..................................................... 82
ЛАБОРАТОРНАЯ РАБОТА № 7
85
Тема: “Программы, использующие динамические структуры”..................... 85
1. Программа, которая создает очередь символов. ......................................... 85
2. Программа, которая создает закольцованный список и затем
последовательно удаляет из списка каждый m-й элемент до тех пор, пока не
будут удалены все. ....................................................................................................... 86
3. Программа, которая работает со стеком. ..................................................... 88
4. Программа, которая работает с деревом. ..................................................... 89
Задания для самостоятельного выполнения ..................................................... 91
7
Типы данных С++
Концепция типа данных
Основная цель любой программы состоит в обработке данных. Данные
различного типа хранятся и обрабатываются по-разному. В любом алгоритмическом
языке каждая константа, переменная, результат вычисления выражения или функции
должны иметь определенный тип.
Тип данных определяет:
 внутреннее представление данных в памяти компьютера;
 множество значений, которые могут принимать величины этого типа;
 операции и функции, которые можно применять к величинам этого типа.
Исходя из этих характеристик, программист выбирает тип каждой величины,
используемый в программе для представления реальных объектов. Обязательное
описание типа позволяет компилятору проводить проверку допустимости различных
конструкций программы. От типа величины зависят машинные команды, которые
будут использоваться для обработки данных.
Все типы языка С++ можно разделить основные и составные. В языке С++
определенно шесть основных типов данных для представления целых (int, long),
вещественных (float, double), символьных (char, wchar_t) и логических величин (bool).
На основе этих типов программист может вводить описание составных типов. К ним
относятся массивы, перечисления, функции, структуры, ссылки, указатели,
объединения и классы. Существуют также четыре спецификатора типов: signed знаковый, unsigned – без знаковый, short - короткий, long - длинный.
Ниже приведена таблица основных типов данных (Fundamental Types – по
спецификации Microsoft).
Имя типа
int
unsigned
int
__int8
unsigned
__int8
Размер
в
байтах
4
Другое имя
Диапазон значений
signed
–2,147,483,648 ; 2,147,483,647
4
unsigned
0 ; 4,294,967,295
1
char
–128 ; 127
1
unsigned char
0 ; 255
__int16
2
unsigned
__int16
2
__int32
4
unsigned
__int32
4
__int64
8
short, short int,
signed short
int
unsigned
short,
unsigned short
int
signed, signed
int, int
unsigned,
unsigned int
long long,
signed long
–32,768; 32,767
0 ; 65,535
–2,147,483,648 ; 2,147,483,647
0 ; 4,294,967,295
–9,223,372,036,854,775,808 ;
9,223,372,036,854,775,807
8
1
long
unsigned long
long
нет
char
1
нет
signed char
unsigned
char
1
нет
0 to 255 при компиляции с ключём /J
–128 ; 127
1
нет
0 ; 255
short
2
unsigned
short
2
long
4
unsigned
long
4
long long
8
unsigned
long long
8
unsigned
__int64
bool
float
double
long double
wchar_t
8
4
8
также
как и
double
2
short int,
signed short
int
unsigned short
int
long int,
signed long int
unsigned long
int
нет (но
эквивалентно
__int64)
нет (но
эквивалентно
unsigned
__int64)
нет
нет
0 ; 18,446,744,073,709,551,615
false или true
–128 ; 127 по умолчанию
–32,768 ; 32,767
0 ; 65,535
–2,147,483,648 ; 2,147,483,647
0 ; 4,294,967,295
–9,223,372,036,854,775,808 ;
9,223,372,036,854,775,807
0 ; 18,446,744,073,709,551,615
3.4E +/- 38 (7 знаков)
1.7E +/- 308 (15 знаков)
нет
также как и double
__wchar_t
0 ; 65,535
9
Лабораторная работа №1
Тема: “Программы, использующие команды ветвления.
Отладка программы“
Отладка программы
Отладку программы выполняют для поиска логических ошибок в программе.
Перед отладкой необходимо откомпилировать программу (F7).
Отладка осуществляется с помощью пошагового выполнения программы и
просмотра текущих значений переменных. Для просмотра текущего значения
переменной нужно поставить курсор на строку, следующую за строкой с
интересующей нас переменной, и поставить точку останова программы <F9>. Далее
нажать кнопку <F5> для выполнения программы до данной строки. Значение
переменной будет отображено на вкладке Locals в нижней части экрана. Можно также
просто перетащить переменную на вкладку Watch.
Вкладки Locals и Watch
Команды отладчика:
<Ctrl> + <F10> - выполняет программу до строки, в которой находится курсор.
<F10> - выполняет один шаг программы (одну строку); подпрограммы выполняются как один шаг.
<F11> - если курсор стоит на строке, в которой выполняется вызов
подпрограммы, то выполняется заход в подпрограмму.
10
<F5> - выполняет программу до той строки, где стоит точка останова программы,
в случае если таких точек нет, программа выполняется полностью.
<F9> - поставить/снять точку останова программы
<Shift> + <F5> - останавливает отладку программы.
Эти клавиши необходимо нажимать, когда активно окно с текстом программы.
Сделать нужное окно активным можно щелчком мыши в этом окне, или с помощью
панели задач, или с помощью комбинации клавиш <Alt> + <Tab>.
Часть 1
Ветвление в программе с помощью вложенных конструкций if-else
Задание
Запустите среду программирования Microsoft Visual Studio 2005.
Вы увидите стартовую страницу данной среды разработки. Далее создайте проект
консольного приложения. Для этого выполните команду меню File|New|Project (или
нажмите <Ctrl>+<Shift>+<N>). Затем выберите тип проекта (Project types:) Visual C++,
если дерево доступных проектов еще не открылось нажмите левой клавишей мыши по
значку «+» с лева от названия типа проекта. Теперь нажмите Win32, выберите из
предоставленных шаблонов (Templates:) Win32 Console Application введите в поле
Name: свою фамилию латинскими буквами. В поле Location: C:\Work (см. рисунок).
Создание нового консольного приложения
Перед вами появится окно мастера создания проектов (см. рисунок на следующей
странице).
11
Нажмите кнопку Next>.
В следующем окне в поле Additional Options: установите флажок Empty project
(см. рисунок).
Нажмите кнопку Finish.
12
В следующем окне щелкните правой клавишей мыши по папке Source Files на
вкладке Solution Explorer, выберите пункт выпадающего меню Add|New Item…
Перед вами появится окно мастера Add New Item. В появившемся окне в разделе
Categories: (находится слева) выберите Code (см. рисунок). Затем в разделе Templates:
выберите C++ File (.cpp) и в поле Name введите имя файла: свою фамилию латинскими
буквами.
13
Затем нажмите кнопку Add.
Набирая далее текст программы, периодически нажимайте <Ctrl>+<S>, при этом
выполняется команда Save и сохраняется текущее состояние программы. Делать это
необходимо во избежание потери результатов своей работы.
В качестве примера возьмем программу решения уравнения ax 2  bx  c  0 для
b d
любых a, b, c. Известно, что решением этого уравнения являются x1, 2 
, где
2a
d = b2 - 4ac при a  0 и d  0 . Хорошая программа должна выдавать ответ в любом
случае, поэтому мы должны рассмотреть все возможные варианты ответа. Если a  0 ,
то наша программа будет решать квадратное уравнение, в противном случае – линейное. В каждом из этих случаев должен быть выдан один из трех вариантов ответа,
следовательно, всего эта программа должна выдавать один из шести вариантов
сообщений.
Наберите нижеследующий текст программы. Обязательно делайте отступы,
используя клавишу <Tab>. Это делает структуру программы более понятной.
ВАЖНО!!! Для того, чтобы вы могли работать с русскими символами,
необходимо при первом запуске вашего приложения правой клавишей мыши щелкнуть
на заголовке консольного окна. Затем выбрать пункт выпадающего меню Умолчания,
перейти на вкладку Шрифт и выбрать там шрифт Lucida Console и нажмите OK. На
вопрос хотите ли вы применить эти свойства только к текущему окну или ко всем
окнам с тем же именем выберете, применить ко всем окнам с тем же именем.
#include <iostream> //!!! Потоковый ввод/вывод
#include <math.h>
#include <windows.h>
using namespace std;
//!!! Используем стандартное пространство имён
int main()
{
//Настройки шрифтов и региональных стандартов:
if(SetConsoleCP(1251)==0)
//проверка правильности установки кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;
/* если не удалось установить кодовую страницу, вывод
сообщения об ошибке */
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
cout<<"Программа решает уравнение вида A*x*x + B*x + C =
0\n";
cout<<"Введите A,B,C, разделяя их пробелом ";
double a=0,b=0,c=0,x1=0,x2=0;
cin >> a >> b >> c;
if ( a != 0 ) // Решение квадратного уравнения:
{
double d = b*b - 4*a*c;
//формула вычисления дискриминанта
if ( d > 0 )
{
14
x1 = (-b + sqrt(d)) / (2*a);
x2 = (-b - sqrt(d)) / (2*a);
cout << "Уравнение имеет два корня: " << x1 <<" и
"<< x2 << endl;
}
else if ( d == 0 )
{
x1=(-b) / (2*a);
cout<<"Уравнение имеет один корень: " << x1 <<
endl;
}
else
cout<<"Действительных корней нет\n";
}
else // Решение линейного уравнения b*x + c = 0:
{
if (b)
// Если b != 0
{
x1 = -c / b;
cout<<"Уравнение имеет один корень: " << x1 <<
endl;
}
else if (!c) // Если с = = 0
cout<<"Решением уравнения является любое число
\n";
else
cout<<"Уравнение не имеет решений\n";
}
return 0;
}
//============================================================
Запустите программу, нажав <Ctrl> + <F5>. В появившемся окне нажмите Yes.
Скорее всего сначала Вы увидите сообщения об ошибках (но если вы
ВНИМАТЕЛЬНО!!! набирали, ошибок НЕ будет). Исправляя ошибки, нужно
начинать с первой, поскольку ошибки могут быть наведенными, т.е. одна ошибка
может повлечь за собой множество сообщений. Нажмите <F8>, исправьте ошибку в
выделенной строке и опять нажмите <F8>. Повторяйте эти действия, пока программа
не запустится. Задайте какие-либо исходные данные и получите ответ.
Организация повторения программы
Для того чтобы предоставить возможность не перезапускать программу при
вводе нового набора исходных данных, используют повторение всей программы с
помощью цикла do следующим образом:
#include …
…
#include <conio.h>
/* Необходимо подключить
фнкции _getch() */
using namespace std;
этот
файл
для
использования
15
int main()
{
if(SetConsoleCP(1251)==0)//проверка правильности установки
кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;//если не
удалось установить кодовую страницу, вывод сообщения об ошибке
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
do
{
… //текст программы
} while (_getch() != 27);
return 0; }
Повторение происходит при нажатии любой клавиши на клавиатуре после получения окончательного ответа программы. При нажатии клавиши <Esc> происходит
остановка программы.
Выполнение программы в пошаговом режиме
Отобразите в окне Watch имена всех переменных, используемых в программе.
Выполните пошаговое выполнение программы (F10) для следующих исходных
данных:
1 2 –3
121
123
023
002
000
Определите сами, какой ответ должна выдавать программа для каждого из этих
наборов. Внимательно посмотрите, какие строчки выполняются в том или ином случае,
какие значения принимают переменные. Убедитесь, что программа выполняет именно
те действия, которые она должна выполнять для текущего набора данных, и выдает
именно тот ответ, который должен быть.
Задание для самостоятельного выполнения
Создайте новый проект под своей фамилией с индексом 2 (например Ivanov2).
Помните, что имя программы должно быть записано латинскими буквами.
Напишите программу для решения системы двух линейных уравнений:
a1 x  b1 y  c1

 a 2 x  b2 y  c 2
Используйте формулы:   a1b2  a 2 b1
 x  c1b2  c 2 b1
 y  a1c2  a 2 c1
16
Программа должна выдавать один из трех вариантов ответов:
y

Если   0 , то x  x и y 


иначе если x  0 и y  0 , то “бесконечное множество решений”,
иначе “решений нет”.
(Правда, следует отметить, что во втором случае для системы типа
0 x  0 y  1
должен выдаваться ответ “нет решений”. )

0 x  0 y  2
Организуйте повторение программы.
Отобразите в окне наблюдения (Watch) все переменные, используемые в
программе, и выполните программу в пошаговом режиме для следующих наборов
данных:
1) 2 3 –5
2)
2 -2 3
3) 2 -2 3
3 -2 12
4 -4 6
4 -4 7
Определите, что должна выдавать программа в каждом из этих случаев и
проверьте правильность работы программы.
Продемонстрируйте результаты своей работы преподавателю.
Часть 2
Ветвление в программе с помощью оператора switch
В качестве примера используем программу, которая подсчитывает во входном
потоке количество русских букв 'а', 'у', 'о' и количество остальных символов.
Напечатайте текст нижеследующей программы.
#include<iostream> //!!! Потоковый ввод/вывод
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
//!!! Используем стандартное пространство имён
int main()
{
if(SetConsoleCP(1251)==0)
//проверка правильности установки кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;
/* если не удалось установить кодовую страницу, вывод
сообщения об ошибке */
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
cout<<"Введите строку: "<<endl;
char ch=0;
// счетчики, которые будут хранить количество букв:
int counta = 0, countu = 0, counto = 0, count = 0;
17
while((ch=cin.get())!='\n')
{
switch (ch)
{
case 'а':
case 'А': counta++; break;
case 'у':
case 'У': countu++; break;
case 'о':
case 'О': counto++; break;
//подсчитываются только видимые символы:
default: if (ch>32 || ch < 0) count++;
}
}
cout<<"Количество букв \"а\" = " << counta << endl;
cout<<"Количество букв \"у\" = " << countu << endl;
cout<<"Количество букв \"о\" = " << counto << endl;
cout<<"Количество остальных символов = " << count << endl;
_getch();
/* Используйте вызов этой функции при запуске программы клавишей <F5>, чтобы в
режиме отладки не закрывалось окно, в котором отображаютcя результаты работы
программы*/
return 0;
}
В этой программе оператор switch повторяется командой while. При каждой
проверке условия цикла из входного потока считывается один символ функцией get().
Прочитанный символ сравнивается с символом '\n' , который соответствует нажатию
клавиши <Enter>. Если нажата клавиша <Enter>, ввод заканчивается и программа
выдает результат на экран.
Выполните программу в пошаговом режиме.
Задание для самостоятельного выполнения
Напишите программу, которая считывает с клавиатуры число типа double, затем
символ, обозначающий знак операции (+ - * / % ^) и второе число типа double. С
помощью оператора switch организуйте проверку символа и выполнение
соответствующей операции для заданных чисел (если это возможно). Знак ^
используйте для обозначения возведения в степень. Возведение в степень в C
выполняется функцией pow(x,y), которая возводит x в степень y. Для того, чтобы
использовать эту функцию, не забудьте вставить в начало файла #include <math.h>
Организуйте повторение всей программы до нажатия клавиши <Esc>.
Продемонстрируйте результаты своей работы преподавателю.
18
Лабораторная работа №2
Тема: “Программы, использующие команды повторения (циклы).
Рекуррентные соотношения“
Часть 1
Программы, работающие с натуральными числами
Наберите одну из трех нижеследующих программ (комментарии набивать не
нужно), подберите тестовые исходные данные и выполните программу в пошаговом
режиме. Остальные программы внимательно просмотрите и запомните реализованные
в них алгоритмы.
1. Программа, которая находит наибольший общий делитель двух натуральных
чисел m и n
В программе реализован алгоритм Евклида нахождения НОД: пока числа не равны, заменять большее число на разность большего и меньшего, затем взять любое из
получившихся чисел в качестве ответа.
Пример: найдем НОД чисел 12 и 16
m
n
12 16
12
4
8
4
4
4
НОД(12,16) = 4
#include<iostream>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std
int main()
{
//Настройки шрифтов и региональных стандартов:
if(SetConsoleCP(1251)==0)
//проверка правильности установки кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
long m, n, nod;
/* Выполним проверку исходных данных: оба числа должны быть > 0; */
/* для проверки исходных данных используется цикл do, поскольку тело цикла
должно выполнится хотя бы один раз */
do
{
19
cout<<"Введите 2 натуральных числа ";
cin >> m >> n;
} while (m < 1 || n < 1);
// алгоритм Евклида:
/* используем цикл while потому, что при равенстве введенных чисел тело цикла
не должно выполниться ни разу */
while (m != n)
// пока числа не равны
if (m > n) m -= n;
// заменяем большее число на разность большего и меньшего
else n -= m;
//
nod = m;
// берем любое число в качестве ответа
cout<<"НОД этих чисел= "<< nod << endl;
// выводим ответ на экран
_getch();
return 0;
}
2. Программа, которая проверяет, является ли число простым
Простым называется число, которое делится только на себя и
на единицу. Для того чтобы проверить, является ли число
простым, проверим все возможные делители, отличные от 1 и
самого числа. Первый делитель числа n находится на отрезке от
n , если на этом отрезке нет делителей, значит число 2 до
простое.
#include<iostream>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
double x;
char flag = 1;
/* проверим, что задано натуральное число, т.е. целое и больше 0:
используем сначала число x типа double, которое может иметь дробную часть,и
если задано число, которое <= 0 или не целое, или его нельзя преобразовать к целому
типу, будем повторять ввод */
do
{
20
cout<<"Введите натуральное число <= 4e9 --> ";
cin >> x;
} while (x <= 0 || (unsigned long)x != x || x > 4e9 );
unsigned long n = x; //преобразуем число x в число n целого типа
/* поищем первый делитель; для поиска используем цикл for, поскольку счетчик
цикла i можно использовать в качестве очередного проверяемого делителя: */
for (unsigned long i = 2; i <= sqrt(x); i++)
{
if (n % i == 0) // если n делится на i
{
flag=0;/* отмечаем с помощью специальной переменной
(флажка), что делитель найден */
break; // и прерываем выполнение цикла
}
}
if (flag) cout<< n<<" - простое число\n";
// в зависимости от значения флажка выводим ответ
else cout << n<<" - не простое число\n";
_getch();
return 0;
}
3. Программа, которая проверяет, является ли число палиндромом
Палиндромом называется симметричное число, например 121, 2332 и т.д.
Для того чтобы проверить, является ли число симметричным, разберем копию числа на
цифры, вычисляя остаток от деления на 10, и из цифр соберем перевернутое число,
используя схему Горнера для вычисления значения многочлена. Если исходное и
перевернутое числа равны, значит введенное число является палиндромом.
Пример: Перевернем число 123
Частное от
деления на 10
123
12
1
Остаток от
деления на 10
3
2
1
Вычисление значения перевернутого числа
по схеме Горнера (берем начальное значение m, равное 0, затем повторяем следующие действия: то, что получилось
раньше умножаем на 10 и добавляем
следующую цифру):
m = ((0*10+3)*10+2)*10+1 = 321
#include<iostream>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl;
//если не удалось установить кодовую страницу, вывод сообщения об ошибке
}
21
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
long n, m, copyn;
short c;
cout<< "Введите натуральное число ";
cin>> n;
copyn = n; // берем копию исходного числа
m=0;
do
// повторяем нижеследующие действия:
{
c = copyn % 10; // получаем последнюю цифру числа
m = m * 10 + c; // добавляем цифру в схему Горнера
copyn /= 10; // делим число нацело на 10
} while (copyn); // пока число не равно 0
if (n==m) cout<< n << " - палиндром\n";
else cout<< n << " - не палиндром\n"; /* если исходное и
перевернутое числа равны, значит введенное число – палиндром*/
_getch();
return 0;
}
Часть 2
Программы, использующие рекуррентные соотношения
Рекуррентными называются соотношения, используемые для вычисления
последовательности значений некоторой величины, причем следующее значение этой
величины вычисляется через предыдущее: S i 1  f ( S i ) .
Наберите одну из трех нижеследующих программ (комментарии набивать не
нужно), подберите тестовые исходные данные и выполните программу в пошаговом
режиме. Остальные программы внимательно просмотрите и запомните реализованные
в них алгоритмы.
4. Программа, которая находит числа Фибоначчи в заданном диапазоне.
Числа Фибоначчи вычисляются по следующему правилу:
F1 = 1, F2 = 1, Fi = Fi-1 + Fi-2.
Обозначим Fi, Fi-1 и Fi-2 как F1, F2 и F3.
Начнем с того, что присвоим начальные значения, равные 1, F2 и F3, а дальше
будем повторять следующие действия: F1 = F2; F2 = F3; F3 = F1 + F2. При этом тройка
чисел будет смещаться по числовой оси вправо пока не выйдет за правую границу заданного отрезка.
Вычисление чисел Фибоначчи начинается c двух единиц, но выводить будем
только те числа, которые попадают в заданный диапазон.
#include<iostream>
#include <math.h>
#include <conio.h>
22
#include <windows.h>
using namespace std;
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl; //если не удалось
установить кодовую страницу, вывод сообщения об ошибке
}
if(SetConsoleOutputCP(1251)==0) //тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
long a, b, f1, f2 = 1, f3 = 1;
cout<< "Задайте границы отрезка \n";
cin>> a >> b;
cout<< "Числа Фибоначчи на этом отрезке:\n";
while (f2 <= b) // вычисляем, пока не вышли за правую границу отрезка
{
if (f2 >= a) cout<< f2 << " ";
// выводим, если число не меньше левой границы отрезка
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
cout<< endl;
_getch();
return 0;
}
5. Программа, которая находит значение квадратного корня из заданного числа,

1 x
используя рекуррентное соотношение: y i 1  y i    y i 
2  yi

Обозначим y i и y i 1 как y1 и y2, а заданную точность  как eps.
Взяв в качестве начального значения x/2, будем повторять следующие действия:
y1 делаем равным y2, а у2 вычисляем по заданной формуле. При этом пара y1и y2
x . Процесс
будет перемещаться по числовой оси, приближаясь к значению
вычислений можно закончить, когда будет выполняться соотношение: |y1-y2| <  , при
этом будет выполнено требуемое отношение: | y i  x | <=  .
#include<iostream>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0
{
23
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
double x, eps;
//выполняем ввод данных с проверкой их на допустимость
do
{
cout<< "Задайте x >= 0 ";
cin>> x;
} while (x < 0);
do
{
cout<< "Введите точность > 0 и <1 ";
cin>> eps;
} while (eps <= 0 || eps >= 1);
//выполняем вычисления, используя рекуррентное соотношение:
double y1, y2=x/2;
do
{
y1 = y2;
y2 = y1 + (x/y1 - y1) / 2;
} while (fabs(y2-y1)>=eps);
cout<< "Вычисленное значение корня "<< y2 << endl;
cout<< "контрольное значение " << sqrt(x) << endl;
_getch();
return 0;
}
2
6. Программа, которая вычисляет сумму ряда  x  1  x 2 
x4 x6


2! 3!
с заданной точностью.
Выражение n! называется факториалом числа n и равно 1  2  3    n .
Обозначим сумму ряда как s, а очередной элемент ряда (слагаемое) как sl.
Начальные значения s и sl нужно взять равными первому члену ряда, а дальше для их
вычисления использовать рекуррентные соотношения.
Для вычисления очередного слагаемого используем соотношение:
sl i 1  sl i * x 2 / z , где z = 1, 2, 3… Проверьте, что при использовании этого
соотношения действительно получаются нужные члены ряда и в знаменателе
автоматически образуется факториал. Обратите внимание, что отдельно факториал
вычислять не нужно.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
using namespace std;
int main()
24
{
setlocale(LC_ALL,"rus_rus.1251");
//!!! Настройки шрифтов и региональных стандартов взять от ОС
double e, sl=1, s=1, z=1,x;
cout<<"Введите x ";
cin>>x;
do
{
cout << "Введите точность > 0 ";
cin >> e;
} while (e <= 0);
// выполняем вычисления:
/* повторяем пока не выполнится условие: | s l | <=  , при этом сумма ряда будет
отличаться от не более чем на  */
do
{
sl = sl*x*x / z;
// вычисляем очередное слагаемое
s += sl; // добавляем его к сумме
z += 1; // увеличивае z на 1
} while ( fabs(sl) >= e);
// повторяем, пока не выполнится условие: | s l | <=  , при этом сумма ряда будет
2
// отличаться от  x не более чем на  .
do
{
sl = sl*x*x / z;
// вычисляем очередное слагаемое
s += sl; // добавляем его к сумме
z += 1; // увеличивае z на 1
} while ( fabs(sl) >= e);
// Определим точность вывода результа ( k - количество цифр после точки),
// например если точность вычислений  = 0.001, то результат должен выводиться с
// тремя знаками после точки. Для вычисления k используем следующий алгоритм: пока
//  меньше 1, повторяем следующие действия:  увеличиваем в 10 раз, k увеличиваем
// на 1, например:

k
0.001 0
0.01
1
0.1
2
1
3
int k=0;
while ( e < 1 )
{
e*=10; ++k;
}
// устанавливает точность вывода манипулятор setprecision(),
// при использовании манипуляторов не забывайте подключать к программе
// заголовочный файл <iomanip>
cout<< "Сумма =
" << setprecision(k+1) << s
<< endl;
cout<< "Контрольное значение : " << exp(x*x)<<endl;
_getch();
25
return 0;
}
7. Пример – программа, которая вычисляет сумму ряда
1 1 1
1
  1   
для заданного количества слагаемых.
1! 2! 3!
n!
В этой программе не требуется вводить x и заданную точность, точность
определяется количеством слагаемых: чем больше n, тем выше точность вычисления
суммы ряда. Для решения этой задачи лучше всего подходит цикл for, поскольку здесь
требуется использовать счетчик.
#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
long double s = 1, sl = 1;
long double n;
cout<<"Введите количество слагаемых ";
cin>>n;
// Вычисляем сумму ряда:
for (long double i =1; i <= n; i++)
{
sl /= i;
/* при использовании рекуррентных соотношений факториал вычисляется
автоматически */
s += sl;
}
cout<<"Сумма=" << setprecision(16) << s;
cout<<"\n
e=" << exp(1.0) << endl;
_getch();
return 0;
}
Задания для самостоятельного выполнения
1. Написать программу, которая проверяет, является ли вводимое с клавиатуры
натуральное число совершенным (совершенным называется число, которое равно
сумме своих делителей, например: 6 = 1 + 2 + 3).
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
26
2. Написать программу для вычисления суммы ряда:
x3
x5
x7
sin x  x 


...
3!
5!
7!
с заданной точностью, используя
рекуррентные соотношения.
Вывести контрольное значение, используя функцию sin().
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
3. Написать программу, которая подсчитывает сумму цифр натурального числа.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
4. Написать программу, которая подсчитывает количество цифр натурального числа.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
5. Написать программу, которая извлекает кубический корень из заданного
положительного
числа,
используя
рекуррентное
соотношение:
yi 1  yi 
1 x
(
 yi )
3 y 2i
с заданной точностью.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
6. Написать программу для вычисления суммы ряда
1
1 1 1
1
 1     ...  ( 1) n
e
1! 2! 3!
n!
для n, вводимого с клавиатуры,
используя рекуррентные соотношения.
Вывести контрольное значение, используя функцию exp().
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
7. Написать программу, которая подсчитывает произведение ненулевых цифр
натурального числа.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
8. Написать программу, которая определяет, является ли натуральное число,
вводимое с клавиатуры, числом Фибоначчи. Числа Фибоначчи вычисляются по
следующему правилу: F1 = 1, F2 = 1, Fi = Fi-1 + Fi-2.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
9. Написать
ex  1  x 
программу
2
3
для
вычисления
суммы
ряда:
n
x
x
x

 ...  ( 1) n 
, где
2! 3!
n!
n вводится с клавиатуры,
используя рекуррентные соотношения.
Вывести контрольное значение, используя функцию exp().
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
27
10. Написать программу, которая определяет, является ли вводимое с клавиатуры
натуральное число какой либо степенью числа 2.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
1
11. Написать программу, которая вычисляет
, используя рекуррентное соотношеx
1 1
 y i ) с заданной точностью.
ние: y i 1  (
2 xy i
Вывести на экран контрольное значение.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
12. Написать программу для вычисления суммы ряда:
4 1 1 1
1
 4  4  4  ... 
96 1
3
5
( 2n  1) 4
значение n ввести с клавиатуры.
Вывести на экран контрольное значение.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
13. Написать программу, которая вычисляет факториал (n!) числа n, вводимого с
клавиатуры ( 0! 1 , n! 1  2  3    n ) как натуральное число.
Организовать повторение всей программы и определить, для какого максимального
числа n можно решить эту задачу.
Выполнить программу в пошаговом режиме.
14. Написать программу, которая извлекает корень n-ой степени из заданного
положительного числа, используя рекуррентное соотношение:
1
x
yi 1  yi  ( n 1  yi ) с заданной точностью.
n y i
Вывести на экран контрольное значение.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
15. Написать программу, которая находит наименьшее общее кратное двух
натуральных чисел m и n, используя соотношение: nok = m*n / nod.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
16. Написать программу, которая раскладывает число на простые множители.
Указание: найдя очередной множитель, разделить число на него, и после этого
опять проверять возможные множители, начиная с 2; тогда не придется проверять,
является ли множитель простым.
17. Написать программу, которая определяет количество делителей натурального
числа.
Организовать повторение всей программы.
Выполнить программу в пошаговом режиме.
28
Лабораторная работа № 3
Тема: “Программы, использующие вспомогательные функции”.
Наберите одну из нижеследующих программ (комментарии набивать не нужно),
подберите тестовые исходные данные и выполните программу в пошаговом режиме.
Остальные программы внимательно просмотрите и запомните реализованные в них
алгоритмы.
1. Программа, которая считывает координаты вершин треугольника на
плоскости и находит все углы этого треугольника в градусах.
a  b  sin C
.
2
Чтобы воспользоваться этой формулой для нахождения угла, нужно найти длины
сторон треугольника.
Углы треугольника можно найти через площадь, поскольку S 
#include<iostream>
#include<iomanip>
#include<conio.h>
#include <windows.h>
#define _USE_MATH_DEFINES
/* Это определение необходимо включать перед подключением математической
библиотеки для использования математических констант */
#include <math.h>
using namespace std;
//-------------------------------------------------------------------//функция Len, которая будет находить длину отрезка между двумя точками,
// используя формулу l  ( x1  x 2) 2  ( y1  y 2) 2 :
double Len ( double x1, double y1, double x2, double y2)
{
return sqrt( pow(x1-x2,2) + pow(y1-y2,2) );
}
//-----------------------------------------------------------/* Следующая функция будет находить угол между двумя сторонами в градусах. В
качестве аргументов функция должна получать длины двух сторон и площадь
треугольника */
double Angle(double a, double b, double s)
{
double x = 2*s / (a*b); //x – это sin C
// находим угол и переводим его в градусы
return asin(x) * 180 / M_PI;
}
//============================================================
int main()
{
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
29
}
double x1, y1, x2, y2, x3, y3; // Координаты вершин
double a, b , c, u1, u2, u3; // Длины сторон и углы треугольника
do
{
cout<<"Введите координаты вершин треугольника: x1 y1
x2 y2 x3 y3 " ;
cin>> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
// Находим длины сторон, вызывая функцию Len()
a=Len(x1,y1,x2,y2);
c=Len(x2,y2,x3,y3);
b=Len(x1,y1,x3,y3);
/* Проверяем возможность построения треугольника: сумма любых двух сторон
должна быть больше третьей стороны
*/
if (a+b>c && b+c>a && a+c>b)
{
cout<<"Длины сторон треугольника: "
<<setprecision(2)<<a<<' '<<b<<' '<<c<<endl;
// Находим площадь треугольника по формуле Герона:
double p = (a+b+c)/2;
double s = sqrt(p*(p-a)*(p-b)*(p-c));
// Находим углы, используя функцию Angle():
u1 = Angle(a, b, s);
u2 = Angle(b, c, s);
u3 = Angle(a, c, s);
cout<<"Углы треугольника: "<<u1<<' '<<u2<<'
'<<u3<< " градусов" << endl;
}
else
cout << "Треугольник вырожден\n";
} while (_getch()!=27);
return 0;
}
2. Программа, которая находит заданное количество чисел, содержащих цифру 3
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<windows.h>
using namespace std;
bool hold3(long n); /* Объявляем функцию, которая будет определять,
содержит ли число цифру 3. Функция будет возвращать значение истина или ложь (true
или false), поэтому функция имеет тип bool. */
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
30
}
if(SetConsoleOutputCP(1251)==0) //тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
int k=0, count = 0;
/* k – количество чисел, которое нужно найти,
count – количество уже найденных чисел */
cout<<"Сколько чисел нужно найти ";
cin >> k;
long n = 1;
/* будем проверять все числа числового ряда, начиная c 1 */
while (count < k) /* пока заданное количество чисел не найдено,
повторяем следующие действия: */
{
if (hold3(n))
// если число содержит цифру 3
{
cout<< n << " ";
// выводим это число
count++;
// и увеличиваем счетчик на 1
}
n++; /* берем следующее число*/
if ( n > 1000 ) break; /* если мы проверяем все числа числового ряда, мы должны помнить, что этот ряд бесконечен, а компьютер может работать
только в конечном диапазоне, зависящем от типа числа. В данном примере проверяемые числа ограничены числом 1000, чтобы выводимые числа уместились на экране. */
}
if (count < k)
cout<< "Не удалось найти заданное количество чисел";
cout<< endl;
_getch();
return 0;
}
/* определение функции, которая проверяет одно число и устанавливает, содержит ли
оно цифру 3: */
bool hold3(long n) // аргументом функции является число n
{
/* алгоритм проверки цифр основан на алгоритме, описанном в примере 3
лабораторной работы № 2 */
do
{
unsigned cifra = n % 10; /* Находим цифру путем вычисления
остатка от деления на 10 */
if (cifra == 3) return true;
n /= 10;
} while (n);
return false;
}
3. Программа, которая находит на заданном отрезке натуральные числа,
которые можно представить в виде суммы квадратов двух натуральных чисел.
#include<iostream>
#include<iomanip>
31
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
/* Определяем функцию, которая будет определять, можно ли представить число
в виде суммы квадратов двух натуральных чисел. Поскольку должно выполняться
равенство n  a 2  b 2 , будем проверять все возможные значения a в диапазоне
[1, n  1] и для каждого а будем вычислять b по формуле: b  n  a 2 . Поскольку b
должно быть натуральным, округлим результат вычисления по формуле до
ближайшего целого. Если в результате округления равенство n  a 2  b 2 нарушается,
значит число нельзя представить в виде суммы квадратов двух натуральных чисел.
Аргументами функции являются: проверяемое число n и ссылки на a и b; a и b
объявлены как ссылки, поскольку функция должна передать их найденные значения
главной программе, которая выведет их на экран. Функция возвращает либо 0, либо 1.
*/
byte IsPossible(long n, long& a, long& b)
{
byte flag = 0;
for (a = 1; a < sqrt((double)(n)); a++)
{
b = long(sqrt((double)(n - a*a)) + .5);
if (n == a * a + b * b)
{
flag = 1; break;
}
}
return flag;
}
//=========================================================
/* Главная программа проверяет заданный диапазон и выводит найденные числа на
экран */
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0) //тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
long m, n;
long a, b;
cout<< "Задайте диапазон (два натуральных числа) \n";
cin >> m >> n;
byte flag=0;
// Проходим заданный диапазон [m,n] и проверяем число i:
for (long i = m; i <= n; i++)
if (IsPossible(i, a, b)) /* Если i удовлетворяет условию,
выполняем нижеследующие действия: */
{
32
if (!flag) /* Если флажок равен 0, значит найдено первое число, в
этом случае выводим поясняющий текст: */
{
cout<< "Числа, которые можно представить ";
cout<< "в виде суммы квадратов двух натуральных
чисел\n";
}
flag = 1; /* Делаем флажок равным 1, текст больше выводиться не
будет */
cout<< i << " = " << a << "*" << a <<" + " << b <<
"*" << b << endl;
// Вывели результат типа 5 = 1*1 + 2*2
}
/* Здесь проверка заданного отрезка закончилась, если флажок остался
равным 0, выводим сообщение: */
if (!flag) cout<< "На этом отрезке нет нужных
чисел\n";
_getch();
return 0;
}
4. Программа, которая находит первое автоморфное число справа от
заданного.
Автоморфным называется число, которое равно последним цифрам своего
квадрата, например 25 (25 * 25 = 625).
#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
bool Automorfnoe(long n)
{
long copy = n;
// Берем копию числа n
long m = 1; /* Сделаем число m, которое равно степени 10, причем
степень равна количеству цифр проверяемого числа n, например для 25 число m = 100
*/
do
{
m *= 10;
copy /= 10;
} while(copy);
if ((n*n % m) == n) /* Берем остаток от деления квадрата числа n на m и
получаем число, состоящее из последние цифр квадрата n, количество которых равно
количеству цифр исходного числа, сравниваем полученное число c n и возвращаем истину, если числа равны */
return true;
else return false;
}
33
int main()
{
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
do
{
long m;
cout<< "Задайте целое число ";
cin>> m;
// Поиск автоморфного числа n, лежащего справа от заданного числа m:
long n = m+1; // Берем первое число
bool flag = true;
while (!Automorfnoe(n)) // пока число не автоморфное
{
n++; // переходим к следующему числу
if (n > 1e5) { flag = FALSE; break;}
/* прерываем поиск, если число стало слишком большим, чтобы
ограничить время выполнения программы и не выйти за допустимый диапазон чисел */
}
if (flag) // флажок, равный true, означает, что число найдено
cout<< "Автоморфное число справа - " << n << " :
" << n <<" в квадрате = " << n * n << endl;
else cout<< "Число не найдено \n";
} while (_getch() != 27);
return 0;
}
5. Программа находит точки пересечения линий y= ax+b и y = c/x +d
(программа иллюстрирует перегрузку имени функции)
Для нахождения точек пересечения решим систему:
ax 2  (b  d ) x  c  0
 y  ax  b


  y  ax  b
c


 y  x  d
x0
Если a не равно 0, решаем квадратное уравнение, в противном случае – линейное.
#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;
/* Определим две функции Root(корень), одну для решения квадратного уравнения, а
другую – для линейного: */
34
void Root(double a, double b, double c, double& x1, double& x2,
byte& k);
void Root(double a, double b, double& x, byte& k);
// Результаты работы функции объявлены как ссылки
int main()
{
if(SetConsoleCP(1251)==0)
//проверка правильности установки кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
double a, b, c, d;
double x1, y1, x2, y2;
byte k;
// количество корней
do
{
cout<< "Задайте a b c d ";
cin>> a >> b >> c >> d;
if (a) // Если а не равно 0, решаем квадратное уравнение
Root(a, b-d, -c, x1, x2, k);
// передаем функции коэффициенты уравнения и получаем корни и количество корней
else
// иначе решаем линейное уравнение:
Root(b-d, -c, x1, k);
// в зависимости от полученного значения k выводим ответ:
switch(k)
{
case 3: cout<< "Линии совпадают \n"; break;
case 2: y1 = a*x1 + b; y2 = a*x2 + b;
cout<<"Линии пересекаются в 2 точках: "
<<setprecision(2)<< x1 << ',' << y1 << " и " << x2 << ',' <<
y2 << endl; break;
case 1: y1 = a*x1+ b;
cout<<"Линии имеют одну общую точку
"<<setprecision(2)<< x1 << ',' << y1 << endl; break;
default: cout<<"Линии не пересекаются\n";
}
} while (_getch() != 27);
return 0;
}
// Подпрограмма для решения квадратного уравнения
void Root(double a, double b, double c, double& x1, double&
x2, byte& k)
{
double d = b*b - 4*a*c;
if (d > 0)
{
k = 2;
x1 = (-b + sqrt(d)) / (2*a);
x2 = (-b - sqrt(d)) / (2*a);
35
if ( x1==0 || x2 == 0 ) k = 1;
// Исключаем нулевое значение x
if ( x1 == 0) x1 = x2;
/* Если ненулевой корень один, то он
будет храниться в x1 */
}
else if (d == 0)
{
x1 = -b / (2*a);
k = 1;
if (x1 == 0) k = 0;
}
else k = 0;
}
// Подпрограмма для решения линейного уравнения
void Root(double a, double b, double& x, byte& k)
{
if (a)
{
k = 1;
x = -b / a;
if (x == 0) k = 0;
}
else if (b) k = 0;
else k = 3;
}
6. Программа для вычисления биноминальных коэффициентов
Чтобы вычислить биноминальные коэффициенты, можно использовать
рекуррентное соотношение: C n0  C nn  1; C nm  C nm1  C nm11 . Для программирования
вычислений по такому соотношению, лучше всего подходит рекурсивная функция,
т.е. функция, которая вызывает сама себя.
#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;
// Рекурсивная функция, которая точно соответствует рекуррентным соотношениям:
int C(int m, int n)
{
if (m == 0 || m == n)
return 1;
else return C(m, n-1) + C(m-1, n-1);
}
int main()
{
//Настройки шрифтов и региональных стандартов
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl;
}
36
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
int n;
cout<< "Задайте n ";
cin >> n;
cout<< "Биноминальные коэффициенты: \n" ;
for (int m = 0; m <= n; m++)
cout<< C(m, n) << " ";
cout<< endl;
_getch();
return 0;
}
Задания для самостоятельного выполнения
1.
Написать программу, которая находит точки пересечения линий, заданных
уравнениями: x2 +(y-a)2 = b2 и y = cx.
Решить задачу с использованием функции.
Подобрать тестовые данные так, чтобы получить все варианты ответов.
Нарисовать на листе бумаги графики, соответствующие тестовым данным.
2.
Написать программу, которая находит точки пересечения линий, заданных
уравнениями: (x-a)2 + y2 = b2 и (x-c)2 + y2 = d2.
Решить задачу с использованием функции.
Подобрать тестовые данные так, чтобы получить все варианты ответов.
Нарисовать на листе бумаги графики, соответствующие тестовым данным
3.
Написать программу, которая находит точки пересечения линий, заданных
уравнениями: y = ax2 + bx + c и y = dx + k.
Решить задачу с использованием функции.
Подобрать тестовые данные так, чтобы получить все варианты ответов.
Нарисовать на листе бумаги графики, соответствующие тестовым данным.
4.
Написать программу, которая считывает длины сторон треугольника, проверяет
возможность построения треугольника и находит все медианы этого треугольника.
Решить задачу с использованием функции, которая вычисляет длину одной
медианы.
5.
Написать программу, которая считывает координаты вершин треугольника на
плоскости, проверяет возможность построения треугольника и находит радиусы
вписанной и описанной окружностей.
Решить задачу с использованием функции, которая вычисляет длину одной
стороны треугольника.
6.
Написать программу, которая считывает длины сторон треугольника, проверяет
возможность построения треугольника и находит все биссектрисы этого треугольника. Решить задачу с использованием функции, которая вычисляет длину
одной биссектрисы.
37
7.
Написать программу, которая находит в заданном диапазоне числа, которые
являются палиндромами, и выводит их на экран.
Проверку "палиндром – не палиндром" оформить в виде функции.
8.
Написать программу, которая находит заданное количество чисел, которые
являются палиндромами, и выводит их на экран Проверку "палиндром – не
палиндром" оформить в виде функции".
9.
Написать программу, которая считывает число с клавиатуры и находит ближайшее
справа натуральное число, которое является палиндромом, и выводит его на экран.
Проверку "палиндром – не палиндром" оформить в виде функции".
10. Написать программу, которая считывает число с клавиатуры и находит ближайшее
справа число, которое является квадратом натурального числа, и выводит его на
экран.
Проверку "квадрат – не квадрат" оформить в виде функции.
11. Написать программу, которая на заданном отрезке находит все числа, являющиеся
квадратами натуральных чисел, и выводит их на экран. Проверку "квадрат – не
квадрат" оформить в виде функции.
12. Написать программу, которая находит заданное количество чисел, являющихся
квадратами натуральных чисел, и выводит их на экран.
Проверку "квадрат – не квадрат" оформить в виде функции.
13. Написать программу, которая находит на заданном отрезке все числа, которые
равны сумме кубов своих цифр (например: 153 = 13 + 53 + 33) и выводит их на
экран. Проверку числа оформить в виде функции.
14. Написать программу, которая находит заданное количество чисел, которые равны
сумме кубов своих цифр (например:153 = 13 + 53 + 33)и выводит их на экран.
Проверку числа оформить в виде функции.
15. Написать программу, которая считывает число с клавиатуры и находит ближайшее
справа число, которое равно сумме кубов своих цифр (например:
153 = 13 + 53 + 33) и выводит его на экран. Проверку числа оформить в виде
функции.
16. Два нечетных простых числа, разность которых равна 2, называются близнецами.
Написать программу, которая находит все числа-близнецы на заданном отрезке и
выводит их на экран. Проверку "простое – не простое" оформить в виде функции.
17. Два нечетных простых числа, разность которых равна 2, называются близнецами.
Написать программу, которая находит заданное количество чисел-близнецов и
выводит их на экран.
Проверку "простое – не простое" оформить в виде функции.
18. Написать программу, которая находит заданное количество чисел, равных сумме
квадратов двух натуральных чисел и выводит их на экран.
Проверку числа оформить в виде функции.
38
19. Написать программу, которая на заданном интервале находит все пары
"дружественных" чисел и выводит их в список. "Дружественными" называются
числа, каждое из которых равно сумме всех натуральных делителей другого,
исключая само другое число, например, такими числами являются 220 и 284.
Вычисление суммы делителей числа оформить в виде функции.
20. Написать программу, которая на заданном интервале находит заданное количество
пар "дружественных" чисел и выводит их на экран."Дружественными" называются
числа, каждое из которых равно сумме всех натуральных делителей другого,
исключая само другое число, например, такими числами являются 220 и 284.
Вычисление суммы делителей числа оформить в виде функции.
21. Написать программу, которая на заданном интервале находит все автоморфные
числа. Автоморфным называется число, которое равно последним цифрам своего
квадрата, например, 52 = 25, 252 = 625.
Проверку числа оформить в виде функции.
22. Написать программу, которая находит заданное количество автоморфных чисел и
выводит их в список. Автоморфным называется число, которое равно последним
цифрам своего квадрата, например, 52 = 25, 252 = 625.
Проверку числа оформить в виде функции.
23. Написать программу, которая считывает число с клавиатуры и находит ближайшее
справа натуральное число, которое является числом Фибоначчи (см. Лаб. раб. №2)
, и выводит его на экран. Проверку числа оформить в виде функции".
24. Написать программу, которая находит в заданном диапазоне все числа, которые
являются степенями двойки, и выводит их на экран.
Проверку "степень – не степень" оформить в виде функции.
25. Написать программу, которая находит заданное количество чисел, которые являются степенями двойки, и выводит их на экран. Проверку " степень – не степень "
оформить в виде функции".
26. Написать программу, которая считывает число с клавиатуры и находит ближайшее
справа натуральное число, которое является степенью двойки, и выводит его на
экран. Проверку " степень – не степень " оформить в виде функции".
27. Написать программу, которая находит в заданном диапазоне все числа, которые
содержат две шестерки, и выводит их на экран.
Проверку числа оформить в виде функции.
28. Написать программу, которая считывает число с клавиатуры и находит ближайшее
справа натуральное число, которое является содержит три шестерки, и выводит его
на экран. Проверку числа оформить в виде функции".
29. Написать программу, которая вычисляет факториал натурального числа, вводимого с клавиатуры с помощью рекурсивной функции. Проверить, для какого максимального числа можно получить точное значение факториала.
n! = 1*2*3…*n
39
30*. Написать программу, которая по известным корням многочлена восстанавливает
все коэффициенты многочлена. Для вычислений использовать рекурсивную функцию.
Рекомендуется воспользоваться соотношением:
Xn + an-1Xn-1 + … a1X + a0 = (X-x1) * (X – x2) * … *(X-xn)
Лабораторная работа № 4
Тема: “Программы, использующие строки символов ”.
Наберите одну из нижеследующих программ (комментарии набивать не нужно),
подберите тестовые исходные данные и выполните программу в пошаговом режиме.
Остальные программы внимательно просмотрите и запомните реализованные в них
алгоритмы.
Ниже приведена таблица функций работы со строками и их краткое описание. За
более подробной справкой обращайтесь к MSDN!
String-Manipulation Routines(Процедуры манипуляции строками)
Routine (Процедура)
Use (Использование)
strcoll, wcscoll, _mbscoll, _strcoll_l,
_wcscoll_l, _mbscoll_l, _stricoll, _wcsicoll,
_mbsicoll, _stricoll_l, _wcsicoll_l, _mbsicoll_l,
_strncoll, _wcsncoll, _mbsncoll, _strncoll_l,
_wcsncoll_l, _mbsncoll_l, _strnicoll,
_wcsnicoll, _mbsnicoll, _strnicoll_l,
_wcsnicoll_l, _mbsnicoll_l
Сравнивают две строки используя
информацию кодовой страницы (_mbsicoll
и _mbsnicoll не чувствительны к регистру)
_mbsdec, _mbsdec_l, _strdec, _wcsdec
Передвигают указатель строки на один
символ назад
_mbsinc, _mbsinc_l, _strinc, _wcsinc
Передвигают указатель строки на один
символ вперёд
_mbsnbcat, _mbsnbcat_l, _mbsnbcat_s,
_mbsnbcat_s_l
Присоединяют первые n байт одной строки
символов к другой
_mbsnbcmp, _mbsnbcmp_l
Сравнивают первые n байт двух
символьных строк
_mbsnbcnt, _mbsnbcnt_l, _mbsnccnt,
_mbsnccnt_l, _strncnt, _wcsncnt
Возвращает количество байт символов
внутри строки символов
_mbsnbcpy, _mbsnbcpy_l, _mbsnbcpy_s,
_mbsnbcpy_s_l
Копирует n байт строки
_mbsnbicmp, _mbsnbicmp_l
Сравнивает n байт двух строк, игнорируя
регистр
_mbsnbset, _mbsnbset_l
Устанавливает первые n байт строки на
указанный символ
_mbsnbcnt, _mbsnbcnt_l, _mbsnccnt,
_mbsnccnt_l, _strncnt, _wcsncnt
Возвращает число символов внутри
поданной последовательности байт
_mbsnextc, _mbsnextc_l, _strnextc,
_wcsnextc
Находит следующий символ в строке
_mbsninc, _mbsninc_l, _strninc, _wcsninc
Advance string pointer by n characters
Передвигает указатель строки на n
символов вперёд
_mbsspnp, _mbsspnp_l, _strspnp, _wcsspnp
Передвигает указатель к первому символу
40
в данной строке, который не содержится в
другой данной строке
_scprintf, _scprintf_l, _scwprintf, _scwprintf_l
Возвращает количество символов в
форматированной строке
_snscanf, _snscanf_l, _snwscanf,
_snwscanf_l, _snscanf_s, _snscanf_s_l,
_snwscanf_s, _snwscanf_s_l
Читает форматированные данные заданной
длинны из стандартного потока ввода
sscanf, _sscanf_l, swscanf, _swscanf_l,
sscanf_s, _sscanf_s_l, swscanf_s,
_swscanf_s_l
Читает форматированные данные заданной
длинны из стандартного потока ввода
sprintf, _sprintf_l, swprintf, _swprintf_l,
__swprintf_l, sprintf_s, _sprintf_s_l,
swprintf_s, _swprintf_s_l, _sprintf_p,
_sprintf_p_l, _swprintf_p, _swprintf_p_l
Записывает форматированные данные в
строку
strcat, wcscat, _mbscat, strcat_s, wcscat_s,
_mbscat_s
Присоединяет одну строку к другой
strchr, wcschr, _mbschr, _mbschr_l
Находит первое появление заданного
символа в строке
strcmp, wcscmp, _mbscmp
Сравнивает две строки
strcoll, wcscoll, _mbscoll, _strcoll_l,
_wcscoll_l, _mbscoll_l, _stricoll, _wcsicoll,
_mbsicoll, _stricoll_l, _wcsicoll_l, _mbsicoll_l,
_strncoll, _wcsncoll, _mbsncoll, _strncoll_l,
_wcsncoll_l, _mbsncoll_l, _strnicoll,
_wcsnicoll, _mbsnicoll, _strnicoll_l,
_wcsnicoll_l, _mbsnicoll_l
Сравнивает две строки используя текущую
кодовую страницу (_stricoll, _wcsicoll,
_strnicoll, and _wcsnicoll не чувствительны
к регистру)
strcpy, wcscpy, _mbscpy, strcpy_s, wcscpy_s,
_mbscpy_s
Копирует одну строку в другую
strcspn, wcscspn, _mbscspn, _mbscspn_l
Находит первое появление символа из
заданного набора символов в строке
_strdup, _wcsdup, _mbsdup, _strdup_dbg,
_wcsdup_dbg
Делает копию строки
strerror, _strerror, _wcserror, __wcserror,
strerror_s, _strerror_s, _wcserror_s,
__wcserror_s
Отображает номер ошибки в строку
сообщения
strftime, wcsftime, _strftime_l, _wcsftime_l
Форматирует строку даты и времени
_stricmp, _wcsicmp, _mbsicmp, _stricmp_l,
_wcsicmp_l, _mbsicmp_l
Сравнивают две строки без учёта регистра
strlen, strlen_l, wcslen, wcslen_l, _mbslen,
_mbslen_l, _mbstrlen, _mbstrlen_l, strnlen,
strnlen_l, wcsnlen, wcsnlen_l, _mbsnlen,
_mbsnlen_l, _mbstrnlen, _mbstrnlen_l
Находит длину строки
_strlwr, _wcslwr, _mbslwr, _strlwr_l,
_wcslwr_l, _mbslwr_l, _strlwr_s, _strlwr_s_l,
_mbslwr_s, _mbslwr_s_l, _wcslwr_s,
_wcslwr_s_l
Переводят строку в нижний регистр
strncat, _strncat_l, wcsncat, wcsncat_l,
_mbsncat _mbsncat_l, strncat_s,
_strncat_s_l, wcsncat_s, _wcsncat_s_l,
_mbsncat_s, _mbsncat_s_l
Присоединяют символы к строке
strncmp, wcsncmp, _mbsncmp, _mbsncmp_l
Сравнивают символы двух строк
41
strncpy, _strncpy_l, wcsncpy, _wcsncpy_l,
_mbsncpy, _mbsncpy_l, strncpy_s,
_strncpy_s_l, wcsncpy_s, _wcsncpy_s_l,
_mbsncpy_s, _mbsncpy_s_l
Копируют символы одной строки в другую
_strnicmp, _wcsnicmp, _mbsnicmp,
_strnicmp_l, _wcsnicmp_l, _mbsnicmp_l
Сравнивают символы двух строк без учёта
регистра
_strnset, _strnset_l, _wcsnset, _wcsnset_l,
_mbsnset, _mbsnset_l
Устанавливают первые n символов строки
равным заданному символу
strpbrk, wcspbrk, _mbspbrk, _mbspbrk_l
Находит первое вхождение символа из
одной строки в другую
strrchr, wcsrchr, _mbsrchr, _mbsrchr_l
Находит первое вхождение символа из
одной строки в другую с конца
_strrev, _wcsrev, _mbsrev, _mbsrev_l
Переворачивает строку
_strset, _strset_l, _wcsset, _wcsset_l,
_mbsset, _mbsset_l
Устанавливают все символы строки
равными заданному
strspn, wcsspn, _mbsspn, _mbsspn_l
Находят первую подстроку одной строки в
другой
strstr, wcsstr, _mbsstr, _mbsstr_l
Находят первое вхождение определённой
строки в другую строку
strtok, _strtok_l, wcstok, _wcstok_l, _mbstok,
_mbstok_l, strtok_s, _strtok_s_l, wcstok_s,
_wcstok_s_l, _mbstok_s, _mbstok_s_l
Находят следующую лексему в строке
_strupr, _strupr_l, _mbsupr, _mbsupr_l,
_wcsupr_l, _wcsupr, _strupr_s, _strupr_s_l,
_mbsupr_s, _mbsupr_s_l, _wcsupr_s,
_wcsupr_s_l
Преобразует строку в верхний регистр
strxfrm, wcsxfrm, _strxfrm_l, _wcsxfrm_l
Преобразует строку в объединённую
форму основанную на местной
информации
vsprintf, _vsprintf_l, vswprintf, _vswprintf_l,
__vswprintf_l, vsprintf_s, _vsprintf_s_l,
vswprintf_s, _vswprintf_s_l, _vsprintf_p,
_vsprintf_p_l, _vswprintf_p, _vswprintf_p_l
Записывают форматированную строку
vsnprintf, _vsnprintf, _vsnprintf_l,
_vsnwprintf, _vsnwprintf_l, vsnprintf_s,
_vsnprintf_s, _vsnprintf_s_l, _vsnwprintf_s,
_vsnwprintf_s_l
Записывают форматированную строку
1. Программа, которая считывает строку символов и сортирует ее по
возрастанию кодов символов
Программа иллюстрирует процесс формирования строки, удовлетворяющей
условию.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include <windows.h>
using namespace std;
42
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
char str1[81], str2[81];
int n=0;
cout << "Задайте строку символов\n";
cin.getline(str1, 80);
for (int i= 32; i<255; i++)
for (int j = 0; j < strlen(str1); j++)
if ( str1[j]+128 == i )
str2[n++] = i-128;
str2[n] = '\0';
cout << "Отсортированная строка:\n";
cout << str2 << endl;
_getch();
return 0;
}
2. Программа перевода числа из десятичной системы счисления в двоичную
Для перевода числа в двоичную систему необходимо получить цифры двоичного
числа, для этого используем тот же алгоритм, что и для получения десятичных цифр:
будем брать остатки от деления на 2. Для получения числа нужно записать цифры в
обратном порядке. Двоичное число будем хранить в виде строки символов.
Первый вариант (с использованием указателя)
#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <String.h>
#include <windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl;//если не
удалось установить кодовую страницу, вывод сообщения об ошибке
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
43
long dec; // десятичное число, которое мы будем переводить
byte ost; // остаток от деления на 2 (двоичная цифра)
char tmp[81]; // строка, которая будет хранить двоичное (binary) число
cout << "Введите неотрицательное целое десятичное число ";
cin >> dec;
char *bin;
//Указатель, который мы будем использовать для получения символа
bin = &(tmp[80] = 0);
/* Присваиваем указателю bin значение, равное адресу последнего символа
строки tmp */
do
{
ost = byte (dec % 2);
*(--bin) = ost + '0';
dec = dec / 2;
} while (dec);
/* Операция декремент (--bin) позволяет записывать цифры в строку в обратном
порядке */
cout << "Соответствующее 2-ое число: ";
cout << bin << endl; // выводим значение по адресу bin, а не tmp!
_getch();
return 0;
}
/* При организации повторения программы, необходимо обратить внимание на то, что
при каждом повторении указателю bin должнo присваиваться значение адреса
последнего символа строки tmp */
Второй вариант ( с использованием индексации)
#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <String.h>
#include <windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
long dec;
byte ost;
char bin[81];
cout <<"Введите целое десятичное число --> ";
cin >> dec;
44
int i = 0; // номер символа в строке
do
{
bin[i++] = dec % 2 + '0'; // записываем цифры в начало строки
dec = dec / 2;
} while (dec);
bin[i] = ‘\0’; // Не забудем отметить конец строки
strrev(bin);
// Для получения правильного ответа строку необходимо перевернуть
cout<<"Соответствующее 2-ое число:\n";
cout<<bin<<endl;
_getch();
return 0;
}
/* Второй вариант может показаться более понятным, однако в этом случае нам
пришлось воспользоваться функцией strrev () из библиотеки функций для работы со
строками, а использование указателей дает нам больше возможностей по работе с
ячейками памяти */
3. Программа перевода числа из двоичной системы в десятичную
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0
{
cerr<<"Fialed to set codepage!"<<endl
}
if(SetConsoleOutputCP(1251)==0
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
char bin[81]; // Строка для хранения двоичного числа
long dec=0; // Результат перевода
char *pb = bin; /* указатель, с помощью которого мы будем получать
символы строки (двоичные цифры) */
char ch;
int i=0;
cout << "Введите двоичное число без знака "<<endl;
do
{
ch=_getch();
if(ch=='0'||ch=='1')
45
{
bin[i++]= ch;
cout << ch;
}
} while (ch != '\r' && i < 81);
bin[i]=’\0’;
cout << endl;
while (*pb)
// пока строка не закончена
dec = dec * 2 + *pb++ - '0';
// вычисляем dec, используя схему Горнера
cout << "Соответствующее десятичное число: ";
cout << dec << endl ;
_getch();
return 0;
}
4. Программа перевода числа из 16-ой системы счисления в 2-ую.
Для перевода 16-го числа в двоичное преобразуем каждую 16-ю цифру в
десятичное число, которое в свою очередь переведем в четверку 2-х цифр. Поскольку
при переводе мы получаем цифры в обратном порядке, перевернем все 16-е число,
переведем каждую цифру, затем перевернем всю 2-ю строку ( например: b6 -> 6b ->
0110 1101 -> 1011 0110)
В этом примере будем считывать 16-е число посимвольно с проверкой каждого
символа.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
char ch;
int n, k ;
char hex[81]; // 16-е число
char bin[321]; // 2-е число
cout<<"Введите 16-ое число: \n";
n=0; k=0; // счетчики символов
46
while ( ( ch=_getch() ) != '\r') /* пока не нажата клавиша
<Enter>, считываем символы с помощью функции _getch() */
{
if (isxdigit(ch) && k<79) /* если считана 16-я цифра и кол-во цифр
не слишком велико */
{
сout << ch; hex[k++]= toupper(ch); /* выводим символ на
экран и записываем его в строку hex, предварительно преобразовав в большую букву */
}
else if (ch == '\b' && k > 0 ) /* Если нажата клавиша
<Backspace> и количество символов в строке > 0 */
{
Cout << "\b \b"; // стираем последний символ на экране
k--; // и возвращаемся в строке на 1 байт назад
}
} //end while
hex[k]=0; bin[n]=0; cout << endl;
// Отмечаем концы строк и переводим курсор
cout << hex << endl; // Выводимое 16-е число будет записано большими
буквами
// Перевод:
_strrev(hex); // Переворачиваем 16-е число
int des; //Здесь будет храниться 10-е число, соответствующее каждой 16-й
цифре
for (UINT i=0; i<strlen(hex); i++) // проходим по строке,
хранящей 16-е число
{
// если очередной символ - цифра
if (hex[i] <= '9')
des = hex[i] - '0'; // получаем соответствующее число
else des = hex[i]-'A'+10; // иначе получаем число для буквы
// получаем 4 двоичных цифры для одной 16-й:
for (int j=0; j<4; j++)
{
bin[n++] = des % 2 + '0';
des/=2;
}
}
bin[n] = '\0';
_strrev(bin); // переворачиваем 2-е число
cout<<"Соответствующее 2-ое число = \n";
for (UINT i=0; i<strlen(bin); i++)
/* выводим 2-е число,
разделяя каждую четверку цифр пробелом */
{
cout<<bin[i];
if ((i+1)%4==0) cout <<' '; /* Если номер выведенной цифры
делится на 4, выводим пробел */
}
cout <<endl; // не забывайте переводить курсор в начало следующей строки
_getch();
return 0;
}
47
5. Программа перевода числа из 2-ой системы счисления в 16-ую.
В этом примере перевод выполняется по таблице, в которой каждой четверке
двоичных цифр соответствует одна шестнадцатеричная.
В программе используется структура TableString, описывающая одну строку таблицы.
#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <string>
#include <ctype.h>
#include <windows.h>
using namespace std;
struct TableString
{
char hex; // 16-ая цифра
char bin[5];
// строка, содержащая четверку 2-х цифр (строка заканчивается ‘\0’)
};
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
char ch;
// используется для посимвольного ввода
int n=0, k=0 ; // счетчики символов
char hex[21]; // 16-е число
char bin[81]; // 2-е число
char zero[81]; // строка, в начале которой будет записан ‘0’
char tmp[5];
// сюда будет копироваться четверка двоичных цифр из строки bin
strcpy(zero,"0"); // записываем ноль в начало строки
cout<<"Введите 2-ое число: \n";
while ( ( ch=_getch() ) != '\r') // пока не нажата клавиша <Enter>
{
if ( (ch=='0'||ch=='1') && k < 79) // если введена 2-я цифра
{
cout<<ch; bin[k++]=ch;
// Выводим ее на экран и записываем в строку
}
else if (ch == '\b' && k > 0 )
// стирание последнего введенного символа
{
48
cout<<"\b \b";
k--;
}
} //end while
bin[k]=0; hex[n]=0; cout << endl;
//делаем длину строки кратной 4:
while(strlen(bin)%4)
{
strcpy(bin,strcat(zero,bin)); /* складываем строку,
содержащую ‘0’, с bin, затем полученную сумму копируем в bin, в результате в начало
bin добавляется ‘0’ */
strcpy(zero,"0"); /* восстанавливаем zero, она должна содержать
только 1 ноль*/
}
Cout << bin << endl; // проверим, что получилось
// Перевод:
TableString table[16] = { {'0', "0000"}, /* обратите
внимание на то, как инициа// лизируется массив структур */
{'1', "0001"},
{'2', "0010"},
{'3', "0011"},
{'4', "0100"},
{'5', "0101"},
{'6', "0110"},
{'7', "0111"},
{'8', "1000"},
{'9', "1001"},
{'A', "1010"},
{'B', "1011"},
{'C', "1100"},
{'D', "1101"},
{'E', "1110"},
{'F', "1111"} };
// проходим по 2-му числу, обрабатывая по 4 цифры:
for (int i=0; i<strlen(bin); i+=4)
{
strncpy(tmp,bin+i,4); // копируем очередные 4 цифры в tmp
tmp[4] = '\0';
// strncpy() признак конца строки не записывает
for (int j=0; j<16; j++) // выполняем поиск в таблице
if (!strcmp(table[j].bin,tmp)) // если strcmp() вернула
0, значит tmp совпала с i-ой строкой таблицы
{
hex[n++]=table[j].hex; /* копируем 16-ю цифру из
таблицы в строку hex */
break;
}
}
hex[n] = '\0';
cout<<"Соответствующее 16-ое число = \n";
cout<<hex<<endl;
_getch();
return 0;
49
}
6. Программа, которая выводит на экран треугольник Паскаля (треугольник
биноминальных коэффициентов)
Программа иллюстрирует применение строк для центрирования по горизонтали
при выводе результата
#include<iostream>
#include<windows.h>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<string>
#include<ctype.h>
#include <stdlib.h>
using namespace std
/* Для вычисления каждого биноминального коэффициента используем рекурсивную
функцию из Лаб. работы №3.*/
int C(int m, int n)
{
if (m == 0 || m == n)
return 1;
else return C(m,n-1)+C(m-1, n-1);
}
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
int k; // количество строк треугольника
do
{
Cout << "Задайте число строк >0 и <=17 --> ";
/* при k > 17 треугольник не уместится на экране */
Cin >> k;
} while (k<1 || k>17);
int y = 3;
// Номер строки, начиная с которой будет выводится треугольник
char str[81], tmp[11];
// строка для вывода на экран и строка для хранения числа
for (int n=0; n < k; n++) // идем по строкам треугольника Паскаля
{
str[0] = '\0';
for (int m=0; m<=n; m++)
// вычисляем коэффициенты в одной строке
50
{
itoa(C(m,n), tmp, 10);
// делаем из коэффициента строку tmp
strcat(str, tmp);
// добавляем строку tmp в строку str
strcat(str, " "); // разделяем числа пробелами
}
int x = 41-strlen(str)/2; /* определяем, с какой позиции в
строке экрана должна начинаться выводимая строка треугольника Паскаля */
for(int i=0; i<x; i++)
cout<<" ";
cout << str << endl; /* выводим строку с заданной позиции
(строка центрирована по горизонтали) */
y++; // переходим к следующей строке экрана
}
_getch();
return 0;
}
Задания для самостоятельного выполнения
1.
Написать программу, которая считывает строку символов с клавиатуры и
распечатывает в столбик: символ –-> код –-> его двоичный эквивалент
для каждого символа.
Выполнить отладку программы на тестовом примере "01A"
(код '0' – 48, код латинской буквы 'A' – 65).
2.
Написать программу, которая считывает строку символов с клавиатуры и
распечатывает в столбик: символ –-> код –-> его 8-й эквивалент
для каждого символа.
Выполнить отладку программы на тестовом примере "01A"
(код '0' – 48, код латинской буквы 'A' – 65).
3.
Написать программу, которая считывает строку символов с клавиатуры и
распечатывает в столбик: символ –-> код –-> его 16 -й эквивалент
для каждого символа.
Выполнить отладку программы на тестовом примере "1AK"
(код '0' – 48, код латинской буквы 'A' – 65).
4.
Написать программу, которая переводит число из 2-й системы счисления в 12-ю
через 10-ю. Выполнить отладку программы с помощью какого–либо примера,
подготовленного Вами на бумаге.
5.
Написать программу, которая переводит число из 3-й системы счисления в 13-ю
через 10-ю. Выполнить отладку программы с помощью какого–либо примера,
подготовленного Вами на бумаге.
6.
Написать программу, которая переводит число из 4-й системы счисления в 14-ю
через 10-ю. Выполнить отладку программы с помощью какого–либо примера,
подготовленного Вами на бумаге.
7.
Написать программу, которая переводит число из 12-й системы счисления в 2-ю
через 10-ю. Выполнить отладку программы с помощью какого–либо примера,
подготовленного Вами на бумаге.
51
8.
Написать программу, которая переводит число из 13-й системы счисления в 3-ю
через 10-ю. Выполнить отладку программы с помощью какого–либо примера,
подготовленного Вами на бумаге.
9.
Написать программу, которая переводит число из 15-й системы счисления в 5-ю
через 10-ю. Выполнить отладку программы с помощью какого–либо примера,
подготовленного Вами на бумаге.
10. Написать программу, которая переводит число из 2-й системы счисления в 8-ю,
не переводя все число в 10-ю . Выполнить отладку программы с помощью
какого–либо примера, подготовленного Вами на бумаге.
11. Написать программу, которая переводит число из 3-й системы счисления в 9-ю,
не переводя все число в 10-ю. Выполнить отладку программы с помощью какого–
либо примера, подготовленного Вами на бумаге.
12. Написать программу, которая переводит число из 8-й системы счисления в 2-ю,
не переводя все число в 10-ю. Выполнить отладку программы с помощью какого–
либо примера, подготовленного Вами на бумаге.
13. Написать программу, которая переводит число из 9-й системы счисления в 3-ю,
не переводя все число в 10-ю. Выполнить отладку программы с помощью какого–
либо примера, подготовленного Вами на бумаге.
14. Написать программу, которая считывает строку символов, которая считывает
строку, содержащую только числа (с проверкой символов при вводе) и подсчитывает количество знаков “минус” в строке.
15. Написать программу, которая считывает строку символов, состоящую только из
латинских букв, цифр и пробелов (с проверкой символов при вводе), и находит
сумму числовых значений цифр, содержащихся в строке.
16. Написать программу, которая считывает строку символов, состоящую только из
латинских букв, пробелов и знаков препинания (с проверкой символов при вводе). Подсчитать, сколько символов верхнего регистра содержится в строке.
17. Написать программу, которая считывает две строки символов, состоящие только
из цифр и пробелов (напишите подпрограмму для посимвольного ввода с проверкой). Исключите из второй строки те символы, которые есть в первой, и выведите
полученную строку на экран.
18. Написать программу, которая считывает строку, состоящую только из русских
букв и пробелов (с проверкой символов при вводе). Удалите из строки повторяющиеся символы и выведите полученную строку на экран (в результирующую
строку каждый символ должен входить только один раз).
19. Написать программу, которая считывает строку, состоящую только из чисел и
пробелов (с проверкой правильности вводимых символов) и найти сумму этих
чисел.
20. Написать программу, которая считывает строку символов, состоящую только из
слов, записанных русскими буквами, пробелов и знаков препинания (с проверкой
правильности вводимых символов). Удалить лишние пробелы из строки, т.е.
оставить между словами только 1 пробел.
21. Написать программу, которая считывает две строки символов одинаковой длины
и проверяет, является ли вторая строка анаграммой первой, т.е. может ли оно
быть получено некоторой перестановкой букв первого слов (например: крот и
корт).
52
22. Написать программу, которая считывает строку текста, состоящую только из
слов записанных латинскими буквами, разделенных запятыми и пробелами (с
проверкой правильности символов). Если за запятой не стоит пробел, вставить
его и получившуюся строку вывести на экран.
23. Написать программу, которая считывает строку текста, состоящую только из слов
записанных русскими буквами, разделенных точками и пробелами (с проверкой
правильности ввода). Если перед точкой стоят пробелы, удалить их и получившуюся строку вывести на экран.
24. Написать программу, которая считывает строку текста, состоящую только из слов
записанных латинскими буквами, разделенных точками и пробелами (с проверкой правильности ввода). Если первое слово, идущее за точкой, начинается с маленькой буквы, заменить эту букву большой и получившуюся строку вывести на
экран.
25. Написать программу, которая считывает строку текста, состоящую только из
чисел, разделенных пробелами (с проверкой правильности символов). Удалить
лишние пробелы между числами, т.е. из нескольких идущих подряд пробелов
оставить только один. Получившуюся строку вывести на экран.
26. Написать программу, которая считывает строку текста, состоящую только из
слов, записанных русскими буквами, разделенных пробелами (с проверкой правильности ввода). Если в слове встречаются две идущие подряд большие буквы,
заменить вторую большую букву маленькой.
27. Написать программу, которая считывает строку текста, состоящую только из русских букв, пробелов и знаков препинания (с проверкой правильности символов) и
подсчитывает, сколько раз заданный символ (который тоже вводится с клавиатуры) встречается в этой строке.
28. Написать программу, которая считывает строку текста, состоящую только из
цифр, пробелов и запятых (с проверкой правильности ввода). Удалить запятые из
строки и результат вывести на экран.
29. Написать программу, которая считывает строку текста, состоящую только из
русских букв и запятых (с проверкой правильности ввода). Заменить запятые
пробелами и результат вывести на экран.
30. Написать программу, которая считывает строку текста, состоящую только из
латинских букв, цифр и пробелов (с проверкой правильности символов) и
выводит на экран те слова, которые начинаются с цифры (словом называется
любая последовательность символов, не содержащая внутри себя пробелов и
отделенная от других слов пробелами).
53
Лабораторная работа № 5
Тема: “Программы, использующие файлы ”.
1. Программа, которая считывает имя файла, открывает его и подсчитывает
количество скобок каждого вида, содержащихся в файле.
Программа иллюстрирует чтение данных из файла посимвольно.
#include<iostream>
#include<windows.h>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream ifl; // Объявляем файл для чтения
char ch;
char name[20]; // Имя файла
do /* Цикл, который повторяет ввод имени файла до тех пор, пока оно не будет
задано правильно */
{
int i = 0; // Счетчик символов
cout<<"Задайте имя файла: ";
while ((ch = _getche()) != '\r') /* Посимвольное чтение
имени позволит прервать цикл в любой момент при нажатии клавиши <Esc> (конечно,
это не обязательно) */
{
if (ch == 27) exit(0);
else name[i++] = ch;
}
cout<<"\n";
name[i] = '\0';
ifl.open(name,ios::in); // пытаемся открыть файл
if(ifl==0)
// Если файл не открыт, выводим окно с сообщением об ошибке
{
cout<<"Файл не найден!\n"; ch = _getch();
if (ch==27) exit(0); /* Можно прервать программу,
увидев сообщение */
54
}
} while (!ifl); // пока файл не открыт
if (ifl) // Если файл открыт, выполняем основные действия:
{
int val; // Символ, считываемый из файла
int count1=0; // Счетчики скобок
int count2=0;
int count3=0;
int count4=0;
int count5=0;
int count6=0;
while (!ifl.eof()) // пока не конец файла
{
val=ifl.get(); // считываем 1 символ
/* проверяем символ и, если это скобка, увеличиваем соответствующий
счетчик: */
switch (val)
{
case '[': count1++; break;
case ']': count2++; break;
case '(': count3++; break;
case ')': count4++; break;
case '{': count5++; break;
case '}': count6++;
}
}
cout << "[=" << count1 << endl;
cout << "]=" << count2 << endl;
cout << "(=" << count3 << endl;
cout << ")=" << count4 << endl;
cout << "{=" << count5 << endl;
cout << "}=" << count6 << endl;
_getch();
}
return 0;
}
2. Программа, инвертирующая файл (переставляющая символы в обратном
порядке)
Используя позиционирование в файле, можно прочитать файл от конца к началу
посимвольно. Используя тот же подход можно инвертировать файл и построчно, но это
потребует чуть больше программного кода.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
55
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream inf; // Объявляем файл для чтения
ofstream outf; // файл для записи
char ch; // символ, который будет считываться из файла
char name1[81]; // имя файла для чтения
char name2[81]; // имя файла для записи
cout<<"Введите имя файла, который нужно инвертировать: ";
cin >> name1;
inf.open(name1); // открываем файл
if ( !inf ) // если файл не открыт
cout<<"Файл не найден" ;
else
{
cout << "Введите имя фaйла, который должен
получиться в результате: ";
cin >> name2;
outf.open(name2); // открываем файл для записи
inf.seekg(-1L, ios::end);
/* выполняем позиционирование
на последний символ файла. Первый параметр – длинное целое число, поэтому наличие
суффикса L обязательно. Если мы не хотим, чтобы результирующий файл начинался с
перехода на другую строку, можно использовать –3L в качестве первого параметра */
do /* повторяем нижеследующие действия до тех пор, пока не дойдем до
первого символа файла */
{
inf.get(ch); // считываем символ
if (ch == '\n') inf.seekg(-1L, ios:: cur);
/* каждая строка текстового файла заканчивается двумя
символами: “\r\n”, но рассматриваются они как один: ‘\n’, поэтому прочитав ‘\n’,
соседний символ пропускаем */
outf << ch; // записываем его в файл
cout << ch; // выводим символ на экран
inf.seekg(-2L, ios::cur); /* делаем два шага назад (мы
движемся в одном направление, а чтение выполняется в другом, поэтому смещать
позицию нужно на прочитанный символ и на тот, который будет считываться */
} while ( !inf.fail() ); /* когда мы попытаемся установить
позицию за началом файла, функция fail() будет давать 1 */
cout << endl; // заканчиваем вывод на экран
outf << endl; // и в файл
inf.close(); outf.close(); // закрываем оба файла
}
56
_getch();
return 0;
}
3. Программа выводит на экран n-ую строку файла
Программа иллюстрирует чтение данных из файла построчно.
#include<iostream>
#include<locale>
//!!! Отвечает за работу с локализацией ОС
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream inf; // Объявляем файл для чтения
char name[21]; // имя файла
char str[81]; // строка для чтения данных из файла
do // повторение программы до нажатия клавиши <Esc>
{
cout << "Задайте имя файла ";
cin >> name;
inf.open(name);
if (!inf) // Если файл не открыт
{
cout<<"Файл не найден\n";
}
else
{
int k = 0; // счетчик прочитанных строк
while ( !inf.eof() ) // пока файл не закончен
{
inf.getline(str,80);
// считываем одну строку файла
k++; // увеличиваем счетчик строк
cout << str << endl;
if ( (k+1) % 23 == 0 )
// выводим текст на экран по 23 строки
{
cout<< "Нажмите любую клавишу";
57
_getch(); /* при нажатии любой клавиши
выводится очередная часть текста */
}
}
int n; // номер строки, которую нужно вывести на экран
inf.seekg(0L, ios::beg); // возвращаемся в начало файла
inf.clear(); // сбрасываем признак конца файла
do
{
cout<<"Введите номер строки от 1 до "<< k
<< " ";
cin>>n;
}while ( n>k || n<1 );
for (int i=1; i<=n; i++)
inf.getline(str,80);
cout<<str<<endl; /* последнюю считанную строку выводим
на экран */
}
inf.close(); /* если открытие файла повторяется, значит файл
должен закрываться */
} while (_getch() !=27);
return 0;
}
Обратите внимание на то, что чтение файла осуществляется последовательно:
чтобы прочитать n-ую строку файла, необходимо прочитать предыдущие (n-1) строк.
Это вызвано тем, что строки разной длины и мы не можем определить, где начинается
каждая строка. Решением проблемы может быть предварительное чтение файла с
записью в массив позиции каждой строки. Работу с массивами мы будем разбирать в
следующей лабораторной работе.
4. Программа, которая переписывает текст из одного файла в другой, удаляя лишние пробелы между словами и делая ширину текста максимум 70 символов
Программа иллюстрирует чтение данных из файла словами (словом называется
последовательность символов, не содержащая внутри себя пробелов и отделенная от
других слов пробелами или пробельными символами типа табуляции). При таком
чтении файла все управляющие символы рассматриваются как разделители между
словами и деление на строки теряется.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
58
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream inf("test.txt"); // Объявляем файл для чтения
fstream outf("rez.txt",ios::out);
// создаваемый файл (можно использовать как для записи, так и для чтения)
char str[81]; // строка для чтения нового файла
char slovo[71]; // 1 слово, считываемое из файла
char rez[81]; // строка для записи в новый файл
rez[0] = '\0'; // делаем строку пустой
if (!inf) // если файл не открыт
cout<<"Файл не найден \n";
else
{
byte flag = 0; // признак первого слова
cout << "Исходный файл:\n";
while (!inf.eof()) // пока не конец файла
{
inf >> slovo ; // считывем слово из файла
cout<<slovo<< ' '; // выводим его на экран
if (strlen(rez)+strlen(slovo)+1<=70 &&
strlen(slovo))
/* если длина строки после добавления к ней нового слова не
превысит 70 и слово не пустое */
{
if (flag) strcat(rez," ");
// если слово - не первое, добавляем пробел
strcat(rez,slovo); // добавляем слово
flag = 1; // в строке уже есть слово
}
else // если строка уже длинная
{
outf << rez << endl; // записываем ее в файл
*rez = '\0'; // строку делаем опять пустой
strcpy(rez,slovo); // копируем в нее слово
}
} //end while
if (*rez) outf << rez << endl;
// если последняя строка – не пустая, записываем ее в файл
outf.close(); // создаваемые файлы нужно закрывать
cout <<"\n\nНажмите любую клавишу \n";
_getch();
outf.open("rez.txt",ios::in);
// открываем созданный файл для чтения
cout << "\nНовый файл:\n";
while( !outf.eof()) // пока не конец файла
{
outf.getline(str,80); // считываем строку
59
cout << str << endl; // выводим ее на экран
}
}
_getch();
return 0;
}
5. Программа, которая считывает текст файла и создает новый файл, заменив во
всем тексте заданное слово на новое (не изменяя деление на строки и количество
пробелов между словами)
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
#include<fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
// Функция, которая будет выполнять команду “Заменить”
void Replace (char*& str, char* olds,char *news)
/* параметрами функции являются ссылка на указатель, который хранит адрес строки,
слово, которое нужно заменить, и новое слово.
Функция будет изменять указатель (адрес строки) */
{
char* rez = new char[2*strlen(str)];
/* новая строка; длина строки может увеличиться в результате замены, поэтому
выделим память в 2 раза больше, чем длина исходной строки */
unsigned char slovo[31]; // 1 слово из строки
unsigned char *s = reinterpret_cast<unsigned char*>(str),
*r = reinterpret_cast<unsigned char*>(rez), *sl; /* указатели, с
помощью которых мы будем двигаться по строке и обрабатывать символ за символом
*/
while (*s) // пока не достигнут конец строки
{
sl = slovo;
// устанавливаем указатель sl на область памяти для хранения слова
while ( *s > 0 && *s <= ' ') *r++ = *s++;
// Скопировали в результирующую строку пробелы
while ( *s > ' ' && *s < 1<<8 ) *sl++ = *s++;
// Скопировали слово
*sl = '\0'; // записали признак конца слова
if (strcmp(reinterpret_cast<char*>(slovo), olds))
// Если очередное слово не нужно заменять
sl = slovo;
// устанавливаем указатель sl на считанное слово
else
sl = reinterpret_cast<unsigned char*>(news);
// иначе на новое слово
while (*sl) *r++ = *sl++;
// копируем то или иное слово в результирующую строку
60
}
*r = '\0'; // записываем признак конца строки
delete []str; // удаляем из памяти старую строку
str = rez; // теперь указатель str хранит адрес новой строки
}
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream inf("test.txt"); // Объявляем файл для чтения
fstream outf("rez.txt",ios::out);
char* str = new char[81] ; // строка для чтения файла
if (!inf)
cout<<"Файл не найден \n";
else
{
while (!inf.eof()) // пока не конец файла
{
inf.getline(str,80); // считываем строку
cout<<str<<endl; // выводим ее на экран
Replace(str, "$$", "???");
// заменяем одно слово на другое
outf << str << endl; // записываем новую строку в файл
}
outf.close(); // созданный файл закрываем
// выводим полученный файл на экран:
outf.open("rez.txt", ios::in);
cout << "\nНовый файл:\n";
while( !outf.eof())
{
outf.getline(str,81);
cout<<str<<endl;
}
}
delete str;
_getch();
return 0;
}
6. Программа, которая считывает данные для структуры Man из файла.
Cтруктура должна содержать следующие поля:
пол, фамилия, имя, отчество, возраст, рост, вес, цвет глаз, цвет волос.
Набор полей, соответствующий одному человеку, должен быть записан в одну строку.
Файл должен содержать информацию о нескольких людях.
61
Программа должна вывести на экран сведения о всех людях, рост которых > 180 см.
Файл с данными:
м Сидоров Иван Петрович 52 185 90 карий русый
ж Иванова Анна Марковна 45 170 72 голубой блонд
м Петров Сидор Юрьевич 34 182 120 зеленый рыжий
…
Программа:
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
// Описание структуры:
struct Man
{
char sex; // пол
char FIO[80]; // фамилия, имя, отчество
int age; // возраст
int height; // рост
int weight; //вес
char ycolor[20]; // цвет глаз
char hcolor[20]; //цвет волос
};
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
fstream fl;
char fName[20];
cout <<"Введите имя файла ";
cin.getline(fName,20);
fl.open(fName,ios::in);
if (!fl) cout<<"Файл не найден.\n";
if (fl)
{
char str[100];
cout <<"Файл с данными: \n";
62
while (!fl.eof())
{
fl.getline(str,100);
cout << str << endl;
}
// Обработка данных:
fl.seekg(0L, ios::beg); // возвращаемся в начало файла
fl.clear();
Man person; /* объявляем конкретный набор данных, который будет
хранить сведения об одном человеке */
char fam[40], name[40], otch[40];
for(int i=0;i<80;i++)
cout << "=";
cout << endl;
// фамилия, имя отчество как отдельные слова
char flag = 1; // признак того, что нужные данные еще не найдены
while (!fl.eof())
{
fl>>person.sex;
// начинаем считывать данные на очередного человека
if (!fl.eof()) // если файл еще не закончен
{
fl >> fam >> name >> otch;
// считываем фамилию, имя отчество
// и собираем их в одну строку FIO:
strcat(fam," ");
strcat(fam,name);
strcat(fam," ");
strcat(fam,otch);
strcpy(person.FIO,fam);
// считываем остальные данные:
fl>>person.age>>person.height >>
person.weight >> person.ycolor >> person.hcolor;
if (person.height > 180)
// если считанные данные удовлетворяют условию (рост > 180)
{
if (flag) cout<<
"Люди, рост которых > 180 см:\n";
/* если найден первый человек, удовлетворяющий
условию, выводим поясняющий текст */
flag = 0; // признак того, что данные найдены
// выводим найденные данные:
cout <<"пол " << person.sex <<" ФИО: "
<< person.FIO << endl <<"возраст: " << person.age <<" рост: "
<< person.height <<" вес: " << person.weight <<" цвет глаз: "
<<person.ycolor <<" цвет волос: "<< person.hcolor << endl ;
} // end if
} // end if
} // end while
if (flag) cout <<"Нет сведений о людях, рост которых
> 180 см.\n";
} // end if
63
_getch();
return 0;
}
Необходимость использования структуры в данном примере не слишком очевидна вследствие небольшого объема примера, однако в реальных задачах, работающих со
множеством объектов, структуры действительно полезны.
7. Программа создающая новый текстовый файл из двух данных, в котором 1-я
строка –строка из первого файла, 2-я строка – строка из 2-го файла, 3-я
строка – содержит общие символы первых 2-х строк.
Программа иллюстрирует использование типа string для работы со строками.
#include <iostream>
#include <iomanip>
#include <conio.h>
#include <string>
#include <ctype.h>
#include <stdlib.h>
#include <windows.h>
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream fi1,fi2; //файлы для чтения
ofstream fo; //файл для записи
string sName1,sName2,sNameRez; //строки для имён файлов
do //проверка правильности ввода
{
cout <<"Введите имя первого файла ";
getline(cin,sName1);
basic_string<char>::size_type index;
//переменная для хранения индекса элемента строки
// следующий цикл удаляет пробелы из имени файла:
while((index=sName1.find(" "))!= string::npos)
sName1=sName1.replace(index,1,
basic_string<char>(""));
} while(sName1.length()==0);
// Повторяем цикл, если длина имени файла стала равна нулю
do
{
cout <<"Введите имя второго файла ";
getline(cin,sName2);
64
basic_string<char>::size_type index;
//переменная для хранения индекса элемента строки.
while((index=sName2.find(" "))!= string::npos)
sName2=sName2.replace(index,1,
basic_string<char>(""));
}while(sName2.length()==0 || sName2.compare(sName1)==0);
/* Повторяем цикл, если длина имени равна нулю или имя второго файла
совпадает с именем первого */
do
{
cout <<"Введите имя результирующего файла ";
getline(cin,sNameRez);
basic_string<char>::size_type index;
//переменная для хранения индекса элемента строки.
while((index=sNameRez.find(" "))!= string::npos)
sName2=sNameRez.replace(index,1,
basic_string<char>(""));
} while(sNameRez.length()==0 ||(sNameRez.compare(sName1)
==0 || sNameRez.compare(sName2)==0));
fi1.open(sName1.c_str()); //открытие файла
if(!fi1)
{
cerr<<"Не могу открыть первый файл.\n";
return 1; //закрытие файла
}
fi2.open(sName2.c_str()); //открытие файла
if(!fi2)
{
cerr<<"Не могу открыть второй файл.\n";
fi1.close(); //закрытие файла
return 2;
}
fo.open(sNameRez.c_str()); //открытие файла
if(!fo)
{
cerr<<"Не могу открыть результирующий файл.\n";
fi1.close();//закрытие файла
fi2.close();//закрытие файла
return 3;
}
string str1,str2,str3="";
do
{
getline(fi1,str1);
getline(fi2,str2);
str3.clear();
int *map1=new int [256],*map2=new int [256];
//создание карт символов в строке
for(int i=0;i<255;++i) //обнуляем карты
map1[i]=map2[i]=0;
65
/* Следующие три цикла записывают в массивы количество повторений каждого
символа соответствующей строки */
for(int i=0;i<str1.length();++i)
map1[static_cast<unsigned char>(str1[i])]++;
//приведение к беззнаковому типу
for(int i=0;i<str2.length();++i)
map2[static_cast<unsigned char>(str2[i])]++;
for(int i=0;i<255;++i)
if(map1[i]&&map2[i])
// Если символ присутствует и в первой и во второй строке:
str3.push_back((char)(i));
// записываем его в конец результирующей строки
// записываем результат в файл:
fo<<str1<<endl;
fo<<str2<<endl;
fo<<str3<<endl;
cout<<str1<<endl;
cout<<str2<<endl;
cout<<str3<<endl;
delete map1; //удаление карт символов для строки
delete map2;
}while(!fi1.eof()&& !fi2.eof()); //выполняем пока одновременно
не конец файлов
fi1.close(); //закрытие файла
fi2.close();
fo.close();
_getch();
return 0;
}
8. Программа создаёт из двух файлов третий, в котором содержатся
максимальные по длине слова из соответствующих строк исходных файлов,
причём все слова длиннее 5-ти символов заключаются в квадратные скобки.
#include<iostream>
#include<iomanip>
#include<conio.h>
#include<string>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
#include<fstream>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
ifstream fi1,fi2;
66
ofstream fo;
string sName1,sName2,sNameRez; //строки, для имён файлов
do //проверка правильности ввода
{
cout <<"Введите имя первого файла ";
getline(cin,sName1);
basic_string<char>::size_type index;
//переменная для хранения индекса элемента строки.
while((index=sName1.find(" "))!=string::npos)
sName1=sName1.replace(index,1,
basic_string<char>(""));
}while(sName1.length()==0);
do
{
cout <<"Введите имя второго файла ";
getline(cin,sName2);
basic_string<char>::size_type index;
//переменная для хранения индекса элемента строки.
while((index=sName2.find(" "))!=string::npos)
sName2=sName2.replace(index,1,
basic_string<char>(""));
}while(sName2.length()==0 || sName2.compare(sName1)==0);
do
{
cout <<"Введите имя результирующего файла ";
getline(cin,sNameRez);
basic_string<char>::size_type index;
//переменная для хранения индекса элемента строки.
while((index=sNameRez.find(" "))!=string::npos)
sName2=sNameRez.replace(index,1,
basic_string<char>(""));
}while(sNameRez.length()== 0 ||
(sNameRez.compare(sName1)==0 || sNameRez.compare(sName2)==0));
fi1.open(sName1.c_str()); // открытие первого файла
if(!fi1)
{
cerr<<"Не могу открыть первый файл.\n";
return 1;
}
fi2.open(sName2.c_str()); //открытие второго файла
if(!fi2)
{
cerr<<"Не могу открыть второй файл.\n";
fi1.close(); //закрытие файла
return 2;
}
fo.open(sNameRez.c_str());
//открытие результирующего файла
if(!fo)
{
67
cerr<<"Не могу открыть результирующий файл.\n";
fi1.close(); //закрытие файла
fi2.close();
return 3;
}
string str1,str2,str3="",sub1,sub2;
// следующий цикл выполняется, пока не закончится хотя бы один из файлов
do
{
getline(fi1,str1);
getline(fi2,str2);
str3.clear();
fo<<str1<<endl;
fo<<str2<<endl;
cout<<str1<<endl;
cout<<str2<<endl;
basic_string<char>::size_type ind1;
//переменная для хранения индекса элемента строки
basic_string<char>::size_type ind2;
// следующий цикл обрабатывает две соответствующие строки, считанные из файлов
do
{
ind1=str1.find(" ");
//находим первый пробел в первой строке
// следующий цикл удаляет пробелы в начале строки
while(ind1==0 && ind1 != string::npos)
// пока пробел – первый и он вообще есть в строке
{
str1=str1.replace(0,1,"");
//удаляем пробелов слева
ind1=str1.find(" ");
// и находим следующий пробел
}
// выделяем слово из строки:
if(ind1!=string::npos)
//если не конец строки
{
sub1=str1.substr(0,ind1);
//копируем подстроку
str1=str1.replace(0,ind1,"");
//удаляем только что скопированное слово из строки
}
else //конец строки
{
sub1=str1.substr(0,str1.length());
// берем подстроку
str1=str1.replace(0,str1.length(),"");
//удаляем её
}
// аналогично только со второй строкой
ind2=str2.find(" ");
while(ind2==0&&ind2!=string::npos)
68
{
str2=str2.replace(0,1,"");
ind2=str2.find(" ");
}
if(ind2!=string::npos)
{
sub2=str2.substr(0,ind2);
str2=str2.replace(0,ind2,"");
}
else
{
sub2=str2.substr(0,str2.length());
str2=str2.replace(0,str2.length(),"");
}
if(max(sub1.length(),sub2.length())>5)
//если подстрока больше пяти символов тогда
{
str3.append((sub1.length()<sub2.length())?("["+sub2+"]
"):("["+sub1+"] ")); /* к третьей строке присоединяем большую из двух
подстрок заключенную в квадратные скобки */
}
else //в противном случае
{
str3.append((sub1.length() < sub2.length())?
sub2+" " : sub1+" "); // мы просто копируем и добавляем пробел
}
}while(str1.length()||str2.length());
fo<<str3<<endl;
cout<<str3<<endl;
}while(!fi1.eof()&&!fi2.eof());
fi1.close(); //закрытие файла
fi2.close();
fo.close();
_getch();
return 0;
}
Задания для самостоятельного выполнения
1. Открыть файл, имя которого задается с клавиатуры. Посчитать и вывести на экран количество байт в этом файле. Первую половину прочитанного файла записать
в другой файл. Вывести полученный файл на экран.
2. Открыть файл, имя которого задается с клавиатуры. Записать в другой файл
первые n байт этого файла, где n задается с клавиатуры (проверьте, что n находится
в допустимых пределах). Вывести полученный файл на экран.
3. Открыть файл, имя которого задается с клавиатуры. Посчитать и вывести на экран количество слов в этом файле. Первую половину слов записать в другой файл.
Вывести полученный файл на экран.
4. Открыть файл, имя которого задается с клавиатуры. Записать в другой файл
первые n слов этого файла, где n задается с клавиатуры (проверьте, что n находится
в допустимых пределах). Вывести полученный файл на экран.
69
5. Открыть файл, имя которого задается с клавиатуры. Посчитать и вывести на экран количество строк в этом файле. Первую половину строк записать в другой файл.
Вывести полученный файл на экран.
6. Открыть файл, имя которого задается с клавиатуры. Записать в другой файл
первые n строк этого файла, где n задается с клавиатуры (проверьте, что n
находится в допустимых пределах). Вывести полученный файл на экран.
7. Открыть файл, имя которого задается с клавиатуры. Создать новый файл, в
который записать в обратном порядке строки исходного файла (инвертировать
файл построчно).
8. Открыть файл, имя которого задается с клавиатуры. Создать строку, которая
будет содержать набор символов содержащихся в файле (каждый символ должен
входить в строку по одному разу). Записать полученную строку в другой файл.
9. Открыть файл, имя которого задается с клавиатуры. Переписать в другой файл
только те строки, которые содержат заданную последовательность символов.
10. Открыть файл, имя которого задается с клавиатуры. Переписать в другой файл
только те строки, которые содержат заданное слово.
11. Открыть файл, имя которого задается с клавиатуры. Переписать в новый файл
только те слова, которые состоят из цифр.
12. Открыть файл, имя которого задается с клавиатуры. Найти сумму чисел,
содержащихся в файле.
13. Открыть файл, имя которого задается с клавиатуры. Найти в этом файле
максимальную по длине строку и переписать строки в новый файл, выровняв длину
каждой строки по максимальной (добавив в конец каждой строки пробелы).
14. Открыть файл, имя которого задается с клавиатуры. Переписать в новый файл
только те строки, которые являются комментариями типа //…
15. Открыть файл, имя которого задается с клавиатуры. Переписать в новый файл
только комментарии типа /*…*/
16. Открыть файл, имя которого задается с клавиатуры. Создать новый файл, удалив
заданную последовательность символов из файла.
17. Открыть файл, имя которого задается с клавиатуры. Создать новый файл,
заменив одну заданную последовательность символов на другую.
18. Открыть файл, имя которого задается с клавиатуры. Создать новый файл,
который содержит набор слов, содержащихся в исходном файле (каждое слово
должно входить в результирующий файл только 1 раз).
19. Открыть файл, имя которого задается с клавиатуры. Переписать в новый файл
только те слова, которые записаны латинскими буквами.
20. Открыть файл, имя которого задается с клавиатуры. Создать новый файл, удалив
лишние пробелы между словами, но не изменяя деление на строки.
21. Открыть файл, имя которого задается с клавиатуры (файл должен содержать
текст, включающий точки). Создать новый файл, удалив пробелы перед точками
(если они есть).
22. Открыть файл, имя которого задается с клавиатуры. Создать новый файл, в
который переписать только те слова, которые записаны большими буквами
(русскими и латинскими).
70
23. Открыть файл, имя которого задается с клавиатуры (файл должен содержать
текст, включающий точки). Создать новый файл, отредактировав текст исходного
файла: если первое слово, идущее за точкой начинается с маленькой буквы,
заменить эту букву на большую.
24. Написать программу, которая считывает из файла данные о продаваемых компьютерах, описываемые следующей структурой:
название, тип процессора, тактовая частота, объем памяти, объем жесткого
диска, производитель, цена.
Вывести на экран сведения о компьютерах с самой высокой тактовой частотой.
25. Написать программу, которая считывает из файла данные о жителях города,
описываемые структурой: Фамилия имя отчество, дата рождения, улица, дом,
квартира.
Вывести на экран сведения о жителях дома, номер которого вводится с клавиатуры (улицы могут быть разными).
26. Написать программу, которая считывает данные об автомобилях, описываемых
следующей структурой: марка, год выпуска, страна-производитель, цена,
фамилия имя отчество владельца.
Вывести на экран сведения об автомобилях иностранного производства.
27. Написать программу, которая считывает из файла данные о студентах,
описываемые следующей структурой: Фамилия имя отчество, номер группы,
количество экзаменов в текущем семестре, количество несданных экзаменов.
Вывести на экран список задолжников.
28. Написать программу, которая считывает данные о продаваемых товарах,
описываемые следующей структурой: Название, цена, страна производитель,
количество поступившего товара, количество проданного товара.
Вывести на экран сведения о товарах, которых осталось меньше половины от
количества поступления.
29. Написать программу, которая считывает данные из файла, содержащего данные
о квартирах, описываемые следующей структурой: улица, дом, номер квартиры,
общая площадь, количество жильцов.
Вывести на экран сведения о квартире, в которой на каждого жильца приходится
наименьшее количество площади.
30. Написать программу, которая считывает данные из файла о фильмах, имеющихся в прокате, описываемые структурой: Название, жанр, страна-производитель,
год выпуска, Фамилия и имя актера, снявшегося в главной роли.
Вывести сведения о фильмах, в которых играет актер, фамилия и имя которого
вводится с клавиатуры.
71
Лабораторная работа № 6
Тема: “Программы, использующие массивы ”.
1. Программа заполняет массив A(50) случайными целыми числами из диапазона
[-20, 30] и упорядочивает его по возрастанию. Исходный и упорядоченный массивы
выводятся на экран дисплея.
Программа иллюстрирует работу
заполненным случайными числами.
с
массивом
фиксированного
размера,
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
using namespace std; // Используем стандартное пространство имён
/* Функция, выполняющая перестановку значений двух переменных (обратите
внимание на то, что аргументы должны быть объявлены как ссылки): */
void swap(int& a, int& b)
{
int c;
c=a; a=b; b=c;
}
// Подпрограмма сортировки методом «пузырька»
void sort(int* a, int n)
{
for ( int i = 1; i < n; i++ ) // отсчитываем проходы по массиву
for ( int j = 0; j < n-i; j++ ) // проходим по массиву
{
if ( a[j] > a[j+1] ) // сравниваем два соседних элемента
swap(a[j], a[j+1]); // переставляем их
}
}
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
int n=50;
int *a=new int[n]; // объявляем массив из 50 элементов
72
cout<<"Исходный массив:\n";
// заполняем массив случайными числами и выводим на экран
int RANGE_MIN = -20; // Минимальный элемент
int RANGE_MAX = 51; // Максимальный элемент
//Пример взят из справки ms-help:
//MS.VSCC.v80/MS.MSDN.v80/MS.VisualStudio.v80.en/dv_vccrt/html
/75d9df25-7aaf-4a88-b940-2775559634e8.htm
for ( int i = 0; i < n; i++ )
{
a[i] = (int)(((double) rand() / (double) RAND_MAX) *
RANGE_MAX + RANGE_MIN); // случайные числа из диапазона [-20, 30]
cout << setw(4) << a[i]; /* выводим на экран элемент массива
(ширина поля вывода – 4 */
}
cout <<endl;
// Вызываем функцию сортировки и передаем ей указатель на массив и размер массива:
sort( a, n);
printf("\nМассив, отсортированный по возрастанию:\r\n");
// для вывода массива на экран требуется цикл:
for (int i = 0; i < n; i++)
{
printf("%4d", a[i]); // выводим элемент массива на экран
}
printf("\r\n"); // перевод курсора в начало следующей строки
_getch();
return 0;
}
2. Программа, которая по заданным корням многочлена степени n восстанавливает все коэффициенты многочлена.
Программа иллюстрирует работу с массивами изменяющегося размера.
Для вычисления коэффициентов можно воспользоваться соотношением:
X n  a n 1 X n 1    a1 X  a0  ( X  x1 )( X  x 2 )  ( X  x n )
В результате при вводе первого корня мы должны получить коэффициенты 1 и
– x, например: при x1 = 2 мы получаем многочлен 1  X  2 (два коэффициента).
При вводе второго и последующих корней коэффициенты вычисляются следующим образом:
a0
a1
a2 … an-1
-a0xn -a1xn … -an-2xn – an-1xn
+
Например: при вводе двух корней 2 и –3 получаем:
(x-2)(x+3) = x2-2x+3x-6 =1x2 + 1x –6
1 -2
+
-1(-3) –(-2)(-3)
--------------------------1
1
-6
73
Проходить по массиву коэффициентов нужно обязательно с конца, поскольку
коэффициенты изменяются в процессе вычислений, а при вычислении нового значения
коэффициента используется коэффициент, стоящий слева от него.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
do
{
int n;
// количество корней
do
{
cout << "Задайте количество корней > 0 --> ";
cin >> n;
} while (n < 1);
double* x = new double [n]; //корни
double* a = new double [n+1]; //коэффициенты многочлена
a[0] = 1; // первый коэффициент равен единице
cout << "Задайте корни:\n";
for (int i = 0; i < n; i++)
{
cout<< i+1 <<"-й корень --> ";
cin >> x[i];
a[i+1] = -a[i] * x[i];
//Добавили последний коэффициент в массив
// вычисляем остальные коэффициенты:
for (int j = i; j >= 1; j--)
a[j] += -a[j-1] * x[i];
}
// вывод:
cout << "Заданы корни: ";
for (int i = 0; i < n; i++)
cout << x[i]<<" ";
cout << endl;
cout << "Коэффициенты многочлена: ";
for (int i=0; i<=n; i++)
74
cout << a[i]<<" ";
cout << endl;
delete []x;
delete []a;
cout<<"Для выхода нажмите Esc\n";
}while(_getch()!=27);
return 0;
}
3. Программа считывает линейный массив из файла, выводит его на экран, и
подсчитывает количество элементов массива, находит min и max элементы
и их индексы.
При работе с линейным массивом, записанным в файл, необязательно
переписывать его в оперативную память (однако следует помнить, что обращение
процессора к оперативной памяти происходит быстрее)
#include<iostream>
#include<locale>
//!!! Отвечает за работу с локализацией ОС
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
#include<fstream> // Этот файл обеспечивает работу с файлами
using namespace std;
/* если с файлом работают как главная программа, так и функции, лучше объявить его
как глобальную переменную */
ifstream file("test.txt");
// Объявляем функцию, которая будет выдавать индексы:
void ShowIndex( int , float );
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
if(!file)
{
cerr<<"Файл test.txt не существует\n";
return 0;
}
float n, min, max; // число, считываемое из файла, минимум и максимум
int k=0; // количество чисел в файле
75
while (1) // как бы бесконечный цикл
{
file>>n;
if (file.eof()) break;
// если достигнут конец файла, выходим из цикла
if (!k) // если считано первое число (k=0)
{
min = n;
max = n;
}
else // если число – не первое
{
if (n<min) min=n;
// если встретилось число меньше, заменяем значение min
if (n>max) max=n;
// если встретилось число больше, заменяем значение max
}
cout<<n<<' '; k++;
/* выводим считанное число на экран и увеличиваем счетчик
прочитанных чисел */
}
cout << endl; // завершаем вывод переводом курсора
cout<<"Количество чисел в файле: " << k << endl;
cout<<"Минимальный элемент: " << min<<endl;
cout<<"Номер(а) минимального элемента: ";
ShowIndex(k, min);
// вызываем функцию и передаем ей количество элементов и значение min
cout<<"Максимальный элемент: " << max <<endl;
cout<<"Номер(а) максимального элемента: " ;
ShowIndex(k, max);
// вызываем функцию и передаем ей количество элементов и значение max
_getch();
return 0;
}
/* Функция, которая считывает k чисел из файла, находит номера элементов, значение
которых совпадает с m, и выводит на экран найденные индексы */
void ShowIndex( int k,float m)
{
file.clear();
file.seekg(0L,ios::beg); // переходим в начало файла
float n; // число, считываемое из файла
for (int i=0; i<k; i++) // отсчитываем k чисел
{
file>>n;
if (n == m) cout << i << ' ';
// если число равно m, выводим номер этого числа на экран
}
cout<<endl;
}
76
4. Программа заполняет массив A[5][5] случайными целыми числами из
диапазона [-3, 3] и находит произведение элементов, стоящих на побочной
диагонали.
Номера элементов, стоящих на главной диагонали, совпадают; номера элементов,
стоящих на побочной диагонали удовлетворяют условию: i + j = n+1, где n –
размер матрицы.
#include<iostream>
#include<locale>
//!!! Отвечает за работу с локализацией ОС
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
using namespace std;
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
//Динамически создаём 2- мерный массив
int n=5, **a= new int*[n];
cout<<"Исходный массив:\n";
int RANGE_MIN = -3; // Минимальный элемент
int RANGE_MAX = 7; // Максимальный элемент
// для прохода по всем ячейкам матрицы обычно используют двойной цикл
for (int i = 0; i < 5; i++) // проходим по строкам матрицы
{
a[i]=new int [n];
// в каждой строке проходим по столбцам:
for (int j = 0; j < 5; j++) // счетчики должны быть разными!
{
a[i][j]=(int)(((double) rand() / (double)
RAND_MAX) * RANGE_MAX + RANGE_MIN);
cout<< setw(5)<<a[i][j];
}
cout<<endl;
/* после вывода строки матрицы переводим курсор в начало следующей строки
на экране */
}
cout <<endl;
// вычисляем произведение:
long p = 1;
for (int i = 0; i < 5; i++)
p *= a[i][5-i-1]; // номер столбца вычисляем через номер строки
77
// обратите внимание на то, что для прохода по диагонали требуется один цикл
cout << "\nПроизведение элементов, стоящих на побочной
диагонали = " << p << endl;
_getch();
return 0;
}
5. Программа считывает матрицу из файла, выводит ee на экран, сортирует
элементы в каждом столбце и отсортированную матрицу записывает в
файл.
Этот пример иллюстрирует использование матрицы, размеры которой определяются в процессе выполнения программы. Размеры матрицы считываются из файла,
хотя это необязательно. Размеры матрицы можно определить, подсчитав количество
чисел в первой строке и количество строк (если каждая строка матрицы записана как
одна строка файла).
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
#include <fstream> // Этот файл обеспечивает работу с файлами
using namespace std; // !!! Используем стандартное пространство имён
// функция перестановки значений двух величин
void swap(float& a, float& b)
{
float tmp;
tmp=a; a=b; b=tmp;
}
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
// Объявляем файлы:
ifstream inf("test.txt");
ofstream outf("sort.txt");
int m,n; // Количество строк и столбцов
register int i,j;
// счетчики (пример использования регистровых переменных)
inf >> m >> n;
/* считываем из файла размеры матрицы, которые должны быть записаны в
начале файла */
78
float *vek, **mat;
/* Указатель на матрицу как на линейный массив и указатель на массив указателей для обращения к элементам массива как к элементам матрицы. Элементы массива объявлены как числа, которые могут иметь дробную часть */
vek=new float[m*n]; // выделяем место под элементы матрицы
mat=new float*[m];
// выделяем место под массив указателей на строки матрицы
for (i=0; i<m; i++) // заполняем массив указателями
mat[i]= &vek[i*n]; // деление на строки матрицы
printf("Исходная матрица:\r\n");
// чтение элементов из файла
for (i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
inf>>mat[i][j];
// считываем элемент как слово и записываем в матрицу
if (inf.eof())
// если достигнут конец файла, а матрица еще не заполнена
{
printf("Не хватает данных\r\n");
_getch();
exit(0);
}
printf("%10.2f",mat[i][j]); // вывод элемента на экран
}
printf("\r\n"); // перевод курсора в начало следующей строки
}
// Сортировка по столбцам методом пузырька:
for (j=0; j<n; j++) // проходим по столбцам
for (int p=1; p<m; p++) // отсчитываем проходы по столбцу
for (i=0; i<m-p; i++)
// сравниваем соседние элементы в столбце
if (mat[i][j]>mat[i+1][j])
swap (mat[i][j],mat[i+1][j]);
// и, если нужно, переставляем их
// Запись в файл и вывод на экран полученной матрицы:
cout << "Отсортированная по столбцам: \n";
for (i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
// запись элемента в файл:
outf <<setiosflags(ios::showpoint)<<
setprecision(2)<<setw(10)<<mat[i][j];
// вывод на экран:
cout <<setiosflags(ios::showpoint) <<
setprecision(2)<< setw(10)<<mat[i][j];
// каждый элемент записывается с двумя цифрами после точки в поле из 8 позиций
}
outf<<endl;
// в конце строки матрицы выводим признак конца строки
79
cout << endl;
}
outf.close();
delete []mat;
delete []vek;
_getch();
return 0;
}
6. Программа, сортирующая файл по длине строки методом быстрой сортировки.
Программа запоминает в массиве длины строк, считанных из файла, и их позиции
в файле ( использование такого массива позволит не переписывать весь файл в оперативную память), затем массив сортируется по возрастанию длины строк. В результате
мы получим начальные позиции строк в такой последовательности, какая нам нужна.
Используя позиционирование, прочитаем строки в нужном порядке и запишем их в
результирующий файл.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<fstream>
#include<windows.h>
using namespace std;
// структура, соответствующая одной строке файла:
struct stroka
{
long pos; // позиция, с которой начинается строка в файле
int len; // длина строки
};
// пример оформления шаблонной функции:
template <class Type> void swapq(Type &a, Type &b)
/* в данной программе эта функция будет переставлять структуры (записи о каждой
строке файла)*/
{
Type tmp;
tmp=a; a=b; b=tmp;
}
// функция быстрой сортировки:
void qusort( stroka *mas, int left, int right )
{
/*параметры: указатель на массив и индексы, определяющие ту часть массива, в
которой в данный момент выполняется сортировка */
register int i,j; // индексы элементов
int x;
i=left; j=right;
x=mas[(left+right) / 2].len; // Берем средний элемент в массиве
80
do // этот цикл будет сравнивать длины строк
{
while( mas[i].len < x && i < right ) i++;
// Находим элемент, который должен стоять правее X
while( mas[j].len > x && j > left ) j--;
// Находим элемент, который должен стоять левее X
if (i <= j )
{
// и меняем их местами:
swapq<stroka>( mas[i], mas [j] );
i++; j--;
}
} while ( i <= j );
/*В результате получили 2 части массива: в одной все элементы меньше X, в
другой – больше */
/* Рекурсивный вызов функции сортировки для двух полученных частей
массива: */
if ( left < j ) qusort( mas, left, j);
if ( i < right ) qusort( mas, i, right);
}
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
// Объявляем файлы:
ifstream inf;
char *name=new char[81]; // имя файла
do // повторение ввода имени файла
{
cout<<"Введите имя файла или нажмите <Esc>";
cout<<" для прекращения работы программы ";
name[0]=_getche(); // считываем первый символ
if (name[0]==27) exit(0);
// Если нажата клавиша <Esc>, прерываем выполнение программы
cin.getline(&name[1],80);
// считываем остальные символы имени
inf.open(name); // открываем файл
if (!inf)
cout<<"Файл не найден ! \n";
} while(!inf); /* повторяем ввод, пока имя файла не будет введено
правильно */
/* этот цикл стоит рассматривать не как руководство к действию, а скорее как
пример возможных вариантов манипуляций со строками */
81
fstream outf("rez.txt",ios::out);
// файл для записи отсортированного текста
char *str=new char[102]; // строка для чтения файла
char *beg=str; // указатель на начало строки
// Определяем количество строк в файле:
int kol=0;
while ( !inf.eof() )
{
inf.getline(str,102);
kol++;
}
// Создаем массив записей о строках:
stroka *mas = new stroka[kol];
inf.clear();
inf.seekg(0l,ios::beg);
mas[0].pos=0; // позиция первой строки
int l; // длина очередной считываемой строки
// считываем текст построчно:
for (int i = 0; i < kol; i++)
{
str = beg;
/* мы будем изменять значение str, но для каждой новой строки указатель
str опять будет хранить адрес начала области памяти, выделенной для строки */
inf.getline(str,102); // считываем строку
l=strlen(str);
if (i < kol-1) // если мы считываем не последнюю строку
{
mas[i+1].pos=inf.tellg();
// запоминаем текущую позицию как начало следующей строки
while ( *str == ' ' || *str == 9 )
{
str++;
mas[i].pos++;
} // обрезали пробелы и знаки табуляции в начале строки
}
mas[i].len = strlen(str) ;
// запомнили длину получившейся строки
}
// Сортируем массив по длине строк:
qusort(mas,0,kol-1);
// считываем текст, используя позиции, хранящиеся в массиве:
inf.clear();
for (int i = 0; i < kol; i++)
{
if (inf.eof()) inf.clear();
// если считана последняя строка в файле
inf.seekg( mas[i].pos, ios::beg );
inf.getline(str,102); // считываем нужную строку
if (*str) outf<<str<<endl;
// и записываем ее в результирующий файл
}
outf.close();
82
cout<<"Смотрите результат работы программы в файле
\"rez.txt\"";
_getch();
return 0;
}
Задания для самостоятельного выполнения
1. Написать программу, которая считывает линейный массив натуральных чисел из
файла, имя которого вводится с клавиатуры, и выводит на экран те элементы,
которые являются простыми числами.
2. Написать программу, которая заполняет линейный массив, размер которого
задается с клавиатуры, случайными натуральными числами в заданном диапазоне,
выводит полученный массив на экран и записывает в файл те элементы, которые
являются простыми числами.
3. Написать программу, которая считывает линейный массив натуральных чисел из
файла, имя которого вводится с клавиатуры, и выводит на экран те элементы,
которые являются степенями двойки.
4. Написать программу, которая заполняет линейный массив, размер которого
задается с клавиатуры, случайными натуральными числами в заданном диапазоне,
выводит полученный массив на экран и записывает в файл те элементы, которые
являются степенями двойки.
5. Написать программу, которая считывает линейный массив натуральных чисел из
файла, имя которого вводится с клавиатуры, и выводит на экран те элементы,
которые являются числами Фибоначчи.
6. Написать программу, которая заполняет линейный массив, размер которого
задается с клавиатуры, случайными натуральными числами в заданном диапазоне,
выводит полученный массив на экран и записывает в файл те элементы, которые
являются числами Фибоначчи.
7. Написать программу, которая считывает линейный массив натуральных чисел из
файла, имя которого вводится с клавиатуры, и выводит на экран те элементы,
которые являются квадратами целых чисел.
8. Написать программу, которая заполняет линейный массив, размер которого
задается с клавиатуры, случайными натуральными числами в заданном диапазоне,
выводит полученный массив на экран и записывает в файл те элементы, которые
являются квадратами целых чисел.
9. Написать программу, которая считывает линейный массив из файла, имя которого вводится с клавиатуры, сортирует его методом быстрой сортировки по возрастанию и выводит на экран
10. Написать программу, которая заполняет линейный массив, размер которого
задается с клавиатуры, случайными натуральными числами в заданном диапазоне,
сортирует его методом быстрой сортировки по убыванию и записывает в файл.
11. Написать программу, которая считывает линейный массив из файла, выводит
его на экран и находит среднее арифметическое элементов массива.
12. Написать программу, которая заполняет массив, размер которого вводится с
клавиатуры, случайными целыми числами в заданном диапазоне, находит среднее
арифметическое этих чисел и записывает в другой файл отклонение каждого
элемента массива от среднего.
83
13. Написать программу, которая считывает линейный массив целых чисел из файла
и определяет, какое число в этом массиве встречается наиболее часто.
14. Написать программу, которая заполняет массив, размер которого вводится с
клавиатуры, случайными целыми числами в заданном диапазоне выводит его на
экран и определяет, какое число в этом массиве встречается наиболее часто.
15. Написать программу, которая считывает линейный массив из файла, выводит
его на экран и определяет, упорядочен ли он по возрастанию.
16. Написать программу, которая заполняет матрицу A размерами m*n, где m и n
задаются с клавиатуры, случайными целыми числами из заданного диапазона,
записывает ее в файл и в конце каждой строки выводит максимальный по модулю
элемент каждой строки матрицы. Полученный файл вывести на экран
17. Написать программу, которая считывает матрицу A размерами m*n из файла,
выводит ее на экран и под каждым столбцом выводит значение модуля
минимального элемента этого столбца.
18. Написать программу, которая заполняет матрицу A размерами m*n, где m и n
задаются с клавиатуры, случайными целыми числами из заданного диапазона,
записывает ее в файл и в конце каждой строки выводит сумму модулей элементов
этой строки. Полученный файл вывести на экран.
19. Написать программу, которая считывает из файла матрицу A размерами m*n,
выводит ее на экран и под каждым столбцом выводит сумму модулей элементов
этого столбца.
20. Написать программу, которая заполняет матрицу A размерами m*n, где m и n
задаются с клавиатуры, случайными целыми числами из заданного диапазона,
записывает ее в файл и в конце каждой строки выводит количество элементов этой
строки кратных 3. Полученный файл вывести на экран.
21. Написать программу, которая считывает из файла матрицу A размерами m*n,
выводит ее на экран и под каждым столбцом выводит количество элементов этого
столбца, кратных 10.
22. Написать программу, которая заполняет матрицу A размерами m*n, где m и n
задаются с клавиатуры, случайными целыми числами из заданного диапазона,
сортирует каждую строку по возрастанию и полученную матрицу записывает в файл.
Полученный файл вывести на экран.
23. Написать программу, которая считывает из файла матрицу A размерами m*n,
сортирует каждый столбец по убыванию и полученную матрицу выводит на экран.
24. Написать программу, которая заполняет матрицу A размерами m*n, где m и n
задаются с клавиатуры, случайными целыми числами из заданного диапазона,
записывает ее в файл и в конце каждой строки выводит индекс максимального
элемента в этой строке. Полученный файл вывести на экран.
25. Написать программу, которая считывает из файла матрицу A размерами m*n,
выводит ее на экран и под каждым столбцом выводит индекс минимального
элемента в этом столбце.
26. Написать программу, которая заполняет матрицу A размерами n*n, где n
задается с клавиатуры, случайными целыми числами из заданного диапазона,
записывает ее в файл и находит произведение элементов, стоящих на главной
диагонали. Полученный файл вывести на экран.
84
27. Написать программу, которая считывает из файла матрицу A размерами n*n, ],
выводит ее на экран и находит максимальный среди элементов, стоящих на главной
диагонали.
28. Написать программу, которая заполняет матрицу A размерами n*n, где n
задается с клавиатуры, случайными целыми числами из заданного диапазона,
записывает ее в файл и находит количество нулевых элементов, стоящих на главной
диагонали. Полученный файл вывести на экран.
29. Написать программу, которая считывает из файла матрицу A размерами n*n,
выводит ее на экран и находит индекс первого элемента, равного нулю, на главной
диагонали.
30. Написать программу, которая считывает из файла данные о продаваемых компьютерах, описываемые следующей структурой:
название, тип процессора, тактовая частота, объем памяти, объем жесткого диска,
производитель, цена.
Вывести на экран сведения обо всех компьютерах, отсортировав их по возрастанию
цены.
31. Написать программу, которая считывает из файла данные о жителях города,
описываемые структурой: Фамилия имя отчество, дата рождения, улица, дом,
квартира.
Вывести на экран сведения обо всех жителях, отсортировав их в алфавитном
порядке по строке “фамилия имя отчество”.
32. Написать программу, которая считывает из файла данные о жителях города,
описываемые структурой: Фамилия имя отчество, дата рождения, улица, дом,
квартира.
Вывести на экран сведения обо всех жителях, отсортировав их в алфавитном
порядке по строке “фамилия имя отчество”.
33. Написать программу, которая считывает данные об автомобилях, описываемых
следующей структурой: марка, год выпуска, страна-производитель, цена, фамилия
имя отчество владельца.
Вывести на экран сведения обо всех автомобилях, отсортировав их в алфавитном
порядке по строке “фамилия имя отчество владельца”.
34. Написать программу, которая считывает из файла данные о студентах,
описываемые следующей структурой: Фамилия имя отчество, номер группы,
количество экзаменов в текущем семестре, количество несданных экзаменов.
Вывести список на экран, отсортировав его в алфавитном порядке по строке
“фамилия имя отчество”.
35. Написать программу, которая считывает данные о продаваемых товарах,
описываемые следующей структурой: Название, цена, страна производитель,
количество
поступившего
товара,
количество
проданного
товара.
Вывести на экран список товаров, отсортировав его по названиям товаров.
36. Написать программу, которая считывает данные из файла, содержащего данные
о продаваемых квартирах, описываемые следующей структурой: улица, дом, номер
квартиры, общая площадь, рыночная стоимость.
Вывести на экран сведения о квартирах, отсортировав их в порядке возрастания
цены.
85
37. Написать программу, которая считывает данные из файла о фильмах,
имеющихся в прокате, описываемые структурой: название, жанр, странапроизводитель, год выпуска, фамилия и имя актера, снявшегося в главной роли.
Вывести на экран сведения о фильмах, отсортировав их в алфавитном порядке по
названиям.
Лабораторная работа № 7
Тема: “Программы, использующие динамические структуры”.
1. Программа, которая создает очередь символов.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include <stdlib.h>
#include<windows.h>
using namespace std;
// структура, которая описывает один узел:
struct Node
{
char data; // элемент данных
Node* next; // указатель на следующий узел
};
int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
// Указатели на первый, текущий и предыдущий узел:
Node *firstPt=NULL, *token=NULL, *prev=NULL;
cout<<"Введите строку символов \n";
char ch, flag=1;
// создаем очередь:
do
{
ch = _getche(); // считываем символ с клавиатуры
token = new Node; // выделяем место под текущий узел
token->data = ch; // записываем элемент данных
token->next = NULL; // указатель на следующий элемент равен 0
if (flag) // если создан первый узел
{
86
firstPt = token; flag = 0; // запоминаем его адрес
}
else prev -> next = token;
// в противном случае запоминаем в ранее созданном узле адрес нового узла
prev = token; // текущий узел становится предидущим
} while (ch != '\r'); // пока не будет нажата клавиша <Enter>
cout<<endl;
//Вывод:
cout <<"Очередь:\n";
token = firstPt; // адрес первого узла
while (token) // пока указатель на текущий узел не равен 0
{
cout<<token -> data; // выводим элемент данных
token = token->next; // переходим к следующему узлу
}
cout <<endl;
_getch();
return 0;
}
2. Программа, которая создает закольцованный список и затем последовательно
удаляет из списка каждый m-й элемент до тех пор, пока не будут удалены все.
#include<iostream>
#include<iomanip>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
using namespace std;
// структура, которая описывает один узел:
struct Node
{
int num;
Node* ptr;
};
// функция, которая добавляет 1 элемент в список:
void Add(Node*& pLast, int i)
/* первый параметр – ссылка на указатель, который будет хранить адрес последнего
добавленного элемента, второй параметр – значение элемента данных, которое будет
записано в этот узел */
{
Node* pNext = new Node; // выделяем место под новый узел
if (pLast) pLast -> ptr = pNext;
// если предыдущий узел существует, подсоединяем новый узел к предыдущему
pNext -> num = i; // записываем элемент данных
pNext -> ptr = NULL;
// указатель, записанный в последнем узле пока никуда не указывает
pLast = pNext; // новый узел становится последним
}
87
// ----------------------------------------------------------// функция, которая удаляет узел с номером m:
int Del(Node*& pToken, int m)
// первый параметр – адрес текущего узла
{
int n; // элемент данных из удаляемого узла
if (pToken->ptr != pToken) // если узел - не единственный
{
// Отсчет:
for (int i = 1; i < m; i++)
pToken = pToken->ptr; // переходим к следующему узлу
//Адрес удаляемого элемента:
Node* tmp = pToken->ptr;
n = tmp->num; // запоминаем значение элемента данных
pToken->ptr = tmp->ptr;
// запоминаем в узле перед удаляемым адрес узла, который расположен за
удаляемым
delete tmp; // удаляем узел
}
else // если узел – единственный, просто удаляем его
{
n = pToken -> num;
delete pToken;
pToken = NULL;
}
return n;
}
//-----------------------------------------------------------int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
do
{
int n, m;
do
{
cout << "Задайте начальное количество элементов
>=1 --> ";
cin >> n;
} while (n < 1);
do
{
cout << "Задайте номер удаляемого элемента от 1
до "<< n << " --> ";
88
cin >> m;
} while ( m < 1 || m > n);
// Указатели на начало и конец списка:
Node *pBegin = NULL, pLast = NULL;
//Формирование списка:
for (int i = 1; i <= n; i++)
{
Add(pLast, i);
if (i == 1) pBegin = pLast;
}
// Закольцуем список:
pLast->ptr = pBegin;
//Занимаем начальную позицию:
Node* pToken = pLast;
// Удаление:
do
{
cout<<"" << Del(pToken, m) << ' ';
} while (pToken);
cout << endl;
cout << "\nНажмите любую клавишу\n";
} while (_getch()!=27);
return 0;
}
3. Программа, которая работает со стеком.
#include<iostream>
#include<iomanip>
#include<math.h>
#include<conio.h>
#include<String.h>
#include<ctype.h>
#include<stdlib.h>
#include<windows.h>
using namespace std;
// структура, которая описывает один узел
struct Node
{
int data;
Node* next;
};
// Функция, которая добавляет элемент в стек
void Push(Node*& first, int num)
// первый параметр – адрес узла на вершине стека
{
Node* token;
if (first==NULL) // если стек пуст
{
first = new Node;
first->next = NULL;
89
}
else // если стек – не пуст
{
token = new Node;
token->next = first; // привязываем узел к предыдущему
first = token;
}
first->data = num; // записываем элемент данных
}
// ----------------------------------------------------------// функция, которая считывает значение из текущего узла и перемещается по стеку вниз
int Pop(Node*& token)
{
int num = token->data;
token = token->next;
return num;
}
//-----------------------------------------------------------int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
int data[] = {2, -3, 7, 12, 4};
Node *first=NULL, *token = NULL;
// создаем стек из элементов массива
for (int i=0; i<5; i++)
Push(first, data[i]);
//Вывод:
token=first;
while (token)
cout << Pop(token)<<" ";
cout <<endl;
_getch();
return 0;
}
4. Программа, которая работает с деревом.
#include<iostream>
#include<conio.h>
#include<windows.h>
using namespace std;
// структура, которая описывает один узел дерева
struct Node
{
double number; // элемент данных
Node* Left; // указатель на левую ветвь
Node* Right; // указатель на правую ветвь
};
90
void Write(double, Node*&); // записывает узел
void Read(Node*); // считывает элемент данных
//------------------------------------------------------------------------int main()
{
if(SetConsoleCP(1251)==0)
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
Node* root=NULL;
double x[] = {5, 2, 8, 7, 2, 9};
cout << "Исходная последовательность:\n";
for (int i=0; i<6; i++)
cout << x[i] <<" ";
cout << endl;
// создаем дерево
for (int i=0; i<6; i++)
Write(x[i], root);
cout <<"Отсортированная последовательность:\n";
// выводим дерево на экран:
Read(root);
cout<<endl;
_getch();
return 0;
}
// -----------------------------------------------------------------------// рекурсивная функция, которая создает новый узел дерева
void Write(double x, Node*& pNode)
// параметры: элемент данных и адрес исходного узла
{
if (!pNode) // если дерева еще нет
{
pNode = new Node;
pNode->number = x;
pNode->Left = pNode->Right = NULL;
}
else /* в противном случае привязываем узел к дереву так,
чтобы все элементы слева были меньше всех элементов справа*/
{
if (x >= pNode->number)
Write(x, pNode->Right); //Спускаемся вправо
else
Write(x, pNode->Left); //спускаемся влево
}
}
/* рекурсивная функция, которая считывает элементы данных
(данные будут выведены на экран в порядке возрастания: */
void Read(Node* token)
{
if (token->Left)
Read(token->Left);
cout << token->number<<" ";
if (token->Right)
Read(token->Right);
}
91
Задания для самостоятельного выполнения
1. Написать программу, которая формирует очередь целых чисел, вводимых с клавиатуры, и выводит элементы очереди на экран. Найти в этой очереди максимальный
элемент и перенести его в начало очереди. Вывести полученную очередь на экран.
2. Написать программу, которая формирует стек из целых чисел, вводимых с клавиатуры, и выводит элементы этого стека на экран. Найти среднее арифметическое
элементов стека и удалить из стека те элементы, значения которых меньше среднего.
3. Написать программу, которая создает закольцованный список из натуральных
чисел, вводимых с клавиатуры. Удалить из этого списка те элементы, которые имеют
четное значение. Вывести элементы списка на экран.
4. Написать программу, которая создает очередь целых чисел из элементов массива,
заданного в программе и позволяет вставить в конец очереди новые элементы,
вводимые с клавиатуры.
5. Написать программу, которая создает очередь целых чисел, вводимых с
клавиатуры. Упорядочить эту очередь по возрастанию и вывести ее на экран.
6. Написать программу, которая создает бинарное дерево целых чисел, вводимых с
клавиатуры. Распечатать содержимое дерево в порядке убывания элементов и
подсчитать количество узлов на этом дереве.
7. Написать программу, которая создает бинарное дерево символов, вводимых с
клавиатуры (каждый символ должен содержаться на дереве только в одном
экземпляре). Вывести символы на экран в порядке возрастания и определить сколько
цифр среди этих символов.
8. Написать программу, которая создает бинарное дерево слов, считываемых из
файла. Распечатать содержимое дерева в алфавитном порядке.
9. Написать программу, которая создает очередь целых чисел, считываемых из файла
и позволяет добавить в эту очередь элемент, вводимый с клавиатуры, под заданным
номером.
10. Написать программу, которая создает стек целых чисел, считываемых из файла, и
удаляет из него повторяющиеся числа. Вывести элементы полученного стека на экран.
11. Написать программу, которая создает двойной связный список целых чисел,
вводимых с клавиатуры. Распечатать этот список в прямом и обратном порядке.
12. Написать программу, которая создает очередь из слов, считываемых из файла
(слова должны содержаться в очереди только в одном экземпляре). Вывести на экран
эту очередь и подсчитать количество слов в ней.
13. Написать программу, которая считывает строку символов, выбирает числа из этой
строки и записывает их в стек. Вывести содержимое стека на экран.
14. Написать программу, которая создает двойной связанный список символов,
вводимых с клавиатуры. Проверить, содержит ли этот список симметричную
последовательность символов (т.е. читается ли он одинаково в обоих направлениях).
15. Написать программу, которая создает очередь символов, считываемых с
клавиатуры, такую, что каждый символ содержится в очереди в одном экземпляре и
каждый узел содержит количество таких символов, введенных с клавиатуры.
16. Написать программу, которая создает очередь слов, считываемых из файла.
Каждое слово должно содержаться в очереди только в одном экземпляре и каждый
узел должен содержать количество таких слов в файле.
92
17. Написать программу, которая создает очередь символов из текста считываемого из
файла. Каждый символ должен содержаться в очереди в одном экземпляре и каждый
узел очереди должен содержать количество таких символов в тексте. Отсортировать
очередь в порядке возрастания количества повторений символов и вывести на экран.
18. Написать программу, которая создает двоичное дерево строк, считываемых из
файла. Вывести на экран содержимое дерева в порядке возрастания длин строк.
19. Написать программу, которая создает очередь целых чисел, считываемых из файла
и заменяет в этой очереди значения элементов, которые равны вводимому с
клавиатуры, на новое, также задаваемое с клавиатуры. Вывести полученную очередь на
экран.
20. Написать программу, которая считывает строку символов, содержащую целые
числа и знаки операций и формирует два стека: чисел и знаков операций. Вывести на
экран элементы полученных стеков.
21. Написать программу, которая создает закольцованный список символов, вводимых
с клавиатуры и выводит список на экран столько раз, сколько символов в списке, при
этом начало вывода должно сдвигаться влево на один символ.
22. Написать программу, которая создает дерево целых чисел, считываемых из файла.
Удалить с дерева все элементы, равные нулю. Вывести элементы дерева в порядке
убывания.
23. Написать программу, которая стек вещественных чисел, считываемых из файла.
Переставить элементы стека так, чтобы последними считывались нулевые элементы, а
взаимное расположение ненулевых элементов не изменилось.
24. Написать программу, которая создает очередь целых чисел из вещественных,
считываемых из файла, округляя их до ближайшего целого. Вывести полученную
очередь на экран.
25. Написать программу, которая считывает целые числа с клавиатуры и создает стек,
содержащий двоичные эквиваленты этих чисел. Вывести полученный стек на экран.
26. Написать программу, которая формирует стек целых чисел, вводимых с
клавиатуры. Поменять местами первый и последний элементы стека. Вывести
полученный стек на экран.
27. Написать программу, которая создает очередь целых чисел, считываемых из
файла. Переставить элементы очереди так, чтобы вначале шли положительные числа
(не меняя их взаимного расположения), а затем все остальные (не меняя их взаимного
расположения).
28. Написать программу, которая считывает текст из файла и формирует очередь
символов из этого текста, не являющихся буквами. Вывести полученную очередь на
экран.
29. Написать программу, которая считывает текст из файла и создает стек чисел,
содержащихся в тексте. Вывести полученный стек на экран.
30. Написать программу, которая создает дерево символов, содержащихся в тексте,
вводимом с клавиатуры, такое что каждый символ включается в дерево только один
раз. Удалить с этого дерева символ, вводимый с клавиатуры. Вывести элементы дерева
в порядке возрастания их беззнаковых кодов.