有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单，于是就随机生成了两个方块的位置（可能相同），标记一下，标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被完全覆盖后才会进行标记。现在他想知道：如果标记前m*n的棋盘能被完全覆盖,标记后的棋盘是否能被完全覆盖?
第一行有一个整数t(1&=t&=100000),表示有t组测试数据。
每组测试数据有三行或一行。
第一行有两个整数 m,n（1&=m,n&=25535）表示行数和列数。
如果需要标记的话，第二、三行都有两个整数 a,b(1&=a&=m,1&=b&=n),表示行标和列标。
若标记前m*n的棋盘能被完全覆盖，则看标记后的棋盘是否能被完全覆盖，能则输出“YES”，否则输出“NO”；若标记前m*n的棋盘不能被完全覆盖则输出“NO”。
个人理解：
1：该棋盘中m,n中至少有一个是偶数才能完全覆盖
2：被标记的两个方块位置行列之和一个为奇数一个为偶数才能继续完全覆盖
C/C++
#include&stdio.h&
int main()
int t,m,n;
scanf(&%d&,&t);
while(t--)
scanf(&%d%d&,&m,&n);
if(m*n%2==0)//判断该棋盘是否能完全覆盖
int a,b,c,d;
scanf(&%d%d%d%d&,&a,&b,&c,&d);
if(((a+b)%2==0&&(c+d)%2!=0)||((a+b)%2!=0&&(c+d)%2==0))//判断棋盘被标记后能否继续被完全覆盖
printf(&YES\n&);
printf(&NO\n&);
printf(&NO\n&);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：300次
排名：千里之外棋盘覆盖问题 - mycapple - 博客园
路漫漫其修远兮，吾将上下而求索！
题目在线：
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 62, Accepted users: 26
Problem 10432 : No special judgement
Problem description
&&在一个2k x 2k ( 即：2^k x 2^k )个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
&&输入文件第一行是一个整数T,表示有多少组测试数据，接下来是T组测试数据，共2T行，每组第一行为整数n,是2的n次幂（1&=n&=64），表示棋盘的大小为n*n,第二行是两个整数，代表特殊方格所在行号和列号。
&&先输出&CASE:i，然后按样例输出。数据间用制表符隔开(&t&),每行最后一个数据后无制表符。
Sample Input
Sample Output
3&&&&&& 3&&&&&& 4&&&&&& 4&&&&&& 8&&&&&& 8&&&&&& 9&&&&&& 9
3 &&&&&&2&&&&&& 2&&&&&& 4&&&&&& 8&&&&&& 7&&&&&& 7&&&&&& 9
5&&&&&& 2&&&&&& 0&&&&&& 6&&&&&& 10&&&&& 10&&&&& 7&&&&&& 11
5&&&&&& 5&&&&&& 6&&&&&& 6&&&&&& 1&&&&&& 10&&&&& 11&&&&& 11
13&&&&& 13&&&&& 14&&&&& 1&&&&&& 1&&&&&& 18&&&&& 19&&&&& 19
13&&&&& 12&&&&& 14&&&& &14&&&&& 18&&&&& 18&&&&& 17&&&&& 19
15&&&&& 12&&&&& 12&&&&& 16&&&&& 20&&&&& 17&&&&& 17&&&&& 21
15&&&&& 15&&&&& 16&&&&& 16&&&&& 20&&&&& 20&&&&& 21&&&&& 21
Judge Tips
&&要求遍历顺序按从左到右，从上到下。
Problem Source
虽然这个问题已经在网上被讨论遍了，但是最近从新拾起算法，感觉有必要夯实一下基础。
棋盘覆盖问题：首先大致描述一下题目：在一个2^k&2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k&0,有4^k种不同的特殊棋盘.下图&图(1)中的特殊棋盘是当k=2时16个特殊棋盘中的一个：
题目要求在棋盘覆盖问题中,要用下图&图(2)所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.
思路分析：当k&0时,将2^k&2^k棋盘分割为4个2^k－1&2^k－1子棋盘,如下图&图(3)所示：
特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格.为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处。如下图&图(4)所示,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为1&1棋盘。
别人的代:1：
1 #include&iostream&
2 using namespace
3 int tile=1;
//L型骨牌的编号(递增)
4 int board[100][100];
5 /*****************************************************
6 * 递归方式实现棋盘覆盖算法
7 * 输入参数：
8 * tr--当前棋盘左上角的行号
9 * tc--当前棋盘左上角的列号
10 * dr--当前特殊方格所在的行号
11 * dc--当前特殊方格所在的列号
12 * size：当前棋盘的:2^k
13 *****************************************************/
14 void chessBoard ( int tr, int tc, int dr, int dc, int size )
if ( size==1 )
//棋盘方格大小为1,说明递归到最里层
int t=tile++;
//每次递增1
int s=size/2;
//棋盘中间的行、列号(相等的)
//检查特殊方块是否在左上角子棋盘中
if ( dr&tr+s && dc&tc+s )
chessBoard ( tr, tc, dr, dc, s );
//不在，将该子棋盘右下角的方块视为特殊方块
board[tr+s-1][tc+s-1]=t;
chessBoard ( tr, tc, tr+s-1, tc+s-1, s );
//检查特殊方块是否在右上角子棋盘中
if ( dr&tr+s && dc&=tc+s )
chessBoard ( tr, tc+s, dr, dc, s );
//不在，将该子棋盘左下角的方块视为特殊方块
board[tr+s-1][tc+s]=t;
chessBoard ( tr, tc+s, tr+s-1, tc+s, s );
//检查特殊方块是否在左下角子棋盘中
if ( dr&=tr+s && dc&tc+s )
chessBoard ( tr+s, tc, dr, dc, s );
//不在，将该子棋盘右上角的方块视为特殊方块
board[tr+s][tc+s-1]=t;
chessBoard ( tr+s, tc, tr+s, tc+s-1, s );
//检查特殊方块是否在右下角子棋盘中
if ( dr&=tr+s && dc&=tc+s )
chessBoard ( tr+s, tc+s, dr, dc, s );
//不在，将该子棋盘左上角的方块视为特殊方块
board[tr+s][tc+s]=t;
chessBoard ( tr+s, tc+s, tr+s, tc+s, s );
54 void main()
cout&&"输入棋盘的size(大小必须是2的n次幂): ";
int index_x,index_y;
cout&&"输入特殊方格位置的坐标: ";
cin&&index_x&&index_y;
chessBoard ( 0,0,index_x,index_y,size );
for ( int i=0; i& i++ )
for ( int j=0; j& j++ )
cout&&board[i][j]&&"/t";
别人代码2：
1 #include &iostream&
2 using namespace
3 const int N = 11;
4 int Board[N][N];
5 int tile = 0;
8 tr:棋盘左上角方格的行号
9 tc:棋盘左上角方格的列号
10 dr:特殊方格所在的行号
11 dc:特殊方格所在的列号
12 size:方形棋盘的边长
14 void ChessBoard(int tr, int tc, int dr, int dc, int size)
if(size == 1)
int t = ++tile, s = size/2;
//覆盖左上角子棋盘
if(dr&tr+s && dc&tc+s)
//特殊方格在此棋盘中
ChessBoard(tr, tc, dr, dc, s);
// 此棋盘无特殊方格
// 用t号L型骨型牌覆盖右下角
Board[tr+s-1][tc+s-1] =
// 覆盖其余方格
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
//覆盖右上角子棋盘
if(dr&tr+s && dc&=tc+s)
ChessBoard(tr, tc+s, dr, dc, s);
Board[tr+s-1][tc+s] =
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
//覆盖左下角子棋盘
if(dr&=tr+s && dc&tc+s)
ChessBoard(tr+s, tc, dr, dc, s);
Board[tr+s][tc+s-1] =
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
//覆盖右下角子棋盘
if(dr&=tr+s && dc&=tc+s)
ChessBoard(tr+s, tc+s, dr, dc, s);
Board[tr+s][tc+s] =
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
60 void DisplayBoard(int size)
for(int i=1; i&= ++i)
for(int j=1; j&= ++j)
printf("%2d ", Board[i][j]);
printf("\n");
70 int main()
ChessBoard(1, 1, 1, 2, 4);
DisplayBoard(4);
随笔 - 275当前位置： >>
算法分析与设计第4章
第四章 基本的算法策略4.1 4.2 4.3 4.4 4.5 4.6Computer Science & Technology School 日9时41分迭代算法 蛮力算法 分而治之算法 贪婪算法 动态规划 算法策略间的比较哈尔滨工业大学（威海） 哈尔滨工业大学（威海）<b
r />计算机科学与技术学院 共60页 第 1 页4.1迭代算法4.1.1 递推法 4.1.2 倒推法 4.1.3 迭代法解方程Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 2 页4.1.1 递推法【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔 子。小兔子到第三个月又开始生下一代小兔子。假若兔子 只生不死，一月份抱来一对刚出生的小兔子，问一年中每 个月各有多少只兔子。 问题分析：因一对兔子从出生后第三个月开始每月生一对小兔 子，则每月新下小兔子的对儿数(用斜体数字表示)显然由 前两个月的小兔子的对儿数决定。则繁殖过程如下： 一月 二月 三月 四月 五月 六月 …… 1 1 1+1=2 2+1=3 3+2=5 5+3=8 ……Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 3 页Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 4 页数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……。 算法1：main( ) { int i,a=1,b=1; print(a,b); for(i=1;i＜=10;i++) { c=a+b; print (c); a=b; b=c； } }哈尔滨工业大学（威海） 哈尔滨工业大学（威海） 计算机科学与技术学院 共60页 第 5 页Computer Science & Technology School 日9时41分算法2： 表4-1 递推迭代表达式 1 2 3 4 5 6 7 8 9 a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a+c …… 由此归纳出可以用“c=a+b; a=b+c; b=c+a;”做循环“不变式”。 算法2如下： main( ) 算法2，最后输出的 并不是12项，而是 { int i,a=1,b=1; 2+3*4共14项。 print(a,b); for(i=1; i＜=4;i++) { c=a+b; a=b+c; b=c+a; print(a,b,c); } }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 6 页【例2】求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。 设a&b且a/b=x...c；则a-bx=c，a、b的最大公约数也是c的 约数,则a、b的最大公约数与b、c的最大公约数相同。 b/c=x1...c1 =& b-cx1=c1 ……，直到余数为0时，除 数即为所求的最大公约数。 算法设计：循环“不变式”第一次是求a、b相除的余数c， 第二次还是求“a”“b” 相除的余数，经a=b,b=c操作，就实 现了第二次还是求“a”“b” 相除的余数，这就找到了循环不 变式。循环在余数c为0时结束。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 7 页算法如下：main（） { int a, input(a,b); if(b=0) {print(“data error”);} else { c = while（c&&0） { a=b; b=c; c=} } print(b); Computer } 哈尔滨工业大学（威海） 计算机科学与技术学院 Science & Technology School日9时41分哈尔滨工业大学（威海）第 8 页共60页4.1.2倒推法所谓倒推法：是对某些特殊问题所采用的违反通常习惯 的，从 后向前推解问题的方法。如下面的例题，因不同方 面的需求而采用了倒推策略。【例1】猴子吃桃问题 一只小猴子摘了若干桃子，每天吃现有桃的一半多 一个，到第10天时就只有一个桃子了，求原有多少个桃？ 数学模型：每天的桃子数为：a10=1, a9=(1+a10)*2, a8=(1+a9)*2,……a10=1，递推公式为： ai=(1+ai+1)*2 i= 9,8,7,6……1Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 9 页【例2】 输出如图4-1的杨辉三角形（限 定用一个一维数组完成）。 数学模型：上下层规律较明显，中间的数 等于上行左上、右上两数之和。 问题分析：题目中要求用一个一维数组即 完成。数组空间一定是由下标从小到大 利用的，这样其实杨辉三角形是按下图 4-2形式存储的。若求n层，则数组最多 存储n个数据。算法设计：A[1] = A[i]=1 A[j] = A[j] + A[j-1] i行 i-1行 i-1行Computer Science & Technology School 日9时41分1 1 1 1 1 3 2 3 1 1 14 6 4 1 …………… 图4-1 杨辉三角形j=i-1，i-2，……，21 1 1 1 2 1 1 3 3 1 1 4 6 4 ……………1图4-2 杨辉三角形存储格式哈尔滨工业大学（威海） 哈尔滨工业大学（威海） 计算机科学与技术学院 共60页 第 10 页算法如下：main( ) 1 1 1 2 1 {int n,i,j,a[100]; 1 3 3 1 input(n); 1 4 6 4 …………… print(“1”); print(“换行符”); a[1]=a[2]=1; print(a[1],a[2]); print(“换行符”); for (i=3;i&=n;i=i+1) {a[1]=a[i]=1; for (j=i-1;j&1;j=j-1) a[j]=a[j]+a[j-1]; for (j=1;j&=i;j=j+1) print(a[j]); print(“换行符”); } }Computer Science & Technology School 日9时41分11哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 11 页【例3】穿越沙漠问题 用一辆吉普车穿越1000公里的沙漠。吉普车的总 装油量为500加仑，耗油率为1加仑/公里。由于沙 漠中没有油库，必须先用这辆车在沙漠中建立临 时油库。该吉普车以最少的耗油量穿越沙漠，应 在什么地方建油库，以及各处的贮油量。问题分析： 1）先看一简单问题：有一位探险家用5天的时间徒步 横穿A、B两村，两村间是荒无人烟的沙漠，如果一 个人只能担负3天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 12 页A城雇用一人与探险家同带3天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险 家正好有3天的食物继续前行，并于第三天打电话雇B城 人带3天食物出发，第四天会面他们会面，探险家得到一 天的食物赴B城。如图4-3主要表示了被雇用二人的行程。AB图4-3 被雇用二人的行程2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为0。这样只 能从终点开始向前倒着推解贮油点和贮油量。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 13 页数学模型：根据耗油量最少目标的分析，下面从后 向前分段讨论。 第一段长度为500公里且第一个加油点贮油为500 加仑。 第二段中为了贮备油，吉普车在这段的行程必须 有往返。 下面讨论怎样走效率高： 1）首先不计方向这段应走奇数次 2）每次向前行进时吉普车是满载。 3）要能贮存够下一加油点的贮油量，路上耗油又 最少。 ……Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 14 页下图是满足以上条件的最佳方案，此段共走3次：第一、二 次来回耗油2/3贮油1/3，第三次耗油1/3贮油2/3，所以第 二个加油点贮油为1000加仑。由于每公里耗油率为1加仑， 则此段长度为500/3公里。 第三段与第二段思路相同。下图是一最佳方案此段共走5次： 第一、二次来回耗油2/5贮油3/5，第三、四次来回耗油 2/5贮油3/5，第五次耗油1/5贮油4/5，第三个加油点贮油 为1500加仑。此段长度为500/5。 ……500/5公里 &――― 500/3公里 ―――& &――― &――― 500公里 第一 ―――& 第二 ―――& 第三 终点&――贮油点（500）&――贮油点（1000）&―――贮油点（1500）…… 图4-4 贮油点及贮油量示意Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 15 页综上分析，从终点开始分别间隔 500，500/3， 500/5，500/7，……（公里）设立贮油点， 直到总距离超过1000公里。每个贮油点的 油量为500，，……。 算法设计：由模型知道此问题只需通过累加 算法就能解决。变量说明：dis表示距终点 的距离，1000- dis则表示距起点的距离， k表示贮油点从后到前的序号。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 16 页desert（ ） { int dis，k，oil,k; dis=500;k=1;oil=500; do{print(“storepoint”,k,”distance”,1000-dis,”oilquantity”,oil)；k=k+1; dis=dis+500/(2*k-1); oil= 500*k; }while ( dis&1000) oil=500*(k-1)+(1000-dis)*( 2*k-1);print(“storepoint”,k,”distance”,0,”oilquantity”,oil)；}Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 17 页4.1.3迭代法解方程迭代法解方程的实质是按照下列步骤构造一个序列x0,x1,…,xn,来 逐步逼近方程f(x)=0的解： 1）选取适当的初值x0； 2）确定迭代格式，即建立迭代关系，需要将方程f(x)=0改 写为x=φ (x)的等价形式；构造序列x0，x1，……，xn，即先求得x1=φ (x0)，再求x2=φ (x1)，……如此反复迭代，就得到一个数列x0， x1，……，xn，若这个数列收敛，即存在极值，且函数 φ (x)连续，则很容易得到这个极限值x*就是方程f(x)=0的根。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 18 页【例1】迭代法求方程组根 算法说明：方程组解的初值X=（x0，x1，?，xn-1）,迭代 关系方程组为：xi=gi(X)(i=0,1,?,n-1),w为解的精度,则 算法如下： for (i=0;i&n;i++) x[i]=初始近似根; do { k=k+1; for (i=0;i&n;i) y[i]=x[i]; for (i=0;i&n;i++) x[i]=gi(y[i]); for (i=0;i&n;i++) c=c+fabs(y[i]-x[i])； } while (c&w and k&maxn )； for (i=0;i&n;i++) print(i，“变量的近似根是”，x[i])； }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 19 页【例2】牛顿迭代法 牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度， 如图4-5所示。首先, 选择一个接近函数f(x)零点的x0, 计算相应 的f(x0)和切线斜率f?(x0)（这里f ?表示函数f的导数）。然后我 们计算穿过点(x0,f (x0))且斜率为f ?(x0)的直线方程为：y ? f ( x0 ) ? f ?( x0 )(x ? x0 )和x轴的交点的x坐标, 也就是求如下方程的解：f ( x0 ) ? f ?( x0 )(x ? x0 ) ? 0将新求得交点的x坐标命名为x1。如图4-5所示，通常x1会比x0更接近方程f(x) = 0的解。接下来用x1开始下 一轮迭代 .Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）图4-5 牛顿迭代法 示意图 计算机科学与技术学院 共60页 第 20 页迭代公式可化简为： 此公式就是有名的牛顿迭代公式。已经证明, 如果f?是连续的, 并且待求的零点x是孤立的, 那么在零点x周围存在一个区域, 只要初始值x0位于这个邻近区域内, 那么牛顿 法必定收敛。 下面给出用牛顿迭代法，求形如ax3+bx2+cx+d=0方程根的 算法，系数a、b、c、d的值依次为1、2、3、4，由主函数 输入。求x在1附近的一个实根。求出根后由主函数输出。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 21 页float f(a,b,c,d) main( ) float a,b,c,d; { float a , b, c, d, print(& 输 入 系 数 { float x1=1 , x0, f0 , f1; a,b,c,d:&); do input(a,b,c,d); { x0=x1; fx=f(a,b,c,d); f0=((a*x0+b)*x0+c)*x0+d; printf(&方程的根为： &,fx); f1=(3*a*x0+2*b)*x0+c; } x1=x0-f0/f1; } while(fabs(x1-x0)&=1e-4);return(x1); }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 22 页【例3】二分法求解方程f(x)=0根 用二 分法求解方程f(x)=0根的前提条件是： f(x)在求解的区间[a,b]上是连续的，且 已知f(a)与f(b)异号，即f(a)*f(b)&0。令[a0,b0]=[a,b]，c0=(a0+b0)/2，若f(c0)=0，则c0为 方 程 f(x)=0 的 根 ； 否 则 ， 若 f(a0) 与 f(c0) 异 号 ， 即 f(a0)*f(c0)&0，则令[a1,b1]=[a0,c0]；若f(b0)与f(c0)异 号，即 f(b0)*f(c0)&0，则令[a1,b1]=[c0,b0]。 依此做下去，当发现f(cn)=0时，或区间[an,bn]足 够小，比如| an-bn |&0.0001时，就认为找到了方程的根。 用二分法求一元非线性方程f(x)= x^3/2+2x^2-8=0（其中 ^表示幂运算）在区间[0，2]上的近似实根r，精确到0.0001. 算法如下：Computer Science & Technology School 日9时41分图4-6 二分法求解 方程示意哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 23 页main( ) { float x,x1=0,x2=2,f1,f2,f; print(“input a,b (f(a)*f(b)&0)”); input(x1,x2); f1=x1*x1*x1/2+2*x1*x1-8; f2=x2*x2*x2/2+2*x2*x2-8; if(f1*f2&0) { printf(&No root&);} do { x=(x1+x2)/2; f=x*x*x/2+2*x*x-8; if(f=0) if(f1*f&0.0) {x1=x; f1=x1*x1*x1/2+2*x1*x1-8;} else x2=x; }while(fabs(f)&=1e-4); print(&root=&,x); }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 24 页4.2 蛮力法基础：计算机运算速度快实例：选择排序、冒泡排序、插入排序、顺序查 找、朴素的字符串匹配、枚举法、盲目搜索算法? 枚举法 ? 其它范例Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 25 页4.2.1枚举法枚举（ enumerate）法（穷举法）根据问题 中的条件将可能的情况一一列举出来，逐一尝 试从中找出满足问题条件的解。枚举法设计的两个方面：1）找出枚举范围：分析问题所涉及的各种情况。 2）找出约束条件：分析问题的解需要满足的条 件，并用逻辑表达式表示。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 26 页【例1】百钱百鸡问题。中国古代数学家张丘建在他的 《算经》中提出了著名的“百钱百鸡问题”：鸡翁一， 值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百 鸡，翁、母、雏各几何? 算法设计1： 设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公 鸡最多买100/5=20只，显然x的取值范围1~20之间；同 理，y的取值范围在1~33之间，z的取值范围在1~100之 间。约束条件： x+y+z=100 且 5*x+3*y+z/3=100Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 27 页算法1如下： main( ) { int x,y,z; for(x=1;x&=20;x=x+1) for(y=1;y&=34;y=y+1) for(z=1;z&=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) { print(the cock number is&,x)； print(the hen number is&, y)； print(the chick number is &z); } } 算法分析：以上算法需要枚举尝试20*34*100=68000次。 算法的效率显然太低Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 28 页算法设计2： 在公鸡（x）、母鸡（y）的数量确定后，小鸡 的数量 z就固 定为100-x-y，无需再进行枚举了。 此时约束条件只有一个： 5*x+3*y+z/3=100 算法2如下：main( ) { int x,y,z; for(x=1;x&=20;x=x+1) for(y=1;y&=33;y=y+1) { z=100-x-y; if(z mod 3=0 and 5*x+3*y+z/3=100) { print(the cock number is&,x)； print(the hen number is&, y)； print(the chick number is &z);} } 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定 Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的 算术计算和条件判断，进一步提高了算法的效率。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 29 页【例2】解数字迷：A B C A B × A D D D D D D 算法设计1：按乘法枚举 1)枚举范围为： A：3――9（A=1，2时积不会得到六位数）,B：0――9, C：0――9 六位数表示为A*10000+B*1000+C*100+A*10+B， 共尝试700次。 2)约束条件为： 每次尝试，先求六位数与A的积，再测试积的各位是否符合 条件，若符合则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始， 每次都取数据的个位，然后整除10，使高位的数字不断变 成个位，并逐一比较。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 30 页算法1如下： main（ ） { int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A&=9; A++) for(B=0; B&=9; B++) for(C=0; C&=9; C++) { F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i&=5; i++) { G2=G1; E1=E1/10; G1= E1 mod 10; if(G1&&G2 ) } if(i=6) print( F，”*”，A，”=”，E); } } ComputerScience & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 31 页算法说明1：算法中对枚举出的每一个五位数与A相乘，结果 存储在变量E中。然后，测试得到的六位数E是否各个位的数 字都相同。鉴于要输出结果，所以不要改变计算结果，而另 设变量E1，用于测试运算。 算法分析1：以上算法的尝试范围是A：3――9，B：0――9， C：0――9 。共尝试700次，每次，不是一个好的算法。 算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时 只需枚举A：3――9 D：1――9，共尝试7*9=63次。每次 尝试，测试商的万位、十位与除数是否相同，千位与个位 是否相同，都相同时为解。 算法2如下:Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 32 页main（）{int A,B,C,D,E,F; for(A=3;A&=9;A++)for(D=1;D&=9;D++){ E = D*100000+D*10000+D*1000+D*100+D*10+D; if(E mod A=0) F=E\A; if(F\10000=A and (F mod 100)\10=A) if(F\1000 mod 10 =F mod 10)print( F，”*”，A，”=”，E);} }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 33 页4.2.2【例3】狱吏问题其它范例某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n 间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n 次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每 一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开 始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转 动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然 是打开的？Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 34 页算法设计1： 1）用n个空间的一维数组a[n],每个元素记录一个锁的状 态，1为被锁上，0为被打开。 2）用数学运算方便模拟开关锁的技巧，对i号锁的一次开 关锁可以转化为算术运算：a[i]=1-a[i]。 3）第一次转动的是1，2，3，……，n号牢房； 第二次转动的是2，4，6，……号牢房； 第三次转动的是3，6，9，……号牢房； ……第i次转动的是i，2i，3i，4i，……号牢房，是起 点为i，公差为i的等差数列。 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第i号牢房对应的数组元素a[i]为0时， 该牢房的囚犯得到大赦。算法1如下：Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 35 页main1( ) {int *a,i,j,n; input(n); a=calloc(n+1,sizeof(int)); for (i=1; i&=n;i++) a[i]=1; for (i=1; i&=n;i++) for (j=i; j&=n;j=j+i) a[j]=1-a[j]; for (i=1; i&=n;i++) if (a[i]=0) print(i,”is free.”); } 算法分析：以一次开关锁计算，算法的时间复杂度为 n(1+1/2+1/3+……+1/n)=O(nlogn)。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 36 页问题分析：转动门锁的规则可以有另一种理解，第一次转动 的是编号为1的倍数的牢房；第二次转动的是编号为2的倍 数的牢房；第三次转动的是编号为3的倍数的牢房；…… 则狱吏问题是一个关于因子个数的问题。令d(n)为自然数 n的因子个数，这里不计重复的因子，如4的因子为1，2， 4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有 的为偶数，见下表:n d(n) 1 1 2 2 3 2表4-3 编号与因数个数的关系 4 5 6 7 8 9 10 11 12 3 2 4 2 4 3 4 2 613 214 15 4 416 …… 5 ……数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于 牢房的门开始是关着的，这样编号为i的牢房，所含1―― i之间的不重复因子个数为奇数时，牢房最后是打开的， 反之，牢房最后是关闭的。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 37 页算法设计2: 1）算法应该是求出每个牢房编号的不重复的因子个数，当它 为奇数时，这里边的囚犯得到大赦。 2）一个数的因子是没有规律的，只能从1――n枚举尝试。算 法2如下： main2( ) {int s,i,j,n; input(n); for (i=1; i&=n;i++) { s=1; for (j=2; j&=i;j=j++) if （i mod j=0） s=s+1; if （s mod 2 =1） print(i,”is free.”); } }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 38 页算法分析：狱吏开关锁的主要操作是a[i]=1- a[i];共执行 了n*(1+1/2+1/3+……+1/n)次，时间近似为复杂 度为O（n log n）。使用了n个空间的一维数组。 算法2没有使用辅助空间，但由于求一个编号的因 子个数也很复杂，其主要操作是判断i mod j是 否为0，共执行了n*(1+2+3+……+n)次，时间复杂 度为O（n2）。 数学模型2：仔细观察表4-3，发现当且仅当n为完 全平方数时,d(n)为奇数；这是因为n的因子是成 对出现的,也即当n=a*b且a≠b时，必有两个因子a， 只有n为完全平方数，也即当n=a2 时, 才会出 现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数 即可。算法3如下：Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 39 页main3( ){ int s,i,j,n; input(n);for (i=1;i&=n;i++)if（i*i&=n） print(i,” } 由此算法我们应当注意：在对运行效率要求较高的大规模 的数据处理问题时，必须多动脑筋找出效率较高的数学模型 及其对应的算法。Computer Science & Technology School 日9时41分free.”);哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 40 页4.3? ? ? ?分而治之算法分治算法框架 二分法 二分法变异 其它分治方法Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 41 页4.3.11．算法设计思想分治算法框架将整个问题分解成若干个小问题后分而治之。如果 分解得到的子问题相对来说还太大，则可反复使用分治策 略将这些子问题分成更小的同类型子问题，直至产生出方 便求解的子问题，必要时逐步合并这些子问题的解，从而 得到问题的解。三个步骤：1）分解； 2）解决； 3）合并。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 42 页2．适合用分治法策略的问题 满足分治法解决问题的条件： 1） 能将这n个数据分解成k个不同子集合，且得到k个子 集合是可以独立求解的子问题，其中1＜k≤n； 2） 分解所得到的子问题与原问题具有相似的结构，便 于利用递归或循环机制； 在求出这些子问题的解之后，就可以推解出原问题的解Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 43 页分治法的一般的算法设计模式如下： Divide-and-Conquer(int n) /n为问题规模/{if（n≤n0） { 解子问题；return(子问题的解)；}/n0 为可解子问题的规模//*分解为较小子问题p1,p2,……pk*/for （i=1 ;i&=k;i++） yi=Divide-and-Conquer(|Pi|); /递归解决Pi/ T =MERGE(y1,y2,...,yk); /合并子问题/ return(T); }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 44 页4.3.2二分法当每次都将问题分解为原问题规模的一半时，称为二 分法。二分法是分治法较常用的分解策略，数据结构课程中 的折半查找、归并排序等算法都是采用此策略实现的。 【例1】金块问题： 老板有一袋金块(共n块)，最优秀的雇员 得到其中最重的一块，最差的雇员得到其中最轻的一块。假 设有一台比较重量的仪器，我们希望用最少的比较次数找出 最重的金块。 算法设计1：比较简单的方法是逐个的进行比较查找。先拿 两块比较重量，留下重的一个与下一块比较，直到全部比较 完毕，就找到了最重的金子。算法类似于一趟选择排序Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 45 页算法如下： maxmin( float a[],int n) { max=min=a[1]; for(i=2 i&=n i++ ) if(max & a[i]) max=a[i]; else if(min & a[i]) min=a[i];}算法分析1：算法中需要n-1次比较得到max。最好的情 况是金块是由小到大取出的，不需要进行与min的比较， 共进行n-1次比较。最坏的情况是金块是由大到小取出的， 需要再经过n-1次比较得到min,共进行2*n-2次比较。至于 在平均情况下，A(i)将有一半的时间比max大，因此平均 比较数是3(n―1)/2。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 46 页算法设计2:问题可以简化为：在含n（n是2的幂（n&=2）） 个元素的集合中寻找极大元和极小元。用分治法（二分法） 可以用较少比较次数地解决上述问题： 1） 将数据等分为两组（两组数据可能差1），目的是分 别选取其中的最大（小）值。 2）递归分解直到每组元素的个数≤2，可简单地找到最 大（小）值。 3）回溯时将分解的两组解大者取大，小者取小，合并 为当前问题的解。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 47 页算法2 递归求取最大和最小元素 float a[n]; maxmin （int i, int j ,float &fmax, float &fmin） { float lmax, lmin, rmax, if (i=j) {fmax= a[i]; fmin=a[i];} else if (i=j-1) if(a[i]&a[j]) { fmax=a[j]；fmin=a[i];} else { fmax=a[i]; fmin=a[j];} else { mid=(i+j)/2; maxmin（i，mid，lmax，lmin）; maxmin（mid+1，j，rmax，rmin）; if(lmax&rmax) fmax= else fmax= if(lmin&rmin)fmin= else fmin= }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 48 页算法分析：MAXMIN需要的元素比较数是多少呢？如果用T(n) 表示这个数，则所导出的递归关系式是:当n是2的幂时，即对于这个某个正整数k，n=2k，有可以证明，任何以元素比较 为基础的找最大和最小元素 的算法，其元素比较下界均为次。 因此，过程MAXMIN在这种意 义上是最优的。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 49 页【例2】残缺棋盘 残缺棋盘是一个有2k×2k （k≥1）个方格的棋盘，其中恰有 一个方格残缺。图4-7给出k=1时各种可能的残缺棋盘，其 中残缺的方格用阴影表示。①号②号 图4-7 四种三格板③号④号这样的棋盘我们称作“三格板”，残缺棋盘问题就是要用这 四种三格板覆盖更大的残缺棋盘。在此覆盖中要求： 1）两个三格板不能重叠 2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格 在这种限制条件下，所需要的三格板总数为(2k×2k -1 )/3。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 50 页算法设计1：分而治之方法解决残缺棋盘问题 1）问题分解过程如下： s=size/2①号 ②号③号④号k=1，2，3，4……都是如此，k=1为停止条件。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 51 页2）棋盘的识别 棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上 角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺 方格或“伪”残缺方格直接用行、列号记录。 ? tr 棋盘中左上角方格所在行。 ? tc 棋盘中左上角方格所在列。 ? dr 残缺方块所在行。 ? dc 残缺方块所在列。 ? size 棋盘的行数或列数。 数据结构设计：用二维数组board[ ][ ]，模拟棋盘。覆盖 残缺棋盘所需要的三格板数目为：( size2 -1 ) / 3 将这些三格板编号为1到( s i z e2-1 ) / 3。则将残缺棋 盘三格板编号的存储在数组board[ ][ ]的对应位置中，这 样输出数组内容就是问题的解。结合图4-9，理解算法。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 52 页图4-9 一个4*4的残缺棋盘及其解算法如下： int amount=0; main（ ） { int size=1,x,y; input(k); for (i=1;i&=k;i++) size=size*2; print(“input incomplete pane ”); input(x,y); Cover(0, 0, x, y, size); } ComputerScience & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 53 页Cover(int tr, int tc, int dr, int dc, int size) { if (size&2) int t = amount ++, // 所使用的三格板的数目 s=size/2; // 子问题棋盘大小 //残缺方格位于左上棋盘 if (dr & tr + s && dc & tc + s) ｛Cover ( tr, tc, dr, dc, s); Board[tr + s - 1][tc + s] = // 覆盖１号三格板 Board[tr + s][tc + s - 1] = Board[tr + s][tc + s] = Cover (tr, tc+s, tr+s-1, tc+s, s); // 覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); ｝Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 54 页else if(dr & tr + s && dc &= tc + s) //残缺方格位于右上象限 ｛Cover ( t r, tc+s, dr, dc, s); Board[tr + s - 1][tc + s - 1] = // 覆盖２号三格板 Board[tr + s][tc + s - 1] = Board[tr + s][tc + s] = Cover (tr, tc, tr+s-1, tc+s-1, s); //覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s);}//残缺方格位于覆盖左下象限else if (dr &= tr + s && dc & tc + s) ｛ Cover(tr+s, tc, dr, dc, s); Board[tr + s - 1][tc + s - 1] = // 覆盖３号三格板 Board[tr + s - 1][tc + s] = Board[tr + s][tc + s] = Cover (tr, tc, tr+s-1, tc+s-1, s); //覆盖其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc+s, tr+s, tc+s, s); ｝Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 55 页// 残缺方格位于右下象限else if (dr &= tr + s && dc &= tc + s) ｛Cover(tr+s, tc+s, dr, dc, s); Board[tr + s - 1][tc + s - 1] = // 覆盖４号三格板 Board[tr + s - 1][tc + s] = Board[tr + s][tc + s - 1] = Cover (tr, tc, tr+s-1, tc+s-1, s); //覆盖其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc, tr+s, tc+s-1, s); ｝ } void OutputBoard(int size) { for (int i = 0; i & i++) { for (int j = 0; j & j++) print( Board[i][j]); 算法分析：因为要覆盖 print(“换行符”); } (size2 -1)/ 3个三格板， 所以算法的时间复杂性 }为Ｏ（size2）。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 56 页4.3.3二分法变异【例4】大整数乘法 在某些情况下，我们需要处理很大的整数，它无法在计 算机硬件能直接允许的范围内进行表示和处理。若用浮 点数来存储它，只能近似地参与计算，计算结果的有效 数字会受到限制。若要精确地表示大整数，并在计算结 果中要求精确地得到所有位数上的数字，就必须用软件 的方法来实现大整数的算术运算。请设计一个有效的算 法，可以进行两个n位大整数的乘法运算。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 57 页数据结构设计：首先用数组存储大整数数 据，再将两个乘数和积都按由低位到高位 逐位存储到数组元素中。 算法设计1：存储好两个高精度数据后，模 拟竖式乘法，让两个高精度数据的按位交 叉相乘，并逐步累加即可得到精确的结果 ，用二重循环就可实现。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 58 页算法设计1：存储两个高精度数据，模拟竖式乘法，让两个 高精度数据的按位交叉相乘，并逐步累加，即可得到精确的 计算结果。用二重循环就可控制两个数不同位相乘的过程。 只考虑正整数的乘法，算法细节设计如下： 1) 按字符型处理，存储在字符串数组s1、s2中，计算结果 存储在整型数组a中。 2)通过字符的ASCII码，数字字符可以直接参与运算，k位 数字与j位数字相乘的表达式为：(s1[k]-48)*(s2[j]48)。 3)每一次数字相乘的结果位数是不固定的，而结果数组中每 个元素只存储一位数字，所以用变量b暂存结果，若超过1位 数则进位，用变量d存储。这样每次计算的表达式为： b= a[i]+(s1[k]-48)*(s2[j]-48)+d。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 59 页main( ) { long b,c,d; int i,i1,i2,j,k,n,n1,n2,a[256]; char s1[256],s2[256]; input(s1); input(s2); for (i=0;i&255;i++) a[i]=0; n1=strlen(s1); n2=strlen(s2); d=0; for (i1=0,k=n1-1;i1&n1;i1++,k--) { for (i2=0,j=n2-1;i2&n2;i2++,j--) { i=i1+i2;b=a[i]+(s1[k]-48)*(s2[j]-48)+d; a[i]= b mod 10;d=b/10;} while (d&0) { i=i+1; a[i]=a[i]+d mod 10; d=d/10;} n=i; } for (i=n;i&=0;i--) print(a[i]); }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 60 页算法说明：循环变量j、k分别是两个乘数字符串的下标。i1 表示字符串str1由低位到高位的位数，范围0――n1-1（与k 相同）。i2表示字符串str2由低位到高位的位数，范围0―― n2-1（与j相同）。i表示乘法正在运算的位，也是计算结果 存储的位置。 算法分析1：算法是以n1,n2代表两个乘数的位数，由算法中的循 环嵌套知，算法的主要操作是乘法，算法的时间复杂度是O （n1*n2）。 算法设计2：下面们用分治法来设计一个更有效的大整数乘积算 法。设计的重点是要提高乘法算法的效率，设计如下： 设X和Y都是n位的二进制整数，现在要计算它们的乘积X*Y。图4-10Computer Science & Technology School 日9时41分大整数X和Y的分段计算机科学与技术学院 共60页 第 61 页哈尔滨工业大学（威海） 哈尔滨工业大学（威海）将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简 单起见，假设n是2的幂)，如图4-10所示。显然问题的答案并不 是A*C*K1+C*D*K2（K1、K2与A、B、C、D无关），也就是说，这 样做并没有将问题分解成两个独立的子问题。按照乘法分配律， 分解后的计算过程如下： 记：X=A*2n/2+B ，Y=C*2n/2+D。这样，X和Y的乘积为： X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D (1) 模型分析： 如果按式(1)计算X*Y，则我们必须进行4次n/2位整数的乘法 (AC，AD，BC和BD)，以及3次不超过n位的整数加法，此外还要 做2次移位 (分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和 移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总 数，则由式(1)，我们有以下(2)式：Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 62 页T（1）=1 T（n）=4T(n/2)+O(n) （2） 由此递归式迭代过程如下： T(n)=4T(n/2)+cn =4(4T(n/22)+cn/21)+cn =42(T(n/23)+ cn/22)+41cn/21+cn =…… =4 k+4k-1 *2c+4k-2 *4c+……+4c2k-1+c2k =O（4k）= O(nlog4) =O（n2） 所以可得算法的时间复杂度为T(n)=O(n2)。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 63 页模型改进： X*Y=A*C*2n+[(A-B)(D-C)+AC+BD]*2n/2+B*D (3) 式(3)看起来比式(1)复杂，但它仅需做3次n/2位整数的乘法： AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得: (4) 用解递归方程的迭代公式法，不妨设n=2k： T(n)=3T(n/2)+cn =3(3T(n/4)+cn/2)+cn =9(T(n/8)+ cn/4)+3cn/2+cn =…… =3k +3k-1 *2c+3k-2 *4c+……+3c2k-1+c2k = O(nlog3) 则得到T(n)=O(nlog3)=O(n1.59)。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 64 页MULT(X,Y,n) {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY} { S=SIGN(X)*SIGN(Y); //S为X和Y的符号乘积 X=ABS(X); Y=ABS(Y); //X和Y分别取绝对值 if（ n=1） if (X=1 and Y=1) return(S)； else return(0)；else{ A=X的左边n/2位; B=X的右边n/2位; C=Y的左边n/2位; D=Y的右边n/2位; ml=MULT(A,C,n/2); m2=MULT(A-B,D-C,n/2); m3=MULT(B,D,n/2); S=S*(m1*2n+(m1+m2+m3)*2n/2+m3); return(S); }Computer Science & Technology School 日9时41分}哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 65 页【例３】求数列的最大子段和。给定n个元素的整数列（可 能有负整数）a1,a2,?? n，求形如： ?,a ai,ai+1,?? j i,j=1,2,?? ?,a ?,n, i&=j 的子段和，使其为最大。当所有整数均为负整数时定义其最 大字段和为0。 如(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时最大子段 和为： 算法设计：此问题用二分法分解后的两个子序列（子问题） 并不独立，因为有可能最长的连续不升数列正好存在于两 个子序列的连接位置。 如果将所给的序列a[1..n]分为长度相等的2段 a[1――(n/2)]和a[(n/2)+1――n],则a[1.n]的最长连续不 升数列有3种情况：Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 66 页如 果 将 所 给 的 序 列 a[1..n] 分 为 长 度 相 等 的 2 段 a[1―― (n/2)]和a[(n/2)+1――n],分别求出这2段的最大子段和,则 a[1.n]的最大子段和有3种情形。 1）a[1..n]的最大子段和与a[1..(n/2)]的最大子段和相同; 2) a[1..n]的最大子段和与a[(n/2)+1..n]的最大子段和相同; 3) a[1..n]的最大子段和为∑a[k],a[i..j]且 1≤i≤(n/2),(n/2),(n/2)+1≤j≤n。情况1）和情况2）可分别递归求得。 对于情况3）,a[(n/2)]与a[(n/2)+1]一定在最优子序列中。 因此,我们可以计算出a[i..(n/2)]的最大值s1;并计算出 a[(n/2)+1..j]中的最大值s2。则s1+s2即为出现情况3)时 的最优值。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 67 页算法如下： int max_sum3(int a[ ],int n) {return(max_sub_sum(a,1,n));} max_sub_sum(int a[ ], int left, int right) {int center,i,j,sum,left_sum,right_sum,s1,s2,lefts, if (left=right) if (a[left]&0) return(a[left]) ; else return(0); else { center=(left+right)/2; left_sum=max_sub_sum(a,left,center); right_sum=max_sub_sum(a,center+1,right); s1=0; lefts=0;Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 68 页for (i=i&=i--) { lefts=lefts+a[i]; if( lefts&s1) s1=} s2=0; rights=0; for( i=center+1;i&=i++) { rights=rights+a[i]; if ( rights&s2) s2=} if (s1+s2&left_sum and right_sum&left_sum) rturn(left_sum); if (s1+s2&right_sum) return(right_sum); return(s1+s2); } }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 69 页4．3．4非等分二分法【例5】选择问题0其它分治方法求一组数的第二小的数。float a[n]; second（int i, int j，float &fmin2, &fmin1） { float lmin2,lmin1,rmin2,rmin1; if（i=j）fmin2=fmin1=a[i] else if (i=j-1) if(a[i]&a[j]) { fmin2=a[j]；fmin1=a[i];} else{fmin2=a[i]; fmin1=a[j];} else { mid=(i+j)/2; second（i，mid，lmin2，lmin1）; second（mid+1，j，rmin2，rmin1）;Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 70 页if (lmin1&rmin1) if （lmin2&rmin1） { fmin1=lmin1; fmin2=lmin2;} else {fmin1=lmin1; fmin2=rmin1;} elseif( rmin2&lmin1) {fmin1=rmin1; fmin2=rmin2;}else } }{fmin1=rmin1; fmin2=lmin1;}算法分析：此算法的时间复杂度与【例1】相同，为O（n）。Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 71 页【例6】选择问题： 对于给定的n 个元素的数组a[0:n-1]，要求 从中找出第k小的元素。 问题分析：选择问题的一个应用就是寻找中值元素，此时 k=[n/2]。 算法设计： 本题可以对全部数据进行排序后，找出问题的解。 用较好的排序方法，算法的复杂性为O( nlogn )。 可以通过改写快速排序算法来解决选择问题，一趟排序分解出 的左子集中元素个数nleft,可能是以下几种情况： 1） nleft=k-1，则分界数据就是选择问题的答案。 2） nleft&k-1，则选择问题的答案继续在左子集中找，问 题规模变小了。 3） nleft&k-1，则选择问题的答案继续在右子集中找，问 题变为选择第k-nleft-1小的数，问题的规模也变小Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 72 页xzwt(int a[ ], int n, int k ) { if (k & 1 || k & n) error(); return select(a, 0, n-1, k); } /在a [ left : right ]中选择第k小的元素/ select(int a[],int left,int right,int k) { int i,j, if (left &= right) return a[left]; i = left-1; //从左至右的指针 j = right + 1; // 从右到左的指针 pivot = a[left+1]; //把最左面的元素作为分界数据 while (1) { do { // 在左侧寻找&= pivot 的元素 i = i + 1; } while (a[i] & pivot);Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 73 页do {j = j - 1;} while (a[j] & pivot); if (i &= j) // 未发现交换对象 Swap(a[i], a[j]); } if (j-left+1=k) a[left] = a[j]; // 设置p i v o t a[j] = if (j-left+1&k) // 对一个段进行递归调用 return select(a,j+1,right,k-j-1+left); else return select(a,left,j-1,k); }Computer Science & Technology School 日9时41分哈尔滨工业大学（威海） 哈尔滨工业大学（威海）计算机科学与技术学院 共60页 第 74 页算法分析： 1）以上算法在最坏情况下的复杂性是O( n2 )，此时left 总是为 空，而且第k个元素总是位于 right子集中。 2）如果假定n是2的幂，通过迭代方法，可以得到算法的平均复杂 性是O (n)。若仔细地选择分界元素，则最坏情况下的时间开销 也可以变成(n)。一种选择分界元素的方法是使用“中间的中间 （m e d i a n - o f - m e d i a n）”规则，该规则首先将 数组a中的n 个元素分成n/r 组，r 为某一整常数，除了最后一 组外，每组都有r 个元素。然后通过在每组中对r 个元素进行排 序来寻找每组中位于中间位置的元素。最后根据所得到的n/r 个 中间元素，递归使用选择算法，求得所需要的分界元素。这里不 深入讨论。 3）注意到这个算法实质上只是利用了分治法的分解策略，分解后 根据不同情况，只处理其中的一个子问题，并没有象【例1】一 Computer 样有回溯合并的过程。 哈尔滨工业大学（威海） 计算机科学与技术学院 Science & Technology School日9时41分哈尔滨工业大学（威海）第 75 页共60页