递归法
C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。
许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。
这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。
我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系：
‘0’+ 0 =‘0’
‘0’+ 1 =‘1’
‘0’+ 2 =‘2’
...
从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。
这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。
我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。
这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。
在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。
/*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/
#include
int binary_to_ascii( unsigned int value)
{
unsigned int quotient;
quotient = value / 10;
if( quotient != 0)
binary_to_ascii( quotient);
putchar ( value % 10 + '0' );
}
递归是如何帮助我们以正确的顺序打印这些字符呢？下面是这个函数的工作流程。
1. 将参数值除以10
2. 如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字
3. 接着，打印步骤1中除法运算的余数
注意在第2个步骤中，我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。
一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。
但是，为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。
当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。
程序中的函数有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。
假定我们以4267这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示：
执行除法之后，堆栈的内容如下：
接着，if语句判断出quotient的值非零，所以对该函数执行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：
堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则他们是不能被访问的。再次执行除法运算之后，堆栈的内容如下：
quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的出发运算之后，堆栈的内容如下：
此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下：
不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行，所以它的效果类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。
现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。
每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0到9之间的整数。把它与字符常量‘0’相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。
输出4：
接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，她所使用的是自己的变量，他们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar 后打印出来的数字是2。
输出42：
接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下：
输出426：
现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字7，也就是它的value参数除10的余数。
输出4267：
然后，这个递归函数就彻底返回到其他函数调用它的地点。
如果你把打印出来的字符一个接一个排在一起，出现在打印机或屏幕上，你将看到正确的值：4267
汉诺塔问题递归算法分析：
一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。
1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第二个和尚），命令：
①你丫把前63个盘子移动到第二柱子上
②然后我自己把第64个盘子移动到第三个柱子上后
③你把前63个盘子移动到第三柱子上
2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，
再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第三和尚），命令：
①你把前62个盘子移动到第三柱子上
②然后我自己把第63个盘子移动到第二个柱子上后
③你把前62个盘子移动到第二柱子上
3、第三个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。
4、到此任务下交完成，到各司其职完成的时候了。完成回推了：
第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分配的第2个盘子。
第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。
从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚----第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。现在我们以有3个盘子来分析：
第1个和尚命令：
①第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）
②第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。
③第2个和尚你把前2个盘子从第二柱子移动到第三柱子。
很显然，第二步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）。其中第一步，第2个和尚他有2个盘子，他就命令：
①第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）
②第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。
③第3个和尚你把第1个盘子从第三柱子移动到第二柱子。
同样，第二步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）
第三步可以分解为，第2个和尚还是有2个盘子，命令：
①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。
②第2个和尚我把第2个盘子从第二柱子移动到第三柱子。
③第3个和尚你把第一柱子上的盘子移动到第三柱子。
分析组合起来就是：1→3 1→2 3→2借助第三个柱子移动到第二个柱子|1→3自私人留给自己的活| 2→1 2→3 1→3借助第一个柱子移动到第三个柱子|共需要七步。
如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5
个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n个盘子需要（2的n次方）-1步。
从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：
（1）把1座上（n-1）个盘子借助3座移到2座。
（2）把1座上第n个盘子移动3座。
（3）把2座上（n-1）个盘子借助1座移动3座。
下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。
很明显: (1)步上是hanoi(n-1,1,3,2)
(3)步上是hanoi(n-1,2,1,3)
用C语言表示出来，就是：
#include
int method(int n,char a, char b)
{
printf("number..%d..form..%c..to..%c.."n",n,a,b);
return 0;
}
int hanoi(int n,char a,char b,char c)
{
if( n==1 ) move (1,a,c);
else
{
hanoi(n-1,a,c,b);
move(n,a,c);
hanoi(n-1,b,a,c);
};
return 0;
}
int main()
{
i nt num;
scanf("%d",&num);
hanoi(num,'A','B','C');
return 0;
}
递归算法：递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法是算法设计中比较常用的一种算法，它的优点在于考虑问题的角度不再局限于过程，而是从整体的角度去思考问题。常见的递归实例有：阶乘，斐波那契数列，汉诺塔等等。下面我们分别用java语言来书写上述的三个例子：
阶乘：
importjava.io.*;
publicclass Factorial{
publicstatic void main(String[] args) throws IOException {
int n,m;
BufferedReader buf;
buf=new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入所求的阶乘数：");
n=Integer.parseInt(buf.readLine());
Factorial factorial=new Factorial();
m=factorial.multiply(n);
System.out.println(n+"的阶乘为："+m);
}
publicint multiply(int n){
//跳出递归条件
if(n==1||n==0){
return1;
}
else{
//子问题分解
returnn*multiply(n-1);
}
}
}
斐波那契数列
importjava.io.*;
publicclass Fibonacci{
publicstatic void main(String[] args) throws IOException {
int n;
BufferedReader buf;
buf=new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入需要输出的Fibonacci的个数：");
n=Integer.parseInt(buf.readLine());
Fibonaccifibonacci=new Fibonacci();
while(n==0){
System.out.print("您所输入的Fibonacci的个数为0，请重新输入！");
n=Integer.parseInt(buf.readLine());
}
for(inti=1;i<=n;i++){
System.out.print(fibonacci.fib(i)+"");
}
}
publicint fib(int n){
//特殊情况
if(n==0){
return0;
}
else{
//跳出递归条件
if(n==1||n==2){
return1;
}
else{
//子问题分解
returnfib(n-1)+fib(n-2);
}
}
}
}
汉诺塔：
importjava.io.*;
publicclass Hanoi{
publicstatic void main(String args[]) throws IOException{
int n;
BufferedReader buf;
buf=new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数");
n=Integer.parseInt(buf.readLine());
Hanoihanoi=new Hanoi();
hanoi.move(n,'A','B','C');
}
publicvoid move(int n,char a,char b,char c){
//跳出递归条件
if(n==1){
System.out.println("盘"+n+"由"+a+" 移至"+c);
}
else{
//子问题分解
move(n-1,a,c,b);
System.out.println("盘"+n+"由"+a+" 移至"+c);
//子问题分解
move(n-1,b,a,c);
}
}
}
从上述代码中我们可以总结出，递归使用的一般规律:
1、问题可分解与原问题相似或相近的子问题。
例如：
n的阶乘可以看做是n乘以n-1的阶乘
斐波那契数列的第n个数是第n-1和n-2个数的和
如果要移动n个盘子的汉诺塔，可以看做是：先移动最上面n-1个汉诺塔和最下面盘子等等
总之，找出递归调用的分解是使用递归调用的关键一步
2、问题求解的时候有跳出或结束标志。
例如：
阶乘n的最后一步肯定是n=1
斐波那契数列的最后求和肯定是第一个数和第二个数
汉诺塔中盘子的个数为1的时候等等
注意：有时候在使用递归算法的时候会碰到一些特殊情况，这个时候读者可以根据需要特殊对待。
例如：斐波那契数列的定义规定F(0)=0,这个时候如果需要那么我们就不能用一般的递归来分解这时就需要特殊对待了。
递归习题
1、斐波那契数列 【问题描述】 斐波纳契数列0,1,1,2,3,5,8,13,21,34,55…从第三项起，每一项都是紧挨着的前两项的和。写出计算斐波那数列任意一个数据项的递归程序。 【输入格式】 所求项数 【输出格式】 数据项的值 【输入样例】 10 【输出样例】 34 2、倒序数 【问题描述】 用递归算法写程序，输入一个非负整数，输出这个数的倒序数。 【输入格式】 一个非负整数 【输出格式】 倒序结果 【输入样例】 123 【输出样例】 321 3、十进制转换成八进制数 【问题描述】 用递归算法，把任一给定的十进制数转换成八进制数输出。 【输入格式】 一个正整数，表示需要转换的十进制数。 【输出格式】 一个正整数，表示转换之后的八进制数。 【输入样例】 15 【输出样例】 17 4、求n!的值 【问题描述】 用递归算法，求n!的精确值（n以一般整数输入）。 【输入样例】 10 【输出样例】 10！=3628800
5、求最大公约数 【问题描述】 用递归方法求两个正整数m和n的最大公约数。（m>0,n>0） 【输入格式】 两个数，即m和n的值。 【输出格式】 最大公约数。 【输入样例】 8 6 【输出样例】 gcd=2 6、背包问题 【问题描述】 简单的背包问题，设有一个背包，可以放入的重量为s。现有n件物品，质量分布为w1，为，…，wn（1≤i≤n），均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找到一组解即可。 【输入格式】 第一行是物品总件数和背包的载重量，第二行为各物品的重量。 【输出格式】 各所选物品的序号和重量。 【输入样例】 5 10 1 2 3 4 5 【输出样例】 number：1 weight：1 number：4 weight：4 number：5 weight：5 7、2的幂次方 任何一个正整数都可以用2 的幂次方表示： 如137=2^7+2^3+2^0 同时约定用括号来表示次方即a^b可表示为a(b) 所以137可表示为 2(7)+2(3)+2(0) 进一步：7=2^2+2+2^0 (2^1用2 表示) 3=2+2^0 所以137可表示为:2(2(2)+2+2(0))+2(2+2(2(0))+2(0) 又如:1315=2^10+2^8+2^5+2+1 所以1315最后可表示为:2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 【输入格式】 正整数(n<=20000) 【输出格式】
递归与分治
分治算法 一、分治算法 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。 分治法解题的一般步骤： （1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。下面通过实例加以说明。 【例1】[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。 另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。
递归基础练习题
递归基础练习题 1. 求1+2+3+……+n的值 2. 求1*2*3*……*n的值 3. 数的全排列问题。将n个数字1，2，…n的所有排列按字典顺序枚举出来 2 3 1 2 1 3 3 1 2 3 2 1 4. 数的组合问题。从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。 如n=3,m=2时，输出： 1 2 1 3 2 3 9. 求两个数的最大公约数。 10. 求两个数的最小公倍数。 5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？ 8. 著名的菲波拉契(Fibonacci)数列，其第一项为1，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。 15. 梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。 6. 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 7. 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？ 11. 输入一个数，求这个数的各位数字之和。 12. 角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。 如：输入22， 输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 STEP=16 13. 将十进制转换为二进制。 14. 计算M＝max(a,b,c)/[max(a+b,b,c)*max(a,b,b+c)],其中a，b，c由键盘输入。 16. 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况? 17. 给出一棵二叉树的中序与后序排列。求出它的先序排列。 18. 求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。 19. 已知一个一维数组A[1..N]。{N<50} 又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。 20. 要求找出具有下列性质的数的个数(包含输入的自然数n)： 先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理: ①. 不作任何处理;
递归神经网络
递归神经网络概述 一、引言 人工神经网络的发展历史己有60多年，是采用物理可实现的系统模仿人脑神经细胞的结构和功能，是在神经生理学和神经解剖学的基础上，利用电子技术、光学技术等模拟生物神经网络的结构和功能原理而发展起来的一门新兴的边缘交叉学科，（下面简称为神经网络，NeuralNetwork）。这些学科相互结合，相互渗透和相互推动。神经网络是当前科学理论研究的主要“热点”之一，它的发展对目前和未来的科学技术的发展将有重要的影响。神经网络的主要特征是：大规模的并行处理、分布式的信息存储、良好的自适应性、自组织性、以及很强的学习能力、联想能力和容错能力。神经网络在处理自然语言理解、图像识别、智能机器人控制等方面具有独到的优势。与冯?诺依曼计算机相比，神经网络更加接近人脑的信息处理模式。 自从20世纪80年代，Hopfield首次提出了利用能量函数的概念来研究一类具有固定权值的神经网络的稳定性并付诸电路实现以来，关于这类具有固定权值 神经网络稳定性的定性研究得到大量的关注。由于神经网络的各种应用取决于神经网络的稳定特性，所以，关于神经网络的各种稳定性的定性研究就具有重要的理论和实际意义。递归神经网络具有较强的优化计算能力，是目前神经计算应用最为广泛的一类神经网络模型。 根据不同的划分标准，神经网络可划分成不同的种类。按连接方式来分主要有两种：前向神经网络和反馈（递归）神经网络。前向网络主要是函数映射，可用于模式识别和函数逼近。递归神经网络因为有反馈的存在，所以它是一个非线性动力系统，可用来实现联想记忆和求解优化等问题。由于神经网络的记亿信息都存储在连接权上，根据连接权的获取方式来划分，一般可分为有监督神经网络、无监督神经网络和固定权值神经网络。有监督学习是在网络训练往往要基于一定数量的训练样木。在学习和训练过程中，网络根据实际输出与期望输出的比较，进行连接权值和阂值的调节。通常称期望输出为教师信号，是评价学习的标准。最典型的有监督学习算法是BP（BackProPagation算法。对于无监督学习，无教师信号提供给网
递归基础练习题
dic递归基础练习题：小的 1. 求1+2+3+……+n的值 2. 求1*2*3*……*n的值 3. 数的全排列问题。将n个数字1，2，…n的所有排列按字典顺序枚举出猴 2 3 1 2 1 3 3 1 2 3 2 1 4. 数的组合问题。从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。 如n=3,m=2时，输出： 1 2 1 3 2 3 5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？ 6. 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 7. 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？ 8. 著名的菲波拉契(Fibonacci)数列，其第一项为0，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。 9. 求两个数的最大公约数。 10. 求两个数的最小公倍数。 11. 输入一个数，求这个数的各位数字之和。 12. 角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。 如：输入22， 输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 STEP=16 13. 将十进制转换为二进制。 14. 计算M＝max(a,b,c)/[max(a+b,b,c)*max(a,b,b+c)],其中a，b，c由键盘输入。 15. 梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。 16. 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况? 17. 给出一棵二叉树的中序与后序排列。求出它的先序排列。 18. 求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。 19. 已知一个一维数组A[1..N]。{N<50} 又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。 20. 要求找出具有下列性质的数的个数(包含输入的自然数n)： 先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理: ①. 不作任何处理;
c++整数拆分和以及递归划分
北京工商大学 计算机与信息工程学院 实验报告 课程：具体数学 专业：计算机应用技术 班级：2班 学号：10011314178
姓名：刘栋 实验整数划分问题 I）实验目的： 利用程序求一个正整数分解成连续自然数的和的形式。方法很多，介绍一种递进求和的形式，也就是普通所说的“滑动窗体模型”。顺便做下拓展，整数的全划分问题。 II）实验内容： ①实验平台和环境：C++ Builder 6.0.； ②实验步骤： i）分析问题 ii）代码：程序1滑动窗体 #include { int i=1,j=2,k; int sum=0; while(i<=N/2) { sum=windows(i,j); while(sum!=N) { if(sum>N) i++; else j++; sum=windows(i,j); } cout< 集合划分问题 实验目的：通过对集合划分问题的算法的设计，进一步熟悉理解并灵活运用递归与分治策略，掌握该算法思想的核心内容。 实验内容： 1）内容描述：n 个元素的集合{1,2,., n }可以划分为若干个非空子集。 例如，当n=4 时，集合{1，2， 3，4}可以划分为15 个不同的非空子 集 2）编程任务：给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。 3）数据输入： 由文件input.txt 提供输入数据。文件的第1 行是元素个数n 和非空 子集数m。 4）结果输出: 程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输 出到文件output.txt 中。 实验原理：假设将m个元素分解到n 个集合中，首先考虑将(m – (n - 1))个元素分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(n - 1)个集合中，然后再考虑将(m – (n - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(n - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。对于每种分配方法的集合个数的求法，可以先用排列组合的方法计算出元素选取的情况，在通过递归计算出选取该元素后所组成的集合的个数。各种分配情况的遍历可以利用一个for()循环来实现，算法源代码如下： 实验源代码： #include 递归树的生成与图示 函数调用自身的编程技术称为递归。递归算法只需少量的代码就可描述出解题过程所需要的多次重复计算，可以大大的减少代码量。 递归过程的理解往往比较困难，本文通过对汉诺塔问题，快速排序等典型递归算法的研究，试图找出递归调用树的生成方法，并给出形象展示调用树的算法，以深入理解递归过程。 关键词：递归算法，递归树，汉诺塔，快速排序 第一章递归算法与递归树的概念 1.1递归算法： 递归算法：在一个过程或函数直接或者间接的调用自己的算法。一个过程或函数在意定义或者说明中直接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，极大地减少了程序的代码量。递归的有点在于通过有限的语句来定义对象的无限集合。 构成递归需具备的条件： 1. 子问题须与原始问题调用同样的函数，且更为简单； 2. 不能无限制地调用本身，需要有个边界条件。 1.2递归树： 递归树：递归树其实就是二叉树，只是通过其来描述递归算法的递归调用过程。通过递归树，我们可以形象的展示出递归算法。 一般来说， 1、递归树的每一个结点为递归的一个数据。 2、递归树的每一个父节点都代表一次递归调用。 第二章递归的例子 2.1汉诺塔问题 Hanoi塔（汉诺塔）问题如下图2.1： 设X Y Z为三个塔座，开始时再塔座上有n个圆盘，他们自上而下由小到大的叠放着，编号依次为1,2,...,n，现在要求将塔座X上的这一叠圆盘移到塔座Z上，并按同样顺序叠放，在移动时要遵循以下规则： （1）每次只能移动一个圆盘； （2）任何时刻都不允许将较大的圆盘放在较小的圆盘之上； （3）在满足（1）（2）两个条件的情况下，可以将圆盘放在任意塔座上。 图2.1 算法： 1)当只有一个盘子的时候，只需要从将X塔上的一个盘子移到Z塔上。 2)当X塔上有两个盘子是，先将X塔上的1号盘子（编号从上到下）移动到Y塔上，再将X塔上的2号盘子移动的Z塔上，最后将Y塔上的小盘子移动到Z塔上。 dic递归基础练习题： 1.求1+2+3+……+n的值 int sum(int a,int b) { if(b==a) return a; return a+sum(a+1,b); } 2. 求1*2*3*……*n的值 cheng(int begin,int end) { if(begin==end) return begin; return begin * cheng(begin+1,end); } 3. 数的全排列问题。将n个数字1，2，…n的所有排列按字典顺序枚举出猴 2 3 1 2 1 3 3 1 2 3 2 1 4. 数的组合问题。从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。 如n=3,m=2时，输出： 1 2 1 3 2 3 5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？ fruit(int begin,int times) { if(times==10) return begin; return fruit((begin+1)*2,times+1); } 6. 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 7. 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？ duck(int begin,int times) { if(times==7) return begin; return duck((begin+1)*2,times+1); } 1、集合的划分(setsub) 【问题描述】 设S是一个具有n个元素的集合，S＝｛a1，a2，……，an｝，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk ，且满足： 则称S1，S2，……，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1 ，a2，……，an 放入k个（0＜k≤n＜30＝无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1 ，a2 ，……，an 放入k个无标号盒子中去的划分数S(n，k)。 【输入样例】 23 7 【输出样例】 4382641999117305 2、数的计数(Noip2001) 【问题描述】 我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理： 不作任何处理； 在它的左边加上一个自然数，但该自然数不能超过原数的一半； 加上数后，继续按此规则进行处理，直到不能再加自然数为止。 输入：自然数n（n≤1000） 输出：满足条件的数 【输入样例】 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136 【输出样例】 6 3、背包问题 问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T 的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。 (例如：有5件可选物品，质量分别为8千克、4千克、3千克、5千克、1千克。假设背包的最大转载质量是10千克。) 4、阿克曼函数（Ackmann） 阿克曼（Ackmann）函数A(x，y)中，x，y定义域是非负整数，函数值定义为： 写出计算Ack(m，n)的递归算法程序。 5、装错信封(letter) 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。 6、扑克牌(card) 有52张牌，使它们全部正面朝上，从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；接着从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；接着第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第1张要翻的牌是第52张为止。统计最后有几张牌正面朝上，以及它们的位置号。 7、求最大公约数(gys) 【问题描述】 用递归方法求两个数m和n的最大公约数。(m>0，n>0) 【输入格式】 输入二个数，即m和n的值。 【输出格式】 输出最大公约数。 【输入样例】 8 6 【输出样例】 gcd=2 8、双色Hanoi塔问题(hanoi) 龙源期刊网 https://www.wendangku.net/doc/b67061395.html, 递归方程求解方法综述 作者：郭萌萌 来源：《软件导刊》2011年第12期 摘要：随着计算机科学的逐步发展，各种各样的算法相继出现，我们需要对算法进行分析，以选择性能更好的解决方案。算法分析中计算复杂度常用递归方程来表达，因此递归方程的求解有助于分析算法设计的好坏。阐述了常用的3种求解递归方程的方法：递推法、特征方程法和生成函数法。这3种方法基本上可以解决一般规模递归方程的求解问题。 关键词：递归；递推法；特征方程；生成函数 中图分类号：TP301文献标识码：A文章编号：（2011） 作者简介：郭萌萌(1983- )，女，山东济南人，硕士，山东英才学院计算机电子信息工程 学院讲师，研究方向为软件工程、算法分析与设计。 0引言 寻求好的解决方案是算法分析的主要目的，问题的解决方案可能不只一个，好的方案应该执行时间最短，同时占有存储空间最小，故算法分析一般考虑时间复杂性、空间复杂性两方面的参数。在算法分析时我们采用时间耗费函数来表示时间参数，用当问题规模充分大时的时间耗费函数的极限表示时间复杂度。 一般算法对应的时间耗费函数常用递归方程表示，找出递归方程的解，就可以表示其对应算法复杂度的渐进阶，从而比较算法的优劣。因此研究递归方程的解法意义重大。下文将分析并给出常用递归方程的3种解法。 1递归方程的解法 递归方程是对实际问题求解的一种数学抽象,递归的本质在于将原始问题逐步划分成具有 相同解题规律的子问题来解决,原始问题与子问题仅在规模上有大小区别,并且子问题的规模比原始问题的规模要小。对于规模为n的原始问题,我们通常会寻找规模n的问题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推导出具有递归特性的运算模型。 根据递归方程的一般形式，常用的解法有三种，分别是递推法、公式法及生成函数法。下面就分别来分析其求解过程。 递归基础练习题 递归基础练习题 1. 求1+2+3+……+n的值 2. 求1*2*3*……*n的值 3. 数的全排列问题。将n个数字1，2，…n的所有排列按字典顺序枚举出来 2 3 1 2 1 3 3 1 2 3 2 1 4. 数的组合问题。从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。 如n=3,m=2时，输出： 1 2 1 3 2 3 9. 求两个数的最大公约数。 10. 求两个数的最小公倍数。 5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？ 8. 著名的菲波拉契(Fibonacci)数列，其第一项为1，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。15. 梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。 6. 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 7. 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？ 11. 输入一个数，求这个数的各位数字之和。 12. 角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。 如：输入22， 输 出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1集合划分问题
递归树的生成与图示
C语言递归练习(附答案)
递归习题汇总
递归方程求解方法综述
递归基础练习题