当前位置：文档之家 › 递推算法(C++版)

递推算法(C++版)

  • 格式：ppt
  • 大小：349.00 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

递推法

递推法
输入：x,y,z的数值 输出：成虫对数 示例：
输入：x=1 y=2 z=8 输出：37
分析
首先我们来看样例：每隔1个月产2对卵，求过8 月（即第8+1=9月）的成虫个数
月份 1 2 3 4 5 6 7 8 9 … 新增卵 0 2 2 2 6 10 14 26 46 … 成虫 1 1 1 3 5 7 13 23 37 …
计算河心n个石礅可承载的最大青蛙数
设f[i]表示河心i个石礅可承载的最大青蛙数(1<=i<=n) 左岸为A,右岸为D
(1) 0个石礅,f[0]=0 (2) 1个石礅,f[1]=m+1 (3) 2个石礅s1,s2，f[2]=?
(1)A上m+1只青蛙s1 (2) A上m+1只青蛙 s2 , (3)s1上的m+1青蛙 s2 (4) A上m+1只青蛙s1 因此，f[2]=m+1+f[1]+f[1]=3*(m+1) (4) 3个石礅s1,s2,s3, (1)A上3(m+1)只青蛙s1,s2 (2) A上m+1只青蛙 s2 , (3)s1,s2上的3(m+1)青蛙 s2 (4) A上3(m+1)只青蛙s1,s2 因此，f[3]=m+1+2*f[2]=7*(m+1) …… (5) n个石礅? (1)A上f(n-1)只青蛙s1…sn-1 (2) A上m+1只青蛙 sn (3)s1…sn-1上的f(n-1)只青蛙sn (4) A上f(n-1)只青蛙s1…sn-1 因此， f[n]=m+1+2*f[n-1]
分析
设数组A[i]表示第i月新增的成虫个数。 由于新成虫每过x个月产y对卵，则可对每个A[i]作如下

算法总结之递推与递归

算法总结之递推与递归

算法总结之递推与递归递推算法递归算法⼤致包括两⽅⾯的内容：1）递归起点； 2）递归关系递推起点递归起点⼀般由题⽬或者实际情况确定，不由递归关系推出。

如果⽆法确定递归起点，那么递归算法就⽆法实现。

可见，递归起点是递归算法中的重要⼀笔。

递推关系递归关系是递归算法的核⼼。

常见的递归关系有以下⼏项：1）⼀阶递推；2）多阶递推；3）间接递推；4）逆向递推；5）多维递推。

下⾯通过栗⼦来详细介绍⼀下上述类别的递推关系。

1. ⼀阶递推在计算f(i)时，只⽤到前⾯项中的⼀项，如等差数列。

公差为3的等差数列，其递推关系为：f(i)=f(i-1)+3eg. 平⾯上10条直线最多能把平⾯分成⼏部分？分析：以直线数⽬为递推变量，假定i条直线把平⾯最多分成f(i)部分，则f(i-1)表⽰i-1条直线把平⾯分成的最多部分。

在i-1条直线的平⾯上增加直线i，易得i与平⾯上已经存在了的i-1条直线最多各有⼀个交点，即直线i最多被分成i段，⽽这i段将会依次将平⾯⼀分为⼆，即直线i将最多使平⾯多增加i部分。

所以，递推关系可表⽰为：f(i)=f(i-1)+i易得当0条直线时，平⾯为1部分。

所以f(0)=1为递推起点。

上述分析可⽤下⾯代码表⽰（c++）：#define MAX 100int f[MAX] //存放f（i）int lines(int n){//输⼊n为直线数⽬//输出最多部分数int i;f(0)=1;for(i=1;i<=n;i++){f[i]=f[i-1]+3;}return f[i];}2. 多阶递推在计算f(i)时，要⽤到前⾯计算过的多项，如Fibonacci数列。

eg.求Fibonacci的第10项。

分析：总所周知，Fibonacci数列中的第n项等于第n-1项加上n-2项。

所以递推关系为f(i)=f(i-1)+f(i-2);且f[0]=f[1]=1。

C++代码如下：#define MAX 100int f[MAX];int fib(int n){//输⼊n为项数//输出第n个fib数int i;f[0]=0;f[1]=1;for(i=2;i<=n;i++){f[i]=f[i-1]+f[i-2];}return f[n]}3. 间接递推在计算f[i]时需要中间量，⽽计算中间量要⽤到之前计算过的项。

递推法

递推法

递推计算方法和应用数学中有不少算法属递推算法。

递推算法就是在一个循环体内随着循环控制变量的变化，逐一通过前面的k 个已知的或已算出的值计算当前待算的值的算法，所用的算式称为递推计算公式。

递推算法分为一维递推算法、二维递推算法和广义递推算法三类。

注意广义递推算法不用了解，一维递推算法又分单步算法和多步算法。

同类递推算法对应相同的基本程度模块，可以作为一个基本类型。

算式给出后程序就能给出，程序和算式有映射关系。

一维递推算法一维递推算法分为单步算法和多步算法。

所谓单步算法是指能用下面的公式表示的算法上式称为一维递推单步算式，00a x =为表头值。

它所对应的程序模块为x[0]:=a;for i=1 to n dox[i]:=f(x[i-1])多步法是指能用下面的公式表示的算法上式表示的算式称为一维递推多步算式，该算法称为一维多步（K 步）算法，1,1,0...-k x x x 的值称为表头值。

它所对应的程序模块为：for i:=0 to k-1 dox[i]:=a[i];for i:=k to n dox[i]:=f(x[i-k],x[i-k+1],…x[i -1]];这里要强调的是，为了使算式和程序之间有一对一的映射关系，应尽量使用数组元素，这也是称为一维递推算法的原因例1计算菲波拉契数列的前21项公式为程序为program p24;varf:array[0..21] of integer;i:integer;beginf[0]:=0;f[1]:=1;for i:=2 to 21 dof[i]:=f[i-1]+f[i-2];for i:=0 to 21 dowrite(f[i],' ');end.该程序和算法的特色为：1. 程序和数学公式有一对一的关系，编程难度低；2. 数组元素的序号本身具有时间顺序特征，程序中不出现数据传递；3. 程序由输入、计算和输出三部分组成，每个程序段都具有明确的单一功能，结构规范 程序中增加一个一维数组并不会发生内存溢出，但却能方便程序设计例2 小数十翻二。

Fibonacci数列(c语言算法题目含答案)

Fibonacci数列(c语言算法题目含答案)
{
s3 = s1 + s2;
if (s3 > 10007)
s3 -= 10007;
Байду номын сангаас s1 = s2;
s2 = s3;
}
return s3;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", F(n));
return 0;
}

问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
答案
#include <stdio.h>
int F(int n)
{
int i, s1 = 1, s2 = 1, s3 = 1;
for (i = 3; i <= n; i++)

C语言迭代法详细讲解

C语言迭代法详细讲解

迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。

迭代法又分为精确迭代和近似迭代。

“二分法”和“牛顿迭代法”属于近似迭代法。

迭代算法是用计算机解决问题的一种基本方法。

它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

例 1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。

如果所有的兔子都不死去，问到第12 个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。

我们不妨假设第 1 个月时兔子的只数为u 1 ，第 2 个月时兔子的只数为u 2 ，第 3 个月时兔子的只数为u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u 1 ＝ 1 ，u 2 ＝u 1 ＋u 1 × 1 ＝ 2 ，u 3 ＝u 2 ＋u 2 × 1 ＝4 ，……根据这个规律，可以归纳出下面的递推公式：u n ＝u n － 1 × 2 (n ≥ 2)对应u n 和u n － 1 ，定义两个迭代变量y 和x ，可将上面的递推公式转换成如下迭代关系：y=x*2x=y让计算机对这个迭代关系重复执行11 次，就可以算出第12 个月时的兔子数。

第二讲 递归与递推

第二讲 递归与递推
2008年冬令营
江 苏 省 青 少 年 信 息 学 奥 林 匹 克 夏 令 营 C 层 次 教 学
例5、由m个A，n个B组成若干个排列。从某个排列 的位置1开始数，数到任意位置时都能保证A的个数 不少于B的个数，则称该排列为合理排列。例如： 当m=2，n=2时排列有 A A B B(合理) A B A B(合 理)A B B A(不合理) B B A A(不合理) 合理排列数有2 种 输入：只有一行两个整数m,n（1≤n≤m≤12）（用 空格分隔） 输出：一个整数（所有的合理排列数） 【样例】 输入 输出 32 5
递归过程例析
先以三个盘的移动为例，看一下移动过程。
江 苏 省 青 少 年 信 息 学 奥 林 匹 克 夏 令 营 C 层 次 教 学
2008年冬令营
递归过程例析
分析 1、当n=1时，只需要移动一次A---C； 2、当n=2时，需要移动三次； A---1---B； A---2---C； B---1---C； 3、当n>=3时，先将前n-1个盘子以C为 中介移到B柱子；再将第n个盘子移到 C柱子；最后将n-1个盘子以A为中介 从B柱移到C柱。
递归关系式——如何求？ 运用函数的前驱值来计算函数当前值的关系式
江 苏 省 青 少 年 信 息 学 奥 林 匹 克 夏 令 营 C 层 次 教 学
2008年冬令营
递归
例3、用递归方法求两个正整数m和n的最大公 约数。
分析：求两个数的最大公约数可以用辗转 相除法，即求m与n的最大公约数等价于求（m mod n）的值与n的最大公约数，此时的n可以当 作新的m ，而（m mod n）的值当作新的n ，所 以原问题的求解又变成求新的m与n的最大公约 数问题，继续下去，直至(m mod n)为0，最大 公约数就是最终存放在n中的值。

04.递推算法(C++版包括习题参考答案)

min{m , n}1 i 0
s 1=
(n i ) * (m i )
2.长方形和正方形的个数之和s 宽为1的长方形和正方形有m个，宽为2的长方形和正方形有 m-1个，┉┉，宽为m的长方形和正方形有1个； 长为1的长方形和正方形有n个，长为2的长方形和正方形有n1个，┉┉，长为n的长方形和正方形有1个； 根据乘法原理
【参考程序】 #include<iostream> using namespace std; int main() { int f[1001][2],n,i,x; cin>>n; f[1][1]=1;f[1][0]=9; for(i=2;i<=n;i++) { x=f[1][0]; if(i==n)x--; f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345; f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345; } cout<<f[n][0]; return 0; }
下面是输入n，输出x1~xn的c++程序： #include<iostream> using namespace std; int main() { int n,i,j,a[101]; cout<<"input n:"; //输入骨牌数 cin>>n; a[1]=1;a[2]=2; cout<<"x[1]="<<a[1]<<endl; cout<<"x[2]="<<a[2]<<endl; for (i=3;i<=n;i++) //递推过程 { a[i]=a[i-1]+a[i-2]; cout<<"x["<<i<<"]="<<a[i]<<endl; } } 下面是运行程序输入 n=30，输出的结果： input n: 30 x[1]=1 x[2]=2 x[3]=3 ........ x[29]=832040 x[30]=1346269

c++递推算法详解

例4：骨牌覆盖问题
有2行n列的长方形方格，要求用n个1*2的骨牌铺满。有多少种铺法？ 如n=3时有以下3种覆盖方法：
方法一
状态：f[i]表示铺满2*i的长方形的方案数 找规律,手工或搜索求出i=1,2,3,4,5的方案数分别为1，2，3，5，8,容易发现 f[i]=f[i-1]+f[i-2](i>=3) 边界条件：f[1]=1,f[2]=2 递推关系式 1 i=1 f[i]= 2 i=2 f[i-1]+f[i-2] i>=3 答案为f[n]，时间复杂度为O(n)。
方法一
根据二项式定理可知： (ax+by)k= = 取i=n,xnym的系数为 其中an和bm可以用快速幂来计算，在lg(n)+lg(m)内完成。 计算 可以用递推来求解。 状态：f[i,j]表示从i个数中选j个数的方案数。f[k,n]就是答案。 根据第i数选还是不选来进行分析： 1.选择第i个数：此情况的方案数等价于从i-1个数中选择j-1个数的方案数即f[i-1,j-1]; 2.不选第i个数：此情况的方案数等价于从i-1个数中选择j个数的方案数即f[i-1,j] 所以f[i,j]=f[i-1,j-1]+f[i-1,j] 边界条件：f[i,0]=1,f[i,i]=1。 计
【问题描述】 栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。 【输入】 【输出】 就一个数n(1≤n≤1000)。 一个数，即可能输出序列的总数目。 【样例】 stack.in stack.out 3 5

基本算法2-递推法实例


一般地，设原来的符合题意的n-1条直线把这平面分成 个区域，再增加一条直线l，就变成n条直线，按题设条 件，这l必须与原有的n-1条直线各有一个交点, 且这n-1个交点 及原有的交点互不重合。这n-1个交点把l划分成n个区间，每 个区间把所在的原来区域一分为二，所以就相应比原来另增 了n个区域，即：
const max=100; var
f1,f2,s:array[1..max] of longint; i,j,k,l,n:longint; begin readln(n); f1[max]:=0 ; f1[max-1]:=1; {F0=10} for i:= 1 to n do
begin f2:=f1; k:=0; { ×7 } for j:= max downto 1 do begin k:=k+f1[j]*7; f1[j]:=k mod 10; k:=k div 10; end;
end.
var a,b:array[1..100] of longint; i,j,n:longint;
begin readln(n); a[100]:=4 ; b[100]:=1; for i:= 2 to n do begin for j:= 100 downto 1 do b[j]:=b[j]*2; for j:= 100 downto 2 do if b[j]>=10 then begin b[j-1]:=b[j-1]+b[j] div 10 ; b[j]:=b[j] mod 10; end; for j:= 100 downto 1 do begin a[j]:=a[j]+b[j]; if a[j]>=10 then begin a[j-1]:=a[j-1]+a[j] div 10 ; a[j]:=a[j] mod 10; end; end; end; j:=1; while a[j]=0 do j:=j+1; for i:= j to 100 do write(a[i]) ;

04.递推算法(C++版包括习题参考答案)


【例6】过河卒（Noip2002） 【问题描述】 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向 下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马 所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点 和P1，„„，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点 (0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给 出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
min{m , n}1 i 0
s 1=
(n i ) * (m i )
2.长方形和正方形的个数之和s 宽为1的长方形和正方形有m个，宽为2的长方形和正方形有 m-1个，┉┉，宽为m的长方形和正方形有1个； 长为1的长方形和正方形有n个，长为2的长方形和正方形有n1个，┉┉，长为n的长方形和正方形有1个； 根据乘法原理
【例3】棋盘格数
设有一个N*M方格的棋盘（ l≤ N≤100，1≤M≤100）。求出该棋盘中包含有多少 个正方形、多少个长方形（不包括正方形）。 例如：当 N=2， M＝3时： 正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。 长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长 方形有2个：3*2的长方形有1个： 程序要求：输入：N，M 输出：正方形的个数与长方形的个数 如上例：输入：2 3 输出：8 10 【算法分析】 1.计算正方形的个数s1 边长为1的正方形个数为n*m 边长为2的正方形个数为(n-1)*(m-1) 边长为3的正方形个数为(n-2)*(m-2) ………… 边长为min{n，m}的正方形个数为(m-min{n，m}+1)*(n-min{n，m}+1) 根据加法原理得出
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

【例3】棋盘格数
设有一个N*M方格的棋盘（ l≤ N≤100，1≤M≤100）。求出该棋盘中包含有多少 个正方形、多少个长方形（不包括正方形）。 例如：当 N=2， M＝3时： 正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。 长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长 方形有2个：3*2的长方形有1个： 程序要求：输入：N，M 输出：正方形的个数与长方形的个数 如上例：输入：2 3 输出：8 10 【算法分析】 1.计算正方形的个数s1 边长为1的正方形个数为n*m 边长为2的正方形个数为(n-1)*(m-1) 边长为3的正方形个数为(n-2)*(m-2) ………… 边长为min{n，m}的正方形个数为(m-min{n，m}+1)*(n-min{n，m}+1) 根据加法原理得出
【参考程序】 #include<iostream> using namespace std; int main() { long long a[101]={0},b[101]={0},i,j,x,y,z; cin>>x>>y>>z; for(i=1;i<=x;i++){a[i]=1;b[i]=0;} for(i=x+1;i<=z+1;i++) //因为要统计到第z个月后，所以要for到z+1 { b[i]=y*a[i-x]; a[i]=a[i-1]+b[i-2]; } cout<<a[z+1]<<endl; return 0; }
【例6】过河卒（Noip2002） 【问题描述】 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向 下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马 所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点 和P1，„„，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点 (0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给 出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排 骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排 列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排 列方法，因此铺法总数表示为x3=3。 由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的 和。 （5）推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是 竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨 牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个 骨牌需要排列，这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有 这两种可能，所以有： xn=xn-1+xn-2 （n>2） x1=1 x2=2 xn=xn-1+xn-2就是问题求解的递推公式。任给n都可以从中获得解答。例如n=5， x3=x2+x1=3 x4=x3+x2=5 x5=x4+x3=8
min{m , n}1 i 0
s 1=
(n i ) * (m i )
2.长方形和正方形的个数之和s 宽为1的长方形和正方形有m个，宽为2的长方形和正方形有 m-1个，┉┉，宽为m的长方形和正方形有1个； 长为1的长方形和正方形有n个，长为2的长方形和正方形有n1个，┉┉，长为n的长方形和正方形有1个； 根据乘法原理
【例2】 有 2χn的一个长方形方格，用一个1*2的骨牌铺满方格。
编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。 【算法分析】 （1）面对上述问题，如果思考方法不恰当，要想获得问题的解 答是相当困难的。可以用递推方法归纳出问题解的一般规律。 （2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。 （3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再 无其他方法，如下左图所示，因此，铺法总数表示为x2=2；
【例5】位数问题 【问题描述】 在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大， 你只需要输出这个答案对12345取余的值。 【输入格式】 读入一个数N 【输出格式】 输出有多少个数中有偶数个数字3。 【输入样例】 2 【输出样例】 73 【数据规模】 1<=N<=1000 【样例说明】 在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73 个
【算法分析】 跳马是一道老得不能再老的题目，我想每位编程初学者都学过，可能是 在学回溯或搜索等算法的时候，很多书上也有类似的题目，一些比赛中也 出现过这一问题的变形（如NOIP1997初中组的第三题）。有些同学一看 到这条题目就去搜索，即使你编程调试全通过了，运行时你也会发现：当 n,m=15就会超时。 其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过 来（我们称之为左点）或是从上面过来（我们称之为上点），所以根据加 法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径 数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到 终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的 路径数目设置为0即可。 用F[i][j]表示到达点(i,j)的路径数目，g[i][j]表示点(i, j)有无障碍，g[i][j]=0 表示无障碍，g[i][j]=1表示有障碍。 则，递推关系式如下： F[i][j] = F[i-1][j] + F[i][j-1] //i>0且j>0且g[i][j]= 0 递推边界有4个： F[i][j] = 0 //g[i][j] = 1 F[i][0] = F[i-1][0] //i > 0且g[i][j] = 0 F[0][j] = F[0][j-1] //j > 0且g[i][j] = 0 F[0][0] = 1 考虑到最大情况下：n=20,m=20，路径条数可能会超过231-1,所以要用 高精度。
【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到 底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。 1、 一步可沿左斜线向下或右斜线向下走； 2、 三角形行数小于等于100； 3、 三角形中的数字为0，1，…，99； 测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入： 5 7 38 810 2744 45265 【算法分析】 此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第i 层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向 前进，为此，我们可以采用倒推的手法，设a[i][j]存放从i,j 出发到达n层的最大 值，则a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1] 即为所求的数字总 和的最大值。
【算法分析】 方法一：排列组合(但需要运用动态规划)。 可以列出公式,在n个格子中放x个3(其中x为偶数,包括0).。 c(n,x)*9^(n-x)-c(n-1,x)*9^(n-x-1) 含义为在n个格子中取x个3,且不考虑第 一位的特殊情况为c(n,x)*9^(n-x)。 而第一位为0的情况,为c(n-1,x)*9^(n-x-1),两者减下,就为答案。 方法二：递推 考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是 取奇数的。 恍然大悟.可以用f[i][0]表示前i位取偶数个3有几种情况,f[i][1]表示前i位取 奇数个3有几种情况。 则状态转移方程可以表示为: f[i][0]=f[i-1][0]*9+f[i-1][1];f[i][1]=f[i-1][0]+f[i-1][1]*9; 边界条件:f[1][1]=1;f[1][0]=9;
【参考程序】 #include<iostream> using namespace std; int main() { int f[1001][2],n,i,x; cin>>n; f[1][1]=1;f[1][0]=9; for(i=2;i<=n;i++) { x=f[1][0]; if(i==n)x--; f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345; f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345; } cout<<f[n][0]; return 0; }
【参考程序】 #include<iostream> using namespace std; int main() { int n,i,j,a[101][101]; cin>>n; for (i=1;i<=n;i++) for (j=1;j<=i;j++) cin>>a[i][j]; //输入数字三角形的值 for (i=n-1;i>=1;i--) for (j=1;j<=i;j++) { if (a[i+1][j]>=a[i+1][j+1]) a[i][j]+=a[i+1][j]; //路径选择 else a[i][j]+=a[i+1][j+1]; } cout<<a[1][1]<<endl; }
第三章 递推算法
递推法是一种重要的数学方法，在数学的各个领域中都 有广泛的运用，也是计算机用于数值计算的一个重要算法。 这种算法特点是：一个问题的求解需一系列的计算，在已知 条件和所求问题之间总存在着某种相互联系的关系，在计算 时，如果可以找到前后过程之间的数量关系（即递推式）， 那么，从问题出发逐步推到已知条件，此种方法叫逆推。无 论顺推还是逆推，其关键是要找到递推式。这种处理问题的 方法能使复杂运算化为若干步重复的简单运算，充分发挥出 计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即 递推关系）。递推算法避开了求通项公式的麻烦，把一个复 杂的问题的求解，分解成了连续的若干步简单运算。一般说 来，可以将递推算法看成是一种特殊的迭代算法。