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

Ответить

Код подтверждения
Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[url] ВКЛЮЧЁН
Смайлики ОТКЛЮЧЕНЫ
Обзор темы
   

Развернуть Обзор темы: Рекурсия...помогите...плиз... (С++)

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

Newbie » 13 мар 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);
};

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

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

Re: Рекурсия...помогите...плиз...

Ксю » 17 май 2008, 10:42

Огромное спасибо!!!

Re: Рекурсия...помогите...плиз...

airyashov » 17 май 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);
    };
}

Re: Рекурсия...помогите...плиз...

Ксю » 16 май 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);
    }
}

Re: Рекурсия...помогите...плиз...

Albor » 16 май 2008, 12:19

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

Re: Рекурсия...помогите...плиз...

BBB » 16 май 2008, 10:44

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

Re: Рекурсия...помогите...плиз...

Albor » 15 май 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);" что делать??


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

Re: Рекурсия...помогите...плиз...

BBB » 15 май 2008, 15:56

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

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

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

Re: Рекурсия...помогите...плиз...

Ксю » 15 май 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);" что делать??

Вернуться к началу