作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

[例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;
}
 

相关软件：