Witam , chciałbym prosić o pomoc w napisaniu funkcji rekurencyjnej która zwróci wartość maksymalną z n-elementowej tablicy (w jezyku C)
C 
C++ 
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
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)
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
1
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)));
edytowany 1x, ostatnio: _13th_Dragon
- Rejestracja:ponad 13 lat
- Ostatnio:około 8 lat
- Postów:1176
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
Zobacz pozostałe 2 komentarze
_13th_Dragon
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.
0x200x20
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.
_13th_Dragon
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.
0x200x20
Wystarczy sobie przeksztalcic w rekurencje ogonowa - kompilator powinien zoptymalizowac. Wciaz prostsze od podzialow tablicy a do tego bardziej wydajne.
_13th_Dragon
Jeżeli użyć funkcji max której ty użyłeś to wcale nie będzie prostsze, dodaje na górze drugą wersje.
- Rejestracja:ponad 12 lat
- Ostatnio:około 10 lat
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
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;
}
edytowany 1x, ostatnio: _13th_Dragon
Zobacz 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 d**y strony.
no prosze, to jeszcze takie triki sie przydaja. Mozesz powiedziec co to za kompilator?
@_13th_Dragon: kiedy przeniesiesz się do 21 wieku? :-P
Kiedy skończą się dobrze płacące zleceniodawcy z 20 wieku.
Dobra odpowiedź! :-) No pochwal się na co lub w czym to piszesz. Wg wiki GCC wspiera łącznie 69 architektur, co Ty robisz. :-o
- Rejestracja:ponad 12 lat
- Ostatnio:około 10 lat
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ć ?
no niestety nie , a funkcji ktorej podales sa nie znane i opertaory
Po prostu czyta i w mozgu wywala mu Syntax Error
być moze dla was to niewiele jednak ja bylbym wdzieczny gdyby ktos to zrobil ;p
- Rejestracja:ponad 12 lat
- Ostatnio:około 10 lat
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
0
"źle działa"? To się nawet nie kompiluje...
Poprawiona wersja: http://ideone.com/t8ngwv
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
2
Masz:
int const n=3;
int a[n]={9,8,7};
int w=najwieksza(n,a);
Oraz:
if (t[n-1]>t[n]) return najwieksza(n-1,t);
else{
t[n-1]=t[n] ;
return najwieksza (n,t);
T[n] to odwołanie się poza zakres tablicy...
Btw. formatowanie kodu (i nie używaj Dev-cpp).
edytowany 1x, ostatnio: msm
- Rejestracja:ponad 12 lat
- Ostatnio:około 10 lat
0
#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=4;
int a[n]={1,4,2,7};
int w=najwieksza(n,a);
printf ("%d",w);
getche ();
return 0;
}
cały kod co jest jeszcze nie tak ?
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
0
Nadal, to co było to zostało, niczego nie zmieniłeś.
@msm - dla tego pytającego nie wystarczy wskazać błąd, on akceptuje wyłącznie gotowce.
- Rejestracja:ponad 12 lat
- Ostatnio:około 10 lat
0
#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-1,t);
}
}
}
int main(void){
int const n=4;
int a[n]={1,4,2,7};
int w=najwieksza(n,a);
printf ("%d",w);
getche ();
return 0;
}
teraz mam zwracany pierwszy element ,nadal ten sam błąd?
1
teraz mam zwracany pierwszy element ,nadal ten sam błąd?
D-O-K-Ł-A-D-N-I-E P-R-Z-E-C-Z-Y-T-A-J P-O-S-T: http://4programmers.net/Forum/C_i_C++/209708-funkcja_rekurencyjna_c?p=914595#id914595