• 设计扩展欧几里德算法的程序描述

    PHP描述
    服务器君一共花费 26.171 ms 进行了 5 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    接前面一小节 扩展欧几里德算法的推导

    前面提到了扩展欧几里德算法的证明和推导,对于这些定理,我们主要关心的是它的应用,是吧。定理用不着,价值就很难体现。扩展欧几里得算法的用途非常广,比如RSA加密算法中求私钥d。

    这里我们要用程序来感受扩展欧几里德算法。还是前面小节的问题:已知等式 47x + 30y = 1; 求x,y的整数解。

    设扩展欧几里德算法为gcdEx(a,b,x,y) 其中a,b为已知,x,y为所求。那么gcdEx(a,b,x,y)函数就有如下的计算过程:

    解释一下这个过程:

    1. 左边是利用朴素欧几里德算法相除得到一系列中间值,gcdEx(47,30,x,y),a = 47,b = 30,所以 gcd(47, 30) = gcd(b, a%b) = gcd(30, 17),直到b=0。

    2. 当b=0时,可以得知x=1,y=0,当知道这两个值的时候,就可以开始根据扩展欧几里德算法倒推了。还记得那个定理吗?这里再说一次:

    x1 = y2
    y1 = x2 - (int)(a/b) * y2
    

    3. 往上一步的x,y看作x1,y1,下面“旧”的x,y看作x2,y2,利用朴素欧几里德算法推导出的结论,x1=y2,y1=x2-(a/b)*y2。其中a,b就是当前gcdEx中的a,b.当这样递归回去到了第一个调用点时,所得到的x,y就是结果,即x=-7,y=11;

    理解了吧?下面我们用程序验证一下。网上一大把其它语言的实现,就是没PHP的,这里就PHP实现一下吧:

    <?php
    $a = 47;
    $b = 30;
    $x;
    $y;
    $re = exgcd($a, $b, $x, $y);
    
    function exgcd($a, $b, &$x, &$y)
    {
    	if($b == 0)
        {
            $x = 1;
            $y = 0;
            return $a;
        }
    	echo 'exgcd() paras $b ='.$b.', $a%$b = '.$a%$b.', $x = '.$x.', $y = '.$y.'<br />';
    	$r = exgcd($b, $a%$b, $x, $y);
    	echo '--exgcd() paras $b ='.$b.', $a%$b = '.$a%$b.', $x = '.$x.', $y = '.$y.'<br />';
    	$t = $x;
    	$x = $y;
    	$y = $t - floor($a/$b)*$y;
    	return $r;
    }
    
    echo '$x = '.$x;
    echo "<br />";
    echo '$y = '.$y;
    echo "<br />";
    
    ?>
    

    程序运行结果:

    exgcd() paras $b =30, $a%$b = 17, $x = , $y = 
    exgcd() paras $b =17, $a%$b = 13, $x = , $y = 
    exgcd() paras $b =13, $a%$b = 4, $x = , $y = 
    exgcd() paras $b =4, $a%$b = 1, $x = , $y = 
    exgcd() paras $b =1, $a%$b = 0, $x = , $y = 
    --exgcd() paras $b =1, $a%$b = 0, $x = 1, $y = 0
    --exgcd() paras $b =4, $a%$b = 1, $x = 0, $y = 1
    --exgcd() paras $b =13, $a%$b = 4, $x = 1, $y = -3
    --exgcd() paras $b =17, $a%$b = 13, $x = -3, $y = 4
    --exgcd() paras $b =30, $a%$b = 17, $x = 4, $y = -7
    $x = -7
    $y = 11
    

    扩展欧几里得算法就是不断地的将b放小,直至b等于0,最后反推求回x和y。前面不断的递归求解一定会有个时候 b=0,所以递归可以结束。结束之后再利用定理反推。

    如果还不清楚,对着程序执行结果和图再仔细想想。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [软件工程与项目管理] 浏览器的HTML解析器 8 个条目
  2. [计算机算法] 从双端队列引出的卡特兰数 3 个条目
  3. [移动开发] Android加载器Loaders 5 个条目
  4. [移动开发] 简单了解Android Fragment 3 个条目
  5. [Python程序设计] 写几个简单的Tornado程序吧 5 个条目
  6. [软件工程与项目管理] 开始了解Git 5 个条目
  7. [PHP程序设计] PHP数组探索 4 个条目
  8. [软件工程与项目管理] 呈现器的布局与绘制 11 个条目
  9. [移动开发] 使用support-v7 ActionBar前的那些坑 3 个条目
  10. [数据库技术] MySQL中英文混合排序 4 个条目
  11. [Python程序设计] Tornado源码解析 23 个条目
  12. [软件工程与项目管理] 浏览器的CSS解析 7 个条目
窗口 -- [协会]