Jaki to język i o co w tym programie chodzi

[robcioo16 0]

Witam

Niedawno przeglądałem matury z informatyki z tego roku (2011);

zainteresowało mnie zadanie 1 z poziomu rozszerzonego.

Czy mógłby mi ktoś przetłumaczyć ten język na Pascala(bo na razie tylko go umiem)i wytłumaczyć to, bo rekurencje miałem tak na szybko przez jedną lekcje, i za bardzo jej nie pojmuję.

 

http://imageshack.us/photo/my-images/857/rekurencja.png/

program ma być napisany rekurencyjnie.

[Lukaszbass 116]

Witam,jezyka programowania nikt ci tutaj nie wytlumaczy,musisz sam sie go nauczyc tak jak tabliczki mnozenia.

[robcioo16 0]

To wiem, ale co najmniej wytłumaczyć ten program.

[Gość DANNY_79]

Podeślij fragment kodu.

[GreQonE 3546]

99% ze jest to C++.

Ale tam nie ma nic do tlumaczenia, toz to proste jak konstrukcja cepa jest.

[Malwin 16]

Rekurencje to ty powinieneś znać z matematyki. Przykładem jest rekurencyjne definiowanie wyrazu ciągu. a_n=2*a_n-1 i a₀=1.

 

Zapewne chodzi o zadanie :

 

Opisana poniżej funkcja rekurencyjna wyznacza, dla liczby naturalnej , długość napisu

uzyskanego przez sklejenie binarnych reprezentacji liczb naturalnych od 1 do n-1 .

 

Funkcja sklej (n)

krok 1. jeśli n =1, to podaj 0 jako wynik i zakończ działanie

krok 2. jeśli n parzysta, to wynikiem jest n -1+ 2* sklej (n / 2)

krok 3. jeśli n nieparzysta, to wynikiem jest n -1+ sklej ((n -1) / 2) + sklej ((n +1)/ 2)

 

W C taka funkcja może wyglądać następująco :

 

int sklej( int n )
{
	if ( n == 1 )
		return 0;
	if ( n % 2 )
		return ( n - 1 + sklej( ( n - 1 ) / 2 ) + sklej( ( n + 1 ) / 2 ) );

	else
		return ( n - 1 + 2 * sklej( n / 2) );	
}

Edytowane 3 Czerwca 2011 przez Malwin

[GreQonE 3546]

Pozwol, ze to zobrazuje:

 

http://mebelki.zoni.pl/dni/2010/01/05/Rekurencja.jpg

[Malwin 16]

"Żeby zrozumieć rekurencję musisz najpierw zrozumieć rekurencję."

[robcioo16 0]

napisałem to w Pascalu ale coś mi nie pasi?

 

program abc;
uses Crt;
var
i:integer;
        
        function ciag(n:real):real;
        begin
        ciag:=n-1+2*ciag(n/2);
        end;

        function ciag2(n:real):real;
        begin
        if n=1 then
        ciag2:=0
        else ciag2:=n-1+ciag2((n-1)/2)+ciag2((n+1)/2);
        end;

        procedure daj;
        begin
        if (i mod 2)=0 then writeln(ciag(i):0:0)
        else writeln(ciag2(i):0:0);
        end;


begin
clrscr;
writeln('podaj n');
readln(i);
clrscr;
daj;
readln;
end.

ciągle tylko error 202. JAk to poprawić?

[Malwin 16]

Bardzo prosty błąd zrób jedną funkcję i w niej sprawdzaj czy i=1 czy i mod 2 jest 0 czy 1 i decyduj czy zwracać konkretną wartość (w przepadku i=1) czy zagłębiać się w rekurencje gdy n>1 . Twój błąd polega na tym, że jak procedura daj przy i=7 wybierze funkcje ciag2 to dalsze rekurencyjne wywołania odbywają się również w oparciu o ciag2. Przeanalizuj co powinno się dziać gdy i=7. Wywołujesz daj. Daj wywoluje ciag2(7). ciag2(7) wywoluje ciag2((n-1)/2) czyli ciag2(3) czyli oki ale dalej wywoła tez ciag2((n+1)/2) czyli ciag2(4), a jak widać tutaj i=4 jest parzyste czyli powinno byc wywolanie ciag(4) a nie ciag2(4) . To jest jeden błąd . Drugi zapewne to przepełnienie stosu. Bo gdy trafisz do funkcji ciag nie ma tam warunku stopu. Ciagle wykonywana jest niekonczaca się rekurencja.

 

Tak jak mówię przepisz to w jedną funkcje tak jak ja to zrobiłem w C.

[robcioo16 0]

dorze zmodyfikowałem troche program

program sklej_rec;
var
x:integer;

          function sklej(n:real):real;
          begin
          if n=1 then sklej:=0;
          if (trunc(n) mod 2)=0 then sklej:=n-1+2*sklej(n/2)
          else  sklej:=n-1+sklej((n-1)/2)+sklej((n+1)/2);
          end;

begin
writeln('podaj liczbe');
readln(x);
writeln(sklej(x));

end.

Ale ciągle wyskakuje mi błąd

 

 

trochę pomyślałem i wychodzi mi tym razem tylko na parzyste

 

program sklej_rec;
var
x:integer;

          function sklej(n:real):real;
          begin
          if n=1 then sklej:=0
          else sklej:=n-1+2*sklej(n/2)
          end;

begin
writeln('podaj liczbe');
readln(x);
writeln(sklej(x):0:0);

end.

Edytowane 6 Czerwca 2011 przez robcioo16