Напишите функцию getNumberOfSquares(int n) (C) / get_number_of_squares, которая возвращает, сколько целых (начиная с 1, 2...) чисел, возведенных в степень 2 и затем сложенных, меньше некоторого числа, заданного в качестве параметра.

Например, 1: Для n = 6 результат должен быть 2, потому что 1^2 + 2^2 = 1 + 4 = 5 и 5 < 6 Например, 2: Для n = 15 результат должен быть 3, потому что 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14 и 14 < 15

Для приведенной выше функции я написал программу, но тестовая программа выдала ошибку, то есть при вводе getNumberOfSquares(100000) функция должна вернуть 66, но моя возвращает 403.

Вот мое решение:

int getNumberOfSquares(int n){

    int sum=0;
    int limit=0;
    for (int i = 1; i < n && n>sum; ++i)
    {
        sum += i*i;
        ++limit;
        if(sum>=n){
            sum -= i*i;
            --limit;
        }
    }
    return limit;
}

mustafalinan

Ответов: 2

Ответы (2)

Предполагая, что целое число в вашей системе имеет 32 бита, i*i переполнится, когда достигнет значения 65536. Это приводит к неточностям.

Но на самом деле он не должен достичь этой точки, поскольку вы продолжаете проверять значения i даже после того, как значение sum превысит n. Вы должны выйти из цикла, когда достигнете этой точки.

int getNumberOfSquares(int n){

    int sum=0;
    int limit=0;
    for (int i = 1; i < n; ++i)
    {
        if (sum + i*i >= n) {
            return limit;
        }
        sum += i*i;
        ++limit;
    }
    return limit;
}

Вы хотите найти наибольшее i такое, что sum < n. Поэтому это должно быть единственным условием, нарушающим цикл. Вам не нужно проверять даже то, что i < n.

Сейчас проблема вашего кода в том, что вы изменяете sum, когда она становится достаточно большой, чтобы разорвать цикл, делая ее снова меньше, чем n. Поэтому если бы sum < n было вашим единственным условием, у вас был бы бесконечный цикл. Но поскольку у вас есть условие i < n, программа продолжает прибавлять и вычитать i*i к sum до тех пор, пока i < n.

Если n достаточно мал, сложение и вычитание i*i не меняет сумму, и когда цикл прерывается, вы получаете свой результат.

Но если i может вырасти настолько, что сумма станет больше, чем наибольший int, который вы можете иметь, sum переполнится и станет бессмысленным значением.

Решением является исключение условия if(sum>=n){}.

Удаление условия покажет, что limit подобен i, поэтому вы можете даже использовать i в качестве возвращаемого значения.

Имея в виду, что вам не нужно условие i < n, ваша функция становится

int getNumberOfSquares(int n) {

    int i, sum = 0;

    for(i = 1; sum < n; ++i) {
        
        sum += i*i;
    }
    
    return i-2;
}

Возвращение i-2, потому что i, составляющее sum > n, было уже на 1 больше, чем значение, которое вы хотели вернуть, а затем, перед тем как sum > n будет проверено, for увеличивает i.

2022 WebDevInsider