PDA

Просмотр полной версии : Рекурсия...помогите...плиз... (С++)



Ксю
14.05.2008, 21:26
Помогите пжалуста...нужно "Составить алгоритм рекурсивного поиска наименьшего элемента массива"
всё что у меня получилось:

#include<iostream.h>
#include<conio.h>
#include <windows.h>

const n=5;
char StrBuf[50];

int vvod(int a[])
{
for(int i=0; i<n; i++)
cin>>a[i];
}

int func(int a[])
{
int i;
int min;
if(i<n) return min;
if(a[i]<min) min=a[i];
min=func(i++,min,a);

}
void main(void)
{
int a[n];
int i=1;
int min=a[0]a[n];

CharToOem("Введите элементы массива: ", StrBuf);
cout << StrBuf<<endl;
vvod(a);
CharToOem("Минимальный элемент равен ", StrBuf);
cout << StrBuf<<func(a)<<endl;

getch();
}

Albor
15.05.2008, 10:12
Помогите пжалуста...нужно "Составить алгоритм рекурсивного поиска наименьшего элемента массива"
всё что у меня получилось:

#include<iostream.h>
#include<conio.h>
#include <windows.h>

const n=5;
char StrBuf[50];

int vvod(int a[])
{
for(int i=0; i<n; i++)
cin>>a[i];
}

int func(int a[])
{
int i;
int min;
if(i<n) return min; // Здесь ошибка - i не инициализирована
if(a[i]<min) min=a[i];
min=func(i++,min,a);

}
void main(void)
{
int a[n];
int i=1;
int min=a[0]a[n]; // а это что такое?

CharToOem("Введите элементы массива: ", StrBuf);
cout << StrBuf<<endl;
vvod(a);
CharToOem("Минимальный элемент равен ", StrBuf);
cout << StrBuf<<func(a)<<endl;

getch();
}
смотри коментарии в коде

Ксю
15.05.2008, 15:21
В общем переделала немного, получиль

#include<iostream.h>
#include<conio.h>
#include <windows.h>

const n=5;
char StrBuf[50];

int vvod(int a[])
{
for(int i=0; i<n; i++)
cin>>a[i];
}

int poisk(int a[], int i, int min)
{
if(i>n) return min;
else if(a[i]<min) min=a[i];
min=poisk(a,i++,min);

}

void main(void)
{
int a[n];
int i=1;
int min=a[0];
CharToOem("Введите элементы массива: ", StrBuf);
cout << StrBuf<<endl;
vvod(a);
CharToOem("Минимальный элемент равен ", StrBuf);
cout << StrBuf<<poisk(a,i,min)<<endl;

getch();
}Но теперь программка не работает...зависает и подчёркивает "min=poisk(a,i++,min);" что делать??

BBB
15.05.2008, 15:56
1. int min=a[0];
Но массив a значениями еще не инициализирован. Так что здесь min присвоится непредсказуемое значение.

2. Так как условие останова рекурсии написано как if(i>n), то при очередном вызове ф-ии poisk второй параметр попадет туда равным n[b]. Далее следует обращение к элементу массива [b]a[i], т.е. в нашем частном случае a[n]. Но последний элмент масива a имеет индекс n-1. Значит, попадаем "мимо памяти".

На глазок, условие останова надо заменить на if(i>=n)

Albor
15.05.2008, 15:56
В общем переделала немного, получиль

#include<iostream.h>
#include<conio.h>
#include <windows.h>

const n=5;
char StrBuf[50];

int vvod(int a[]) // тип функции подразумевает возвращаемое значение, здесь
//можно сделать void а не int
{
for(int i=0; i<n; i++)
cin>>a[i];
}

int poisk(int a[], int & i, int & min) // передача параметров по ссылке
// даст гарантию сохранения значения в переменной после отработки функции
{
if(i>n) return min; // а если условие не выполнится, то что вернёт функция?
// То есть по замыслу ф-ция должна вернуть int, но реально - может и не вернуть
else if(a[i]<min) min=a[i];
min=poisk(a,i++,min);

}

void main(void)
{
int a[n];
int i=1;
int min=a[0];
CharToOem("Введите элементы массива: ", StrBuf);
cout << StrBuf<<endl;
vvod(a);
CharToOem("Минимальный элемент равен ", StrBuf);
cout << StrBuf<<poisk(a,i,min)<<endl;

getch();
}Но теперь программка не работает...зависает и подчёркивает "min=poisk(a,i++,min);" что делать??

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

BBB
16.05.2008, 10:44
Albor,
int poisk(int a[], int & i, int & min) // передача параметров по ссылке
// даст гарантию сохранения значения в переменной после отработки функции
На мой взгляд, var-параметры для i и min здесь не нужны совсем.

Albor
16.05.2008, 12:19
Я комментировал то что есть. И, поскольку, Ксю делает присваивание переменной min, я и сделал такое предложение. В алгоритм я особо не вникал, и так очевидно, что функция построена некорректно. Как по мне, то,на первый взгляд, можно было бы обойтись указателями, скажем, передавать в функцию указатель на конец массива и текущий указатель, приращивая его и сравнивая с указателем на конец массива.

Ксю
16.05.2008, 22:18
Мне обязательно нужно чтобы была РЕКУРСИЯ....
программку переписала...и она даже запускается...только берёт самый первый элемент и выводит его как наименьший...

#include<iostream.h>
#include<conio.h>
#include <windows.h>

const n=5;
char StrBuf[50];
int i;

int poisk(int a[],int & min);
void vvod(int a[]);

void main(void)
{
int a[n];
int i=1;


CharToOem("Введите элементы массива: ", StrBuf);
cout << StrBuf<<endl;
vvod(a);
int min=a[0];
CharToOem("Минимальный элемент равен =", StrBuf);
cout << StrBuf<<poisk(a,min)<<endl;

getch();
}

void vvod(int a[])
{
for(int i=0; i<n; i++)
cin>>a[i];
}

int poisk(int a[],int & min)
{

if(i>=n) return min;
else if(a[i]<min)
{min=a[i];
i++;
min=poisk(a,min);
}
}

airyashov
17.05.2008, 00:59
Ваша ошибка int i=1; индекс не меняется


#include<iostream.h>
#include<conio.h>
#include <windows.h>

const n=5;
char StrBuf[50];
int i;

int poisk(int a[], int NextIndex);
void vvod(int a[]);

void main(void)
{
int a[n];

CharToOem("Введите элементы массива: ", StrBuf);
cout <<StrBuf<<endl;
vvod(a);

CharToOem("Минимальный элемент равен =", StrBuf);
cout <<StrBuf<<poisk(a,n-1)<<endl;

getch();
}

void vvod(int a[])
{
for(int i=0; i<n; i++)
cin>>a[i];
}

int poisk(int a[], int IndexNext)
{
if (IndexNext==0) return a[0];
else
{
int z=poisk(a,IndexNext-1);
return return ((a[IndexNext]<z)?a[IndexNext]:z);
};
}

Ксю
17.05.2008, 10:42
Огромное спасибо!!!

Danike
12.03.2010, 06:07
Написать программу упорядочивания массива из 10 элементов методом быстрой сортировки, используя рекурсию.

Пример ввода:
12 45 78 91 21 43 11 12 1 8

Пример вывода:
1 8 11 12 12 21 43 45 78 91

P.S. Идея алгоритма состоит в следующем. Применим к массиву так называемую процедуру разделения относительно среднего элемента. Вообще-то, в качестве «среднего» можно выбрать любой элемент массива, но для наглядности мы будем выбирать действительно, по возможности, средний по своему номеру элемент. Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие, чем элемент, выбранный в качестве среднего, а в правой — большие. Это достигается путем просмотра массива попеременно с обоих концов, при этом каждый элемент сравнивается с выбранным средним, и элементы, находящиеся в «неподходящей» части, меняются местами. После завершения процедуры разделения средний элемент оказывается на своем окончательном месте, т. е. его «судьба» определена и мы можем про него забыть. Далее процедуру разделения необходимо повторить отдельно для левой и правой части: в каждой части выбирается среднее, относительно которого она делится на две, и так далее. Понятно, что одновременно процедура не может заниматься и левой, и правой частями, поэтому необходимо каким-то образом запомнить запрос на обработку одной из двух частей (например, правой), и заняться оставшейся частью (например, левой). Так продолжается до тех пор, пока не окажется, что очередная обрабатываемая часть содержит ровно один элемент. Тогда нужно вернуться к последнему из необработанных запросов, применить к нему все ту же процедуру разделения и так далее... В конце концов массив окажется полностью упорядочен.

Newbie
13.03.2010, 01:12
Когда-то работало, но коду хз сколько времени, могут возникнуть какие нить траблы)



template <class T>
inline void swap(T array[], int pos1, int pos2)
{
T temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;

};

template <class T>
inline int partiton(T array[], int start, int end, int pe_index)
{
T pe = array[pe_index];
swap(array, pe_index, end);
int head = start, tail = end - 1;

while(true)
{
while(array[head] < pe) ++head;
//assert(array[head] >= pe);

while((array[tail] > pe) && (tail > start)) --tail;
//assert(array[tail] <= pe);

if(head >= tail) break;
swap(array, head++, tail--);
};
swap(array, head, end);
assert(array[head] == pe);

return head;
};

template <class T>
inline int get_pe(T array[], int lower, int upper)
{
int mid = (upper + lower) / 2;
if(array[lower] <= array[mid])
{
if(array[mid] <= array[upper]) return mid;
else if (array[upper] <= array[lower]) return lower;
else return upper;
}
else
{
if(array[lower] <= array[upper]) return lower;
else if (array[upper] <= array[mid]) return mid;
else return upper;
}
//return lower;
};

template <class T>
inline void qsort_base(T array, int head, int tail)
{
int diff = tail - head;

if(diff < 1) return;

if(diff == 2)
{
if(array[head] > array[tail]) swap(array, head, tail);
return;
}

int pe_index = get_pe(array, head, tail);

int mid = partiton(array, head, tail, pe_index);
assert((mid >= head) && (mid <= tail));

qsort_base(array, head, mid-1);
qsort_base(array, mid+1, tail);

};

template <class T>
inline void qsort(T array, int size)
{
int head = 0, tail = size - 1;
qsort_base(array, head, tail);
};