数学问题
数学问题
xiaohejun
发布于 2020-02-18 09:16:41
发布于 2020-02-18 09:16:41
数学问题 时间限制：2000/1000 MS（Java / Others）内存限制：32768/32768 K（Java / Others） 总提交：1321接受提交：476
问题描述 给定一个正整数n，请计算k个满足多少正整数 ķ^k≤ N。
输入 没有超过50个测试用例。
每种情况只包含一行中的积分整数n。
1 ≤ N ≤ 1e18
产量 对于每个测试用例，输出整数表示正整数k满足的数量 k^k≤ N 在一条线上。
样品输入 1 4
样品输出 1 2
错误答案：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
// 正整数
long long n;
int k = 1, sum = 0;
while (scanf("%I64d", &n) != EOF && n >= 1 && n <= 1e18)
{
while (k <= n)
{
if (pow(k, k) <= n)
{
sum++;
k++;
}
else {
break;
}
}
printf("%d\n", sum);
sum = 0;
k = 1;
}
return 0;
}正确答案：
#include<iostream>
#include<cmath>
using namespace std;
long long a[20];
void deal()
{
for (int i = 1; i <= 15; i++) // 计算k的k次方
{
long long result = 1;
for (int j = 1; j <= i; j++)
{
result *= i;
}
a[i] = result;
}
a[16] = (long long)1e18 * 9; // 界限是1e18
}
int main()
{
deal();
long long n;
while (cin >> n)
{
for (int i = 1; i <= 16; i++)
{
if (a[i] > n)
{
cout << i - 1 << endl;
break;
}
}
}
}出错原因：
1. 你会发现两种方法的最大不同：
- 第一种是每一次算出一个k的k次方来和n比较，使用pow()函数计算k的k次方
- 第二种是把k^k(1<=k<=15)放在一个数组中，并且在最后一个数中放a[16] = 1e18 * 9计算k的k次方的函数是自己写的
2. 第二种成功的方法为什么(1<=k<=15)，并且在数组下标16位放1e16*9：
- 15^15 = 437,893,890,380,859,375 ，一共18位，但是比1e18小
- 16^16 = 18,446,744,073,709,511,616 ，一共20位, 比1e18大
- long long的最大值：9,223,372,036,854,775,807，一共19位
- 这样就确定了k的范围，并且解释了为什么在数组下标16位放1e16*9
- 当然你也可以这样写，只要最大的数字比1e18大就好
a[16] = (long long)1e18 + 1; // 界限是1e18- 但是这样不是最严谨，尽量放大一点是最严谨的
2. 重点要解释的问题，使用pow()函数为什么会出错：
pow()函数返回的是double类型的数，使用pow()函数打印15的15次方你会发现：
pow(15,15)
再拿计算器计算
计算器计算15^15
两个结果不一样，对比下面两张图你就会发现
long long
这里写图片描述
当数字大到15^15时两个计算的结果就不同，所以这就导致了第一种方法出现错误答案的原因！
总结：
解题时注意关注数据类型的取值范围和精度问题，还有题目中的数据的取值范围。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-09-092，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录