UC知道pascal--丑数
来源：百度知道 编辑：UC知道 时间：2024/05/16 07:59:29
1.求丑数（UGLY）
源程序名 ugly.??? (PAS,C,CPP)
可执行文件名 ugly.EXE
输入文件名 ugly.IN
输出文件名 ugly.OUT
所谓丑数，就是指那些因子只含2，3，5的数。1，2，3，4，5，6，8，9，10，12，15是最前面的11个丑数。为了方便起见，把1也看作是丑数。
请你编写一个程序，输入n，n<3000，寻找并打印第n个丑数。
样例输入：
11
样例输出：
15
源程序名 ugly.??? (PAS,C,CPP)
可执行文件名 ugly.EXE
输入文件名 ugly.IN
输出文件名 ugly.OUT
所谓丑数，就是指那些因子只含2，3，5的数。1，2，3，4，5，6，8，9，10，12，15是最前面的11个丑数。为了方便起见，把1也看作是丑数。
请你编写一个程序，输入n，n<3000，寻找并打印第n个丑数。
样例输入：
11
样例输出：
15
14怎么不是的？
我编出来输入11输出14
var
a:array[1..10000]of integer;
i,n,s:integer;
begin
a[1]:=1;
read(n);
s:=2;
for i:=2 to n*n do
if i mod 2=0 or i mod 3=0 or i mod 5=0 then
begin
a[s]:=i;
inc(s);
end;
writeln(a[n]);
end.
标准做法是用堆来管理。（没看过堆这种数据结构就去看看）
1.堆清空。
2.加入1。
3.取堆中根结点数m，打印，并在堆中加入m*2,m*3,m*5。(开个HASH表，添加过的数不重复添加。)
4.反复进行步骤3，直到打印了n个数。
5.退出。
另3楼，说了丑数只能是2、3、5的倍数，14是7的倍数了。
找不出规律，一个个死做吧...
hh