数学研发论坛

 找回密码
 欢迎注册
楼主: gxqcn

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

[复制链接]
 楼主| 发表于 2013-10-18 11:40:14 | 显示全部楼层
mathematica 发表于 2013-10-18 11:29
上面是我写的c++代码,结果和上面应该一样,一两秒钟就能搞定了,c++的效率挺高的!


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

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

点评

你现在仅是“做对”,离“做好”还相差得很远呢。。。  发表于 2013-10-21 07:22
那你们什么时候给我发录取通知呢???????????  发表于 2013-10-18 18:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 11:46:51 | 显示全部楼层
没想到我自己居然还会点c++
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 12:05:44 | 显示全部楼层
#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);
                        }
                }
        }
}

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

点评

这个欠缺考虑2^11这个之类的  发表于 2013-10-18 17:55
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 17:56:52 | 显示全部楼层
  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. (*检查是否相等*)
复制代码
最终的结果自己运行吧

点评

k应该从0开始变化  发表于 2013-10-18 18:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 17:57:53 | 显示全部楼层
对于mathematica是秒杀级别的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 18:16:46 | 显示全部楼层
(*这个是有依据的代码,上面的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不需要增大*)
这个是秒杀级别的代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 18:19:36 | 显示全部楼层
ab2=Divisors[2^200*3^200*5^200][[1;;200]]
这个是mathematica的一行代码,而且绝对是正确的代码

点评

缺点就是速度太慢了  发表于 2013-10-18 18:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 18:44:11 | 显示全部楼层
对九楼提问的回答
  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 (*输出最后的结果*)
复制代码

点评

{10, 8, 4}这个是输出结果!  发表于 2013-10-18 18:44
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-21 10:47:34 | 显示全部楼层
设所求项数为$n$,任何一个整数只需$O(1)$的空间存储,任意两个整数做一次运算只需$O(1)$的时间,

那么用 三重循环 + 排序 的方法,时间复杂度是$O(n\log n)$,空间复杂度是$O(n)$,代码如下:
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;

  4. unsigned int max2,max3,max5,i,j,k,n,a[2000];

  5. int main()
  6. {
  7.         max2=max3=max5=-1;
  8.         max2/=2;
  9.         max3/=3;
  10.         max5/=5;
  11.         for(i=1;;i*=2)
  12.         {
  13.                 for(j=i;;j*=3)
  14.                 {
  15.                         for(k=j;;k*=5)
  16.                         {
  17.                                 a[n++]=k;
  18.                                 if(k>max5)break;
  19.                         }
  20.                         if(j>max3)break;
  21.                 }
  22.                 if(i>max2)break;
  23.         }
  24.         sort(a,a+n);
  25.         for(i=0;i<200;i++)
  26.                 printf(i%10>8?"%u\n":"%u ",a[i]);
  27.         return 0;
  28. }
复制代码
如果用 最小堆 实现一个 优先队列,那么时间复杂度不变,空间复杂度将降为$O(n^(2/3))$,代码略。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-10-21 11:31:02 | 显示全部楼层
无需排序,也无需任何除法运算,就能直接构造出来的。

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

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

点评

好方法!时间复杂度降至$O(n)$。  发表于 2013-10-21 18:42
把你的代码拿上来,让大家看看你的对不对,我怎么感觉你的算法不对???????  发表于 2013-10-21 13:44

评分

参与人数 1威望 +3 贡献 +3 鲜花 +3 收起 理由
KeyTo9_Fans + 3 + 3 + 3 好方法!时间复杂度降至$O(n)$。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-7-17 04:22 , Processed in 0.059154 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表