МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра МОЭВМ

отчет

по лабораторной работе №1

по дисциплине «Алгоритмы и структуры данных»

Тема: ПРОГРАММИРОВАНИЕ РЕКУРСИВНЫХ АЛГОРИТМОВ

Студент гр. 3303
Преподаватель

Санкт-Петербург

2018

---

Цель работы.

Познакомиться с основными понятиями и приёмами рекурсивного программирования, получить навыки программирования рекурсивных процедур и функций на языке программирования С++.

Написать рекурсивную функцию Ф для преобразования вектора α.

Ф ункция Ф преобразует вектор, не меняя его длину.

Например: Ф(1,2,3,4,5) = 1,2,3,4,5; Ф(4,3,2,1) = 3,4,1,2; Ф(4,3,2) = 3,4,2 .

Основные теоретические положения.

Рекурсивным называется объект, содержащий сам себя или определенный с помощью самого себя.

Мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания. Точно так же бесконечные вычисления можно описать с помощью конечной рекурсивной программы. Рекурсивные алгоритмы лучше всего использовать, когда решаемая задача, вычисляемая функция или обрабатываемая структура данных определены с помощью рекурсии.

Если процедура (функция) Р содержит явное обращение к самой себе, она называется прямо рекурсивной. Если Р содержит обращение к процедуре (функции) Q, которая содержит (прямо или косвенно) обращение к Р, то Р называется косвенно рекурсивной.

Ход работы

1. Произведён анализ задания и выделена рекурсивная функция Ф и разработана её рекурсивная часть.

2. Разработана программа, содержащая в себе:

Структуру vect хранящий указатель на числовой массив и длину этого масссива.

struct vect{

   			int* arr;
    			int size;
		};

1. Функцию для распечатки вектора

void print_vector(vect &vector,int start,int len){

    if(vector.size < len) len = vector.size;
    cout<<"Обработанный вектор = (";
    for (int i= 0;i<len;i++){
       cout<<vector.arr[start+i];
       if(i != (len-1)) cout<<",";
    }
    cout<<")"<<endl;

}

2. Функцию Φ для обработки вектора

void change(vect &vector,int start,int len){

if(len > 2){

if(len % 2 == 1){

change(vector,start,len/2+1);

change(vector,start + len/2 ,len/2);

}else{

change(vector,start,len/2);

change(vector,start + len/2,len/2);

}

}

if(len == 2 && (vector.arr[start +1] < vector.arr[start])){

int x = vector.arr[start];

vector.arr[start] = vector.arr[start+1];

vector.arr[start+1] = x;

}

if(len == 1) return;

}

3. Функция main для инициализации массива, его считывания и передачи в структуру vect, вызова функции Φ и распечатки результата.

Также производиться проверка на корректность исходных данных и обработка векторов до выхода по ключевому слову.

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    char exit_str[20];
    vect vector;
    do{
        char str[5];
            printf("%s","Введите длину вектора: ");
         fgets(str, sizeof(str), stdin);
        while (sscanf(str, "%d", &vector.size) != 1) {
            printf("Ошибка ввода. Попробуйте ещё:");
            fgets(str, sizeof(str), stdin);
        }
        int arr[vector.size];
        vector.arr = arr;
        printf("Введите вектор \n");
        for (int i=0;i<vector.size;i++){
            printf("%d число:",i+1);
            fgets(str, sizeof(str), stdin);
            while (sscanf(str, "%d", &arr[i]) != 1) {
                printf("Ошибка ввода. Попробуйте ещё:");
                fgets(str, sizeof(str), stdin);
            }
        }
        change(vector,0,vector.size);
        print_vector(vector,0,vector.size);
        printf("Введите new для продолжения\n");
        scanf("%s",exit_str);
        printf("\n");
       fgets(str, sizeof(str), stdin);
    }while(strcmp(exit_str,"new") == 0);
    exit(1);
    return a.exec();
}

---

3. Сопоставление рекурсивного и итеративного решения показывает, что итеративное решение гораздо сложнее рекурсивного в создании и понимании и не обладает преимуществом в скорости.

4. В данной задаче использование рекурсии целесообразно из-за её простоты и в данном случае эффективности т. к. нет лишних вызовов самой функции, а данный изменяются по указателю.

Примеры работы программы

На рисунках 1,2,3 приведены примеры работы программы.

Рисунок 1 —пример 1.

Рисунок 2 — пример 2.

Рисунок 3 — пример 3.

Вывод

Было проведено ознакомление с рекурсивными функциями и их программированием. Была написана рекурсивная функция Φ для преобразования вектора и её работа была успешно протестирована. В данной задаче рекурсивная функция имеет преимущество из-за своей простоты и удобства.

---

ПРИЛОЖЕНИЕ A

Код программы main.cpp

#include <QCoreApplication>

#include <iostream>

#include <cstdio>

using namespace std;

struct vect{

int* arr;

int size;

};

void print_vector(vect &vector,int start,int len){

if(vector.size < len) len = vector.size;

cout<<"Обработанный вектор = (";

for (int i= 0;i<len;i++){

cout<<vector.arr[start+i];

if(i != (len-1)) cout<<",";

}

cout<<")"<<endl;

}

void change(vect &vector,int start,int len){

if(len > 2){

if(len % 2 == 1){

change(vector,start,len/2+1);

change(vector,start + len/2 ,len/2);

}else{

change(vector,start,len/2);

change(vector,start + len/2,len/2);

}

}

if(len == 2 && (vector.arr[start +1] < vector.arr[start])){

int x = vector.arr[start];

vector.arr[start] = vector.arr[start+1];

vector.arr[start+1] = x;

}

if(len == 1) return;

}

int main(int argc, char *argv[])

{

QCoreApplication a(argc, argv);

char exit_str[20];

vect vector;

do{

char str[5];

printf("%s","Введите длину вектора: ");

fgets(str, sizeof(str), stdin);

while (sscanf(str, "%d", &vector.size) != 1) {

printf("Ошибка ввода. Попробуйте ещё:");

fgets(str, sizeof(str), stdin);

}

int arr[vector.size];

vector.arr = arr;

printf("Введите вектор \n");

for (int i=0;i<vector.size;i++){

printf("%d число:",i+1);

fgets(str, sizeof(str), stdin);

while (sscanf(str, "%d", &arr[i]) != 1) {

printf("Ошибка ввода. Попробуйте ещё:");

fgets(str, sizeof(str), stdin);

}

}

change(vector,0,vector.size);

print_vector(vector,0,vector.size);

printf("Введите new для продолжения\n");

scanf("%s",exit_str);

printf("\n");

fgets(str, sizeof(str), stdin);

}while(strcmp(exit_str,"new") == 0);

exit(1);

return a.exec();

}

---

Смотрите также файлы

• report_lr2.docx

• report_lr3.docx

• report_lr4.docx

• 1. Дієслово.docx

• 2. Дієприкметник. Дієприслівник.docx