View original (French)

Lcm with recursion

Solved/Closed
AMOULA_info Posted messages 3 Status Membre -  
 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
Configuration: Windows XP Internet Explorer 6.0

9 réponses

Réponse 1 / 9
Anonymous user
 
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.
8
rouna10
 
```html function ppcm(a,b:word): longint;

var
r:integer;

begin
if (b = 0) then
ppcm := 0
else if (a mod b = 0) then
ppcm := a
else
ppcm:=( a div (a mod b))* ppcm(a,a mod b);
end; ```
0
rouna10
 
If you run your program with integers a and b (for example a=23 and b=5) you found a false result.
You need to replace "ppcm:=( a div r)* ppcm(b,r);" with "ppcm:=( a div r)* ppcm(a,r);"
0
rouna10
 
```html

Write this same algorithm without using any function or procedure.

```
0
Sahar
 
Thank you
0
lido
 
this result is wrong... it is necessary to replace ppcm:=(a div r)*ppcm(b,r); with ppcm:=ppcm(b,r)*(a div r); and it is not the same thing.
0
Réponse 2 / 9
AMOULA_info Posted messages 3 Status Membre 9
 
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;
1
dali
 
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?
0
amoula_info > dali
 
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
0
3loulou > amoula_info
 
THANK YOU FOR YOUR HELP
0
fenni
 
Here is an optimal solution:

Function ppcm (a, b, r : integer) : integer;
begin
if (r mod b)=0
then ppcm := r
else ppcm := ppcm (a, b, r+a) ;
end;
The call will be: Writeln ('PPCM = ', ppcm(a,b,a));
0
Réponse 3 / 9
Ouhiby
 
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)
1
Réponse 4 / 9
amoula_info
 
Hi Ouhiby,
for the recursive function ppcmrec2, I think (and I've tested it actually) that it is incorrect.
1
Ouhiby
 
Oh yes, I couldn't correct it!!!
What do you think?
0
Réponse 5 / 9
lkj
 
I found several solutions
but which one is the most accurate
please
very urgent!!!!!!!!!!!
1
rouna10
 
```pascal function ppcm(a,b:word): longint;

var
r:integer;

begin
if (b = 0) then
ppcm := 0
else if (a mod b = 0) then
ppcm := a
else
ppcm:=( a div (a mod b))* ppcm(a,a mod b);
end;

{ it is the most just } ```
0
Réponse 6 / 9
rihab chebbah
 
Désolé, je ne peux pas vous aider.
1
Réponse 7 / 9
Malebete
 
Astonishing the number of algorithms proposed that assume a >= b ;)

Test them with lcm(1, 53), or even lcm(0, 22) ;))
1
Réponse 8 / 9
Anonymous user
 
```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; ```
1
Réponse 9 / 9
Ouhiby
 
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.
0