Lcm with recursion
Solved/Closed
AMOULA_info
Posted messages
3
Status
Member
-
lido -
lido -
Bonjour,
Hello everyone
I would like to know how to calculate the lcm(a,b) using the recursive method in Pascal without adding another parameter to the function header, knowing that I know the iterative method with two ways:
1st method:
function lcm(a,b: integer):integer;
var i :integer;
begin
i:=1;
if a*b = 0 then lcm :=0 else
begin
while a*i mod b <> 0 do
i:=i+1;
lcm:=a*i;
end;
end;
2nd method:
function lcm(a,b: integer):integer;
var max,min :integer;
begin
if a*b = 0 then lcm :=0 else
begin
if a>b then begin max :=a; min:=b ; end
else begin max :=b; min :=a; end;
while max mod min <> 0 do
max := max +(a+b-min);
lcm:=max;
end;
end;
Thank you for your help
Hello everyone
I would like to know how to calculate the lcm(a,b) using the recursive method in Pascal without adding another parameter to the function header, knowing that I know the iterative method with two ways:
1st method:
function lcm(a,b: integer):integer;
var i :integer;
begin
i:=1;
if a*b = 0 then lcm :=0 else
begin
while a*i mod b <> 0 do
i:=i+1;
lcm:=a*i;
end;
end;
2nd method:
function lcm(a,b: integer):integer;
var max,min :integer;
begin
if a*b = 0 then lcm :=0 else
begin
if a>b then begin max :=a; min:=b ; end
else begin max :=b; min :=a; end;
while max mod min <> 0 do
max := max +(a+b-min);
lcm:=max;
end;
end;
Thank you for your help
Configuration: Windows XP Internet Explorer 6.0
9 answers
-
I present to you the complete solution of the entire program that calculates the LCM (Least Common Multiple) of two integers a and b using the recursive method while respecting the constraints for inputting a and b:
program lcm_rec;
uses wincrt;
var
a,b:word;
procedure input(var a,b:word);
begin
repeat
writeln('enter a: ');
readln(a);
writeln('enter b: ');
readln(b);
until ((a>b) and (a>0));
end;
function lcm(a,b:word): longint;
var
r:integer;
begin
if (b = 0) then
lcm := 0
else if (a mod b = 0) then
lcm := a
else
begin
r:=a mod b;
lcm:=( a div r)* lcm(b,r);
end;
end;
begin
input(a,b);
writeln('the lcm of ',a,' and ',b,' is ',lcm(a,b));
end. -
Thank you all, I found the solution myself!!!
function lcm(a,b:integer) : integer;
var r : integer;
begin
if a mod b = 0 then lcm := a
else
begin
r:=a mod b;
lcm:=( a div r)* lcm(b,r);
end;
end;-
Hello
with all my respect for your point of view, regarding this solution (it's a good solution); but it lacks the division by zero test :) that is to say if the second parameter is equal to zero then the solution is incorrect (run time error) :) . okay?- Thank you for your interest and especially for your politeness, but it is enough to add another test at the beginning to solve this problem.
function ppcm(a,b:integer) : integer;
var r : integer;
begin
if b = 0 then ppcm := 0
else if a mod b = 0 then ppcm := a
else
begin
r:=a mod b;
ppcm:=( a div r)* ppcm(b,r);
end;
end;
my real problem was with parameters making the new call to the function.
and here is how I found the solution.
ppcm(a,b)* pgcd(a,b) = a*b {mathematical theorem}
hence pgcd(a,b ) = (a*b) / ppcm(a,b)
and since pgcd(a,b) = pgcd(b,r) {with r = a mod b} and pgcd (b,r) = (b*r)/ ppcm(b,r) {} according to the previous theorem}
we can conclude that (a*b) / ppcm(a,b) = (b*r) / ppcm(b,r) hence ppcm(a,b) =( (a*b)/ (b*r))*ppcm(b,r)
= (a div r )*ppcm(b,r)
I hope I was clear enough
-
-
-
Function ppcmRec1 (a,b,i :integer):integer;
begin
if a * b = 0 then
ppcmR := 0
else
if a * i mod b = 0 then
ppcmR := a * i
else
ppcmR := ppcmRec1(a,b,i+1);
End;
Call X :=ppcmRec1(a,b,1) -
Hi Ouhiby,
for the recursive function ppcmrec2, I think (and I've tested it actually) that it is incorrect. -
-
-
Astonishing the number of algorithms proposed that assume a >= b ;)
Test them with lcm(1, 53), or even lcm(0, 22) ;)) -
```pascal Function lcm (a,b:integer):integer;
begin
if a=b then lcm:=a
else if a>b
then lcm:=(lcm(a-b,b)*a) div (a-b)
else lcm:=(lcm(a,b-a)*b) div (b-a);
end; ``` -
Sorry, I made some call errors :)
Here is the complete solution InShaAllah
Program testppcm ;
uses wincrt;
function ppcm1(a,b: integer):integer;
var i :integer;
begin
i:=1;
if a*b = 0 then
ppcm1 :=0
else
begin
while a*i mod b <> 0 do
i:=i+1;
ppcm1:=a*i;
end;
end;
Function ppcmRec1 (a,b,i :integer):integer;
begin
if a * b = 0 then
ppcmRec1 := 0
else
if a * i mod b = 0 then
ppcmRec1 := a * i
else
ppcmRec1 := ppcmRec1(a,b,i+1);
End;
function ppcm2(a,b: integer):integer;
var max,min :integer;
begin
if a*b = 0 then
ppcm2 :=0
else
begin
if a>b then
begin
max :=a;
min:=b ;
end
else
begin
max :=b;
min :=a;
end;
while max mod min <> 0 do
max := max +(a+b-min);
ppcm2:=max;
end;
end;
function ppcmRec2(a,b: integer):integer;
Var
max,min : integer;
Begin
if a*b = 0 then
ppcmRec2 :=0
else
begin
if a>b then
begin
max :=a;
min:=b ;
end
else
begin
max :=b;
min :=a;
end;
if max mod min = 0 then
ppcmRec2:=max
else
ppcmRec2 := ppcmRec2(max +(a+b-min),b);
end;
End;
Begin
{example of call}
Writeln(ppcm1(15,3));
Writeln(ppcmRec1(3,15,1));
Writeln(ppcm2(4,12));
Writeln(ppcmRec2(23,42));
{
Result :
15
15
12
84
}
End.