这道题我用的是终极打表的方法。。。。。。。。。。
哈哈哈，为了避免代码太长刷屏，把我自己的代码放到最后。。。这道题当我想到这种方法的时候哈哈大笑。。。
这题倒是让我变得很会用 word 的替换。。。回车是^p，先把回车都去掉，然后再把所有的“，”改成“，^p”。原因是开始的回车有把很多数字隔开，这样编译器就没法识别了；后一个因为编译器一行最多2048个字符
大家注意亮点【代码长度】：
我自己的代码效率很低，所以想到这种方法。。。网上的结题报告多用的是，指针法
我的低效代码：
#include <stdio.h>
int ugly[1510];
void Process()
{
ugly[1]=1;
int i;
int tmp;
int flag; //观察有没有经过除法
//要处理 2~1500 这么多数
int count=1;
for(i=2; ;i++)
{
tmp=i;
while(1)
{
flag=0;
if(tmp%2==0)
{
tmp/=2;
flag=1;
}
if(tmp%3==0)
{
tmp/=3;
flag=1;
}
if(tmp%5==0)
{
tmp/=5;
flag=1;
}
if(tmp==1) //处理完毕，i是一个ugly数
{
ugly[count]=i;
printf("%d\n",i);
count++;
break;
}
if(flag==0) //没经过处理
break;
}
if(count>=1500)
return;
}
}
int main()
{
//这道题的数据量只有1500，完全可以打表
Process();
printf("over\n");
int n;
int count;
int i;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
return 0;
count=0;
for(i=1; ;i++)
{
if(ugly[i]==1)
count++;
if(count==n)
break;
}
printf("%d\n",i);
}
return 0;
}
1.
别人的思路之一：
题目意思是求由2，3，5的乘积组成的数从大到小排列，从1开始，2，3，4，5，6，8，9，。。。
基本思想是设3个指针，分别表示3个素数乘到哪了，然后通过比较3个指针位置的递推结果来确定下一个数是什么。
别人的代码之一：
#include<iostream>
using namespace std;
int a[1510];
int main()
{
int p2,p3,p5;
p2=p3=p5=a[1]=1;
int n;
for(int i=2;i<=1500;i++)
{
int t2=a[p2]*2;
int t3=a[p3]*3;
int t5=a[p5]*5;
if(t2<t3&&t2<t5) {a[i]=t2;p2++;}
else if(t3<t2&&t3<t5) {a[i]=t3;p3++;}
else if(t5<t2&&t5<t3) {a[i]=t5;p5++;}
else if(t2==t3&&t2<t5) {a[i]=t2;p2++;p3++;}
else if(t2==t5&&t2<t3) {a[i]=t2;p2++;p5++;}
else if(t3==t5&&t3<t2) {a[i]=t3;p3++;p5++;}
else {a[i]=t2;p2++;p3++;p5++;}
}
while(cin>>n&&n!=0)
{
cout<<a[n]<<endl;
}
system("pause");
return 0;
}
2.
别人的思路之二：
poj 1338,2247,2545,2591
这几个都是类似的题目，就是将满足要求的数列出来，给出一个n，问你第n个数是多少？
以1338为例：
对于每一个质数2 3 5，我们都要找到对应的之前已经计算出的最小的丑数使之乘以这个质数后大于当前的丑数，然后再从这三个里取最小的那个，我们记录三个数a2,a3,a5，分别保存对应的质数计算到哪个下标了,然后更新所有质数对应的下标，使之乘积大于当前的丑数。
别人的代码之二：
#include <iostream>
using namespace std;
const int M=1501;
int ans[M];
int getMin(int a,int b,int c)
{
int rs=0;
if(a>b)
rs=b;
else
rs=a;
if(rs>c)
rs=c;
return rs;
}
int main()
{
int a2,a3,a5,i,tmp,n;
a2=1;
a3=1;
a5=1;
ans[1]=1;
for(i=2;i<M;i++)
{
tmp=getMin(ans[a2]*2,ans[a3]*3,ans[a5]*5);
ans[i]=tmp;
if(tmp==ans[a2]*2)
++a2;
if(tmp==ans[a3]*3)
++a3;
if(tmp==ans[a5]*5)
++a5;
// cout<<a2<<" "<<a3<<" "<<a5<<endl;
}
while(cin>>n)
{
if(0 == n)
break;
cout<<ans[n]<<endl;
}
return 0;
}
我AC的终极打表代码：
#include <stdio.h>
int ugly[1502]={0,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,
16384,
16875,
17280,
17496,
18000,
18225,
18432,
18750,
19200,
19440,
19683,
20000,
20250,
20480,
20736,
21600,
21870,
22500,
23040,
23328,
24000,
24300,
24576,
25000,
25600,
25920,
26244,
27000,
27648,
28125,
28800,
29160,
30000,
30375,
30720,
31104,
31250,
32000,
32400,
32768,
32805,
33750,
34560,
34992,
36000,
36450,
36864,
37500,
38400,
38880,
39366,
40000,
40500,
40960,
41472,
43200,
43740,
45000,
46080,
46656,
46875,
48000,
48600,
49152,
50000,
50625,
51200,
51840,
52488,
54000,
54675,
55296,
56250,
57600,
58320,
59049,
60000,
60750,
61440,
62208,
62500,
64000,
64800,
65536,
65610,
67500,
69120,
69984,
72000,
72900,
73728,
75000,
76800,
77760,
78125,
78732,
80000,
81000,
81920,
82944,
84375,
86400,
87480,
90000,
91125,
92160,
93312,
93750,
96000,
97200,
98304,
98415,
100000,
101250,
102400,
103680,
104976,
108000,
109350,
110592,
112500,
115200,
116640,
118098,
120000,
121500,
122880,
124416,
125000,
128000,
129600,
131072,
131220,
135000,
138240,
139968,
140625,
144000,
145800,
147456,
150000,
151875,
153600,
155520,
156250,
157464,
160000,
162000,
163840,
164025,
165888,
168750,
172800,
174960,
177147,
180000,
182250,
184320,
186624,
187500,
192000,
194400,
196608,
196830,
200000,
202500,
204800,
207360,
209952,
216000,
218700,
221184,
225000,
230400,
233280,
234375,
236196,
240000,
243000,
245760,
248832,
250000,
253125,
256000,
259200,
262144,
262440,
270000,
273375,
276480,
279936,
281250,
288000,
291600,
294912,
295245,
300000,
303750,
307200,
311040,
312500,
314928,
320000,
324000,
327680,
328050,
331776,
337500,
345600,
349920,
354294,
360000,
364500,
368640,
373248,
375000,
384000,
388800,
390625,
393216,
393660,
400000,
405000,
409600,
414720,
419904,
421875,
432000,
437400,
442368,
450000,
455625,
460800,
466560,
468750,
472392,
480000,
486000,
491520,
492075,
497664,
500000,
506250,
512000,
518400,
524288,
524880,
531441,
540000,
546750,
552960,
559872,
562500,
576000,
583200,
589824,
590490,
600000,
607500,
614400,
622080,
625000,
629856,
640000,
648000,
655360,
656100,
663552,
675000,
691200,
699840,
703125,
708588,
720000,
729000,
737280,
746496,
750000,
759375,
768000,
777600,
781250,
786432,
787320,
800000,
810000,
819200,
820125,
829440,
839808,
843750,
864000,
874800,
884736,
885735,
900000,
911250,
921600,
933120,
937500,
944784,
960000,
972000,
983040,
984150,
995328,
1000000,
1012500,
1024000,
1036800,
1048576,
1049760,
1062882,
1080000,
1093500,
1105920,
1119744,
1125000,
1152000,
1166400,
1171875,
1179648,
1180980,
1200000,
1215000,
1228800,
1244160,
1250000,
1259712,
1265625,
1280000,
1296000,
1310720,
1312200,
1327104,
1350000,
1366875,
1382400,
1399680,
1406250,
1417176,
1440000,
1458000,
1474560,
1476225,
1492992,
1500000,
1518750,
1536000,
1555200,
1562500,
1572864,
1574640,
1594323,
1600000,
1620000,
1638400,
1640250,
1658880,
1679616,
1687500,
1728000,
1749600,
1769472,
1771470,
1800000,
1822500,
1843200,
1866240,
1875000,
1889568,
1920000,
1944000,
1953125,
1966080,
1968300,
1990656,
2000000,
2025000,
2048000,
2073600,
2097152,
2099520,
2109375,
2125764,
2160000,
2187000,
2211840,
2239488,
2250000,
2278125,
2304000,
2332800,
2343750,
2359296,
2361960,
2400000,
2430000,
2457600,
2460375,
2488320,
2500000,
2519424,
2531250,
2560000,
2592000,
2621440,
2624400,
2654208,
2657205,
2700000,
2733750,
2764800,
2799360,
2812500,
2834352,
2880000,
2916000,
2949120,
2952450,
2985984,
3000000,
3037500,
3072000,
3110400,
3125000,
3145728,
3149280,
3188646,
3200000,
3240000,
3276800,
3280500,
3317760,
3359232,
3375000,
3456000,
3499200,
3515625,
3538944,
3542940,
3600000,
3645000,
3686400,
3732480,
3750000,
3779136,
3796875,
3840000,
3888000,
3906250,
3932160,
3936600,
3981312,
4000000,
4050000,
4096000,
4100625,
4147200,
4194304,
4199040,
4218750,
4251528,
4320000,
4374000,
4423680,
4428675,
4478976,
4500000,
4556250,
4608000,
4665600,
4687500,
4718592,
4723920,
4782969,
4800000,
4860000,
4915200,
4920750,
4976640,
5000000,
5038848,
5062500,
5120000,
5184000,
5242880,
5248800,
5308416,
5314410,
5400000,
5467500,
5529600,
5598720,
5625000,
5668704,
5760000,
5832000,
5859375,
5898240,
5904900,
5971968,
6000000,
6075000,
6144000,
6220800,
6250000,
6291456,
6298560,
6328125,
6377292,
6400000,
6480000,
6553600,
6561000,
6635520,
6718464,
6750000,
6834375,
6912000,
6998400,
7031250,
7077888,
7085880,
7200000,
7290000,
7372800,
7381125,
7464960,
7500000,
7558272,
7593750,
7680000,
7776000,
7812500,
7864320,
7873200,
7962624,
7971615,
8000000,
8100000,
8192000,
8201250,
8294400,
8388608,
8398080,
8437500,
8503056,
8640000,
8748000,
8847360,
8857350,
8957952,
9000000,
9112500,
9216000,
9331200,
9375000,
9437184,
9447840,
9565938,
9600000,
9720000,
9765625,
9830400,
9841500,
9953280,
10000000,
10077696,
10125000,
10240000,
10368000,
10485760,
10497600,
10546875,
10616832,
10628820,
10800000,
10935000,
11059200,
11197440,
11250000,
11337408,
11390625,
11520000,
11664000,
11718750,
11796480,
11809800,
11943936,
12000000,
12150000,
12288000,
12301875,
12441600,
12500000,
12582912,
12597120,
12656250,
12754584,
12800000,
12960000,
13107200,
13122000,
13271040,
13286025,
13436928,
13500000,
13668750,
13824000,
13996800,
14062500,
14155776,
14171760,
14348907,
14400000,
14580000,
14745600,
14762250,
14929920,
15000000,
15116544,
15187500,
15360000,
15552000,
15625000,
15728640,
15746400,
15925248,
15943230,
16000000,
16200000,
16384000,
16402500,
16588800,
16777216,
16796160,
16875000,
17006112,
17280000,
17496000,
17578125,
17694720,
17714700,
17915904,
18000000,
18225000,
18432000,
18662400,
18750000,
18874368,
18895680,
18984375,
19131876,
19200000,
19440000,
19531250,
19660800,
19683000,
19906560,
20000000,
20155392,
20250000,
20480000,
20503125,
20736000,
20971520,
20995200,
21093750,
21233664,
21257640,
21600000,
21870000,
22118400,
22143375,
22394880,
22500000,
22674816,
22781250,
23040000,
23328000,
23437500,
23592960,
23619600,
23887872,
23914845,
24000000,
24300000,
24576000,
24603750,
24883200,
25000000,
25165824,
25194240,
25312500,
25509168,
25600000,
25920000,
26214400,
26244000,
26542080,
26572050,
26873856,
27000000,
27337500,
27648000,
27993600,
28125000,
28311552,
28343520,
28697814,
28800000,
29160000,
29296875,
29491200,
29524500,
29859840,
30000000,
30233088,
30375000,
30720000,
31104000,
31250000,
31457280,
31492800,
31640625,
31850496,
31886460,
32000000,
32400000,
32768000,
32805000,
33177600,
33554432,
33592320,
33750000,
34012224,
34171875,
34560000,
34992000,
35156250,
35389440,
35429400,
35831808,
36000000,
36450000,
36864000,
36905625,
37324800,
37500000,
37748736,
37791360,
37968750,
38263752,
38400000,
38880000,
39062500,
39321600,
39366000,
39813120,
39858075,
40000000,
40310784,
40500000,
40960000,
41006250,
41472000,
41943040,
41990400,
42187500,
42467328,
42515280,
43046721,
43200000,
43740000,
44236800,
44286750,
44789760,
45000000,
45349632,
45562500,
46080000,
46656000,
46875000,
47185920,
47239200,
47775744,
47829690,
48000000,
48600000,
48828125,
49152000,
49207500,
49766400,
50000000,
50331648,
50388480,
50625000,
51018336,
51200000,
51840000,
52428800,
52488000,
52734375,
53084160,
53144100,
53747712,
54000000,
54675000,
55296000,
55987200,
56250000,
56623104,
56687040,
56953125,
57395628,
57600000,
58320000,
58593750,
58982400,
59049000,
59719680,
60000000,
60466176,
60750000,
61440000,
61509375,
62208000,
62500000,
62914560,
62985600,
63281250,
63700992,
63772920,
64000000,
64800000,
65536000,
65610000,
66355200,
66430125,
67108864,
67184640,
67500000,
68024448,
68343750,
69120000,
69984000,
70312500,
70778880,
70858800,
71663616,
71744535,
72000000,
72900000,
73728000,
73811250,
74649600,
75000000,
75497472,
75582720,
75937500,
76527504,
76800000,
77760000,
78125000,
78643200,
78732000,
79626240,
79716150,
80000000,
80621568,
81000000,
81920000,
82012500,
82944000,
83886080,
83980800,
84375000,
84934656,
85030560,
86093442,
86400000,
87480000,
87890625,
88473600,
88573500,
89579520,
90000000,
90699264,
91125000,
92160000,
93312000,
93750000,
94371840,
94478400,
94921875,
95551488,
95659380,
96000000,
97200000,
97656250,
98304000,
98415000,
99532800,
100000000,
100663296,
100776960,
101250000,
102036672,
102400000,
102515625,
103680000,
104857600,
104976000,
105468750,
106168320,
106288200,
107495424,
108000000,
109350000,
110592000,
110716875,
111974400,
112500000,
113246208,
113374080,
113906250,
114791256,
115200000,
116640000,
117187500,
117964800,
118098000,
119439360,
119574225,
120000000,
120932352,
121500000,
122880000,
123018750,
124416000,
125000000,
125829120,
125971200,
126562500,
127401984,
127545840,
128000000,
129140163,
129600000,
131072000,
131220000,
132710400,
132860250,
134217728,
134369280,
135000000,
136048896,
136687500,
138240000,
139968000,
140625000,
141557760,
141717600,
143327232,
143489070,
144000000,
145800000,
146484375,
147456000,
147622500,
149299200,
150000000,
150994944,
151165440,
151875000,
153055008,
153600000,
155520000,
156250000,
157286400,
157464000,
158203125,
159252480,
159432300,
160000000,
161243136,
162000000,
163840000,
164025000,
165888000,
167772160,
167961600,
168750000,
169869312,
170061120,
170859375,
172186884,
172800000,
174960000,
175781250,
176947200,
177147000,
179159040,
180000000,
181398528,
182250000,
184320000,
184528125,
186624000,
187500000,
188743680,
188956800,
189843750,
191102976,
191318760,
192000000,
194400000,
195312500,
196608000,
196830000,
199065600,
199290375,
200000000,
201326592,
201553920,
202500000,
204073344,
204800000,
205031250,
207360000,
209715200,
209952000,
210937500,
212336640,
212576400,
214990848,
215233605,
216000000,
218700000,
221184000,
221433750,
223948800,
225000000,
226492416,
226748160,
227812500,
229582512,
230400000,
233280000,
234375000,
235929600,
236196000,
238878720,
239148450,
240000000,
241864704,
243000000,
244140625,
245760000,
246037500,
248832000,
250000000,
251658240,
251942400,
253125000,
254803968,
255091680,
256000000,
258280326,
259200000,
262144000,
262440000,
263671875,
265420800,
265720500,
268435456,
268738560,
270000000,
272097792,
273375000,
276480000,
279936000,
281250000,
283115520,
283435200,
284765625,
286654464,
286978140,
288000000,
291600000,
292968750,
294912000,
295245000,
298598400,
300000000,
301989888,
302330880,
303750000,
306110016,
307200000,
307546875,
311040000,
312500000,
314572800,
314928000,
316406250,
318504960,
318864600,
320000000,
322486272,
324000000,
327680000,
328050000,
331776000,
332150625,
335544320,
335923200,
337500000,
339738624,
340122240,
341718750,
344373768,
345600000,
349920000,
351562500,
353894400,
354294000,
358318080,
358722675,
360000000,
362797056,
364500000,
368640000,
369056250,
373248000,
375000000,
377487360,
377913600,
379687500,
382205952,
382637520,
384000000,
387420489,
388800000,
390625000,
393216000,
393660000,
398131200,
398580750,
400000000,
402653184,
403107840,
405000000,
408146688,
409600000,
410062500,
414720000,
419430400,
419904000,
421875000,
424673280,
425152800,
429981696,
430467210,
432000000,
437400000,
439453125,
442368000,
442867500,
447897600,
450000000,
452984832,
453496320,
455625000,
459165024,
460800000,
466560000,
468750000,
471859200,
472392000,
474609375,
477757440,
478296900,
480000000,
483729408,
486000000,
488281250,
491520000,
492075000,
497664000,
500000000,
503316480,
503884800,
506250000,
509607936,
510183360,
512000000,
512578125,
516560652,
518400000,
524288000,
524880000,
527343750,
530841600,
531441000,
536870912,
537477120,
540000000,
544195584,
546750000,
552960000,
553584375,
559872000,
562500000,
566231040,
566870400,
569531250,
573308928,
573956280,
576000000,
583200000,
585937500,
589824000,
590490000,
597196800,
597871125,
600000000,
603979776,
604661760,
607500000,
612220032,
614400000,
615093750,
622080000,
625000000,
629145600,
629856000,
632812500,
637009920,
637729200,
640000000,
644972544,
645700815,
648000000,
655360000,
656100000,
663552000,
664301250,
671088640,
671846400,
675000000,
679477248,
680244480,
683437500,
688747536,
691200000,
699840000,
703125000,
707788800,
708588000,
716636160,
717445350,
720000000,
725594112,
729000000,
732421875,
737280000,
738112500,
746496000,
750000000,
754974720,
755827200,
759375000,
764411904,
765275040,
768000000,
774840978,
777600000,
781250000,
786432000,
787320000,
791015625,
796262400,
797161500,
800000000,
805306368,
806215680,
810000000,
816293376,
819200000,
820125000,
829440000,
838860800,
839808000,
843750000,
849346560,
850305600,
854296875,
859963392
};
int main()
{
//这道题的数据量只有1500，完全可以打表
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
return 0;
printf("%d\n",ugly[n]);
}
return 0;
}
时间： 2024-03-16 09:11:02