数学研发论坛

 找回密码
 欢迎注册
查看: 6312|回复: 107

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

[复制链接]
发表于 2013-10-18 07:36:55 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
求前 200 项可表示成 $2^r*3^s*5^t$ (r,s,t 均为整数)的自然数序列。
  • 请证明:以上序列最大值小于 $2^30$;
  • 请用 C / C++ 语言编程输出该序列,要求算法的空间及时间复杂度尽可能地低。

附注:可解除须 C / C++ 的限定,欢迎大家用自己熟悉的计算机语言提交代码。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-10-18 07:40:27 | 显示全部楼层
两年前我给公司面试题库出了几道算法题,但迄今几乎无人可正确作答,
上述题目是在某面试题基础上再升级的,难度有所提高,因为咱们论坛里高手多。

点评

没看到我给你的留言吗?  发表于 2013-10-18 19:14
面试时是在纸上写代码(用 C / C++ 写),确实没人能将算法写个大概了,许多人完全摸不着头脑。  发表于 2013-10-18 10:57
不要说无人正确解答好不好?最多只是效率的问题.我就对前一千万个数分解质因数逐一判定,你觉得这不是正确的办法吗?  发表于 2013-10-18 10:52
我给你发短信息了,给你空间留言了,看见了吗?  发表于 2013-10-18 09:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 09:42:31 | 显示全部楼层
假设r\s\t是正整数,那么这个数必然是2*3*5=30的倍数,然后乘以2/4/8/16/32/.............
3/9/27/................
5/25/125.............

点评

这样将会遗漏大量符合要求的数据。  发表于 2013-10-18 10:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 10:26:49 | 显示全部楼层
(r+1)*(s+1)*(t+1)<=200

点评

2^9*3^4*5^3=518400 与 (9+1)*(4+1)*(3+1)=200  发表于 2013-10-18 11:40
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 10:33:58 | 显示全部楼层
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32,
36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108,
120, 125, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240,
243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432,
450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675, 720, 729,
750, 768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 1125, 1152,
1200, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536, 1600,
1620, 1728, 1800, 1875, 1920, 1944, 2000, 2025, 2048, 2160, 2187,
2250, 2304, 2400, 2430, 2500, 2560, 2592, 2700, 2880, 2916, 3000,
3072, 3125, 3200, 3240, 3375, 3456, 3600, 3645, 3750, 3840, 3888,
4000, 4050, 4096, 4320, 4374, 4500, 4608, 4800, 4860, 5000, 5120,
5184, 5400, 5625, 5760, 5832, 6000, 6075, 6144, 6250, 6400, 6480,
6561, 6750, 6912, 7200, 7290, 7500, 7680, 7776, 8000, 8100, 8192,
8640, 8748, 9000, 9216, 9375, 9600, 9720, 10000, 10125, 10240, 10368,
10800, 10935, 11250, 11520, 11664, 12000, 12150, 12288, 12500, 12800,
12960, 13122, 13500, 13824, 14400, 14580, 15000, 15360, 15552, 15625,
16000, 16200
是这些数吗?如果r\s\t可以是零的话

点评

查看前面若干项,完全满足题意。  发表于 2013-10-18 10:44
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-10-18 10:36:21 | 显示全部楼层


如果是为了证明第1问,
则基本上踩在点子上了,
即构造一整数 $2^r*3^s*5^t < 2^30$, 且满足 $(r+1)(s+1)(t+1)>=200$ 即可。

比如:$2^6*3^6*5^6 = 30^6 < 32^6 = 2^30$,而 $7^3 = 343 > 200$。

此问的目的,仅仅提示:在用32位系统下,所求序列选用 int 型数据类型足矣(不会溢出;即:无需大整数运算)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 10:43:18 | 显示全部楼层
如果rst必须大于零,那么是
30, 60, 90, 120, 150, 180, 240, 270, 300, 360, 450, 480, 540, 600,
720, 750, 810, 900, 960, 1080, 1200, 1350, 1440, 1500, 1620, 1800,
1920, 2160, 2250, 2400, 2430, 2700, 2880, 3000, 3240, 3600, 3750,
3840, 4050, 4320, 4500, 4800, 4860, 5400, 5760, 6000, 6480, 6750,
7200, 7290, 7500, 7680, 8100, 8640, 9000, 9600, 9720, 10800, 11250,
11520, 12000, 12150, 12960, 13500, 14400, 14580, 15000, 15360, 16200,
17280, 18000, 18750, 19200, 19440, 20250, 21600, 21870, 22500, 23040,
24000, 24300, 25920, 27000, 28800, 29160, 30000, 30720, 32400, 33750,
34560, 36000, 36450, 37500, 38400, 38880, 40500, 43200, 43740, 45000,
46080, 48000, 48600, 51840, 54000, 56250, 57600, 58320, 60000, 60750,
61440, 64800, 65610, 67500, 69120, 72000, 72900, 75000, 76800, 77760,
81000, 86400, 87480, 90000, 92160, 93750, 96000, 97200, 101250,
103680, 108000, 109350, 112500, 115200, 116640, 120000, 121500,
122880, 129600, 131220, 135000, 138240, 144000, 145800, 150000,
153600, 155520, 162000, 168750, 172800, 174960, 180000, 182250,
184320, 187500, 192000, 194400, 196830, 202500, 207360, 216000,
218700, 225000, 230400, 233280, 240000, 243000, 245760, 259200,
262440, 270000, 276480, 281250, 288000, 291600, 300000, 303750,
307200, 311040, 324000, 328050, 337500, 345600, 349920, 360000,
364500, 368640, 375000, 384000, 388800, 393660, 405000, 414720,
432000, 437400, 450000, 460800, 466560, 468750, 480000, 486000

点评

把你 5# 的结果依次 *30 即可得本楼结果。  发表于 2013-10-18 10:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 11:10:05 | 显示全部楼层
  1. (*求前200个2/3/5的幂的整数*)
  2. Clear["Global`*"];(*Clear all variables*)
  3. fun[n0_]:=Module[{n=n0,s2,s3,s5,out},
  4.                  s2=0;While[Mod[n,2]==0,s2=s2+1;n=n/2];(*不断地除以2*)
  5.                  s3=0;While[Mod[n,3]==0,s3=s3+1;n=n/3];(*不断地除以3*)
  6.                  s5=0;While[Mod[n,5]==0,s5=s5+1;n=n/5];(*不断地除以5*)
  7.                  (*如果正好只是2/3/5的倍数,则n应该=1*)
  8.                  If[n==1,out=1,out=0];
  9.                  out
  10.                 ]
  11. Select[Range@500000,fun[#]==1&][[1;;200]]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-10-18 11:20:01 | 显示全部楼层
在 6# 里,我只是随便构造了一个数来证明。

请你帮忙找一下:$2^32$ 以内,序列里素因子数目最多的那个数是哪个?
即:$n=2^r*3^s*5^t < 2^32$ 且使 $(r+1)(s+1)(t+1)$ 最大?

点评

r=10;s=8;t=4___11*9*5=495,n=4199040000  发表于 2013-10-18 11:44
你这个问题不是一般的难!  发表于 2013-10-18 11:30
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-10-18 11:29:50 | 显示全部楼层
  1. #include <iostream>
  2. using namespace std;
  3. int myfun(long n);
  4. int main()
  5. {
  6.         int k=0;//用来计算到底有多少个满足条件的整数
  7.         //先取一个较大的上限,如果满足条件,自动中断循环
  8.     for (long i=1;i<=800000;i++)
  9.     {
  10.                 if (myfun(i)==1)
  11.                 {
  12.                         printf("%d\n",i);
  13.                         k++;
  14.                 }
  15.                 if (k>=200)
  16.                 {
  17.                         break;
  18.                 }
  19.     }
  20.         return 0;
  21. }
  22. //子函数,用来判定整数是否满足要求,如果满足要求则返回1,如果不满足x则返回0
  23. int myfun(long n)
  24. {
  25.         int out;
  26.         while (n%2==0) { n=n/2; }
  27.         while (n%3==0) { n=n/3; }
  28.         while (n%5==0) { n=n/5; }
  29.         //如果只可能含有2/3/5因数,那么n最后应该等于1
  30.         if (n==1)
  31.         {
  32.                 out=1;
  33.         }
  34.         else
  35.         {
  36.                 out=0;
  37.         }
  38.         return out;
  39. }

复制代码
上面是我写的c++代码,结果和上面应该一样,一两秒钟就能搞定了,c++的效率挺高的!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-1-16 11:47 , Processed in 0.171272 second(s), 25 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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