Подтвердить что ты не робот

Нужно ли явно обрабатывать отрицательные числа или ноль при суммировании квадратов?

У меня недавно был тест в моем классе. Одна из проблем заключалась в следующем:

Given a number n, write a function in C/C++ that returns the sum of the digits of the number squared. (The following is important). The range of n is [ -(10^7), 10^7 ]. Example: If n= 123, your function should return 14 (1^2 + 2^2 + 3^2 = 14).

Это функция, которую я написал:

int sum_of_digits_squared(int n) 
{
    int s = 0, c;

    while (n) {
        c = n % 10;
        s += (c * c);
        n /= 10;
    }

    return s;
}

посмотрел прямо на меня. Итак, теперь тест вернулся, и я обнаружил, что учитель не дал мне все пункты по причине, которую я не понимаю. По его словам, для того, чтобы моя функция была завершена, я должен был добавить следующую деталь:

int sum_of_digits_squared(int n) 
 {
    int s = 0, c;

    if (n == 0) {      //
        return 0;      //
    }                  //
                       // THIS APPARENTLY SHOULD'VE 
    if (n < 0) {       // BEEN IN THE FUNCTION FOR IT
        n = n * (-1);  // TO BE CORRECT
    }                  //

    while (n) {
        c = n % 10;
        s += (c * c);
        n /= 10;
    }

    return s;
}

Аргументом для этого является то, что число n находится в диапазоне [- (10 ^ 7), 10 ^ 7], поэтому оно может быть отрицательным числом. Но я не вижу, где моя собственная версия функции терпит неудачу. Если я правильно понимаю, значение while(n) - это while(n != 0), а не , а while (n > 0), поэтому в моей версии функции число n не может не войти в петля. Это будет работать точно так же.

Затем я попробовал обе версии этой функции на своем компьютере дома, и я получил точно такие же ответы на все примеры, которые я пробовал. Итак, sum_of_digits_squared(-123) равен sum_of_digits_squared(123) (что опять-таки равно 14) (даже без деталей, которые я, очевидно, должен был добавить). Действительно, если я пытаюсь напечатать на экране цифры числа (от наименьшего до наибольшего значения), в случае 123 я получаю 3 2 1, а в случае -123 я получаю -3 -2 -1 (который на самом деле вроде интересно). Но в этой проблеме это не имеет значения, так как мы возводим цифры в квадрат.

Так кто же не прав?

РЕДАКТИРОВАТЬ: мой плохой, я забыл указать и не знал, что это важно. Версия C, используемая в нашем классе и тестах, должна быть C99 или более новой. Таким образом, я предполагаю (читая комментарии), что моя версия получит правильный ответ в любом случае.

4b9b3361

Ответ 1

Подводя итоги обсуждения, которое просачивалось в комментариях:

  • Нет веских причин для предварительного тестирования на n == 0. Тест while(n) отлично с этим справится.
  • Вероятно, ваш учитель все еще привык к более ранним временам, когда результат % с отрицательными операндами был определен по-другому. В некоторых старых системах (включая, в частности, ранний Unix на PDP-11, где Деннис Ритчи первоначально разработал C), результат a % b всегда был в диапазоне [0 .. b-1], что означает, что -123% 10 было 7. В такой системе необходим предварительный тест для n < 0.

Но вторая пуля относится только к более ранним временам. В текущих версиях стандартов C и C++ целочисленное деление определено для усечения до 0, поэтому получается, что n % 10 гарантированно даст вам (возможно, отрицательную) последнюю цифру n, даже когда n отрицательно.

Итак, ответ на вопрос "В чем смысл while(n)?" "Точно так же, как while(n != 0)", и ответ "Будет ли этот код работать правильно как для отрицательного, так и для положительного n?" "Да, под любым современным компилятором, соответствующим стандартам". Ответ на вопрос "Тогда почему инструктор отметил это?" возможно, они не знают о существенном переопределении языка, которое произошло с C в 1999 году и с C++ в 2010 году или около того.

Ответ 2

Ваш код в порядке

Вы абсолютно правы, а ваш учитель не прав. Нет абсолютно никакой причины добавлять эту дополнительную сложность, поскольку это никак не влияет на результат. Это даже вносит ошибку. (См. ниже)

Во-первых, отдельная проверка, если n равен нулю, очевидно, совершенно не нужна, и это очень легко реализовать. Если честно, я на самом деле подвергаю сомнению вашу компетентность учителя, если у него есть возражения по этому поводу. Но я думаю, что каждый может время от времени пускать мозги. Тем не менее, я ДЕЙСТВИТЕЛЬНО считаю, что while(n) следует изменить на while(n != 0), потому что он добавляет немного большей ясности, даже не стоя дополнительной строки. Это незначительная вещь, хотя.

Второй более понятен, но он все еще не прав.

Вот что говорит стандарт C11 6.5.5.p6 :

If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b и a%b is undefined.

Сноска гласит:

Это часто называют "усечением до нуля".

Усечение до нуля означает, что абсолютное значение для a/b равно абсолютному значению для (-a)/b для всех a и b, что, в свою очередь, означает, что ваш код в порядке. Тем не менее, ваш учитель имеет смысл, что вы должны быть осторожны, потому что факт, что вы возводите в квадрат результат, на самом деле имеет решающее значение. Вычисление a%b согласно приведенному выше определению - простая математика, но это может пойти вразрез с вашей интуицией. Например, 7%3==1, но (-7)%(-3)==(-1). Вот фрагмент, демонстрирующий это:

$ cat > main.c 
#include <stdio.h>

void f(int a, int b) 
{
    printf("a: %2d b: %2d a/b: %2d a\%b: %2d (a%b)^2: %2d (a/b)*b+a%b==a: %5s\n",
           a, b ,a/b, a%b, (a%b)*(a%b), (a/b)*b+a%b == a ? "true" : "false");
}

int main(void)
{
    int a=7, b=3;
    f(a,b);
    f(-a,b);
    f(a,-b);
    f(-a,-b);
}

$ gcc main.c -Wall -Wextra -pedantic -std=c99

$ ./a.out
a:  7 b:  3 a/b:  2 a%b:  1 (a%b)^2:  1 (a/b)*b+a%b==a:  true
a: -7 b:  3 a/b: -2 a%b: -1 (a%b)^2:  1 (a/b)*b+a%b==a:  true
a:  7 b: -3 a/b: -2 a%b:  1 (a%b)^2:  1 (a/b)*b+a%b==a:  true
a: -7 b: -3 a/b:  2 a%b: -1 (a%b)^2:  1 (a/b)*b+a%b==a:  true

Итак, по иронии судьбы, ваш учитель доказал свою точку зрения, ошибаясь.

Код вашего учителя имеет недостатки

Да, это действительно так. Если входом является INT_MIN, и архитектура использует два дополнения И, если битовая комбинация, в которой бит знака равен 1, а все биты значения равны 0, НЕ является значением прерывания (использование двух дополнений без значений прерывания очень распространено), тогда ваш Код учителя приведет к неопределенному поведению в строке n = n * (-1). Ваш код - если даже немного - лучше, чем его. И если учесть небольшую ошибку, сделав код ненужным сложным и получив абсолютно нулевое значение, я бы сказал, что ваш код НАМНОГО лучше.

Но опять же, ваш учитель прямо говорит, что n должно быть в диапазоне [- (10 ^ 7), 10 ^ 7]. Так что это могло бы спасти его, если бы не случай, когда int не обязательно является 32-битным целым числом. Если вы скомпилируете его для 16-битной архитектуры, оба ваших фрагмента кода будут ошибочными. Но ваш код все еще намного лучше, потому что в этом сценарии была бы ошибка, упомянутая выше INT_MIN. Чтобы избежать этого, вы можете использовать вместо этого long. Тогда вы будете в безопасности. long гарантированно сможет хранить все значения в диапазоне [-2147483647; 2147483647]

Ответ 3

Мне не совсем нравится ни ваша версия, ни ваша учительница. Ваша версия учителя делает дополнительные тесты, которые вы правильно указали, не нужны. Оператор C mod не является правильным математическим модом: mod 10 с отрицательным числом приведет к отрицательному результату (правильный математический модуль всегда неотрицателен). Но так как вы все равно возводите в квадрат, без разницы.

Но это далеко не очевидно, поэтому я бы добавил к вашему коду не проверки вашего учителя, а большой комментарий, объясняющий, почему он работает. Например.:

/* ПРИМЕЧАНИЕ: это работает для отрицательных значений, потому что модуль получает квадрат */

Ответ 4

ПРИМЕЧАНИЕ: Поскольку я писал этот ответ, вы пояснили, что используете C. Большая часть моего ответа касается C++. Однако, поскольку в вашем заголовке все еще есть C++, а вопрос все еще помечен C++, я решил ответить в любом случае, если это все еще полезно для других людей, тем более что большинство ответов, которые я видел до сих пор, в основном неудовлетворительный.

В современном C++ (примечание: я действительно не знаю, где на этом стоит С), кажется, ваш профессор ошибается в обоих случаях.

Во-первых, эта часть прямо здесь:

if (n == 0) {
        return 0;
}

В C++ это в основном то же самое, что и:

if (!n) {
        return 0;
}

Это означает, что ваше время эквивалентно чему-то вроде этого:

while(n != 0) {
    // some implementation
}

Это означает, что поскольку вы просто выходите из своего if, если while не будет выполняться в любом случае, на самом деле нет смысла помещать это if здесь, поскольку то, что вы делаете после цикла и в if, в любом случае эквивалентны, Хотя я должен сказать, что по какой-то причине они были другими, вам нужно иметь это, если.

Так что на самом деле это утверждение if не особенно полезно, если я не ошибаюсь.

Вторая часть, где вещи становятся волосатыми:

if (n < 0) {
    n = n * (-1);
}  

Суть проблемы заключается в том, что выводит модуль отрицательного числа.

В современном C++ это, по-видимому, в основном четко определено:

  Двоичный/оператор дает частное, а двоичный оператор% - остаток от деления первого выражения на второе. Если второй операнд/или% равен нулю, поведение не определено. Для целочисленных операндов оператор/дает алгебраический фактор с любой отброшенной дробной частью; если частное a/b представимо в типе результата, (a/b) * b + a% b равно a.

И позже:

  Если оба операнда неотрицательны, то остаток неотрицателен; если нет, то знак остатка определяется реализацией.

Как правильно указывает автор цитируемого ответа, важная часть этого уравнения здесь:

(a/b)*b + a%b

Если взять пример вашего случая, вы получите что-то вроде этого:

-13/ 10 = -1 (integer truncation)
-1 * 10 = -10
-13 - (-10) = -13 + 10 = -3 

Единственный улов - последняя строка:

Если оба операнда неотрицательны, то остаток неотрицателен; если нет, то знак остатка определяется реализацией.

Это означает, что в таком случае только знак sign определяется реализацией. Это не должно быть проблемой в вашем случае, потому что вы все равно возводите это значение в квадрат.

Тем не менее, имейте в виду, что это не обязательно относится к более ранним версиям C++ или C99. Если это то, что использует ваш профессор, возможно, именно поэтому.


ОБНОВЛЕНИЕ: Нет, я не прав. Похоже, это относится и к C99 или новее:

C99 requires that when a/b is representable:

(a/b) * b + a%b shall equal a

И другое место:

  Когда целые числа делятся и деление является неточным, если оба операнда положительны, результат оператора/является наибольшим целым числом, меньшим алгебраического отношения, а результат оператора% положителен. Если любой из операндов отрицателен, то, является ли результат оператора/наибольшим целым числом, меньшим, чем алгебраический фактор, или наименьшим целым числом, большим, чем алгебраический фактор, определяется реализацией, как и знак результата оператора%. Если частное a/b представимо, выражение (a/b) * b + a% b должно быть равно a.

Does either ANSI C or ISO C specify what -5 % 10 should be?

Так что да. Даже в C99 это, кажется, не влияет на вас. Уравнение то же самое.

Ответ 5

Как уже отмечали другие, специальная обработка для n == 0 бессмысленна, поскольку для каждого серьезного программиста на C очевидно, что "while (n)" делает свою работу.

Поведение для n & lt; 0 не так очевидно, поэтому я бы предпочел увидеть эти две строки кода:

if (n < 0) 
    n = -n;

или хотя бы комментарий:

// don't worry, works for n < 0 as well

Честно говоря, в какое время вы начали считать, что n может быть отрицательным? При написании кода или при чтении замечаний вашего учителя?

Ответ 6

Это напоминает мне о назначении, которое я провалил

Еще в 90-х. Лектор рассказывал о циклах, и, короче говоря, нашим заданием было написать функцию, которая возвращала бы число цифр для любого заданного целого числа> 0.

Так, например, количество цифр в 321 будет 3.

Хотя в задании просто сказано написать функцию, которая возвращает количество цифр, ожидалось, что мы будем использовать цикл, который делит на 10, пока... вы не получите его, как описано в лекции.

Но использование циклов не было явно заявлено, поэтому я: took the log, stripped away the decimals, added 1 и впоследствии подвергся критике перед всем классом.

Дело в том, что целью задания было проверить наше понимание того, что мы узнали во время лекций. Из лекции, которую я получил, я узнал, что учитель информатики был немного придурком (но, может быть, подонком с планом?)


В вашей ситуации:

написать функцию в C/C++, которая возвращает сумму цифр квадрата числа

Я определенно дал бы два ответа:

  • правильный ответ (сначала возводите квадрат в число) и
  • неправильный ответ в соответствии с примером, просто чтобы держать его счастливым ;-)

Ответ 7

Я бы не стал спорить о том, лучше ли оригинальное или современное определение "%", но любой, кто пишет два оператора return в такую короткую функцию, вообще не должен учить программированию на С. Дополнительный возврат - это оператор goto, и мы не используем goto в C. Кроме того, код без проверки нуля будет иметь тот же результат, дополнительный возврат затруднит чтение.

Ответ 8

Как правило, в заданиях не все оценки ставятся только потому, что код работает. Вы также получаете оценки за простоту чтения, эффективность и элегантность решения. Эти вещи не всегда взаимоисключающие.

Я не могу сказать, что "использовать значимые имена переменных".

В вашем примере это не имеет большого значения, но если вы работаете над проектом с миллионами строк, читаемость кода становится очень важной.

Еще одна вещь, которую я склонен видеть в C-коде, это люди, которые пытаются выглядеть умно. Вместо использования while (n! = 0) я покажу всем, насколько я умен, написав while (n), потому что это означает то же самое. Что ж, это так и есть в вашем компиляторе, но, как вы и предложили, учитель старой версии не реализовал его так же.

Типичным примером является обращение к индексу в массиве, в то же время увеличивая его; Числа [i++] = iPrime;

Теперь следующий программист, работающий над кодом, должен знать, увеличивается ли я до или после назначения, просто чтобы кто-то мог похвастаться.

Мегабайт дискового пространства дешевле, чем рулон туалетной бумаги, иди для ясности, а не пытаясь сэкономить место, твои коллеги-программисты будут счастливее.