Funkcja rekurencyjna [C]

Odpowiedz Nowy wątek
2013-01-02 17:27
0

Witam , chciałbym prosić o pomoc w napisaniu funkcji rekurencyjnej która zwróci wartość maksymalną z n-elementowej tablicy (w jezyku C)

Pozostało 580 znaków

2013-01-02 17:33
0

Dziel tablice na pół i szukaj maksa w obu połówkach (tą samą funkcją) a potem porównaj maksy z jednej i z drugiej połówki i zwróć tą większą wartość (warunek stopu rekurencji to oczywiście tablica 1 elementowa)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2013-01-02 17:41
int recmax(int *begin,int *end)
  {
   int a,b,*mid;
   a=end-begin;
   if(a>1)
      {
       mid=begin+(a>>1);
       a=recmax(begin,mid);
       b=recmax(mid,end);
       return a>b?a:b;
      }
   return *begin;
  }

druga wersja z użyciem max()

int recmax(int *begin,int *end)
  {
   int *mid=begin+((end-begin)>>1);
   return mid>begin?max(recmax(begin,mid),recmax(mid,end)):*begin;
  }

wywołanie:

int tb[]={1,8,9,7,5,4,3,2};
printf("%d",recmax(tb,tb+sizeof(tb)/sizeof(*tb)));

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2013-01-02 18:34

Pozostało 580 znaków

2013-01-02 17:50
0

... albo po prostu uzyj rekurancji jako iteracji, o cos w ten desen:

func max_in_arr(tab, size, pos)
  if(pos >= size) reurn -Inf;
  else return max(tab[pos], max_in_arr(tab, size, pos+1))

Na prosbe @_13th_Dragon wersja z rekursja ogonowa:

func max_in_arr(tab, size, pos, curr_max)
  if(pos >= size) reurn curr_max;
  else return max_in_arr(tab, size, pos+1, max(curr_max, tab[pos])))
edytowany 4x, ostatnio: 0x200x20, 2013-01-16 12:48
Pokaż pozostałe 2 komentarze
W poście wyżej ilość zagnieżdżonych wywołań wynosi log(N), czyli mniej więcej 32 wywołania dla 16 GB tablicy. - _13th_Dragon 2013-01-02 18:04
a jak machne sobie iteracje to ilosc zagniezdzonych wynosi 0 dla 16GB tablicy. Przeciez to zadanie jest wylacznie edukacyjne i jakos nie wydaje mi sie zeby mialo dzialac dla tablicy 16GB. A taka forma rekurencji jest prostsza do zrozumienia. - 0x200x20 2013-01-02 18:08
Edukacja między innymi musi uczyć kiedy to czemu uczymy się należy stosować a kiedy nie należy, ty podałeś przykład jak NIE należy używać rekurencji. - _13th_Dragon 2013-01-02 18:10
Wystarczy sobie przeksztalcic w rekurencje ogonowa - kompilator powinien zoptymalizowac. Wciaz prostsze od podzialow tablicy a do tego bardziej wydajne. - 0x200x20 2013-01-02 18:25
Jeżeli użyć funkcji max której ty użyłeś to wcale nie będzie prostsze, dodaje na górze drugą wersje. - _13th_Dragon 2013-01-02 18:32

Pozostało 580 znaków

2013-01-02 18:44
0

potrafiłby zrobić to ktoś nie uzywając "begin"?

@edit
ahh moj blad nie zauwazylem ze begin jest typu int i myslalem ze to jakas "funkcja"

edytowany 1x, ostatnio: Ssyys, 2013-01-02 18:52
Zamień begin na A i po strawie. - _13th_Dragon 2013-01-02 18:47
nie do konca rozumiem co dzieje się tu: mid=begin+(a>>1); - Ssyys 2013-01-02 18:50
mid=begin+a/2; - _13th_Dragon 2013-01-02 18:56

Pozostało 580 znaków

2013-01-02 18:54
1
int max(int a,int b) { return a>b?a:b; }
int recmax(int A[],int B[])
  {
   int *M=A+((B-A)>>1);
   return M>A?max(recmax(A,M),recmax(M,B)):A[0];
  } 
int main()
  {
   int tb[]={1,8,9,7,5,4,3,2};
   printf("%d",recmax(tb,tb+sizeof(tb)/sizeof(*tb)));
   return 0;
  }

lub:

int *max(int a[],int b[]) { return a[0]>b[0]?a:b; }
int *recmax(int A[],int B[])
  {
   int *M=A+((B-A)>>1);
   return M>A?max(recmax(A,M),recmax(M,B)):A;
  }
int main()
  {
   int tb[]={1,8,9,7,5,4,3,2};
   printf("%d",*recmax(tb,tb+sizeof(tb)/sizeof(*tb)));
   return 0;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2013-01-02 18:54
Pokaż pozostałe 3 komentarze
Zbyt często muszę pisać programy pod urządzenia, kompilator dla których nie ma nawet pojęcia "optymalizacja" więc (B-A)>>1 jest o wiele szybsza niż (B-A)/2. Jeżeli edukacji programowania nie rozpoczęto od podstaw kodu binarnego i operacji bitowych to tą edukację rozpoczęto od dupy strony. - _13th_Dragon 2013-01-02 19:05
no prosze, to jeszcze takie triki sie przydaja. Mozesz powiedziec co to za kompilator? - 0x200x20 2013-01-02 19:22
@_13th_Dragon: kiedy przeniesiesz się do 21 wieku? :-P - Endrju 2013-01-02 22:21
Kiedy skończą się dobrze płacące zleceniodawcy z 20 wieku. - _13th_Dragon 2013-01-02 22:25
Dobra odpowiedź! :-) No pochwal się na co lub w czym to piszesz. Wg wiki GCC wspiera łącznie 69 architektur, co Ty robisz. :-o - Endrju 2013-01-02 22:33

Pozostało 580 znaków

2013-01-02 22:14
0

Miałbym prośbę , aby ktoś napisał tą funkcje tylko operatorami które wystepują w tej funkcji którą podam na dole , ze wzgledu na to że tylko je poznałem i tylko tych wolno mi uzywać ,byłbym wdzieczny:

jest to funkcja rekurencyjna odwracajaca tablice
void list(int n, int t[]){
if(n>0){
list (n-1,t);
printf ("%d",t[n-1])
}
}
int main (void){
const int n=5
int a[n]={7,-6,0,4};
list(n,a)

Głupi leń nie jest w stanie funkcji max napisać ? - _13th_Dragon 2013-01-02 22:26
no niestety nie , a funkcji ktorej podales sa nie znane i opertaory - Ssyys 2013-01-02 22:29
Po prostu czyta i w mozgu wywala mu Syntax Error - 0x200x20 2013-01-02 22:35
być moze dla was to niewiele jednak ja bylbym wdzieczny gdyby ktos to zrobil ;p - Ssyys 2013-01-02 22:47

Pozostało 580 znaków

2013-01-07 14:52
0

a mógłby sprawdzić ktoś czemu ta funkcja źle działa??

#include <stdio.h>
#include<conio.h>

int najwieksza(int n ,int t[]){ 
    if(n==1)return t[0];

    else{

    if (t[n-1]>t[n]) return najwieksza(n-1,t);
    else{
     t[n-1]=t[n] ;
      return najwieksza (n,t);
}

}
}
    int main(void){
        int const n=3;
        int a[n]={9,8,7};
        int w=najwieksza(n,a);
        printf ("%d",w);
        getche ();
        return 0;

    }

używaj tagów <code> - msm

edytowany 1x, ostatnio: msm, 2013-01-07 15:26

Pozostało 580 znaków

2013-01-07 15:07
0

"źle działa"? To się nawet nie kompiluje...
Poprawiona wersja: http://ideone.com/t8ngwv


Yhy, poprawiona? :P - msm 2013-01-07 15:28
"poprawiona" w rozumieniu "ta już się kompiluje" :P - Patryk27 2013-01-07 15:29

Pozostało 580 znaków

2013-01-07 15:17
0

Uzywam dev c++ u mnie Twoja wersja zwraca nieprawidłowa wartość 322..

nawet w Tym kompilatorze online wychodzą złe wyniki !!!

edytowany 1x, ostatnio: Ssyys, 2013-01-07 15:22

Pozostało 580 znaków

2013-01-07 15:20
0

Kompilator ci już powiedział co jest nie tak.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0