递推递归算法pascal讲解.pptVIP

【例5】设有一个背包可以放入的物品重量为S，现有n（n=10）件物品，重量分别是w1，w2，w3，…wn。 从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。找出一组解即可。 输入：Ex.in 6 10 1 4 7 8 7 5 输出：Ex.ans number:1 weight:1 number:2 weight:4 number:6 weight:5 输入：Ex.in 6 100 21 33 53 24 22 12 输出：Ex.ans number:1 weight:21 number:2 weight:33 number:4 weight:24 number:5 weight:22 const m=10; var t:array[1..m] of integer; x,y,i:integer; f:boolean; function sng(x:integer) :integer; begin if x0 then sng:=1; if x=0 then sng:=0; if x0 then sng:=-1; end; 递推和递归算法 淮南市计算机学会中小学思维训练基地 递推是迭代算法中最基本的表现形式，是一种不断用变量的旧值递推出新值的解决问题的方法，常见的的递推方式是从小规模问题推解出大规模问题。 问题求解的基本步骤 1.确定迭代模型 分析前一个（或几个）值与下一个值迭代关系的数学模型。 2.建立迭代关系式 将迭代模型转换为“循环不变式”---迭代关系式。 3.控制迭代过程 确定迭代过程的结束条件。 （1）迭代次数确定 （2）迭代次数不确定 基本步骤 递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意：?(1) 递归就是在过程或函数里调用自身;?(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁）。 【例1】 快速练习：简单骨牌铺方格问题 【问题描述】： 在2×n的一个长方形方格中，用n个1× 2的骨牌铺满方格，输入n (n0)，要求编程计算铺满方格的方案总数。 例如n=3时，为2× 3方格，骨牌的铺放方案有三种，如下图： 上述问题，如果思考方法不恰当，求解相当困难，我们可以用递推迭代的方法归纳出问题解的一般规律。 当n=1时，只能是一种铺法，表示为X1=1; 算法分析 当n=2时，骨牌可以两个并列竖排，也可以两个并列横排，铺法总数表示为X2=2; 算法分析 当n=3时，可以分两种情况考虑：先竖排放置 和 先横排放置； （1）若先竖排放置，剩下未铺满的区域为2×2的方格，有X2=2种铺法。 算法分析 n=2 的区域 有X2种铺法 即n=3时，若先竖排，则铺满整个方格有X2种铺法！ 当n=3时，可以分两种情况考虑：先竖排放置 和 先横排放置； （2）若先横排放置，下方的方格也必须横排，则剩下未铺满的区域为2×1的方格，有X1=1种铺法 。 算法分析 n=1 的区域 有X1种铺法 即n=3时，若先横排，则铺满整个方格有X1种铺法！ 算法描述 print(“Please Input N”); input(n); a[1]=1; a[2]=2; for i:=3 to n do a[i]=a[i-1]+a[i-2]; print(a[n]); 骨牌铺方格升级版 【问题描述】： 在1×n的一个长方形方格中，用若干个1×1、 1×2、 1×3的骨牌铺满方格，输入n (n0)，要求编程计算铺满方格的方案总数。 输入样例 36 输出样例 2082876103 var f:array[0..1000]of longint; i,n:longint; procedure setio; begin assign(input,domino.in); assign(output,domino.out); reset(input); rewrite(output); end; procedure print; begin close(input); close(output); end; begin setio; readln(n); f[0]:=1; f[1]:=1; f[2]:=2; for i:=3 to n do f[i]:=f[i-1]+f[i-2]+f[i-3]