《实用算法的分析与程序设计》的读书笔记(第2天）
递归 第20页
[例1]划分问题
设s是一个具有n个元素的集合s
下列条件的子集合sl，s z，·。，s k：
1．si 56呼
(al，a z，·。，a。)，现将s集合划分成K个满足
2．S；门Sj＝69 ’
3．S1廖S 2LJ S 3LJ·．·廖Sn＝S ·
(1毒i，j毒k，i，6j)
则称s n，s z，…，s n是s的一个划分。它相当于把s集合中的n个元素a n·．·a n放人k
个无标号的盒子中，使得没有一个盒子为空。试确定n个元素a1…an放人k个无标号
盒的划分数s(n，k)。
分析：
设n个元素a n…a n故人k个无标号盒的划分数为s(n，k)。在配置过程中，有两种互
不相容的情况：
1．设(a n)是k个子集中的一个子集，于是把(a n…a n—1)划分为k一1子集有s(n一
1，k—1)个划分数；
2．如果(an)不是k个子集中的一个，即an必与其它的元素构成一个子集。首先把
(a，，…，an—1)划分成k个子集，这共有s(n一1，k)种划分方式。然后再把an加入到k
个子集中的一个子集中去，这有k种加入方式。对于每一种加入方式，都使集合划分为k
个子集，因此由乘法原理知，划分数共有
k*s(n一1，k)。
应用加法原理于上述两种情况，得出I a，，…，an)划分为k个子集的划分数：
s(n，k)＝s(n一1，k一1)十k*s(n一1，k) (n＞1，k>=1)
现在考虑s(n,k)的边界条件：1). s(n,0)=0; 当k>n时s(n,k)=0;
2).s(n,1)=1; s(n,n)=1;
由此得到递归定义：
s(n，k)＝s(n一1，k一1)十k*s(n一1，k) (n＞k，k>=1)
s(n，k)＝o (n＜k)或(k＝0＜n)
s(n，k)＝1 (k＝1)或(k＝n)
题解：
#include<iostream.h>
int s(int n,int k)
{
int sum;
if(n<k||k==0) sum=0;
else if(k==1||k==n) sum=1;
else sum=s(n-1,k-1)+k*s(n-1,k);
return sum;
}
int main()
{
int n,k;
while(cin>>n>>k){
int sum=s(n,k);
cout<<sum<<endl;
}
return 1;
}
分治法 第22页
所谓分治策略：既将原问题分成n个规模较小而结构与原问题相似的
子问题。递归地解这些子问题，然后合并其结果就得到原问题的解。n＝2
时的分治法又称二分法。
分治法在每一层递归上都有三个步骤：
分解：将原问题分解成一系列子问题；
解决：递归地解各子问题。若子问题足够小，则直接解
合并：将子问题的结果合并成原问题的解；
[例1I合并排序
对序列A[1]，A[2]，……，A[n]进行合并排序。
算法分析：
合并排序的算法就是二分法。
分解：将n个元素各含rn／2。1(或Ln／2J)个元素的子序列
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已排序的子序列以得到排序结果。
前面在贪心法中用到的函数 merge(int p,int q,int r)与merge(int p,int r)就
是典型的二分排序法。这里不再重复。
枚举法 第31页
所谓枚举法，指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件
判定哪些是无用的，哪些是有用的。能使命题成立，即为其解.
一般来说，如果预先对问题确定了解的个数以及各个解的值域。我们则可以利用ror语
句和条件判断语句逐步求解或证明.
如果我们无法预先确定解的个数或各解的值域，我们只能采用隐式图搜索的算法求
解，例如回溯法等。由于回溯搜索，每个可能解的枚举一般不止一次，因此在相同的检验
条件下，回溯法要比枚学法费时一些。
[例0填写运算符
输入任意5个数 x1,x2,x3,x4,x5
每相邻两个数间填上一个运算符。在填入四个运算符后，使得表达式值为一个指定值
y(y由键盘输入)。求出所有满足条件的表达式。
分析：为了解决运算的优先级问题，我们设置如下变量：
f——减法标志。减法运算时，置f＝一1，否则f＝1；
q——若当前运算符为十(一)时，q存贮运算符的左项值；
若当前运算符为*(／)时，q存贮两数乘(除)后的结果；
p——累加器。每填一个算符p＝p十f *q。
然后四重for循环，解决问题。这是一道典型的枚举题，运算
量很大。具体程序还是比较简单，故不再转化。
枚举法有其计算量大的缺点，但是如果能够排除那些明显不属
于解集的元素，在局部地方使用枚举法，其效果会十分显著。
[例2]时针问题
在图1．5。1所示的3×3阵列中有9个时钟，我们的目标是旋转时钟指针，使所有
时钟的指针都指向12点。允许旋转时钟指针的方法有9种，每一种移动用一个数字号(1，
2，…，9)表示。 图1．5—2示出了9个数字号与相应的受控制的时钟，这些时钟在图中以灰
色标出，其指针将顺时针旋转90度。
输入数据：
输入9个数码，这些数码给出9个时钟针的初始位置。数码与时刻
的对应关系为0-->12点,1->3点,2-->6点,3-->9点。
例：3 3 0 2 2 2 2 1 2
输出数据：
输出一个最短的移动序列（数字）
例：5 8 4 9
题解：
#include<iostream.h>
int clocks[9],map[9];
void init()
{
int i;
for(i=0;i<9;i++){
cin>>clocks[i];
clocks[i]=(4-clocks[i])%4;
}
}
int order(int k)
{
int c=k;
while(c>4)c-=4;
while(c<0)c+=4;
return c;
}
void clock()
{
init();
int i; bool flag=false;
for(map[0]=0;map[0]<=3;map[0]++)
for(map[1]=0;map[1]<=3;map[1]++)
for(map[2]=0;map[2]<=3;map[2]++){
map[3]=order(clocks[0]-map[0]-map[1]);
map[5]=order(clocks[2]-map[1]-map[2]);
map[4]=order(clocks[1]-map[0]-map[1]-map[2]);
map[6]=order(clocks[3]-map[0]-map[3]-map[4]);
map[8]=order(clocks[5]-map[2]-map[4]-map[5]);
map[7]=order(clocks[7]-map[6]-map[8]-map[4]);
if(clocks[6]==(map[3]+map[6]+map[7])%4&&
clocks[4]==(map[4]+map[0]+map[2]+map[6]+map[8])%4&&
clocks[8]==(map[5]+map[7]+map[8])%4){
for(i=0;i<9;i++)
if(map[i]!=0)cout<<(i+1);
cout<<endl;
flag=true;
}
}
if(!flag)cout<<"NO ANSWER!";
}
int main()
{
clock();
return 1;
}
