lab1 / report_lr1
.docx
МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра МОЭВМ
отчет
по лабораторной работе №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, которая содержит (прямо или косвенно) обращение к Р, то Р называется косвенно рекурсивной.
Ход работы
-
Произведён анализ задания и выделена рекурсивная функция Ф и разработана её рекурсивная часть.
-
Разработана программа, содержащая в себе:
Структуру vect хранящий указатель на числовой массив и длину этого масссива.
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;
}
-
Функция 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();
}
-
Сопоставление рекурсивного и итеративного решения показывает, что итеративное решение гораздо сложнее рекурсивного в создании и понимании и не обладает преимуществом в скорости.
-
В данной задаче использование рекурсии целесообразно из-за её простоты и в данном случае эффективности т. к. нет лишних вызовов самой функции, а данный изменяются по указателю.
Примеры работы программы
На рисунках 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();
}