[ACM_ZJUT_1299]幸运妈妈
杰拉斯 | 时间:2012-04-11, Wed | 25,062 views编程算法
幸运妈妈
Time Limit:1000MS Memory Limit:32768K
Description
某外星国并没实行计划生育,决定选出幸运妈妈。具体如下: 假设妈妈生了N个孩子,若N能表示成某个正整数X的K次幂(K>1),N可能有多种表示方法,找出最小的X并输出相应的K,你若找到,则政府将奖励那位妈妈,你帮她快速断定一下吧! 例如 16=2^4=4^2,64=4^3=2^6=8^2则16应表示为2^4,64应表示为2^8。
Input
每行一个正整数N,输入文件以0为结束标志。(0<N<10000)
Output
每行有两个整数,如果能表示,则输出X K,(中间用一个空格隔开)如果不能,则输出0 0;
Sample Input
5 4 16 27 0
Sample Output
0 0
2 2
2 4
3 3Source
这道题用了两种方法来做,都是Wrong Answer,不知为何,还请各位大牛指教!
第一种,若XK = N,则K = logXN = lg(N) / lg(X),那么通过判断K是否为整数来确定N能否写为N的K次方:
#include<iostream> #include<cmath> #include<float.h> int main(){ int n; while(scanf("%d", &n) != EOF && n){ int X = 0, K = 0; if(n == 1){ X = 1; K = 2; } else for(int i = 2; i <= sqrt((float)n); ++i){ double tmp = log((float)n) / log((float)i); if(fabs(tmp - (int)tmp) <= FLT_EPSILON){ //判断tmp是否为整数 K = tmp; X = i; break; } //printf("%d\n", tmp); } printf("%d %d\n", X, K); } return 0; }无法通过,因此想到了第二种方法,即用map来存10000以内的所有最小X情况,然后根据用户输入的N直接输出:
#include<iostream> #include<cmath> #include<map> using namespace std; struct s{ int X; int K; }; int main(){ int n = 10000; map<int, s> m; m[1].X = 1; m[1].K = 2; for(int i = 2; i <= 100; ++i){ for(int j = 2; j < 15; ++j){ int num = pow((float)i, j); if(num > 10000 || (m[num].X > 0 && m[num].X < i)){ break; } m[num].X = i; m[num].K = j; } } while(scanf("%d", &n) != EOF && n){ printf("%d %d\n", m[n].X, m[n].K); } return 0; }没想到还是Wrong Answer,百思不得其解,还请各位大牛多多指教。。
后记:
让我纠结了这么久的原因竟然是题目出错,AC代码如下:
#include<iostream> #include<cmath> #include<map> using namespace std; struct s{ int X; int K; }; int main(){ int n = 10000; map<int, s> m; for(int i = 99; i >= 2; --i){ for(int j = 2; j < 15; ++j){ int num = pow((float)i, j); if(num > 10000 || (m[num].X > 0 && m[num].K < j)){ continue; } m[num].X = i; m[num].K = j; } } while(scanf("%d", &n) != EOF && n){ printf("%d %d\n", m[n].X, m[n].K); } return 0; }老师的代码:
#include<iostream> using namespace std; struct s{ int x,y; } ; int main(){ s a[10000]; for(int k=1;k<=9999;k++) { a[k].x=0;a[k].y=0; } for(int i=2; i<100; i++){ int t=i*i; for(int j=2; t<10000; j++,t*=i) a[t].x=i, a[t].y=j; } for(int n; cin>>n && n; ) cout<<a[n].x<<" "<<a[n].y<<"\n"; }如需转载请注明出处:杰拉斯的博客
相关文章
这应该是 K = logX N = lg(N) / lg(X) 被你误导了。。。
第一种,四舍五入不对,左边 double 型,小数部分不一般为零;右边 int 型,运算时自动转换为 double 型,小数部分为零。两者必然不等。
判断两个 double 型相等一般用 fabs( d1 - d2 ) <= FLT_EPSILON ,而不是直接用 operator ==
(FLT_EPSILON 是 浮点运算相关常量,位于 float.h (ANSI C 头文件,具体值在不同编译器略有差别,也可以自己定义,一般取 1E-3~1E-5 就差不多了,看具体情况 ))
所以要判断 K == lg(N) / lg(X) 可以用
fabs( K - log(N)/log(X) ) <= FLT_EPSILON ,
我觉得写 ( K * log(X) - log(N) ) <= FLT_EPSILON 更好,一方面乘法效率比除法高,另外误差也更小。
改改改。。。
按你原来的思路,14行的 if 条件可以写 fabs( tmp - (int)(tmp + 0.5) ) <= FLT_EPSILON 试试
个人认为,第二种没什么必要
受教了,但改了之后还是Wrong Answer。。
其实我也举得第二种没有必要,但只是想换个保鲜点的方式,可惜还是无法通过,不知为何?
你的代码我简单测了一下,WA主要是浮点运算误差造成的。这种误差通常在两种情况下会发生,一是分母较小作除法(2^13),一是两数相近作减法(3^5)。你测以下2^13,3^5,10^3,17^3,25^2。这题要想不WA只能自己实现一个整数版的log()。
你的第二种方法估计也是这个原因,具体我没测试,很可能是因为pow()的误差造成的。
不对,<1000,pow()也不会有误差