7=1+1+2+3 7=1+2+4 7=1+2+2+2 7=1+3+3 7=2+5 7=2+2+3 7=3+4
【分析过程】： N是任意的。N=1
1. 10=3+7与10=7+3 是同一个拆分。 2. n=7.
第一步，将N拆分为2项之和： 7=1+6 7=2+5 7=3+4
此拆分的特点是第2个加数总大于第1个加数，第1个加熟从1变化到 n div 2; 第二步：只要发现第2个加数大于1，就可以按第一步的方法重复拆分。比如 7=1+6 7=1+1+5 7=1+2+4 7=1+3+3 ….
其中7=1+1+5对它进行继续拆分 7=1+1+1+4
7=1+1+2+3…….
【如何用算法实现】
用数组a[0..100],a[k]中存储已完成的一种拆分。比如：7=1+6。可以用数组a表示：a[0]=7，a[1]=1，a[2]=6，k=2，继续拆分从a[k]（从a[2] 开始）；a[k]能否再次拆分取决于a[k] div 2 是否大于或等于a[k-1]；在这里，我们采取的回溯（递归）过程中有两个元素：nx表示要拆分的数值大小，kx表示nx存储在数组元素a[kx]中，即a[kx]=nx。
参考程序： var
n,i,j:integer;
a:array[0..100] of integer;
procedure sum(nx,kx:integer); var
k,m,l:integer; begin j:=j+1;
write('Sum No.',j:3,':',a[0],'='); {输出标头} for k:=1 to kx-1 do
write(a[k],'+'); {输出前面的加数}
writeln(a[kx]); {输出最后一个加数并换行} k:=kx;
l:=a[k]; {第一组拆分结束，重新赋值}
for m:=a[k-1] to l div 2 do {新赋值的拆分范围} begin
a[k]:=m;
a[k+1]:=l-m; {新赋值初始化拆分} sum(a[k+1],k+1); {回溯下一个}
- 11 -
end; end;
begin
read(a[0]); j:=0;
if a[0]>=2 then {a[0]>=2时才有数据可以拆分} for i:=1 to a[0] div 2 do {第一个加数的拆分范围} begin a[1]:=i;
a[2]:=a[0]-a[1]; {初始化拆分} sum(a[0],2); {调用sum} end; {when a[0]>2} writeln; end.
{补充部分} 一、线性表 1 2 二、栈 先进后出
三、队列 先进先出
四、矩阵
我们可以用二维数组表示 即行列式
五、树
二叉树的遍历问题：
1. 先序遍历 ：根→左→右 2. 中序遍历 ：左→根→右 3. 后序遍历 ：左→右→根
六、图论
第一：图的权
第二：无向图和有向图
马拦过河卒
【问题描述】
棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下\\或者向右.同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点.因此称为“马拦过河卒”。
- 12 -
棋盘用坐标表示，A点（0,0）、B点（n,m）(n,m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 【输入】
一行四个数据，分别表示B点坐标和马的坐标。 【输出】
一个数据，表示所有的路径条数。 【样例】 Knight.in 6 6 3 3 Knight.out 6
问题解答： 【算法分析】
从起点开始往下走（只有两个方向可以走），如果某个方向可以走再继续下一步，直到终点，此时计数（计算可走路径数）。最后输出所有路径数。这种方法可以找出所有可能的走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时。 【参考程序】 program knight;
const {定义马可以走的八个点的坐标的变化情况} dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2); dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1); var
n,m,x,y,i:byte; {n,m为棋盘B点位置,x,y为马所在的位置} g:array[0..20,0..20] of 0..1;
{描述棋盘上的点是否受马控制，如果为0则表示不受马控制，卒可以走过；如果为1，} {如果为1，则受马控制，卒不可以走过，例如，若g[4，3]=1，则表示棋盘上坐标为 } {（4，3）的点受马控制，卒不可以走} c:longint; {存在总路径数} infile,outfile:text;
procedure sol(x,y:integer); {小卒走的过程，利用递归} var
i:integer; begin
if (x=n) and (y=m) then c:=c+1 {如果已达终点则总路径数增加1} else
- 13 -
begin
if (y {主程序} begin assign(infile,?knight.in?); {装载输入文件} assign(outfile,?knight.out?); {装载输出文件} reset(infile);readln(infile,n,m,x,y);close(infile);{从文件读入数据,然后关闭文件} g[x,y]:=1; {将马所在坐标点标记为1,则卒不可走过} for i:=1 to 8 do if (x+dx[i]>=0) and (x+dx[i]<=n) and (y+dy[i]>=0) and (y+dy[i]<=m) then g[x+dx[i],y+dy[i]]:=1; {将马可能的八个控制点标记为1,表示卒不可走} sol(0,0); rewrite(outfile);writeln(outfile,c);close(outfile);{将答案写到输出文件} end. 思考：如果不使用递归，应该怎么解决本题。 程序如下： program knight; const {定义马可以走的八个点的坐标的变化情况} dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2); dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1); {定义每个点两个方向的增量} di:array[1..2] of integer=(1,0); dj:array[1..2] of integer=(0,1); var n,m,x,y,i,j:byte; g:array[0..20,0..20] of 0..1;{记录棋盘上的点是否可走，1为不可走，0为可走} f:array[0..20] of integer; {方向数组，记录每个点走向下一点时所走的方向，1为向右，2为向下} a,b:array[0..20] of integer; {记录每一步所走的点的坐标，a对应x轴坐标，b对应y轴坐标} p,k:integer; {k记录当前走到第几步，p则用来暂存当前所走方向} c:longint; {c用来记录所能走的路径条数} infile,outfile:text; begin assign(infile,'knight.in'); assign(outfile,'knight.out'); reset(infile);readln(infile,n,m,x,y);close(infile); g[x,y]:=1; for i:=1 to 8 do if (x+dx[i]>=0) and (x+dx[i]<=n) and (y+dy[i]>=0) and (y+dy[i]<=m) then g[x+dx[i],y+dy[i]]:=1; {将马所在点及马所控制点初始化为1，表示不能走} for i:=0 to 20 do begin f[i]:=0;a[i]:=0;b[i]:=0 end;{初始化f、a、b等数组} k:=1; i:=0;j:=0; p:=0; c:=0; while k>0 do - 14 - begin p:=f[k]+1; i:=a[k]; j:=b[k]; if (i=m) and (j=n) then begin c:=c+1;k:=k-2;f[k+1]:=0 end {如果到达了终点，则返回前两步，同时将前一步的方向值回复0} else begin while p<3 do {对当前点试探它的两个方向指向的点。 begin {如果两个点中有任一个点可走，则则令该可走的点变为当前点，继续向下一步试探} if (i+di[p]<=m) and (j+dj[p]<=n) and (g[i+di[p],j+dj[p]]=0) then begin f[k]:=p; k:=k+1; a[k]:=i+di[p]; b[k]:=j+dj[p]; break end; p:=p+1 end; if p=3 then begin f[k]:=0; k:=k-1 end;{如果p到达了3，则证明当前点的两个方向及不可走或者之前已经走过，因此返回上一步} end; end; rewrite(outfile);writeln(outfile,c);close(outfile); end. 本方法的程序段比上一种更长一些，但是却是一种经典的回溯表现，在路径探索时通常都可以利用这种方法来完成。例如：马走日，骑士游历，走迷宫等问题的解决。它的基本思想是：设置增量数组及方向数组，方向数组的值作为增量数组的下标，正好一一对应不同的方向，于是在程序中，对每一步可能走的方向进行试探，如果有某个方向可走，则走到下一步，且对下一步做同样的试探。如果该步所有方向都不可走，则返回上一步。试探上一步的其他方向。 分治策略 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。当我们需要解决一个规模比较大的任务时，可以先把该任务分解成多个子任务完成，求出每个子任务的解，再找到适当的方法，将它们组合成整个问题的解。在完成任务的过程中，我们始终遵循一个原则，将大任务化为小任务即大化小的原则，这样的策略，我们称之为分治策略。 问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 8.1 分治策略的定义 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1 - 15 -