第一章回溯法(习题三)

回溯法习题汇总1.1 马拦过河卒源程序名knight.???（pas, c, cpp）可执行文件名knight.exe输入文件名knight.in输出文件名knight.out【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。

卒行走的规则：可以向下、或者向右。

同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

因此称之为“马拦过河卒”。

棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

【输入】一行四个数据，分别表示B点坐标和马的坐标。

【输出】一个数据，表示所有的路径条数。

【样例】knight.in knight.out6 6 3 3 6【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。

最后输出所有的路径数。

这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。

1.2 出栈序列统计源程序名stack1.???（pas, c, cpp）可执行文件名stack1.exe输入文件名stack1.in输出文件名stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。

你已经知道栈的操作有两·种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。

现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。

请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

【输入】一个整数n（1<=n<=15）【输出】一个整数，即可能输出序列的总数目。

0-1背包问题计科1班朱润华 2012040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。

问题的解空间至少包含问题的一个（最优）解。

对于0-1背包问题，解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有0-1赋值。

例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为C。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。

这4个物品的单位重量价值分别为[3,2,3,5,4]。

以物品单位重量价值的递减序装入物品。

先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。

由此得一个解为[1,0.2,1,1]，其相应价值为22。

回溯法实例详解（转）概念回溯算法实际上⼀个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满⾜求解条件时，就“回溯”返回，尝试别的路径。

回溯法是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。

但当探索到某⼀步时，发现原先选择并不优或达不到⽬标，就退回⼀步重新选择，这种⾛不通就退回再⾛的技术为回溯法，⽽满⾜回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较⼤的问题都可以使⽤回溯法，有“通⽤解题⽅法”的美称。

基本思想在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。

当探索到某⼀结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

（其实回溯法就是对隐式图的深度优先搜索算法）。

若⽤回溯法求问题的所有解时，要回溯到根，且根结点的所有可⾏的⼦树都要已被搜索遍才结束。

⽽若使⽤回溯法求任⼀个解时，只要搜索到问题的⼀个解就可以结束。

解题步骤　（1）针对所给问题，确定问题的解空间：⾸先应明确定义问题的解空间，问题的解空间应⾄少包含问题的⼀个（最优）解。

（2）确定结点的扩展搜索规则（3）以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索⼦集树，排列数及其他 ⼦集树概念：当所给问题是从n个元素的集合S中找出S满⾜的某种性质的⼦集时，相应的解空间树称为⼦集树。

例如，0-1背包问题，要求在n个物品的集合S中，选出⼏个物品，使物品在背包容积C的限制下，总价值最⼤（即集合S的满⾜条件<容积C下价值最⼤>的某个⼦集）。

另：⼦集树是从集合S中选出符合限定条件的⼦集，故每个集合元素只需判断是否（0,1）⼊选，因此解空间应是⼀颗满⼆叉树回溯法搜索⼦集树的⼀般算法void backtrack(int t)//t是当前层数{if(t>n)//需要判断每⼀个元素是否加⼊⼦集，所以必须达到叶节点，才可以输出{output(x);}else{for(int i=0;i<=1;i++)//⼦集树是从集合S中，选出符合限定条件的⼦集，故每个元素判断是（1）否（0）选⼊即可（⼆叉树），因此i定义域为{0,1}{x[t]=i;//x[]表⽰是否加⼊点集，1表⽰是，0表⽰否if(constraint(t)&&bound(t))//constraint(t)和bound(t)分别是约束条件和限定函数{backtrack(t+1);}}}}　排列树概念：当问题是确定n个元素满⾜某种性质的排列时，相应的解空间称为排列树。

回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。

回溯是搜索算法中的一种控制策略。

它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。

按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

递归回溯法算法框架[一]procedure Try(k:integer);beginfor i:=1 to 算符种数 Doif 满足条件 thenbegin保存结果if 到目的地 then 输出解else Try(k+1);恢复：保存结果之前的状态{回溯一步}end;end;递归回溯法算法框架[二]procedure Try(k:integer);beginif 到目的地 then 输出解elsefor i:=1 to 算符种数 Doif 满足条件 thenbegin保存结果Try(k+1);end;end;例 1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

【算法分析】非常明显，这是一道回溯的题目。

从1 开始，每个空位有 20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。

第 20个数还要判断和第1个数的和是否素数。

〖算法流程〗1、数据初始化； 2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】program z74;框架[一]var a:array[0..20]of byte;b:array[0..20]of boolean;total:integer;function pd(x,y:byte):boolean;var k,i:byte;begink:=2; i:=x+y; pd:=false;while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k);if k>trunc(sqrt(i)) then pd:=true;end;procedure print;var j:byte;begininc(total);write('<',total,'>:');for j:=1 to 20 do write(a[j],' ');writeln;end;procedure try(t:byte);var i:byte;beginfor i:=1 to 20 doif pd(a[t-1],i)and b[i] thenbegina[t]:=i; b[i]:=false;if t=20 then begin if pd(a[20],a[1]) then print;endb[i]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);total:=0;try(1);write('total:',total);END.通过观察，我们可以发现实现回溯算法的特性：在解决过程中首先必须要先为问题定义一个解的空间．这个空间必须包含问题的一个解。

python回溯法例题回溯法是一种常用的算法思想，用于解决各种组合优化问题，尤其在解决NP完全问题方面有着广泛的应用。

本文将通过一个具体的例题来介绍和解释python回溯法的实现过程。

任务名称：python回溯法例题问题描述：给定一个由不同整数组成的数组nums，编写一个函数，返回所有可能的排列组合。

解题思路：要解决这个问题，我们可以使用回溯法来生成所有可能的排列组合。

回溯法是一种通过试错的方式搜索解空间的算法。

具体来说，我们从问题的一个初始解开始，通过一系列的决策，逐步构建问题的解，如果在构建的过程中发现当前的解不符合要求，我们就回溯到上一个状态，重新进行决策。

在本例中，我们可以使用一个递归函数来实现回溯法。

我们定义一个辅助函数backtrack，它接受一个当前的排列，一个用于标记数字是否被使用的数组，以及一个用于存储所有解的结果数组。

在函数中，我们首先检查当前的排列是否已经包含了所有的数字，如果是的话，我们将当前的排列添加到结果数组中。

然后，我们遍历所有的数字，对于每一个数字，如果它没有被使用过，我们将其添加到当前的排列中，然后递归调用backtrack函数，继续构建下一个数字。

最后，我们将当前的数字从排列中移除，以便进行下一次决策。

下面是具体的代码实现：```pythondef permute(nums):def backtrack(curr_perm, used, result):if len(curr_perm) == len(nums):result.append(curr_perm[:])else:for i in range(len(nums)):if not used[i]:curr_perm.append(nums[i])used[i] = Truebacktrack(curr_perm, used, result)used[i] = Falsecurr_perm.pop()result = []used = [False] * len(nums)backtrack([], used, result)return result```我们可以使用这个函数来解决给定数组的排列组合问题。

回溯算法经典问题请设计⼀个函数，⽤来判断在⼀个矩阵中是否存在⼀条包含某字符串所有字符的路径。

路径可以从矩阵中的任意⼀个格⼦开始，每⼀步可以在矩阵中向左，向右，向上，向下移动⼀个格⼦。

如果⼀条路径经过了矩阵中的某⼀个格⼦，则该路径不能再进⼊该格⼦。

分析：回溯算法这是⼀个可以⽤回朔法解决的典型题。

⾸先，在矩阵中任选⼀个格⼦作为路径的起点。

如果路径上的第i个字符不是ch，那么这个格⼦不可能处在路径上的第i个位置。

如果路径上的第i个字符正好是ch，那么往相邻的格⼦寻找路径上的第i+1个字符。

除在矩阵边界上的格⼦之外，其他格⼦都有4个相邻的格⼦。

重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

由于回朔法的递归特性，路径可以被开成⼀个栈。

当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格⼦的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。

由于路径不能重复进⼊矩阵的格⼦，还需要定义和字符矩阵⼤⼩⼀样的布尔值矩阵，⽤来标识路径是否已经进⼊每个格⼦。

当矩阵中坐标为（row,col）的格⼦和路径字符串中相应的字符⼀样时，从4个相邻的格⼦(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下⼀个字符如果4个相邻的格⼦都没有匹配字符串中下⼀个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前⼀个，然后重新定位。

⼀直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置class Solution {public:bool hasPath(char* matrix, int rows, int cols, char* str){if(str==NULL||rows<=0||cols<=0)return false;bool *isOk=new bool[rows*cols]();for(int i=0;i<rows;i++){for(int j=0;j<cols;j++)if(isHsaPath(matrix,rows,cols,str,isOk,i,j))return true;}return false;}bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *isOk,int curx,int cury){if(*str=='\0')return true;if(cury==cols){curx++;cury=0;}if(cury==-1){curx--;cury=cols-1;}if(curx<0||curx>=rows)return false;if(isOk[curx*cols+cury]||*str!=matrix[curx*cols+cury])return false;isOk[curx*cols+cury]=true;bool sign=isHsaPath(matrix,rows,cols,str+1,isOk,curx-1,cury)||isHsaPath(matrix,rows,cols,str+1,isOk,curx+1,cury)||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury-1)||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury+1);isOk[curx*cols+cury]=false;return sign;}};。

回溯法是一种解决0-1背包问题的有效方法。

以下是使用回溯法解决0-1背包问题的具体步骤和例题：1.定义问题：假设有N件物品，每件物品有一定的重量Wi和价值Vi，背包能够承受的最大重量为W。

目标是选择一些物品放入背包，使得背包中物品的总价值最大，同时不超过背包的最大承重。

2.使用回溯法求解：回溯法的核心是深度优先搜索，通过尝试每一种可能性来找到最优解。

o初始化：将所有物品按照价值从大到小排序。

o递归函数：▪如果当前选择的物品重量超过了背包的承重，则返回（因为无法放入背包）。

▪如果当前选择的物品价值大于之前所有选择物品的总价值，则更新当前最大价值。

▪标记当前选择的物品为已选（例如，使用一个布尔数组表示）。

▪递归地尝试下一个物品。

o回溯：如果递归到最后一个物品，并且没有超过背包的承重，则将最后一个物品加入背包，并更新最大价值。

然后回溯到上一个物品，尝试不放入背包中。

3.求解步骤：o初始状态：未选择任何物品，总价值为0。

o递归函数：对于每个物品i，如果未选择（即第i个物品的布尔数组标记为false），则执行递归函数。

如果选择了第i个物品，并且总价值大于当前最大价值，则更新最大价值。

标记第i个物品为已选。

然后递归地尝试下一个物品。

o回溯：如果尝试了所有物品都没有超过背包的承重，并且总价值大于当前最大价值，则将最后一个选择的物品加入背包，并更新最大价值。

然后回溯到上一个物品，尝试不放入背包中。

4.例题：假设有3件物品，重量分别为20、15、10，价值分别为20、30、25，背包的承重为25。

根据回溯法求解的步骤如下：o首先尝试第一个物品（重量20，价值20）。

由于20>25，所以无法放入背包。

o接下来尝试第二个物品（重量15，价值30）。

由于15+20=35>25，所以也无法放入背包。

o然后尝试第三个物品（重量10，价值25）。

由于10+20=30<25，所以可以放入背包中。

此时的最大价值为25+25=50。

回溯算法经典例题回溯算法是一种解决问题的方法，其核心思想是通过深度优先搜索来寻找解决方案。

回溯算法通常用于解决需要重复操作的问题，例如迷宫问题、图论问题等。

以下是回溯算法的经典例题:1. 八皇后问题八皇后问题是一个经典的回溯算法例题，它要求在 8×8 的国际象棋棋盘上放置八个皇后，使得它们无法相互攻击。

回溯算法的核心思想是，不断尝试每个皇后的位置，直到找到合法的位置为止。

具体实现如下:```cpp#include <iostream>using namespace std;int queen_board[8][8] = {{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0}}};int main(){int n = 8;int queen = 0;for (int i = 0; i < 8; i++){for (int j = 0; j < 8; j++){if (queen_board[i][j] == 0){queen_board[i][j] = queen++;cout << "Queen placed on " << i << ", " << j << endl;}}}return 0;}```在这个实现中，我们首先初始化一个 8×8 的矩阵来表示皇后可以放置的位置，如果当前位置已经放置了一个皇后，则将该位置标记为已经放置，并重新搜索下一个位置。

第9课时秦九韶算法知识点一秦九韶算法的原理1．用秦九韶算法计算f(x）＝6x5－4x4＋x3－2x2－9x当x＝x0时的值，需要加法(或减法）与乘法运算的次数分别为( ）A．5，4 B．5,5 C．4，4 D．4，5答案D解析n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法,缺一项就减少一次加法运算．f(x）中无常数项,故加法次数要减少一次,为5－1＝4．故选D．2．用秦九韶算法求多项式f（x)＝1＋2x＋x2－3x3＋2x4在x＝－1时的值，v2的结果是( )A．－4 B．－1 C．5 D．6答案D解析n＝4，a4＝2，a3＝－3，a2＝1，a1＝2，a0＝1,由秦九韶算法的递推关系式得v0＝2，v1＝v0x＋a3＝－5,v2＝v1x＋a2＝6．3．用秦九韶算法求多项式f（x)＝7x6＋6x5＋3x2＋2当x＝4时的值时,先算的是( ）A．4×4＝16 B．7×4＝28C．4×4×4＝64 D．7×4＋6＝34答案D解析因为f（x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0＝（…((a n x＋a n－1）x＋a n－2)x＋…＋a1)x ＋a0,所以用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4时的值时,先算的是7×4＋6＝34．4．用秦九韶算法求多项式f(x)＝x4－2x3＋3x2－7x－5，当x＝4时的值，给出如下数据．①0 ②2 ③11 ④37 ⑤143其中运算过程中(包括最终结果)会出现的数有________．(只填序号）答案②③④⑤解析将多项式改写成f（x）＝(（（x－2）x＋3)x－7）x－5．v＝1；v＝1×4－2＝2；1v＝2×4＋3＝11；2v＝11×4－7＝37；3v＝37×4－5＝143．4知识点二利用秦九韶算法计算多项式的值5．用秦九韶算法求多项式f（x）＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值．解f(x)＝(((（(（7x＋6）x＋5)x＋4）x＋3)x＋2）x＋1）x,所以有v＝7；v＝7×3＋6＝27；1v＝27×3＋5＝86；2v＝86×3＋4＝262；3v＝262×3＋3＝789;4v＝789×3＋2＝2369;5v＝2369×3＋1＝7108；6v＝7108×3＝21324．7故当x＝3时，多项式f（x）＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21324．易错点利用秦九韶算法求含空项的n次多项式的值时易出现错误6．已知f（x）＝3x4＋2x2＋4x＋2，利用秦九韶算法求f(－2)的值．易错分析由于没有抓住秦九韶算法原理的关键,没有正确改写多项式并使每一次计算只含有x的一次项而致误．正解f（x)＝3x4＋0·x3＋2x2＋4x＋2＝（（（3x＋0)x＋2)x＋4)x＋2，v＝3×（－2)＋0＝－6；1v＝－6×(－2）＋2＝14；2v＝14×（－2)＋4＝－24；3v＝－24×（－2）＋2＝50．4故f（－2）＝50．一、选择题1．用秦九韶算法计算多项式f(x)＝3x6＋9x5＋5x4＋6x3＋12x2＋8x－7在x＝2时的值，需要做乘法和加法的次数分别是( )A．5,5 B．5，6 C．6，6 D．6，5答案C解析因为f(x）的最高次数是6，所以需要做乘法和加法的次数都是6．2．用秦九韶算法求多项式f(x）＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6在x＝－4时，v4的值为（）A．－57 B．220 C．－845 D．3392答案B解析v0＝3,v1＝3×（－4)＋5＝－7，v＝－7×（－4）＋6＝34,2v＝34×（－4）＋79＝－57,3v＝－57×（－4）－8＝220．43．已知多项式f（x)＝4x5＋3x4＋2x3－x2－x－错误!，用秦九韶算法求f（－2)等于（）A．－错误! B．错误! C．错误! D．－错误!答案A解析∵f(x)＝（（（(4x＋3）x＋2)x－1）x－1）x－错误!,∴f(－2）＝（（（(4×(－2）＋3）×（－2)＋2)×(－2）－1)×（－2）－1)×（－2)－错误!＝－错误!．4．秦九韶算法的先进性主要体现在减少运算次数，下列说法正确的是( )A．可以减少加法运算次数B．可以减少乘法运算次数C．同时减少加法和乘法的运算次数D．加法次数和乘法次数都有可能减少答案B解析秦九韶算法可以把至多n n＋12次乘法运算减少为至多n次乘法运算．加法运算次数不变．5．用秦九韶算法计算函数y＝2x3－3x2＋2x－1在x＝2时的函数值，则下列各式正确的是（）A．v0＝2 B．v0＝1 C．v1＝4 D．v2＝7答案A解析根据秦九韶算法，把多项式改写成y＝(（2x－3）x＋2)x－1,从内到外依次计算:v0＝2，v1＝2×2－3＝1,v2＝1×2＋2＝4，v3＝4×2－1＝7．二、填空题6．已知f(x)＝x5＋2x3＋3x2＋x＋1，用秦九韶算法计算x＝3时的值，v3的值为________．答案36解析v0＝1,v1＝1×3＋0＝3，v2＝3×3＋2＝11，v3＝11×3＋3＝36，…．7．用秦九韶算法求多项式f(x)＝5x5＋3x3＋2x2＋10,当x＝3时f(x）的值为________．答案1324解析f（x)＝5x5＋0x4＋3x3＋2x2＋0x＋10＝(((（5x＋0）x＋3)x＋2)x＋0)x＋10＝(（(（5x）x＋3)x＋2）x）x＋10，当x＝3时，有v0＝5，v1＝5×3＝15，v2＝15×3＋3＝48，v3＝48×3＋2＝146，v4＝146×3＝438,v5＝438×3＋10＝1324，∴f(3)＝1324．8．用秦九韶算法求多项式f（x)＝1－5x－8x2＋10x3＋6x4＋12x5＋3x6当x＝－4时的值时，v0，v1，v2，v3，v4中最大值与最小值的差是________．答案62解析多项式变形为f(x)＝3x6＋12x5＋6x4＋10x3－8x2－5x＋1＝(（(((3x＋12）x＋6)x＋10）x－8)x－5）x＋1,v＝3，v＝3×（－4）＋12＝0,1v＝0×（－4）＋6＝6，2v＝6×(－4)＋10＝－14，3v＝－14×(－4）－8＝48，4∴v4最大，v3最小．∴v4－v3＝48－（－14)＝62．三、解答题9．利用秦九韶算法求多项式f（x)＝3x6＋12x5＋8x4－3．5x3＋7．2x2＋5x－13，当x＝6时的值，写出详细步骤．解f（x)＝((（（(3x＋12)x＋8)x－3．5)x＋7．2)x＋5)x－13，v＝3，v＝v0×6＋12＝30，1v＝v1×6＋8＝188，2v＝v2×6－3．5＝1124．5，3v＝v3×6＋7．2＝6754．2，4v＝v4×6＋5＝40530．2，5v＝v5×6－13＝243168．2．6f（6）＝243168．2．10．用秦九韶算法计算多项式f(x）＝5x7＋x6－x3＋x＋3当x＝－1时的值，并判断f(x)在区间[－1，0］内有没有零点．解∵f（x)＝5x7＋x6－x3＋x＋3＝((（(（(5x＋1)x＋0)x＋0）x－1)x＋0)x＋1)x＋3,∴当x＝－1时,v0＝5,v＝5×(－1）＋1＝－4，1v＝－4×（－1）＋0＝4，2v＝4×（－1）＋0＝－4,3v＝－4×(－1）－1＝3，4v＝3×(－1）＋0＝－3，5v＝－3×(－1)＋1＝4,6v＝4×(－1)＋3＝－1，7∴f（－1）＝－1．又f（0)＝3，∴f(0）·f(－1)<0，由零点存在定理，知f(x）在区间[－1,0]内有零点．尊敬的读者：本文由我和我的同事在百忙中收集整编出来，本文档在发布之前我们对内容进行仔细校对，但是难免会有不尽如人意之处，如有疏漏之处请指正，希望本文能为您解开疑惑,引发思考。

火柴游戏• 有红，绿，蓝三种颜色的火柴，所有火柴长度一样。

用它们可以组成一些数字， 如下图所示：•• 为了让组成的火柴好看一些，我们规定：有公共点的火柴必须不同色。

例如，用红火柴4根和蓝火柴3根可以组成数12，21，7等。

而且有些方案虽然数字和它们的排列顺序都相同，但是有颜色之分。

问：一共可以组成多少个数（可以包含多个数字，但至少包含一个数字）？同一个数用不同颜色表示算作不同的数，火柴可以有剩余。

• 输入• 三个整数n1， n2， n3 (0 ≤ n1，n2，n3 ≤ 15)，即三种颜色的火柴的数目。

• 输出• 仅一个数，即可以组成的数的数目。

结果保证不超过1016。

骑士游历问题设有一个n*m 的棋盘(2≤n ≤50，2≤m ≤50)，如下图。

在棋盘上任一点有一个中国象棋马，马走的规则为：1.马走日字2.马只能向右走。

即左图所示：当n ，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。

例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。

应输出2(即由(1，5)到(3，5)共有2条路径，如下图)：输入：n ，m ，x1，y1，x2，y2(分别表示n ，m ，起点坐标，终点坐标) 输出：路径数目(若不存在从起点到终点的路径，输出0)过河卒如图，A点有一个过河卒，需要走到目标B点。

卒行走的规则：可以向下、或者向右。

••同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

例如上图C点上的马可以控制8个点（图中的P1，P2….P8）。

卒不能通过对方马的控制点。

•棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：C≠A，同时C≠B）。

现在要求你计算出卒从A点能够到达B点的路径的条数。

•输入：•键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输出：•屏幕输出一个整数（路径的条数）。