matlab - matlab中的扩展算法实现

Question

我发现了以下扩展欧几里得算法的伪代码

我实现了以下算法

    function [x1,y1,d1]=extend_eucledian(a,b)
            if b==0
                x1=1;
                y1=0;
                d1=a;
                return;
            end

            [x1,y1,d1]=extend_eucledian(b,mod(a,b));


 x1=y1;
y1=x1-floor(a/b)*y1;
d1=d1;

        end

当我运行这个程序时，我得到了以下结果

[x1,y1,d1]=extend_eucledian(23,20)

x1 =

     0


y1 =

     0


d1 =

     1

我猜 [x1,y1,d1] 在迭代过程中没有改变它们的值，例如，我尝试过以下代码

    function [x1,y1,d1]=extend_eucledian(a,b)
            if b==0
                x1=1;
                y1=0;
                d1=a;
                return;
            else
                 x1=y1;
y1=x1-floor(a/b)*y1;
d1=d1;
            end

            [x1,y1,d1]=extend_eucledian(b,mod(a,b));



        end

但是我得到了

>> [x1,y1,d1]=extend_eucledian(23,20)
Undefined function or variable 'y1'.

Error in extend_eucledian (line 8)
                 x1=y1;

我该如何解决这个问题？我哪里出错了？

Answer 1

可以通过引入中间工作变量来解决这个问题，该变量将存储递归调用的结果:

function [x,y,d]=extended_euclid(a,b)
    if b==0
        x=1;
        y=0;
        d=a;
        return;
    end
    [x1,y1,d1]=extended_euclid(b,mod(a,b));  

    x=y1;
    y=x1-floor(a/b)*y1;
    d=d1;

end 

此函数按预期工作:

>> [x, y, d] = extended_euclid(23,20)

x =    
     7

y =    
    -8

d =    
     1


>> [x, y, d] = extended_euclid(25,20)

x =    
     1    

y =    
    -1    

d =    
     5