ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1079. Maximum

Please explain me why my recursive function return 26589 for n=1 (Pascal)
Posted by IlushaMax 2 Apr 2016 14:59
I know that my algorithm exactly correct but only mathematically but not in program

var n1:longword;
function max(n:longword):word;
begin
max:=max+(n mod 2);
if (n<>1) then
if n mod 2=0 then
max(n div 2)
else
begin
max(n div 2);
max((n div 2)+1);
end;
end;

begin
writeln(max(n1));
end.

Maybe I do not fully understand how do recursive functions operate.

Edited by author 02.04.2016 15:07
Re: Please explain me why my recursive function return 26589 for n=1 (Pascal)
Posted by Jane Soboleva (SumNU) 2 Apr 2016 15:33
If you change word to longint, it returns even more~
Even if you leave just
function max(n:longword):word;
begin
max:=max+(n mod 2);
end;
, it will return an enormous number. Because, you see, in this very first row, you try to assign the function its own value (plus something). But it might be initialized in its own mysterious ways. So it's not how you do it.

So uh... i solved this one long ago without any recursion, and i'm not quite sure what you're trying to do, but i modified it a bit, so at least it's trying to make some sense (even though it returns the wrong result still; but it's not that bad anymore, and maybe you'll be able to fix it into a proper version). So there you go.

function max(n:longint):longint;
var funcRes: longint;
begin
funcRes:=(n mod 2);
if (n <> 1) then
if n mod 2 = 0 then inc(funcRes, max(n div 2))
else begin
inc(funcRes, max(n div 2));
inc(funcRes, max((n div 2)+1));
end;
max:=funcRes;
end;
Re: Please explain me why my recursive function return 26589 for n=1 (Pascal)
Posted by IlushaMax 2 Apr 2016 16:45
Thank you very much. I understood
Re: Please explain me why my recursive function return 26589 for n=1 (Pascal)
Posted by Jane Soboleva (SumNU) 2 Apr 2016 17:16
No problem. If you want to use recursion for calculations, maybe i'd suggest something like this:

var i, n1, r1, maximum: longint;
function x(p: longint): longint;
begin
if p <= 1 then x:=p else
if p mod 2 = 0 then x:=x(p div 2)
else x:=x(p div 2) + x(p div 2 + 1);
end;
begin
maximum:=0;
for i:=0 to n1 do begin
r1:=x(i);
if maximum < r1 then maximum:=r1;
end;
writeln(maximum);
end.

But i think it's kinda slower than if you'd just precalculated the array, and then precalculated another array for maximums.
It was quite likely harder back in the days, with 64kb turbo pascal limitations and all, so maybe you'd have to use smarter ways, rather than those blunt ones nowadays~
Re: Please explain me why my recursive function return 26589 for n=1 (Pascal)
Posted by IlushaMax 2 Apr 2016 20:33
I meant I understood that  I've used wrong way to get maximum. By the way I accidentally started to write a program that prints out the number from this sequence. And namely this way I think would be good to solve it. I was interested to write such a program and that's what I got:
var n:longword; r:word;

procedure max(n1,n2:word; var res:word);
begin
if n1 and (n1-1)=0 then inc(res) else
if n1=3 then inc(res,2) else
if n1 mod 2=0 then max(n1 div 2,0,res) else max(n1 div 2, (n1 div 2)+1,res);
if n2<>0 then
if n2 and (n2-1)=0 then inc(res) else
if n2=3 then inc(res,2) else
if n2 mod 2=0 then max(n2 div 2,0,res) else max(n2 div 2, (n2 div 2)+1,res);

end;

begin
if n=1 then writeln(1) else
if n and (n-1)=0 then writeln(1) else
if n mod 2=0 then begin max(n div 2,0,r); writeln(r); end else
begin
max(n div 2, (n div 2)+1,r);
writeln(r);
end;