本文主要是介绍HDOJ 1058 Humble Numbers解题报告【DP】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Humble Numbers题目详见http://acm.hdu.edu.cn/showproblem.php?pid=1058
开始拿到这个题目的时候还纠结了半天,英语很差的话这个题是不可能AC的。。而我就是其中之一。。。
Humber Number不用管它啥意思,就是一类定义的数而已。如果一个数的质因数(素因数)仅仅是2、3、5 or 7的话那就被称为Humber Number。特殊的1也在其列。而且题目给出了前20个Humber Number。1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27。注意仅仅二字,11包含质因数11,26包含质因数13都不在其列。编写程序求第n个Humble Number。输入输出格式要搞明白。
OK,搞清了题意,那就来分析一下。这个题的意思很清楚明了,就是给你一个N,求出第N个Humble Number。如何求?一开始我想到遍历,可是觉得很麻烦,估计会很超时。我就想啊,既然是2 3 5 7 ,我用1和他们相加如何?得到了3 4 6 8,这些数肯定是Humble Number。可是如何继续下去呢?用3和2 3 5 7相加?得到 5 6 8 10,还要用4和他们相加?继续下去?感觉很繁琐,就像是一颗树4叉树一样。
所以我放弃了这个思路,又开始想遍历,如果我知道了某个数是不是Humble Number,那我不就可以统计第N个了吗?从1开始遍历,如果i是Humble Number,那我就nums++,知道nums和你给定的N相等我们就求出了。。如何判断一个数是不是Humble Number呢?Humble Number的质因数只能是2 3 5 7 ,被这些数分别整除后结果肯定是1,而且整除次数最多是Number/2.
OK,上代码
#include <iostream>
using namespace std;//查看n是不是Humble Number
int IsHumbleNumber(long int n);int main()
{ long int nums;long int number;long int i;while(cin>>number){if(0==number)break;nums=0; //初始化 记录有多少个HumbleNumber for(i=1;;i++){if(IsHumbleNumber(i))nums++;if(number==nums)break;} //此时i的值就是第number个humble number//输出格式if((number>=4)&&(number<=20))cout<<"The "<<number<<"th humble number is "<<i<<endl; //英语差了这个题别想AC了。。。else if(1==(number-(number/10)*10))cout<&l
这篇关于HDOJ 1058 Humble Numbers解题报告【DP】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!