Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] Рекурсия...

Автор: Жука 21.3.2007, 17:17

Здрасте все!очень-очень прошу, ПОМОГИТЕ, smile

!!!У меня тут задача на рекурсию, я совсем запуталась, ничегошеньки не понимаю... smile

Условие вот такое:
Описать функцию min(x) для определения минимального элемента линейного массива х, введя вспомогательную рекурсивную функцию min1(k), находящую минимум среди последних элементов массива х, начиная с k-го.

а вот мое, я не боюсь этого слова, решение...

Код


#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int min1(int *mas,int k,int n)
{int b,z;
if (k<n)
{z=min1(mas,k+1,n);
if(mas[k]<z)
min1(mas,k,n)=mas[k];
else min1(mas,k,n)=z;}
return z;
}

int min(int *mas,int i,int k)
{int s,tk;
tk=mas[0];
while(i<k)
{if (tk<mas[i+1])
tk=tk;
else tk=mas[i+1];
i++;}
if (tk<min1(mas,k,n)) return tk;
else
return min1(mas,k,n);}

void main()
{clrscr();
int n;
cout<<"Vvedite kol-vo elementov massiva: ";
cin>>n;
int *mas;
mas=new int[n];
cout<<"Dannii massiv: ";
int i=0;
randomize() ;
while(i<n)
{mas[i]=random(30);
cout<<mas[i]<<" ";
i++;}
int k=0;
cout<<"Vvedite nomer elementa, s kotorogo nachnetsya poisk: ";
cin>>k;
i=0;
if(abs(k)>=n ||abs(k)<=0) cout<<"Oshibka!";
else
cout<<"Minimalnii element massiva: "<<min(mas,i,k);
delete [] mas;
getchar() ;}

вобщем у меня не работает(чего и следовало ожидать)...умоляю..ХЭЛП

Автор: apook 21.3.2007, 18:21

Опиши на словах принцип работы каждой( что должна делать )функции, а то на первый взгляд полная городьбба (придется писать свой вариант( smile

))

Автор: cardinal 21.3.2007, 18:35

Жука, найчись рисовать дерево рекурсии - сразу все понятно будет...

Автор: Жука 21.3.2007, 18:53

ну короче первая ф-ция мин1 ищет минимум среди элементов массива, начиная с к-го и до конца.вот она и должна быть рекурсивной.вторая ф-ция-мин-ищет минимум среди элементов с 1 по к-ый.она должна использовать мин1(ну или не должна...).а потом результаты поиска сравниваются..и выводится минимальный элемент массива..вот такая ерунда

Автор: Бонифаций 21.3.2007, 18:55

давай посмотрим.

min(x) и min1 по описанию похожи как два брата близнеца. только у min - весь массив, а у min1 - с к элемента. Тогда min можно выразить через min1 как

Код


int min(int x[], int n) {
  return min1(x,n,0);
}

то есть min это min1 с 0 элемента.

min1 должен рекурсивно искать минимальный элемент. Алгоритм очень простой. Берем k элемент и вычисляем минимум всех остальных элементов выше его с помощью min1(k+1). А потом тот который меньше из этих двух значений то и возвращаем. то есть

Код


int min1(int x[], int n, int k) {
  int current;
  int allother;
  current = x[k];
  allother = min1(x,n,k+1);

 return (current < allother?  current: allother);
);

Теперь еще надо предусмотреть чтобы не вышло бесконечной рекурсии. по правилам такая проверка вставляется в самое начало рекурсивной процедуры. Для нас это k должно быть = n-1 ( последний элемент массива x - если мы добрались до последнего элемента - нет смысла сравнивать его с чем то еще). Тогда конечный вариант min1

Код


int min1(int x[], int n, int k) {
  int current;
  int allother;
  if (k == n-1)  return x[k]; /* вот это вот проверка выхода из рекурсии */

  current = x[k];
  allother = min1(x,n,k+1);

 return (current < allother?  current: allother);
);

Вам осталось еще продумать проверки против бестолковых данных (типа n==0 и тд)

Автор: Жука 21.3.2007, 21:19

Спасибочки)))
обьясните ток пожалуста что вот это такое:

Код


return (current < allother?  current: allother);

я с таким впервые сталкиваюсь, препод спросит а я не отвечу сроду smile

и еще...у меня min правильно составлена, особенно там , где она к min1 обращается???

Автор: zkv 21.3.2007, 21:26

Цитата(Жука @ 21.3.2007, 21:19

)

return (current < allother? current: allother);

практически тоже, что и:

Код


if( current < allother )
   return current;
else
   return allother;

а вообще ? : - тернарная операция, или оператор, как вам больше нравится smile

ps у вас ужасно оформлен код, поэтому вникать в него особого желания нет

Автор: Жука 21.3.2007, 21:30

господи Боже мой)как все сложно-то!!спасибо smile

) можно вас немного подоставать...а у меня min правильно???

Автор: apook 22.3.2007, 12:01

Цитата

а у меня min правильно???

НЕТ

Участок кода из твоей функции min

Код


tk=mas[0];
while( i<k )
{
    if (tk<mas[i+1]) tk=tk;
    else tk=mas[i+1];
    i++;
    }

Фактически этот код ищет максимальный эл-т массива

Код


i=1; // тогда-уж так
tk=mas[ 0 ];
while( i<k )
{
    if( tk>mas[ i ] )
        tk=mas[ i ];
    i++;
    }

Вобще есть какой-то замысел но он теряется, тебе надо стараться представлять
что делает каждая строчка.

Попробуй понять то что сама накодила.. Получилось?? Нет? Это нормально..

Автор: Жука 22.3.2007, 19:02

ВСЕМ-ВСЕМ-ВСЕМ ОГРОМНОЕ СПАСИБО!!!! smile