Решение задач по программированию на языке 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.