Потопахин Виталий Валерьевич РЕШЕНИЕ ЗАДАЧ ПО ПРОГРАММИРОВАНИЮ НА ЯЗЫКЕ C++ Пояснительная записка
Главная цель курса: изучение методов решения логически сложных задач по программированию.
В процессе изучения слушатели освоят методы решения задач, основанные на применении сведений из теории графов (деревья, цепи, циклы), рекурсивных функций и некоторых других понятий дискретной математики. Рассмотрят большое количество примеров, попробуют самостоятельно решить различные по содержанию и уровню сложности задачи.
Основные знания.
Древовидные структуры данных.
Понятие рекурсии.
Понятие эвристики, понятие модели.
Тематическое планирование
№
|
Тема
|
лекции
|
лабораторные
|
1
|
Построение и обход деревьев
|
4
|
2
|
2
|
Эвристические методы в задачах перебора
|
2
|
2
|
3
| Рекурсивные задачи |
2
|
2
|
4
|
Моделирование физических процессов
|
2
|
4
| ИТОГО |
10
|
10
|
Текст пособия
Главной структурной единицей программы на языке С++, является программный модуль, именуемый в С++ функцией. Как и в любом другом языке, эта основная конструкция устроена так:
Для неё указывается список переменных, значения которых определяются при вызове функции - так называемый список формальных переменных.
Функция имеет тело, состоящее из команд языка, выполнение которых производится так, как если бы данная функция была отдельной независимой программой.
Переменные, определяемые в теле функции, это локальные переменные - то есть такие, значения которых, доступны только внутри данной функции.
Функция имеет доступ к глобальным переменным.
Функция может возвращать значения в точку программы, в которой был осуществлён вызов функции.
То, что было перечислено выше, имеет место в любом языке программирования, только имеет разные названия (функция, процедура, подпрограмма). В С++ есть ряд особенностей которые делают функцию - функцией именно С++. Перечислим эти особенности.
Место расположение функции не имеет значения. Этим самым С++ сильно отличается, от например языка Паскаль в котором устанавливается жёсткая иерархия процедур/функций. Благодаря этому свойству программист получает большую свободу действий и при написании программы и при разработке алгоритма.
Возврат значений из функции и соответственно прерывание её работы может произойти в любой точке её тела. Более того, таких точек выхода из функции может быть много, столько, сколько нужно программисту.
Существует одна функция - которая считается главной в том смысле, что выполнение программы начинается именно с неё. Её имя фиксировано – main()
Пример программы С++. Расчёт факториала
#include
#include
void main()
{ int n,a;
cin >> n; // ввод
a=1;
for (int i=1;i<=n;i++) a=a*i; // цикл
cout<
}
Записанная выше программа состоит из одной главной функции, в которой используются операции ввода-вывода, оператор присваивания и конструкция цикла. Перед программой с помощью команды #include указываются файлы содержащие описания используемых функций и операций.
Любая языковая конструкция, за исключением заголовка функции завершается точкой с запятой. Сложный оператор организуется с помощью скобок {} сама функция также является сложным оператором.
ОПРЕДЕЛЕНИЕ ТИПОВ ПЕРЕМЕННЫХ
Определить переменную в С++ возможно в любом месте программы и это определение будет действовать от места определения до первой соответствующей закрывающей скобки.
Пример
Void main()
{ int I;
for (I=1;I<=6;I++)
{ int u=I;
}
}
В этом примере переменную I можно использовать в любом месте функции main() от точки её объявления. Переменная u может быть использована только внутри сложного оператора выполняемого в циклической конструкции. В языке С++ маленькие буквы и большие различаются как разные символы.
Некоторые наиболее часто используемые типы данных
Int - целое
Float - действительное
Char - символьное
Определение массивов в С++
Пример. Int a[10], d[5] здесь определены два массива. Один имеет имя «a» тип целый, состоит из 10 элементов пронумерованных от 0 до 9. Второй массив: имя «d» тип символьный, состоит из 5 элементов пронумерованных от 0 до 4.
Многомерный массив определяется так: int a[10][12][2]; здесь определён массив размерности 3.
Структуры в С++
Структурой называется сложное данное, состоящее из нескольких компонентов разного типа. Для обращения к компоненту необходимо указать имя структуры и через точку имя компонента. Со структурой можно обращаться как с единым целым. Ниже пример программы демонстрирующий обращение к компоненту структуры.
void main()
{ struct example {int t; float a[10];} y;
example r;
y.a[1]=8.7;
r.t=6;
}
В данном примере example – это описание структуры. Переменную данного типа можно описать двумя способами. Первым способом описана переменная y. Вторым способом описана переменная r.
Собственные типы в С++
Собственным типом в С++ называется тип данных созданный программистом из базовых типов и конструкций. Ниже показан пример программы, в котором создается тип - массив из 100 элементов.
void main()
{ typedef int a[100];
a s;
s[1]=7;
}
Преобразование типов в С++
Язык С++ слабо типизируемый. Это означает, что компилятор очень слабо заботится о соответствии типов переменных. Это означает, что нет необходимости специально заботится о преобразовании типов различных переменных. В С++ следующая запись не создаст никаких проблем:
int y; char t=”h”; y=t;
ОПЕРАТОР ПРИСВАИВАНИЯ
Оператор присваивания в С++ имеет несколько форм. Самая общая форма:
Имя переменной = арифметическое выражение.
В этой форме оператора справа от знака равенства может находится любое правильно записанное арифметическое выражение. Это универсальный оператор. С++ однако полагает, что у программиста может возникнуть потребность как можно быстрее выполнить операцию, и при этом нет необходимости записывать любое выражение. Для этого существуют более специальные формы оператора присваивания. Ниже эти формы показаны на примере оператора прибавляющего к переменной единицу:
Общая форма a=a+1
Более специальная форма a+=1
Узкоспециальная форма a++
Третья форма используется только для увеличения значения величины переменной на единицу. Во второй форме знак плюс можно заменить на знак любой другой арифметической операции. В третьей форме знак плюс можно заменить на минус.
Примеры: a*=2*r; a—
Примечание. Возможно следующее применение оператора присваивания: c=u=y=5 в этом примере 5 будет права налево присвоено всем указанным в операторе переменным.
ОПЕРАТОР ЦИКЛА
Общая форма оператора цикла с параметром
For ([выражение1];[выражение2];[выражение3]) оператор
Выражение 1 вычисляется перед первым шагом цикла и может быть использовано для инициализации параметра цикла.
Выражение 3 вычисляется на каждом шагу цикла и может быть использовано для увеличения значения параметра цикла
Оператор выполняется до тех пока истинно Выражение2.
Все три описателя цикла могут быть пропущены. То есть язык С++ допускает такую запись цикла for (;;) эта запись не имеет смысла однако ошибки в этом не будет.
Ещё один пример. Сумма множества чисел
#include
#include
void main()
{ int n;
cin >> n;
int s=0;
for (int i=1;i<=n;i++)
{ int a;
cin >> a;
s+=a;
}
cout << s;
}
Существует также форма оператора цикла по условию. В С++ предусмотрено два цикла по условию. Цикл с предусловием (сначала проверяется условие затем выполняются операции тела цикла) и цикл с постусловием. Запишем пример приведённый выше с применением этих двух форм цикла.
-
Цикл с предусловием
|
Цикл с постусловием
|
#include
void main()
{ int i,n,s;
s=0;
cin >> n;
i=1;
while (i<=n)
{ int a;
cin >> a;
s+=a;
i++;
}
cout <
}
|
#include
void main()
{ int i,n,s;
s=0;
cin >> n;
i=1;
do
{ int a;
cin >> a;
s+=a;
i++;
}
while (i<=n);
cout <
}
|
УСЛОВНЫЙ ОПЕРАТОР
В С++ имеются два оператора работающие на выбор из возможных альтернатив. Это условный оператор if и оператор – переключения switch. Оператор if имеет следующую форму записи:
If (условие) оператор1; else оператор2;
Если условие истинно, то выполняется оператор1 иначе выполняется оператор2 или если ключевое слово else отсутствует, то оператор следующий за оператором if.
Условие в операторе формируется с помощью логических операций:
== равно
!= не равно
> больше
< меньше
И логических связок:
&& логическое И
логическое ИЛИ
! логическое НЕ
Пример.
int a=7;
if (! (a==5)) cout << “hello”
Условие в операторе имеет значение истина, поэтому результатом работы программы будет печать слова hello.
Более сложный пример. Дан массив чисел. Найти в нём наибольшее.
#include
#include
#include
void main()
{ int n,a[10];
cin >> n;
for (int i=1;i<=n;i++) cin >> a[i];
int max=a[1];
for (i=2;i<=n;i++)
if (a[i]>max) max=a[i];
cout << max;
}
Оператор переключения switch
Этот оператор полезен, если есть необходимость организовать выбор из нескольких альтернатив. Рассмотрим следующий пример:
#include
#include
void main()
{ int x;
cin >> x;
switch (x)
{ case 1: cout << "button1";break;
case 2: cout << "button2";break;
case 3: cout << "button3";break;
default: cout << “cccccc”;
}
}
В этой программе относительно переменной х предполагается, что она может принимать несколько значений. Если эта переменная примет значение 1, 2 ил 3 то будет выведено соответствующее сообщение. Если же значение переменной х будет какое-то иное, то будет выведено сообщение «сссссс».
Оператор break необходим для прерывания последовательности выполнения операторов в операторе switch. Без него управление передаётся на соответствующий case и затем выполняются все операторы следующие ниже. То есть при х=2 будут выведены следующие сообщения: button2, button3, cccccc.
ВВОД – ВЫВОД
В С++ существует две возможности ввода/вывода данных – форматный и неформатный ввод/вывод. Неформатный ввод/вывод осуществляется посредством следующих команд
>> ввод
<< вывод
Но чтобы ими пользоваться необходимо ввести ещё одно понятие – понятие потока данных. С++ полагает, что любая программа всегда имеет дело с двумя потоками байтов данных: входным потоком и выходным. Из входного потока программа получает данные и результаты своей обработки направляет в выходной поток.
Внутри этих потоков нет целых, действительных или массивов или строк. Потоки не имеют структуры. При вводе данные побайтно выбираются из потока и передаются в структуры определённые в программе и уже в них обретают смысл как элементы массива, символы и т.д.
Потоки данных имеют следующие имена:
cin - входной поток
cout - выходной поток
Пример 1. Ввести массив символов
#include
#include
void main()
{ int i; char [10];
for (i=0;i<=10;i++) cin >> a[i];
for (i=0;i<=10;i++) cout << a[i];
}
Пример 2. Ввести список номеров имеющих следующий формат (символ, целое число)
#include
#include
void main()
{ int i; char a[10];int d[10];
for (i=0;i<=3;i++)
cin >> a[i] >> d[i];
for (i=0;i<=3;i++)
cout << a[i] << “ ” << d[i] << “\n”
}
“\n” – управляющий символ перевода на новую строку.
Форматный ввод/вывод в С++
Для форматного ввода/вывода в С++ предусмотрены две библиотечные функции:
scanf – функция для ввода данных
printf – функция для вывода данных
Они имеют следующий общий вид:
scanf или printf(“Описание формата”, список переменных)
Описание формата может содержать описатели формата и строки символов. Описатель формата устроен следующим образом:
% символ идентифицирующий формат. Для примера запишем программу последнего примера с помощью функций prinf и scanf.
#include
#include
void main()
{ int i; char a[10];int d[10];
for (i=0;i<=3;i++)
scanf("%c%d",&a[i], &d[i]);
for (i=0;i<=3;i++)
printf("simbol %c chislo %d \n",a[i],d[i]);
}
Здесь применяются следующие описатели формата:
с – символ
d – целое
Для дальнейшей работы нам к этому списку пока достаточно добавить ещё описатель f – указывающий на ввод величины типа float.
Две полезных функции
Gotoxy(int, int) – установка курсора на экране монитора
Clrscr() – очистка экрана в символьном режиме.
Ввод/вывод из файлов
Работа с файлами требует выполнения следующих шагов:
Создать файловую переменную.
Открыть файл.
Выполнить требуемые операции чтения, записи.
Закрыть файл.
Файловая переменная
Для создания переменной файлового типа имеется специальный тип FILE. Объявление файловой переменной выполняется так
FILE * имя переменной.
Открытие файла
Для открытия файла используется процедура fopen. Она для своей работы требует указания имени файла и способа доступа. Способ доступа – это указание на то, что можно делать с этим файлом. Нам для дальнейшей работы необходимо два способа доступа r – доступ на чтение; w – доступ на запись.
Способы доступа можно указывать одновременно, ниже пример того, как это можно делать.
Работа с файлом
Для операций чтения/записи в С++ используются функции fprintf и fscanf. В отличии от функций scanf и printf для них требуется указать файловую переменную.
Закрытие файла
Для закрытия используется функция fclose (файловая переменная)
#include
void main()
{ FILE *h; так объявляется файловая переменная
h=fopen("file.dat", "w"); файл открывается на запись
for (int i=1;i<=100;i++) fprintf(h,"%d\n",i); записываются сто целых
fclose(h); файл закрывается
h=fopen("file.dat", "r"); файл открывается на чтение
int a;
for (i=1;i<=100;i++)
{fscanf(h,"%d\n",&a); читается сто целых
printf("%d\n",a); прочитанные числа выводятся на экран.
}
}
Программа записанная ниже решает ту же задачу, что и программа записанная выше, той разницей, что она использует функцию установки файловой переменой в определенную позицию. Её формат следующий:
FSEEK(файловая переменная, позиция, точка отсчёта)
Позиция – число байт которые необходимо отсчитать от точки отсчёта.
Точка отсчёта – точка от которой отсчитывается указанная позиция. Есть несколько способов указать такую точку.
SEEK_SET отсчёт от начала файла.
SEEK_CUR отсчёт от текущей позиции
SEEK_END отсчёт от конца файла
#include
void main()
{ FILE *h;
h=fopen("file.dat", "wr");
for (int i=1;i<=100;i++) fprintf(h,"%d\n",i);
fseek(h,0,SEEK_SET);
int a;
for (i=1;i<=100;i++)
{fscanf(h,"%d\n",&a);
printf("%d\n",a);
}
}
ОПРЕДЕЛЕНИЕ ФУНКЦИЙ
Как уже говорилось программа на С++ может состоять из нескольких функций.
Рассмотрим пример такой программы. Дано число N найти сумму делителей (за исключением единицы и самого числа) всех составных чисел от 1 до N включительно.
#include
#include
int sum(int);
int delitel(int,int);
void main()
{ int n,s=0;
cin >> n;
for (int i=1;i<=n;i++)
s+=sum(i);
cout << s;
}
int sum(int x)
{int s=0;
for (int i=2;i
if (delitel(x,i)) s+=i;
return s;
}
int delitel(int n,int i)
{ int t=0;
do
{ t+=i;
}
while (t
if (t==n) return 1; else return 0;
}
Жирным шрифтом выделены так называемые прототипы функций. Это короткие описания содержащие имена функций, типы получаемых данных и тип возвращаемого данного. Описывать прототип необходимо только в том случае если функция используется раньше чем описывается как это имеет место в приведённом примере.
УКАЗАТЕЛИ
Указателем в С++ называется специальный тип переменных содержащих не значение, а адрес области памяти в котором хранится значение. Ниже пример программы, в которой объявляется два указателя. Для одного из них выполняется операция инициализации new по которой ему выделяется область памяти. Затем с его помощью создается фактически массив переменных.
#include
void main()
{ int *t,*u;
t=new int;
u=t;
for (int i=1;i<=10;i++) {*t=i;t++;}
for (i=1;i<=10;i++) {cout << *u << " "; u++;}
}
Примечание. Применение операции ++ к указателю увеличивает адрес в нём содержащийся.
СТРОКИ В С++
В С++ нет специального строкового типа обозначаемого специальным идентификатором. Для этих целей используется указатель на тип char. Ниже приведён пример программы в котором определяется строковая переменная, вводится её значение, затем вычисляется длина и выводится в стандартный поток. Файл прототипов string.h
#include
#include
void main()
{ char *h;
h=new char;
cin >> h;
cout << strlen(h);
}
ГРАФИКА С++
Ниже приведён пример программы в которой рисуется пирамидка из окружностей:
#include
#include
void main()
{ int dr=DETECT,md;
initgraph(&dr,&md,"");
for (int i=1;i<=9;i++)
{ setcolor(i);
circle(300,400-i*30,60-i*5);
setfillstyle(1,i);
floodfill(300,400-i*30,i);
}
}
|
