Question

C语言程序设计：求第1500个只有2，3，5因子的数。数是从小到大排列，第一个数是1，1＝2^0*3^0*5^0

不要百度的，求大神自己写，最好能详细说明一下，新手有些可能看不懂（不是C＋＋，是C）

Answer 1

这题可以用动态规划解

状态转移方程是F[n]=min(F[当前2的指数]*2,F[当前3的指数]*3,F[当前5的指数]*5)

即下一项的值等于当前2的指数项的值×2、当前3的指数项的值×3或当前5的指数项×5中最小的那个，同时将对应因子的指数加1

其中F[n]代表第n个只有2,3,5因子的数

#include<stdio.h>
double min(double index_2,double index_3,double index_5) //min函数返回三者中最小的一个
{
    double min_t=index_2;
    if(min_t>index_3) min_t=index_3;
    if(min_t>index_5) min_t=index_5;
    return min_t;
}
int main()
{
    double f[1500];
    int times_2=0; //将三个因子的次数都置为0
    int times_3=0;
    int times_5=0;
    f[0]=1; //将第一项置为1
    int i;
    for(i=1;i<1500;i++)
    {
        f[i]=min(f[times_2]*2,f[times_3]*3,f[times_5]*5); //第i项的值等于第times_2项*2、第times_3项*3、第times_5项*5中最小的一个,注意可能有相等的情况
        //同时将对应因子的次数加1，可能有相等的情况，因此必须逐一判断
        if(f[i]==f[times_2]*2) times_2++;
        if(f[i]==f[times_3]*3) times_3++;
        if(f[i]==f[times_5]*5) times_5++;
    }
    printf("%.0f",f[1499]); //输出第1500项的值
}

追问

没学过动态规划，完全看不懂

追答

那这个题对你来说太难了，你可以跳过
或者用你学过的穷举法解，不过这样一定会超时。