算法扩展递归

‘壹’ 算法除了递归还有什么

算法的分类分为七类，分别是：

1、基本算法 : 包括枚举和搜索两种，分为深度优先搜索，广度优先搜索，启发式搜索和遗传算法；

2、数据结构的算法数论；

3、代数算法；

4、计算几何的算法，求凸包；

5、图论算法：包括哈夫曼编码，树的遍历，最短路径算法，最小生成树算法，最小树形图，网络流算法和匹配算法 ；

6、动态规划；

7、其他算法：包括数值分析，加密算法，排序算法，检索算法和随机化算法。

‘贰’ 递归算法一般用什么实现

递归算法一般用递归函数实现，依靠系统栈完成递归的返回计算。

‘叁’ 扩展欧几里德算法的扩展算法

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在无数组整
数对 x，y ，使得 gcd（a，b）=ax+by。
c++语言实现 intexgcd(lla,llb,ll&x,ll&y){if(a==0){x=0;y=1;returnb;}else{lltx,ty;lld=exgcd(b%a,a,tx,ty);x=ty-(b/a)*tx;y=tx;returnd;}}求解 x，y的方法的理解
设 a>b。
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
2，a>b>0 时
设 ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b);
则:ax1+ by1= bx2+ (a mod b)y2;
即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;
也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);
根据恒等定理得：x1=y2; y1=x2- [a / b] *y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
扩展欧几里德算法
扩展欧几里德算法是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使用C++的实现： intexGcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=exGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnr;}把这个实现和Gcd的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。
可以这样思考:
对于a'=b,b'=a%b 而言，我们求得 x, y使得 a'x+b'y=Gcd(a',b')
由于b'=a%b=a-a/b*b (注：这里的/是程序设计语言中的除法)
那么可以得到:
a'x+b'y=Gcd(a',b') ===>
bx+(a - a / b * b)y = Gcd(a', b') = Gcd(a, b) ===>
ay +b(x - a / b*y) = Gcd(a, b)
因此对于a和b而言，他们的相对应的p，q分别是 y和(x-a/b*y)
使用扩展欧几里德算法解决不定方程的办法
对于不定整数方程pa+qb=c，若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。
上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，p * a+q * b = Gcd(a, b)的其他整数解满足：
p = p0 + b/Gcd(a, b) * t
q = q0 - a/Gcd(a, b) * t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可，但是所得解并不是该方程的所有解，找其所有解的方法如下：
在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，可以
得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p * a+q * b = c的其他整数解满足：
p = p1 + b/Gcd(a, b) * t
q = q1 - a/Gcd(a, b) * t(其中t为任意整数)
p 、q就是p * a+q * b = c的所有整数解。
编程时 exgcd 更多用于求解“中国剩余定理”相关知识 举个例子比如n除以5余2 除以13余3 那么n最小是多少，所有的n满足什么条件？
n（min)=42
n=42+k*65
欧几里德算法的扩展
扩展欧几里德算法不但能计算(a，b)的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下： intgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;if(0==a)//有一个数为0,就不存在乘法逆元{ar=0;br=0;returnb;}if(0==b){ar=0;br=0;returna;}x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;intnk;for(t3=x3%y3;t3!=0;t3=x3%y3){k=x3/y3;t2=x2-k*y2;t1=x1-k*y1;x1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3;}if(y3==1)//有乘法逆元{ar=(y2+b)%b;//对求出来负的乘法逆元进行处理，使之在模b的完全剩余集里br=(y1+a)%a;//原来这里是错的return1;}else//公约数不为1,无乘法逆元{ar=0;br=0;returny3;}}扩展欧几里德算法对于最大公约数的计算和普通欧几里德算法是一致的。计算乘法逆元则显得很难明白。我想了半个小时才想出证明他的方法。
首先重复操作整除中的一个论断：
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数(t1，t2，t3)，用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假设前k行都成立，考察第k+1行
对于k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分别满足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根据扩展欧几里德算法，假设t3(k-1) = j t3(k) + r
则：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
则
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得证
因此，当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。

‘肆’ 求算法设计：基本递归算法一

递归算法 就是函数或过程的自我调用，算法精炼，但较为抽象。
由于是自我调用，但一定要保证逐步简化，最终能结束退出，否则会造成堆栈溢出。

‘伍’ 算法设计的基本方法里面的“递归”是什么意思

递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰.。 递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的，每次增加 1，直至达到要计算其阶乘的那个数。下面的段落是用文字定义的计算阶乘的一个函数。“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。”要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。这就是一个递归示例。递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理） ，并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。很明显，这样永远也不会到达一个终止点。因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。下面仍然是阶乘函数，这次是用 JScript 代码编写的。 // 计算阶乘的函数。如果传递了// 无效的数值（例如小于零），// 将返回 -1，表明发生了错误。若数值有效，// 把数值转换为最相近的整数，并// 返回阶乘。function factorial(aNumber) {aNumber = Math.floor(aNumber); // 如果这个数不是一个整数，则向下舍入。if (aNumber < 0) { // 如果这个数小于 0，拒绝接收。 return -1; } if (aNumber == 0) { // 如果为 0，则其阶乘为 1。 return 1; } else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。}

‘陆’ 递归算法怎么做

递归就是函数方法的自我调用。
不是什么问题都可以用递归算法的， 要看具体问题是否适合用递归方法解决。

‘柒’ 《算法设计与分析》中递归的概念是什么 谢谢大家。。

自己调用自己，调到底部再，层层返回，不推荐使用，比较耗时间。

‘捌’ 请教高人 递归算法编写思路技巧

一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
利用递归算法解题，首先要对问题的以下三个方面进行分析：
一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。
二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。
三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。
把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：
if 边界条件 1 成立 then
赋予边界值 1
【 elseif 边界条件 2 成立 then
赋予边界值 2
┇ 】
else
调用解决问题的通式
endif
例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。
分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很容易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下来按照上面介绍的一般格式定义递归子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；
(2) 盘子只许在三根针上存放；
(3) 永远不许大盘压小盘。
梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。
要求设计一个程序输出盘子的移动过程。
分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。
当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：
(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；
(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；
(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很容易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。
这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
参考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 递归子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

‘玖’ 递归算法的实现

如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
递归的一般模式
procere aaa(k:integer);
begin
if k=1 then (边界条件及必要操作)
else begin
aaa(k-1);
(重复的操作);
end;
end;
C#:例子
例：一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少。
public class MainClass{public static void Main(){Console.WriteLine(Foo(30));}public static int Foo(int i){if (i <= 0)return 0;else if(i > 0 && i <= 2)return 1;else return Foo(i -1) + Foo(i - 2);}}
又如:
procere a;
begin
.
.
.
a;
.
.
.
end;
这种方式是直接调用.
又如:
procere c(形参);forward;
procere b;
局部说明
begin
. .
c(实参);
. .
end;
procere c;
局部说明；
begin
. .
b;
. .
end;
这种方式是间接调用.
例1计算n!可用递归公式如下:
fac:=n*fac(n-1) {当n>0时}
fac(n)={
fac:=1; { 当n=0时}
可编写程序如下:
program facn;
var
n:integer;
function fac(n:integer):real;
begin
if n=0
then fac:=1
else fac:=n*fac(n-1);
end;
begin
write('n=');readln(n);
writeln(n,'!=',fac(n):0:0);
end. JavaScript:例子//递归算法//递归算法functionrecursionAlgorithm(num){ if(num<=1)//判断如果num小于等于1的情况下，返回本身 { return1; }else { returnnum*arguments.callee(num-1);//调用函数本身进行返回 }}

‘拾’ 关于递归算法

你输入了三次，所以递归有三层，最外面一层是 a = A,程序停止在if(a!= '#') printf();
中间的一层是 a = B,程序同样停止在if(a!= '#') printf(); 最里面的一层，也就是你输入a = #,
程序在判断完两个if后返回到上一层，if(a! ='#') printf("%c\n",a); 输出 B ，然后再返回上一层输出 A