#include<stdio.h>
#define swap(a,b) { int tmp; tmp=a; a=b; b=tmp; }
main()
{
int a[10], dim=10;
int i, j, gap;
for (i=0;i<dim;i++)
{
printf("Элемент\n");
scanf("%d",&a[i]);
}
printf("Было\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
for (gap = dim/2; gap > 0; gap/=2) /* Выбор интервала */
for (i = gap;i < dim; i++) /* Проходмассива */
/* Сравнение пар, отстоящих на gap друг от друга */
for (j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap) swap(a[j], a[j+gap]);
printf("Стало\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
}
Функция называется рекурсивной, если ее значение для данного аргумента определяется через значения той же функции для предшествующих аргументов. В программировании функция называется рекурсивной, если последовательность операторов, составляющих тело функции, включает в себя один или несколько вызовов самой этой функции.
Рассмотрим более подробно организацию и работу рекурсивных подпрограмм.
Рекурсию можно использовать для вычисления факториала n!. Чтобы найти n!, нужно определить (n-1)!. А для этого необходим (n-2)! и так далее.
#include <conio.h>
#include <stdio.h>
int z;
int Fact(int n)
{
if (n == 1) return 1;
else return Fact(n - 1) * n; }
main()
{ int n;
printf("Число? \n");
scanf("%d",&n);
z = Fact(n); printf("%d",z);
}
2.3 Задача Ханойские башни
Легенда говорит ,– в одном из храмов Юго-Восточной Азии находятся три вертикальных стержня, на которые нанизаны 64 золотых кольца разного диаметра. Некогда бог Вишну поместил все 64 кольца на первый стержень так, что диаметр колец снизу вверх уменьшался, и повелел жрецам переместить башню из колец с первого стержня на третий, соблюдая следующее правило: на каждом шаге можно перенести самое верхнее кольцо с одного из стержней наверх другого стержня при условии, что на каждом из стержней кольца будут сохранять форму башни (т.е. их диаметр снизу вверх уменьшается). С тех пор много тысяч лет жрецы днем и ночью перекладывают кольца. Легенда гласит, что когда все кольца окажутся на третьем стержне, наступит конец света.
Программа:
#include <stdio.h>
#include <dos.h> /* sleep() */
#define MAX_NRINGS 64 /* Максимальное число колец */
int st[4][MAX_NRINGS]; /* 1,2,3 - стержни */
int nr[4]; /* Число колец на стержнях */
int nmoves; /* Число перемещений */
/* ---------------------------------------------- */
/* Печать текущего расположения колец на стержнях */
/* ---------------------------------------------- */
void print_st(void)
{
int i, j;
for(i = 1; i <= 3; i++) {
printf("\n| ");
for(j = 0; j < nr[i]; j++) printf("%d ", st[i][j]);
}
printf("\n");
}
/* ------------------------------------ */
/* Установка начального положения колец */
/* ------------------------------------ */
void init(int nrings)
{
for(nr[1] = 0; nrings > 0; nr[1]++,nrings--)
st[1][nr[1]] = nrings;
* Нанизали кольца на 1-й стержень */
nr[2] = nr[3] = 0;
/* Два других стержня пусты */
nmoves = 0;
print_st();
}
/* ----------------------------- */
/* Функция переносит одно кольцо */
/* со стержня n1 на стержень n2 */
/* ----------------------------- */
void move1(int n1, int n2)
{
st[n2][nr[n2]++] = st[n1][--nr[n1]];
sleep(1); /* Пауза в 1 секунду */
print_st(); /* Печать текущей позиции */
nmoves++;
}
/* ------------------------------------------------- */
/* Функция hanoi перемещает верхние nrings колец */
/* со стержня i1 на стержень i3, используя стержень */
/* i2 в качестве промежуточного. 1 <= i1,i2,i3 <= 3. */
/* ------------------------------------------------- */
void hanoi(int nrings, int i1, int i2, int i3)
{
if(nrings == 1)
move1(i1, i3);
else {
hanoi(nrings-1, i1, i3, i2);
move1(i1, i3);
hanoi(nrings-1, i2, i1, i3);
}
}
main()
{
int nrings;
printf("Числоколец: "); scanf("%d", &nrings); init(nrings);
hanoi(nrings, 1, 2, 3);
printf("Переносколецзавершен.\n");
printf("Число перемещений - %d.\n", nmoves); return(0);
}
В прложении N1 показано решение некоторых задачи на языке С.
Глава 3. Основы С++
3.1 Отличия С++ от С
1. В С++ ключевое слово void не обязательно (эквивалентно int m(); и int m(void)).
2. В С++ все функции должны иметь прототипы.
3.Если в С++ функция возвращает тип, отличный от void, то оператор return должен содержать значение типа.
4.В С++ можно выбирать место для объявления локальных переменных не только в начале блока.
5.В С++ ввод-вывод может осуществляться не только с помощью функций, но и с помощью операций.
3.2 Объектно-ориентированное программирование в С++
Развитие средств вычислительной техники требовало новых методик программирования:
- программирование небольших программ на базе переключателей;
- программирование на ассемблере;
- программирование на языках высокого уровня (Фортран);
- программирование на языках структурного программирования (Паскаль, Си);
- объектно-ориентированное программирование (ООП).
ООР позволяет разбить задачу на ряд самостоятельных связанных между собой подзадач, содержащих модели объектов реального мира.
Каждая подзадача содержит коды и данные, относящиеся к объекту, что упрощает решение задачи в целом и позволяет решать задачи большего объема.
Понятие объекта тесно связано с понятием класса. Класс – это дальнейшее развитие понятия структуры. Он позволяет создавать новые типы и определять функции, манипулирующие с этими типами.
Объект - это представитель определенного класса.
ООП использует механизмы инкапсуляции, полиморфизма и наследования.
Инкапсуляция позволяет создавать объекты - данные, процедуры и функции, манипулирующие с этими данными.
Данные, доступные для использования внутри объекта - private, данные доступные извне - public.
В общем, виде объект можно рассматривать как переменную, определенную программистом.
Полиморфизм позволяет одно имя функции использовать для решения разных задач (общих для класса действий).
В зависимости от данных выполняются те или иные действия.
Наследование позволяет одному объекту наследовать свойства другого объекта, т.е. порожденный класс наследует свойства родительского класса и добавляет собственные свойства.
3.2.1 Классы
Класс используется для создания объектов. Основная форма имеет вид:
class имя класса
{
закрытые функции и переменные
public:
открытые функции, функции-члены и переменные
}
список объектов;//не является обязательным
Закрытые функции и переменные - члены(members) доступны только для других членов этого класса.
Открытые функции и переменные доступны для любой части программы, в которой находится класс.
Функции, объявленные внутри описания класса называются функциями членами (member functions).
Для определения функций-членов используется форма:
тип имя класса:: имя функции-члена (параметры)
{
тело функции
}
Два двоеточия после имени класса называются операцией расширения области видимости (scope resolution operator).
Определение класса только определяет тип объектов, а сами объекты не задает), мять не выделяется). Для создания объектов имя класса используется как спецификатор типа данных.
После создания объекта к открытым членам класса можно обращаться, используя операцию точка.
Пример.
#include <iostream.h>
class class1 {//объвленсласс class1
int a; //доступна для функций членов class1
public:
int kwadrat(int b);//функциячленкласса class1
};
int class1::kwadrat(int b) //определениефункции kwadrat()
{
a=b*b;
return a;
}
main()
{
class1 c; //создается объект с типа class1
cout<<"\n"<<c.kwadrat(3)<<"\n";//вычисление и вывод квадрата трех
return 0;
}
3.2.2 Перегрузка функций
Две или более функции, имеющие одно и тоже имя называются перегружеными. Обычно функции отличаются количеством и типом аргументов. Транслятор автоматически на основании количества или типов аргументов выберет правильный вариант.
Пример.
#include <iostream.h>
void k(int a);//прототиппервойфункции
void k(int a, float b); //прототип второй функции
void k(int a) //описание первой функции
{
cout << a <<"\n";
}
voidk(inta, floatb) //описание второй функции
{
cout <<a<<"\n"<< b <<"\n";
}
main()
{
k(4);//вызов первой функции
k(5, 10.2);//вызов второй функции
return 0;
}
3.2.3 Конструкторы
Для автоматической инициализации создаваемых объектов в С++ используется функция - конструктор (constructor function), которая включается в описание класса.
Функция конструктор имеет тоже имя, что и класс и не возвращает ни какого значения.
Пример:
#include <iostream.h>
// Объявление класса class1
class class1 {
int a;
public:
class1(); // Конструктор
void kwadrat();
};
// Инициализация а конструктором при создании объекта pr
class1::class1()
{
a=100;
}
//Функция возведения в квадрат и печати
void class1::kwadrat()
{
cout << a*a;
}
main()
{
class1 pr;//Создание объекта pr
pr.kwadrat(); //Вызов функции kwadrat
return 0;
}
Как видно из примера конструктор вызывается при создании объекта pr.
3.2.4 Деструкторы
Функция деструктор (destructor)вызывается при удалении объекта для освобождения ресурсов (памяти и т.д.). Она также включается в объявление класса. Перед описанием деструктора ставится значок ~.
Пример.
#include <iostream.h>
// Объявление класса class1
class class1 {
int a;
public:
class1(); // Конструктор
~class1(); //Деструктор
void kwadrat();
};
// Инициализация а конструктором при создании объекта pr
class1::class1()
{
a=100;
}
//Освобождение ресурсов деструктором
class1::~class1()
{
cout<<"Освобождение\n";
}
//Функция возведения в квадрат и печати
void class1::kwadrat()
{
cout << a*a<<"\n";
}
ain()
class1 pr;//Создание объекта pr
pr.kwadrat(); //Вызов функции kwadrat
return 0;
}
Деструктор вызывается при удалении объекта или выхода из программы.
3.2.5 Конструкторы с параметрами
Конструктору можно передать параметры. Для этого нужно добавить необходимые параметры в объявление и определение конструктора. Затем при объявлении объекта параметры задаются в качестве аргумента.