博文
算法设计之分治法(3)(2007-10-09 10:51:00)
摘要：例5 比赛安排（1996年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题）
设有2^n（n<=6）个球队进行单循环比赛，计划在2^n-1天内完成，每个队每天进行一场比赛，设计一个比赛安排，使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为：
队
1
2
3
4
时间
比赛
1 – 2
3 – 4
第一天
1 – 3
2 – 4
第二天
1 – 4
2 – 3
第三天
分析：已知参加比赛的球队数x(x=2^n)，要设计一个比赛安排表。分析题目要求（单循环比赛的比赛规则），我们可以归纳出比赛安排表必须满足的条件：
①球赛需要在x-1天内完成。
②每个球队每天有且只能有一场比赛。
③任意两个球队必须进行过一场比赛，并且只能进行一场比赛。
当只有两个球队进行比赛时，比赛安排表的设计非常简单，只要让两个球队直接进行一场比赛就可以了。当不止两个球队时，我们可以将所有的球队分成两半。x个球队的比赛安排表就可以通过x/2个球队的比赛安排表来产生。这样递归地使用这种一分为二的方法对球队进行分割，直到只剩下两个球队。
日期\球队
1
2
3
4
5
6
7
8
2
2
1
4
3
6
5
8
7
3
3
4
1
2
7
8
5
6
4
4
3
2
1
8
7
6
5
5
5
6
7
8
1
2
3
4
6
6
5
8
7
2
1
4
3
7
7
8
5
6
3
4
1
2
8
8
7
6
5
4
3
2
1
如图，是一张8个球队的比赛安排表。其中第i行与第j列相交的数字a(i,j)表示第j个球队在第i-1天所遇到的对手。（表的第一行为8个球队的编......
算法设计之分治法(2)(2007-10-09 10:50:00)
摘要：经典示例
例1 最大最小问题：老板有一袋金块，共n块。将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重和最轻的金块。
算法分析：这个问题可以转化一个具有n个元素的数组里，寻找最大和最小元素问题。
一般算法是遍历数组，依次将每个元素和当前最大，最小值判断，直至遍历数组结束，返回最大，最小值。
void MaxMin(int a[], int n, int *max, int *min)
{
int i = 0;
*max = *min = a[0];
for (i=1; i<n; i++)
{
if (a[i] < *min)
*min = a[i];
if (a[i] > *max)
*max = a[i];
}
}
很清楚，在输入规模为n时，这个算法所执行的元素比较次数是2n-2。用分治法可以较少比较次数地解决上述问题：
如果集合中只有1个元素，则它既是最大值也是最小值；
如果有2个元素，则一次Max(i,j)，一次Min(i,j)就可以得到最大值和最小值；
如果有多于2个元素，则把集合分成两个规模相当子集合，递归的应用这个算法分别求出两个子集合的最大值和最小值，最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值；让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。
void MaxMin2(int ......
算法设计之分治法(1)(2007-10-09 10:47:00)
摘要：引言
说到分治算法，最容易想到的例子是在数组中查找元素，常用的算法是遍历整个数组进行查找，算法时间复杂度为O（n）；但是对于有序数组，使用二分查找法，可以使时间复杂度减少到O（logn）。
普通查找法：
int IsElement(int a[], int len, int x) //判断数据x是否为数组a的元素，如果是返回该元素的下标，否则返回-1
{
int i;
for (i=0; i<len; i++)
{
if (a[i] == x)
return i;
}
return -1;
}
二分查找法：
int IsElement(int a[], int len, int x)
{
int left = 0;
int right = len - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;//寻找中点，以便将数组分成两半
if (a[mid] == x)//刚好找到
return mid......
算法设计之递归法(3)(2007-10-06 19:15:00)
摘要：练习：
1． 小猴吃枣：小猴第一天摘下若干枣子，当即吃掉了一半，不过瘾又多吃了一个；第二天吃了剩下的一半又多吃了一个；以后每一天都吃了前一天剩下的一半多一个。到第十天小猴再想吃时，见到只剩下一只枣子了。问第一天这堆枣子有多少？
2． MyCathy函数定义如下：
x – 10 ， x > 100
M（x）= {
M（M（x+11））， x <= 100
分别用递归和非递归方式编写函数计算给定x的M（x）的值。
3． 使用递归函数表达欧几里德算法。
4． 设对于给定的x和系数a[i]求下列n阶多项式的值：
n阶多项式：Pn(x) = an.x^n + a(n-1).x^(n-1) + ... + a1.x + a0
函数接口：double Poly(double coeff[], int n, double x);
参考程序：
1. 算法分析：可用递归方法，返回第n天的桃子数量。
递归公式：F（n） = 1， n= 10； F（n） = （F（n+1）+ 1）*2， n= 10；
#include <stdio.h>
int Peach(int n);
int main(void)
{
int i;
for (i=1; i<=10; i++)
printf("第%d天这堆枣子有%d个\n", i, Peach(i));
getchar();
return 0;
}
int Peach(int n)
{
if (n < 10)
&nb......
算法设计之递归法(2)(2007-10-06 19:14:00)
摘要：递归和非递归的转换
在第一讲《算法设计之枚举法》中我们有一道练习题：
例6：构造一个3*3的魔方：把数字1-9添入如图的表格中
2
7
6
9
5
1
4
3
8
要求每横，竖，斜列之和均相等（如图是一种情况）。输出所有可能的魔方。
当时我们是使用枚举法解的，通过剪枝等优化后得到一个8重嵌套循环，而且每个循环的结构都是一样的，既繁琐，又复杂。既然如此，那么我们是否可以用一个递归函数来实现呢？答案是肯定的。程序如下：
#include<stdio.h>
#define MAX 9
int IsElement(int a[], int len, int x);
void F(int a[], int len);
int main()
{
int a[MAX] = {0};
int i;
for (a[0]=1; a[0]<=MAX; a[0]++)
{
F(a, 0);
}
getchar();
return 0;
}
void F(int a[], int len)//以递归代替多重嵌套循环
{
int i;
if (len < MAX-2 && IsElement(a, len, a[len]))
{
len++;
&nb......
算法设计之递归法(1)(2007-10-06 19:13:00)
摘要：前言
说白了递归就象我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：……也就是直接或间接地调用了其自身。
就象上面的故事那样，故事中包含了故事本身。因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。
函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。对于代码中功能性较强的、重复执行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。
例如我们把上面的讲故事的过程包装成一个函数，就会得到：
void Story()
{
puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：");
getchar();//按任意键听下一个故事的内容
Story(); //老和尚讲的故事，实际上就是上面那个故事
}
函数的功能是输出这个故事的内容，等用户按任意键后，重复的输出这段内容。我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。于是我们可以得到下面的程序：
#include<stdio.h>
const int MAX = 3;
void Story(int n);//讲故事
int main(void)
{
Story(0);
getchar();
return 0;
}
void Story(int n)
{
if (n < MAX)
{
......
算法设计之迭代法(2)(2007-09-27 09:34:00)
摘要：参考答案：
1．#include<stdio.h>
#include<stdlib.h>
int main()
{
int n;
puts("input n: ");
scanf("%d", &n);
puts("过程:");
printf("%d -> ", n);
while (n != 1)
{
if (0 == (n&1))
n = n / 2; //迭代关系式
else
n = n * 3 + 1; //迭代关系式
printf("%d -> ", n);
}
printf("\b\b\b\b \n");//去掉多余的“ -> ”
system("pause");
return 0;
}
2. 算法分析： 根据题意，阿米巴每3分钟分裂一次，那么从开始的时候将阿米巴放入容器里面......
算法设计之迭代法(1)(2007-09-27 09:34:00)
摘要：军人在进攻时常采用交替掩护进攻的方式，若在数轴上的点表示A，B两人的位置，规定在前面的数大于后面的数，则是A>B，B>A交替出现。但现在假设军中有一个胆小鬼，同时大家又都很照顾他，每次冲锋都是让他跟在后面，每当前面的人占据一个新的位置，就把位置交给他，然后其他人再往前占领新的位置。也就是A始终在B的前面，A向前迈进，B跟上，A把自己的位置交给B（即执行B = A操作），然后A 再前进占领新的位置，B再跟上……直到占领所有的阵地，前进结束。像这种两个数一前一后逐步向某个位置逼近的方法称之为迭代法。
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
利用迭代算法解决问题，需要做好以下三个方面的工作：
一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
最经典的迭代算法是欧几里德算法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a, b) = gcd(b, a mod b)
证明：a可以表示成a = kb + r，则r = a mod b 。假设d是a,b的一个公约数，则有 d%a==0, d%b==0，而r = a - kb，因此d%r==0 ，因此d是(b, a mod b)的公约数
同理，假设d 是(b, a mod b)的公约数，则 d......
算法设计之枚举法(3)(2007-09-20 08:40:00)
摘要：练习：
1．元旦义卖：总共带50件商品，有两种构成，钥匙扣2块一个，漫画书4块一本，要卖出160块要如和搭配？
2．构造一个3*3的魔方：把数字1-9添入如图的表格中
2
7
6
9
5
1
4
3
8
要求每横，竖，斜列之和均相等（如图是一种情况）。输出所有可能的魔方。
3. 虫食算: 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
____________
44445509678
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑10进制加法的虫食算。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。
给定等式 A B C D E
D F G
+ D F G
───────
X Y Z D E
其中每个字母代表一个数字，且不同数字对应不同字母。编程求出这些数字并且打出这个数字的算术计算竖式。
参考答案：
1．#include<stdio.h>
const int KEYPRICE = 2; //一个钥匙扣的价格
const int BOOKPRICE = 4; //一本漫画书的价格
void Print(int money, int res);//计算......
算法设计之枚举法(2)(2007-09-20 08:38:00)
摘要：例3. 将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.
例如:三个三位数192,384,576满足以上条件.(NOIP1998pj)
算法分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：
for (a=1; a<10; a++)
for (b=1; b<10; b++)
for (c=1; c<10; c++)
...
for (i=1; i<10; i++)
这样下去，枚举次数就有387420489（9的9次方）次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，枚举的范围就减少为（326-123=）203次，在细节上再进一步优化，枚举范围就更少了。程序如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int Function(int lib[][3]);//主处理函数
int main()
{
int lib[100][3] = {0};
int len = Function(lib);
int i;
for (i=0; i<len; i++)
{
printf("%5d%5d%5d\n", lib[i][0], lib[i][1], lib[i][2]);
}
getchar();
return 0;
}
int Function(int lib[][3])//主处理函数
{
......