方程ax+by=c整数解的应用 例1:有三个分别装有a升水、b升水和c升水的量筒(gcd(a,b)=1,c>b>a>0),现c筒装满水,
问能否在c筒个量出d升水(c>d>0)。若能,请列出一种方案。
算法分析:
量水过程实际上就是倒来倒去,每次倒的时候总有如下几个持点:
1.总有一个筒中的水没有变动;
2.不是一个筒被倒满就是另一个筒被倒光;
3.c筒仅起中转作用,而本身容积除了必须足够装下a简和b简的全部水外,别无其
它限制。 程序如下: program mw;
type
node=array[0..1] of longint;
var
a,b,c:node;
d,step,x,y:longint;
function exgcd(a,b:longint;var x,y:longint):longint;
var t:longint;
begin
if b=0 then
begin
exgcd:=a;;x:=1;y:=0;
end
else
begin
exgcd:=exgcd(b,a mod b,x,y);
t:=x;x:=y;y:=t-(a div b)*y
end;
end;
procedure equation(a,b,c:longint;var x0,y0:longint);
var d,x,y:longint;
begin
d:=exgcd(a,b,x,y);
if c mod d>0 then
begin
writeln('no answer');
halt;
end else
begin
x0:=x*(c div d);
y0:=y*(c div d);
end;
end;
procedure fill(var a,b:node);
var t:longint;
begin
if a[1]<b[0]-b[1] then t:=a[1]
else t:=b[0]-b[1];
a[1]:=a[1]-t;
b[1]:=b[1]+t
end;
begin
write('a,b,c,d=');
readln(a[0],b[0],c[0],d);
equation(a[0],b[0],d,x,y);
step:=0;
a[1]:=0;b[1]:=0;c[1]:=c[0];
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
if x>0 then
repeat
if a[1]=0 then fill(c,a) else
if b[1]=b[0] then fill(b,c) else fill(a,b);
inc(step);
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
until c[1]=d
else
repeat
if b[1]=0 then fill(c,b) else
if a[1]=a[0] then fill(a,c) else fill(b,a);
inc(step);
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
until c[1]=d;
end.
|