Материал: Larin_Anton_AiSD_21_1

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

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

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

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

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

отчет

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

по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»

Тема: Рекурсия

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

2019

Цель работы.

Научится реализовывать рекурсивные алгоритмы, решать с их помощью задачи. Написать программу реализующую рекурсивный алгоритм.

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

Самое простое определение рекурсии можно дать как вызов функции из неё же самой, непосредственно или через другие функции. (например, функция foo() вызывает функцию bar(), а функция bar() — функцию foo(). Количество вложенных вызовов функции называется глубиной рекурсии. На каждый вызов функции приходятся как временные затраты, так и затраты памяти в области стека, основная часть которых приходится на хранение аргументов функции и ее локальных переменных.

Очень хорошо использование рекурсии ложится на задачи, которые можно разделять на себе подобные. Иногда это не так просто увидеть (например не очевидно утверждение, утверждение, что "сумма элементов массива - это сумма первого элемента плюс сумма остальных элементов" ).

При разработке рекурсивного алгоритма, в первую очередь следует продумать условие завершения рекурсии. Часто, это выглядит как обработка частных конечных случаев.

Рассмотрим пример, который присутствует, по-видимому, во всех учебниках по программированию. Функция факториал натурального аргумента n обозначается как n! и определяется соотношением

n!=123...(n – 1)n .

Удобно доопределить 0!=1 и считать, что n – целое неотрицательное число.

Некоторым недостатком данного определения является наличие в нём многоточия «...», передающего речевой оборот «и так далее» и имеющего интуитивно понятный читателю смысл. Можно дать точное, так называемое рекурсивное определение функции n!, лишенное этого недостатка, т. е. не апеллирующее к нашей интуиции.

Определим:

а) 0! = 1 ,

б) n! = (n  1)!n при n > 0.

Соотношения можно рассматривать как свойства ранее определенной функции, а можно (как в данном случае) использовать их для определения этой функции.

Далее для функции n! будем использовать обозначение fact (n) , указывая имя функции и за ним в скобках  аргумент. Тогда определение можно записать в виде fact (n)  if n = 0 then 1 else fact (n  1)  n

Задание

Функция Ф преобразования целочисленного вектора  определена следующим образом:

Например: Ф(1,2,3,4,5) = 1,2,2,3,3,4,4,5; Ф(1,2,3,4,5,6) = 1,2,2,3,4,5,5,6; Ф(1,2,3,4,5,6,7) = 1,2,3,4,4,5,6,7; Ф(1,2,3,4,5,6,7,8) = 1,2,3,4,5,6,7,8. Отметим, что функция Ф может удлинять вектор. Реализовать функцию Ф рекурсивно.

Реализация

В основной функции main последовательно происходит:

Вызов функций parseArgs, которая обрабатывает аргумента командной строки;

Затем, если требуется, открытие файлов на вход и выход;

Вызов функции input для считывания данных из потока ввода (либо автоматический сгенерированных функцией awtoInput) в целочисленный вектор.

Вектор передается в рекурсивную функцию phi, которая обрабатывает его согласно правилам, данным в условии задачи.

Результат выводится в консоли и, опционально, в файл.

Программа поддерживает настройку при помощи параметров из командной строки. Получить информацию от них можно аргументом «-h»

Они следуюшие:

-h help

-A [N] Автоматическое тестирование на векторах длины 2 — N (N=2 по умолчанию; игнорирует параметры -i и -r при вводе)

-r Дает выбор перезапустить программу после исполнения. Не совместимо с «-i»

-i [file] Ввод из файла file, вместо стандартного потока stdin («in» по умолчанию)

-o [file] Вывод в файл file помимо стандартного потока stdout («out по умолчанию»)

Тесты.

-1.

Input:

Result:

0.

Input:1

Result:1

1.

Input:1 2

Result:1 2

2.

Input:1 2 3

Ba: 1 2

aC: 2 3

Result:1 2 2 3

3.

Input:1 2 3 4

B: 1 2

C: 3 4

Result:1 2 3 4

4.

Input:1 2 3 4 5

Ba: 1 2 3

Ba: 1 2

aC: 2 3

aC: 3 4 5

Ba: 3 4

aC: 4 5

Result:1 2 2 3 3 4 4 5

5.

Input:1 2 3 4 5 6

B: 1 2 3

Ba: 1 2

aC: 2 3

C: 4 5 6

Ba: 4 5

aC: 5 6

Result:1 2 2 3 4 5 5 6

6.

1 2 3 a 5 4 s

Error: Bad input data

7.

^[[DIS IS^[[BAD

Error: Bad input data

Выводы.

В результате работы была написана полностью рабочая программа решающая поставленную задачу при использовании изученных теоретических материалов. Программа было протестирована, результаты совпадают с контрольными из примеров в условии; неправильный ввод приводит к стабильному завершении программы.

Приложение(листинг программы)

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

using namespace std;

#define DEFAULT_IFILE_NAME "in"

#define DEFAULT_OFILE_NAME "out"

istream *inFile;

bool readFromFile= false;

ostream *outFile;

bool printToFile= false;

bool repeat= false;

bool awto = false;

int awtoLim = 0;

int parseArgs(int argc, char** argv, string &iFileName, string &oFileName); //Parses arguments. Returns 1 if program is to be closed

int input(istream *istr,vector<int> &inp); //Fills int vector from *istr

void printStr(string str); //Prints string to all necessary outputs

void printColl(vector<int> alpha,int recLvl = 0); //Prints given collection to all necessary outputs. alpha - collection to print, recLvl - offset

vector<int> phi(vector<int> &alpha,int recLvl = 0); //Recursively processes alpha

int awtoInput(vector<int> &inp, int lim); //input function for auto testing

void help(){

cout<<"-h\t\thelp\n";

cout<<"-A [N]\t\tAuto testing with 0 to N vector length (ignores -i and -r)\n";

cout<<"-r\t\tchose to repeat input after compliton. Incompatable with \"-i\"!\n";

cout<<"-i [file]\t input from file (\""<<DEFAULT_IFILE_NAME<<"\" by default)\n";

cout<<"-o [file]\t output to file (\""<<DEFAULT_OFILE_NAME<<"\" by default)\n";

}

void setIFile(istream* istr){

inFile=istr;

}

void setOFile(ostream* ostr){

outFile=ostr;

}

int main(int argc, char** argv) {

//Variables

string iFileName;

string oFileName;

vector<int> inp;//input container

vector<int> res;//result container

ofstream oFile;

ifstream iFile;

bool r = true;

//Parse arguments

if(parseArgs(argc,argv,iFileName,oFileName))return 0;

//Manage files

if (printToFile){

oFile.open(oFileName,ios::out);

if(!oFile){

printStr("Cannot open file: "+oFileName+"\n");

return 1;

}

setOFile(&oFile);

}

if (readFromFile){

iFile.open(iFileName);

if(!iFile){

printStr("Cannot open file: "+iFileName+"\n");

return 1;

}

setIFile(&iFile);

}

while(r) {

//Input

if(!awto) {

if (input(readFromFile ? &iFile : &cin, inp)) {

printStr("Error: Bad input data\n");

return 1;

}

} else {

if(awtoInput(inp,awtoLim))return 0;

}

//Process and print

printStr("\nInput:");

res = phi(inp);

printStr("Result:");

printColl(res);

//Checks

if(awto){

r= true;

} else {

if (repeat) {

printStr("\nRepeat? [1-Yes|0-No]\n");

cin.clear();

int t;

cin >> t;

r = t;

if (r)printStr("\n");

else printStr("Good bye!\n");

} else r = false;

}

}

if(printToFile)oFile.close();

return 0;

}

int parseArgs(int argc, char** argv, string &iFileName, string &oFileName){

//vector<int> t;

//bool done=0;

int i=1;

//string fileName;

while(i<argc){

//if(argc>1){

if(!((string)argv[i]).compare("-h")){

help();

return 1;

} else if(!((string)argv[i]).compare("-i")){

readFromFile=true;

if(i!=argc-1 && argv[i+1][0]!='-'){

iFileName=(string)argv[i+1];

i++;

} else iFileName = DEFAULT_IFILE_NAME;

i++;

} else if(!((string)argv[i]).compare("-o")){

printToFile=true;

if(i!=argc-1 && argv[i+1][0]!='-'){

oFileName=(string)argv[i+1];

i++;

} else oFileName = DEFAULT_OFILE_NAME;

i++;

} else if(!((string)argv[i]).compare("-r")){

repeat=true;

i++;

}

else if(!((string)argv[i]).compare("-A")){

awto=true;

if(i!=argc-1 && argv[i+1][0]!='-'){

awtoLim=atoi(argv[i+1]);

i++;

} else awtoLim = 2;

i++;

}

}

if(readFromFile&&repeat){

readFromFile=false;

printStr("Warning! -i, -r are incompatable. -i is ignored!\n");

}

return 0;

}

int input(istream *istr,vector<int> &inp){

#define INS ( readFromFile?(*inFile):cin )

if(!inp.empty())inp.clear();

int a;

printStr("Enter integer elements of vector alpha(end with EOF):\n");

INS>>a;

while(!INS.fail() && !INS.eof()){

inp.push_back(a);

INS>>a;

}

if(!INS.fail()){inp.push_back(a);return 0;}

else if(!INS.eof()){return 1;}

else return 0;

}

int awtoInput(vector<int> &inp, int lim){

static int n = 0;

if(!inp.empty())inp.clear();

if(n<=lim){

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

inp.push_back(i+1);

}

n++;

return 0;

}else return 1;

}

void printStr(string str){

cout<<str;

if(printToFile&&outFile&&(*outFile))(*outFile)<<str;

}

void printColl(vector<int> alpha,int recLvl) {

while (recLvl--) {

cout << "\t ";

if (printToFile&&outFile) (*outFile) << "\t ";

}

for(auto it = alpha.begin();it!=alpha.end();it++){

cout<<*it<<" ";

if (printToFile&&outFile) (*outFile) <<*it<<" ";

}

cout << endl;

if (printToFile&&outFile) (*outFile) << endl;

}

vector<int> phi(vector<int> &alpha,int recLvl){

printColl(alpha,recLvl);

size_t len=alpha.size();

if(len<=2){//exit condition

return alpha;

}

else if(!(len&1)){//even

vector<int> beta(alpha.begin(),alpha.begin()+len/2); //Getting Beta

printStr("B:");

beta= phi(beta,recLvl+1); //Getting phi(Beta)

vector<int> gamma(alpha.begin()+len/2,alpha.end()); //Getting Gamma

printStr("C:");

gamma= phi(gamma,recLvl+1); //Getting phi(Gamma)

vector<int> res(beta);

res.insert(res.end(),gamma.begin(),gamma.end()); //Getting Result

return res;

}

else{//odd

vector<int> beta(alpha.begin(),alpha.begin()+len/2+1); //Getting Beta+a

printStr("Ba:");

beta= phi(beta,recLvl+1); //Getting phi(Ba)

vector<int> gamma(alpha.begin()+len/2,alpha.end()); //Getting a+Gamma

printStr("aC:");

gamma= phi(gamma,recLvl+1); //Getting phi(aC)

vector<int> res(beta);

res.insert(res.end(),gamma.begin(),gamma.end()); //Getting Result

return res;

}

}

11