递推算法--幂积序列

问题提出：

设x,y为非负整数，试计算集合M={2^x*3^y|x>=0,y>=0}的元素小于指定整数n的个数，并求这些元素从小到大排序的第m项。

 以下给出案例求解的三种设计：

1.穷举求解

设计要点：

集合元素由2的幂与3的幂及其乘积组成，设元素从小到大排序的第k项为f(k)。显然，f(1)=1,f(2)=2。

设置a从3开始递增至n循环，对每一个a(赋值给j),逐次试用2试商，然后逐次试用3试商。

试商后若j>1，说明原a有2，3以外的因数，不属于该序列。

若j=1，说明原a只有2，3的因数，为序列第k项赋值。

由于实施从小到大穷举赋值，所得项无疑是从小到大的序列。

当达到指定的n，退出循环，输出指定项f(m)。

代码如下： 

代码  1 #include <stdio.h>
 2 void main()
 3 {int  k,m;  
 4  long  a,j,n,f[1000];
 5  printf("  计算小于n的项数，请指定n: ");
 6  scanf("%ld",&n);
 7  printf("  输出序列的第m项，请指定m: ");
 8  scanf("%d",&m);
 9  f[1]=1;f[2]=2;k=2;
10  for(a=3;a<=n;a++)
11  { j=a;
12      while(j%2==0) j=j/2;     // 反复用2试商  
13      while(j%3==0) j=j/3;     // 反复用3试商  
14    if(j==1)
15       { k++;f[k]=a;}
16   }                     
17  printf("  幂序列中小于%ld的项数为：%d\n",n,k); 
18  if(m<=k)
19     printf("  从小到大排序的第%d项为：%ld\n",m,f[m]); 
20  else
21  printf("  所输入的m大于序列的项数！\n");
22 }
23 

2. 递推排序求解

设计要点：

为探索x+y=i时各项与x+y=i−1时各项之间的递推规律，剖析x+y的前若干项情形：

x+y=0时，元素为1（初始条件）；

x+y=1时，元素为2*1=2,3*1=3，共2项；

x+y=2时，序列有2*2=4,2*3=6,3*3=9，共3项；

x+y=3时，序列有2*2*2=8,2*2*3=12,2*3*3=18,3*3*3=27，共4项；

……

可归纳出以下递推关系：

x+y=i时，序列共i+1项，其中前i项是x+y=i−1时的所有i项分别乘2所得；最后一项为x+y=i−1时的最后一项乘3所得（即t=3^i）。

注意，对x+y=i−1的所有i项分别乘2，设为f[h]*2，必须检测是否小于n而大于0。同样，对t也必须检测是否小于n而大于0。只有小于n且大于0时才能赋值。

这里要指出，最后若干行可能不是完整的，即可能只有前若干项能递推出新项。为此设置变量u: 当一行有递推项时u=1；否则u=0。只有当u=0时停止，否则会影响序列的项数。

代码  1 #include <stdio.h>
 2 void main()
 3 {int i,j,h,k,m,u,c[100]; 
 4  double d,n,t,f[1000];
 5  printf("  计算小于n的项数，请指定n: ");
 6  scanf("%lf",&n);
 7  printf("  输出序列的第m项，请指定m: ");
 8  scanf("%d",&m);
 9  k=1;t=1.0; i=1;
10  c[0]=1; f[1]=1.0;
11  while(1)
12  { u=0;
13    for(j=0;j<=i-1;j++)  
14    { h=c[i-1]+j;
15      if(f[h]*2<n && f[h]>0)  // 第i行各项为前一行各项乘2  
16         { k++;f[k]=f[h]*2;u=1;
17        if(j==0) c[i]=k;    // 该行的第1项的项数值赋给c(i)  
18         } 
19      else break;     
20     }
21   t=t*3;                 // 最后一项为3的幂  
22   if(t<n && t>0)
23   { k++;f[k]=t; }        // 用t给f[k]赋值          
24   if(u==0) break; 
25   i++;
26   }
27   for(i=1;i<k;i++)        // 逐项比较排序  
28     for(j=i+1;j<=k;j++)
29        if(f[i]>f[j])
30         { d=f[i];f[i]=f[j];f[j]=d;}    
31    printf("  幂序列中小于%f的项数为：%d\n",n,k); 
32   if(m<=k)
33     printf("  从小到大排序的第%d项为：%.0f\n",m,f[m]); 
34  else
35  printf("  所输入的m大于序列的项数！\n");
36 }
37 

设计要点:

从u=1, f(u)=1开始, 在已求得f(u)的基础上,可递推地求出f(u+1)：求出各大于f(u)的最小数, 取其中最小者即为f(u+1)。

递推结合比较赋值设置永真外循环，实施乘2的内循环。

首先，从p=0开始，若q[p]<=f[u]，则递推得一个3的幂即q[p]=3^p，并赋给最小值标志量h。

然后转入内循环i(0——p-1)中，若q[i]<=f[u]，则q[i]乘2,即q[i]=2*q[i]。

然后q[i]与h比较，即2^j*3^i（i<p）与3^p比较，取较小者为h。

若h≤n，则h赋值给序列新的项，用u标记的项数。

若h>n，表明递推结合比较赋值完成，退出外循环，输出序列的项数u与序列中指定的项f[m]后结束。

代码如下：

代码  1 #include <stdio.h>
 2 void main()
 3 { int i,m,u,p;
 4  double n,h,f[1000],q[100];
 5  printf("  计算小于n的项数，请指定n: ");
 6  scanf("%lf",&n);
 7  printf("  输出序列的第m项，请指定m: ");
 8  scanf("%d",&m);
 9  u=1; f[u]=1.0; 
10  p=0; q[p]=1.0;
11  while(1)
12  { if(q[p]<=f[u])
13   { p++; q[p]=3*q[p-1]; }
14     h=q[p];                      // 递推3的幂，q[p]=3^p  
15     for(i=0;i<p;i++)
16        { if(q[i]<=f[u]) q[i]*=2; // 幂积q[i]=2^j*3^i,j=1,2,3,…  
17           if(q[i]<h) h=q[i];
18        }
19     if(h>n) break;
20    u++;f[u]=h;      
21    }
22    printf("  幂序列中小于%.0f的项数为：%d\n",n,u);  
23    if(m<=u)
24       printf("  从小到大排序的第%d项为：%.0f\n",m,f[m]); 
25   else
26     printf("  所输入的m大于序列的项数！\n");
27 }
28