ITPub博客

首页 > 应用开发 > IT综合 > 《实用算法的分析与程序设计》的读书笔记(第2天) (转)

《实用算法的分析与程序设计》的读书笔记(第2天) (转)

原创 IT综合 作者:worldblog 时间:2007-12-13 13:19:26 0 删除 编辑
《实用算法的分析与程序设计》的读书笔记(第2天) (转)[@more@]递归 第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
int s(int n,int k)
{
 int sum;
 if(n  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<  }
  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
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<  flag=true;
  }
  }
  if(!flag)cout<<"NO ANSWER!";
}
int main()
{
 clock();
  return 1;
}


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752043/viewspace-992875/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    6241
  • 访问量
    2463328