求形如 2^r*3^s*5^t 的整数序列

gxqcn

mathematica 发表于 2013-10-18 11:29
上面是我写的c++代码,结果和上面应该一样,一两秒钟就能搞定了,c++的效率挺高的!

相当不错！比到我们公司来面试的都好，至少结果是正确的。

请继续优化：比如不用除法指令、直接快速构造等，也许效率还可成千上百倍的提高！

mathematica

没想到我自己居然还会点c++

mathematica

#include <iostream>
int main()
{
        int i[10]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
        int j[5]={1, 3, 9, 27, 81};
        int k[4]={1, 5, 25, 125};
        long ijk;
        for (int ii=0;ii<=9;ii++)
        {
                for (int jj=0;jj<=4;jj++)
                {
                        for (int kk=0;kk<=3;kk++)
                        {
                                ijk=i[ii]*j[jj]*k[kk];
                                printf("%d\n",ijk);
                        }
                }
        }
}

不知道这个结果为什么和上面的不一样

mathematica

1. Clear["Global`*"];(*Clear all variables*)
   
2. x=Table[2^k,{k,1,20}];
   
3. y=Table[3^k,{k,1,20}];
   
4. z=Table[5^k,{k,1,20}];
   
5. xyz=Tuples[{x,y,z}];
   
6. newxyz=(Sort@Map[Apply[Times,#]&,xyz])[[1;;200]](*小括号一定不能少*)
   
7. (*以上是方法一,下面的是方法二*)
   
8. (*下面的代码有可能是正确的*)
   
9. ab1=Divisors[2^20*3^20*5^20][[1;;200]]
   
10. (*下面的代码一定是正确的*)
    
11. ab2=Divisors[2^200*3^200*5^200][[1;;200]]
    
12. (*检查是否相等*)
    

复制代码

最终的结果自己运行吧

mathematica

对于mathematica是秒杀级别的

mathematica

(*这个是有依据的代码,上面的20次方只不过是猜测的*)
k=12;ab1=Divisors[2^k*3^k*5^k][[1;;200]];
k=13;ab2=Divisors[2^k*3^k*5^k][[1;;200]];
k=14;ab3=Divisors[2^k*3^k*5^k][[1;;200]];
ab1-ab2(*如果不相等,则k需要增大*)
ab2-ab3(*如果相等,则证明k不需要增大*)
这个是秒杀级别的代码

mathematica

ab2=Divisors[2^200*3^200*5^200][[1;;200]]
这个是mathematica的一行代码,而且绝对是正确的代码

mathematica

对九楼提问的回答

1. (*对9楼的回答*)
   
2. Clear["Global`*"];(*Clear all variables*)
   
3. rmax=Floor@Log[2,2^32];
   
4. smax=Floor@Log[3,2^32];
   
5. tmax=Floor@Log[5,2^32];
   
6. chengji0=0;
   
7. (*使用穷举法*)
   
8. Do[n=2^r*3^s*5^t;
   
9.    ys=2^32-n;(*计算2^32比n大多少*)
   
10.    chengji=(r+1)*(s+1)*(t+1);(*计算成绩*)
    
11.    If[ys>=0&&chengji>chengji0,
    
12.       chengji0=chengji;
    
13.       out={r,s,t};
    
14.    ],
    
15.     {r,0,rmax},
    
16.     {s,0,smax},
    
17.     {t,0,tmax}
    
18. ];out (*输出最后的结果*)
    

复制代码

KeyTo9_Fans

设所求项数为$n$，任何一个整数只需$O(1)$的空间存储，任意两个整数做一次运算只需$O(1)$的时间，

那么用 三重循环 + 排序 的方法，时间复杂度是$O(n\log n)$，空间复杂度是$O(n)$，代码如下：

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. unsigned int max2,max3,max5,i,j,k,n,a[2000];
   
6. 
   
7. int main()
   
8. {
   
9.         max2=max3=max5=-1;
   
10.         max2/=2;
    
11.         max3/=3;
    
12.         max5/=5;
    
13.         for(i=1;;i*=2)
    
14.         {
    
15.                 for(j=i;;j*=3)
    
16.                 {
    
17.                         for(k=j;;k*=5)
    
18.                         {
    
19.                                 a[n++]=k;
    
20.                                 if(k>max5)break;
    
21.                         }
    
22.                         if(j>max3)break;
    
23.                 }
    
24.                 if(i>max2)break;
    
25.         }
    
26.         sort(a,a+n);
    
27.         for(i=0;i<200;i++)
    
28.                 printf(i%10>8?"%u\n":"%u ",a[i]);
    
29.         return 0;
    
30. }

复制代码

如果用 最小堆 实现一个 优先队列，那么时间复杂度不变，空间复杂度将降为$O(n^(2/3))$，代码略。

gxqcn

无需排序，也无需任何除法运算，就能直接构造出来的。

请注意到一个事实：
除首项“1”外，在序列顺序增长的过程中，追加项（即新项）总可由现有序列中之前的某项，或乘2或乘3或乘5（可同时兼具多种途径）构造获得。
我们要做好的是：记录好现有待乘项（*2、*3、*5）的位置，并由此快速获得追加项的值。

用上述原理，可先人工模拟计算，得到其前几项：{ 1,2,3,4,5,6,8,9,10,12,15,16,... }，
揣摩其规律，就可以得到比较快捷的算法。