Решение задач по программированию на языке C++
Изучение методов решения логически сложных задач по программированию. Эвристические методы в задачах перебора. Моделирование физических процессов. Структурная единица программы на языке С++. Расчёт факториала. Наиболее часто используемые типы данных.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | методичка |
Язык | русский |
Дата добавления | 23.05.2012 |
Размер файла | 24,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
6
Решение задач по программированию на языке C++
Потопахин Виталий Валерьевич
Пояснительная записка
Главная цель курса: изучение методов решения логически сложных задач по программированию.
В процессе изучения слушатели освоят методы решения задач, основанные на применении сведений из теории графов (деревья, цепи, циклы), рекурсивных функций и некоторых других понятий дискретной математики. Рассмотрят большое количество примеров, попробуют самостоятельно решить различные по содержанию и уровню сложности задачи.
Основные знания.
Древовидные структуры данных.
Понятие рекурсии.
Понятие эвристики, понятие модели.
Тематическое планирование
№ |
Тема |
лекции |
лабораторные |
|
1 |
Построение и обход деревьев |
4 |
2 |
|
2 |
Эвристические методы в задачах перебора |
2 |
2 |
|
3 |
Рекурсивные задачи |
2 |
2 |
|
4 |
Моделирование физических процессов |
2 |
4 |
|
ИТОГО |
10 |
10 |
Текст пособия
Главной структурной единицей программы на языке С++, является программный модуль, именуемый в С++ функцией. Как и в любом другом языке, эта основная конструкция устроена так:
Для неё указывается список переменных, значения которых определяются при вызове функции - так называемый список формальных переменных.
Функция имеет тело, состоящее из команд языка, выполнение которых производится так, как если бы данная функция была отдельной независимой программой.
Переменные, определяемые в теле функции, это локальные переменные - то есть такие, значения которых, доступны только внутри данной функции.
Функция имеет доступ к глобальным переменным.
Функция может возвращать значения в точку программы, в которой был осуществлён вызов функции.
То, что было перечислено выше, имеет место в любом языке программирования, только имеет разные названия (функция, процедура, подпрограмма). В С++ есть ряд особенностей которые делают функцию - функцией именно С++. Перечислим эти особенности.
Место расположение функции не имеет значения. Этим самым С++ сильно отличается, от например языка Паскаль в котором устанавливается жёсткая иерархия процедур/функций. Благодаря этому свойству программист получает большую свободу действий и при написании программы и при разработке алгоритма.
Возврат значений из функции и соответственно прерывание её работы может произойти в любой точке её тела. Более того, таких точек выхода из функции может быть много, столько, сколько нужно программисту.
Существует одна функция - которая считается главной в том смысле, что выполнение программы начинается именно с неё. Её имя фиксировано - main()
Пример программы С++. Расчёт факториала
#include <stdio.h>
#include <iostream.h>
void main()
{ int n,a;
cin >> n; // ввод
a=1;
for (int i=1;i<=n;i++) a=a*i; // цикл
cout<<a; //вывод
}
Записанная выше программа состоит из одной главной функции, в которой используются операции ввода-вывода, оператор присваивания и конструкция цикла. Перед программой с помощью команды #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;
ОПЕРАТОР ПРИСВАИВАНИЯ
Оператор присваивания в С++ имеет несколько форм. Самая общая форма:
Имя переменной = арифметическое выражение.
В этой форме оператора справа от знака равенства может находится любое правильно записанное арифметическое выражение. Это универсальный оператор. С++ однако полагает, что у программиста может возникнуть потребность как можно быстрее выполнить операцию, и при этом нет необходимости записывать любое выражение. Для этого существуют более специальные формы оператора присваивания. Ниже эти формы показаны на примере оператора прибавляющего к переменной единицу:
1. Общая форма a=a+1
2. Более специальная форма a+=1
3. Узкоспециальная форма a++
Третья форма используется только для увеличения значения величины переменной на единицу. Во второй форме знак плюс можно заменить на знак любой другой арифметической операции. В третьей форме знак плюс можно заменить на минус.
Примеры: a*=2*r; a--
Примечание. Возможно следующее применение оператора присваивания: c=u=y=5 в этом примере 5 будет права налево присвоено всем указанным в операторе переменным.
ОПЕРАТОР ЦИКЛА
Общая форма оператора цикла с параметром
For ([выражение1];[выражение2];[выражение3]) оператор
Выражение 1 вычисляется перед первым шагом цикла и может быть использовано для инициализации параметра цикла.
Выражение 3 вычисляется на каждом шагу цикла и может быть использовано для увеличения значения параметра цикла
Оператор выполняется до тех пока истинно Выражение2.
Все три описателя цикла могут быть пропущены. То есть язык С++ допускает такую запись цикла for (;;) эта запись не имеет смысла однако ошибки в этом не будет.
Ещё один пример. Сумма множества чисел
#include <stdio.h>
#include <iostream.h>
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 <iostream.h> void main() { int i,n,s; s=0; cin >> n; i=1; while (i<=n) { int a; cin >> a; s+=a; i++; } cout <<s; } |
#include <iostream.h> void main() { int i,n,s; s=0; cin >> n; i=1; do { int a; cin >> a; s+=a; i++; } while (i<=n); cout <<s; } |
УСЛОВНЫЙ ОПЕРАТОР
В С++ имеются два оператора работающие на выбор из возможных альтернатив. Это условный оператор if и оператор - переключения switch. Оператор if имеет следующую форму записи:
If (условие) оператор1; else оператор2;
Если условие истинно, то выполняется оператор1 иначе выполняется оператор2 или если ключевое слово else отсутствует, то оператор следующий за оператором if.
Условие в операторе формируется с помощью логических операций:
§ == равно
§ != не равно
§ > больше
§ < меньше
И логических связок:
§ && логическое И
§ логическое ИЛИ
§ ! логическое НЕ
Пример.
int a=7;
if (! (a==5)) cout << “hello”
Условие в операторе имеет значение истина, поэтому результатом работы программы будет печать слова hello.
Более сложный пример. Дан массив чисел. Найти в нём наибольшее.
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
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 <stdio.h>
#include <iostream.h>
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 <stdio.h>
#include <iostream.h>
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 <stdio.h>
#include <iostream.h>
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 <stdio.h>
#include <iostream.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
#include <iostream.h>
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<x;i++)
if (delitel(x,i)) s+=i;
return s;
}
int delitel(int n,int i)
{ int t=0;
do
{ t+=i;
}
while (t<n);
if (t==n) return 1; else return 0;
}
Жирным шрифтом выделены так называемые прототипы функций. Это короткие описания содержащие имена функций, типы получаемых данных и тип возвращаемого данного. Описывать прототип необходимо только в том случае если функция используется раньше чем описывается как это имеет место в приведённом примере.
УКАЗАТЕЛИ
Указателем в С++ называется специальный тип переменных содержащих не значение, а адрес области памяти в котором хранится значение. Ниже пример программы, в которой объявляется два указателя. Для одного из них выполняется операция инициализации new по которой ему выделяется область памяти. Затем с его помощью создается фактически массив переменных.
#include <iostream.h>
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 <iostream.h>
#include <string.h>
void main()
{ char *h;
h=new char;
cin >> h;
cout << strlen(h);
}
ГРАФИКА С++
Ниже приведён пример программы в которой рисуется пирамидка из окружностей:
#include <iostream.h>
#include <graphics.h>
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);
}
}
Графические процедуры С++
Initgraph(& int, & int, “”) - Инициализация графического режима
Setcolor(int) - Определение цвета объектов
circle(int, int, int) - Рисование окружности
setfillstyle(int, int) - Определение способа закраски внутренней области контура.
floodfill(int, int, int) - Закраска внутренней области контура.
line(int, int, int, int) - Рисование линии.
cleardevice() - Очистка графического экрана
rectangle(int, int, int, int) - Рисование прямоугольника.
Размещено на Allbest.ru
Подобные документы
Написание программы вычисления сопротивления электрической цепи, состоящей из двух параллельно и двух последовательно соединенных сопротивлений. Схема машинного алгоритма по условию задачи. Применение операций при написании программ на языке C/C++.
контрольная работа [17,3 K], добавлен 09.11.2010Описание программного продукта, решающего задачу по автоматизации сбора данных, связанных с деятельностью кружка по программированию. Изучение и совершенствование навыков программирования на различных языках среди студентов и школьников старших классов.
дипломная работа [418,3 K], добавлен 10.07.2017Ханойские башни: постановка задачи, условия перемещения дисков со стержня на стержень. Стратегия решения, используемые предикаты. Текст программы на языке Пролог. Построение модели решения задачи о ферзях. Примеры использования списков в языке Пролог.
презентация [72,0 K], добавлен 29.07.2012Проектирование программы в среде Delphi для тестирования знаний студентов по программированию, с выводом оценки по окончанию тестирования. Разработка экранных форм и алгоритма программы. Описание программных модулей. Алгоритм процедуры BitBtn1Click.
курсовая работа [365,0 K], добавлен 18.05.2013"Moodle" - модульная объектно-ориентированная динамическая среда обучения, ее использование для разработки систем дистанционного обучения. Общее представление о дистанционном практикуме по программированию. Разработка структуры данных и алгоритмов.
дипломная работа [1,2 M], добавлен 09.11.2016Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Изучение основных конструкций и способов написания программ на языке Паскаль. Обзор принципов работы и интерфейса написанной программы. Обработка и модификация двумерных массивов. Файловые структуры данных. Текстовые файлы. Элементы машинной графики.
курсовая работа [761,7 K], добавлен 11.03.2015Разработка программы на языке Си++ и осуществление постановки и выбора алгоритмов решения задач обработки экономической информации, создание и редактирование базы данных, сортировка записей по определенному запросу, анализ эффективности обработки данных.
контрольная работа [316,8 K], добавлен 28.08.2012Программирование на языке Паскаль: алфавит, решение задач, простейшие программы, разветвляющие программы, циклические программы, ввод-вывод, массивы, подпрограммы, строковые данные, записи, файлы, использование библиотеки CRT, графика в Паскале.
учебное пособие [211,1 K], добавлен 30.03.2008Разработана программа решения двух задач на языке программирования Turbo Pascal. Спецификация задания. Описание входных и выходных данных. Математическая постановка задачи. Алгоритм ее решения. Описание и блок-схема программы. Результаты тестирования.
курсовая работа [275,8 K], добавлен 28.06.2008