时间超限问题 - 编程论坛

#2

rjsp2020-11-02 10:31

你都不肯将题目告知大家，那大家能猜出你想完成什么功能？

从你的代码来看，你就是想输出 n的平方根的整数部分，那为什么不直接 printf( "%.0f\n", floor(sqrt(n)) );

程序代码：

#include <stdio.h>
#include <math.h>

int main( void )
{
for( unsigned n; scanf("%u",&n)==1; )
printf( "%.0f\n", floor(sqrt(n)) );
}

#3

祁建邵2020-11-02 10:58

回复 2楼 rjsp

忘记了。
题目：

输出[1，n]内所有的完全平方数。

输入
输入一个正整数n，n < 2^30

输出
输出[1，n]内所有的完全平方数。

样例输入
10
100
样例输出
3
10

#4

祁建邵2020-11-02 10:59

回复 2楼 rjsp

是输出完全平方数个数。

#5

lin51616782020-11-02 11:22

取值范围最大 2的30次方
你每一个数字都尝试一次 O(n)太慢导致超时
你可以换一个思路
一个数字对应一个完全平方数
比如 5 对应 25
只要一个数字的平方没有超过n
那么一定有一个完全平方数在里面
反过来想就是 n开根取整是最后一个完全平方数的对应数
包括n开方取整在内前面全部数字都有对应完全平方数
那就很简单了
(int)sqrt(n)+1
就可以了
+1是处理 0
比如 [0,5]有多少个完全平方数
5开根取整是 2
表示包括2在内前面的数字都有完全平方数
0 1 2 一共是3 这3个数字对应完全平方数是 0 1 4
符合题目要求的范围0-5
数量是3

#6

nosnoy2020-11-02 14:48

回复 3楼祁建邵

开最大值平方取整，就是完全平方数的值

#7

风过无痕19892020-11-03 02:53

以下是引用祁建邵在2020-11-2 10:58:27的发言：

忘记了。
题目：
输出[1，n]内所有的完全平方数。

输入
输入一个正整数n，n < 2^30

输出
输出[1，n]内所有的完全平方数。

样例输入
10
100
样例输出
3
10

说实话，这个题目看不懂，要求输出所有的完全平方数，然而，样例输入和样例输出又是那个样子。
这里有三个技巧：1、最大数一半的平方是绝对要大于最大数的！所以，循环到最大数一半即可，这样可以节省不少的时间；2、两个数相乘所需要的时间也必定小于开平方所需要的时间。3、当 j 大于 i 的平方，中断此次循环，进一步节省时间。下面是我的程序：

程序代码：

#include<stdio.h>
int main()
{
    int i,j,n,sum = 0;
    scanf_s("%d", &n);

    for (i = 1; i <= n / 2; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (j == i * i)
            {
                printf("%d\n", j);
                sum += 1;
            }
            else if(j > i * i)      // 当 j 大于 i 的平方，中断此次循环，进一步节省时间
                break;
        }

    }
    printf("%d\n", sum);
}

#8

祁建邵2020-11-03 22:56

回复 5楼 lin5161678

懂了，谢谢大哥。

#9

祁建邵2020-11-03 22:58

回复 7楼风过无痕1989

谢谢大哥。