我最近在班上进行了一次测试。其中一个问题如下:

给定一个数字n,用C/ c++编写一个函数,返回该数字的数字和的平方。(以下是重要的)。n的取值范围是[-(10^7),10^7]。示例:如果n = 123,函数应该返回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不会失败进入循环。这还是一样的。

Then, I tried both versions of the function on my computer at home and I got exactly the same answers for all the examples that I tried. So, sum_of_digits_squared(-123) is equal to sum_of_digits_squared(123) (which again, is equal to 14) (even without the detail that I apparently should've added). Indeed, if I try to print on the screen the digits of the number (from least to greatest in importance), in the 123 case I get 3 2 1 and in the -123 case I get -3 -2 -1 (which is actually kind of interesting). But in this problem it wouldn't matter since we square the digits.

那么,谁错了呢?

编辑:我的错,我忘了说明,也不知道这很重要。我们的类和测试中使用的C版本必须是C99或更新版本。所以我猜(通过阅读评论)我的版本无论如何都能得到正确答案。


当前回答

总结一下评论中流传的讨论:

There is no good reason to test in advance for n == 0. The while(n) test will handle that case perfectly. It's likely your teacher is still used to earlier times, when the result of % with negative operands was differently defined. On some old systems (including, notably, early Unix on a PDP-11, where Dennis Ritchie originally developed C), the result of a % b was always in the range [0 .. b-1], meaning that -123 % 10 was 7. On such a system, the test in advance for n < 0 would be necessary.

但第二颗子弹只适用于更早的时代。在C和c++标准的当前版本中,整数除法被定义为向0截断,因此即使n为负数,n % 10也保证会给出n的最后一位(可能是负数)。

因此,对于“while(n)的含义是什么?”这个问题的答案是“与while(n != 0)完全相同”,而对于“这段代码对于负n和正n是否都能正常工作?”的答案是“在任何现代的、符合标准的编译器下都能正常工作”。“那为什么老师要把它记下来?”这个问题的答案很可能是他们没有意识到1999年C语言和2010年左右c++发生了重大的语言重新定义。

其他回答

你和你老师的说法我都不太喜欢。你的老师的版本会做额外的测试,而你正确地指出这些测试是不必要的。C的模运算符不是一个正确的数学模:一个负数模10将产生一个负的结果(正确的数学模总是非负的)。但既然你把它平方了,没什么区别。

但这还远远不够明显,所以我不会在代码中添加老师的检查,而是添加一个大注释,解释为什么它可以工作。例如:

注意:这适用于负值,因为模量得到平方*/

您的代码完全没问题

你完全正确,你的老师错了。完全没有理由增加额外的复杂性,因为它根本不会影响结果。它甚至引入了一个bug。(见下文)

首先,单独检查n是否为零显然是完全不必要的,这很容易实现。老实说,如果你的老师对此有异议,我真的怀疑他的能力。但我想每个人都会时不时地脑子里放个屁。然而,我确实认为while(n)应该改为while(n != 0),因为它增加了一点额外的清晰度,甚至不需要花费额外的行。不过这是一件小事。

第二点比较容易理解,但他还是错了。

这就是C11标准6.5.5。p6说:

如果商a/b可表示,则表达式(a/b)*b + a%b等于a;否则,a/b和a%b的行为都没有定义。

脚注是这样说的:

这通常被称为“趋近于零的截断”。

向零截断意味着a/b的绝对值等于所有a和b的(-a)/b的绝对值,这反过来意味着您的代码完全没问题。

模是简单的数学,但可能违反直觉

However, your teacher does have a point that you should be careful, because the fact that you're squaring the result is actually crucial here. Calculating a%b according to above definition is easy math, but it might go against your intuition. For multiplication and division, the result is positive if the operands have equal sign. But when it comes to modulo, the result has the same sign as the first operand. The second operand does not affect the sign at all. For instance, 7%3==1 but (-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

讽刺的是,你的老师用错误来证明他的观点。

你老师的代码有缺陷

Yes, it actually is. If the input is INT_MIN AND the architecture is two's complement AND the bit pattern where the sign bit is 1 and all value bits are 0 is NOT a trap value (using two's complement without trap values is very common) then your teacher's code will yield undefined behavior on the line n = n * (-1). Your code is - if ever so slightly - better than his. And considering introducing a small bug by making the code unnecessary complex and gaining absolutely zero value, I'd say that your code is MUCH better.

In other words, in compilations where INT_MIN = -32768 (even though the resulting function cannot receive an input that is < -32768 or > 32767), the valid input of -32768 causes undefined behavior, because the result of -(-32768i16) cannot be expressed as a 16-bit integer. (Actually, -32768 probably would not cause an incorrect result, because -(-32768i16) usually evaluates to -32768i16, and your program handles negative numbers correctly.) (SHRT_MIN could be -32768 or -32767, depending on the compiler.)

But your teacher explicitly stated that n can be in the range [-10^7; 10^7]. A 16-bit integer is too small; you would have to use [at least] a 32-bit integer. Using int might seem to make his code safe, except that int is not necessarily a 32-bit integer. If you compile for a 16-bit architecture, both of your code snippets are flawed. But your code is still much better because this scenario reintroduces the bug with INT_MIN mentioned above with his version. To avoid this, you can write long instead of int, which is a 32-bit integer on either architecture. A long is guaranteed to be able to hold any value in the range [-2147483647; 2147483647]. C11 Standard 5.2.4.2.1 LONG_MIN is often -2147483648 but the maximum (yes, maximum, it's a negative number) allowed value for LONG_MIN is -2147483647.

我要对您的代码做哪些更改?

您的代码已经很好了,所以这些并不是真正的抱怨。它更像是,如果我真的,真的需要对你的代码说些什么,有一些小事情可以让它更清晰一点。

变量的名字可以稍微好一点,但这是一个很短的函数,很容易理解,所以这不是什么大问题。 您可以将条件从n更改为n!=0。语义上,它是100%等效的,但它让它更清楚一点。 将c的声明(我将其重命名为digit)移动到while循环内部,因为它只在那里使用。 将参数类型更改为long,以确保它可以处理整个输入集。

int sum_of_digits_squared(long n) 
{
    long sum = 0;

    while (n != 0) {
        int digit = n % 10;
        sum += (digit * digit);
        n /= 10;
    }

    return sum;
}

实际上,这可能会有一点误导,因为-如上所述-可变数字可以得到负值,但数字本身永远不会是正数或负数。有一些方法可以解决这个问题,但这真的是吹毛求疵,我不关心这些小细节。特别是最后一位的单独函数太过分了。具有讽刺意味的是,这是你的教师代码实际上解决的问题之一。

Change sum += (digit * digit) to sum += ((n%10)*(n%10)) and skip the variable digit completely. Change the sign of digit if negative. But I would strongly advice against making the code more complex just to make a variable name make sense. That's a VERY strong code smell. Create a separate function that extracts the last digit. int last_digit(long n) { int digit=n%10; if (digit>=0) return digit; else return -digit; } This is useful if you want to use that function somewhere else. Just name it c as you originally do. That variable name does not give any useful information, but on the other hand, it's not misleading either.

但说实话,在这一点上你应该转向更重要的工作。:)

正如其他人指出的那样,对n==0的特殊处理是毫无意义的,因为对于每个认真的C程序员来说,显然“while(n)”可以完成这项工作。

n<0的行为不是那么明显,这就是为什么我更喜欢看到这两行代码:

if (n < 0) 
    n = -n;

或者至少是一个评论:

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

说实话,你什么时候开始考虑n可能是负的?写代码的时候,还是读老师的评语的时候?

一般在作业中,不是所有的分数都是因为代码可以运行。你也会因为你的解决方案易于阅读、高效和优雅而得分。这些事情并不总是相互排斥的。

我强调的一点是“使用有意义的变量名”。

在你的例子中,这没有太大的区别,但是如果你正在处理一个有一百万行代码的项目,可读性就变得非常重要了。

我在C代码中看到的另一件事是人们试图看起来聪明。 我不使用while(n != 0),而是用while(n)来告诉大家我有多聪明,因为它的意思是一样的。 在你的编译器中是这样的,但正如你所建议的,老师的旧版本并没有以同样的方式实现它。

一个常见的例子是引用数组中的一个索引,同时增加它;数字[i++] = iPrime;

现在,下一个处理代码的程序员必须知道i是在赋值之前还是之后递增的,这样就有人可以炫耀了。

1兆字节的磁盘空间比一卷卫生纸便宜,追求清晰而不是试图节省空间,你的程序员同事会更开心。

问题陈述令人困惑,但数值示例澄清了数字平方的数字和的含义。以下是改进版:

在C和c++的公共子集中编写一个函数,该函数接受范围为[-107,107]的整数n,并返回以10为底的该表示的数字的平方和。例如:如果n是123,你的函数应该返回14(12 + 22 + 32 = 14)。

你写的函数很好,除了2个细节:

The argument should have type long to accommodate for all values in the specified range as type long is guaranteed by the C Standard to have at least 31 value bits, hence a range sufficient to represent all values in [-107, 107]. (Note that type int is sufficient for the return type, whose maximum value is 568.) The behavior of % for negative operands is non-intuitive and its specification varied between the C99 Standard and previous editions. You should document why your approach is valid even for negative inputs.

以下是修改后的版本:

int sum_of_digits_squared(long n) {
    int s = 0;

    while (n != 0) {
        /* Since integer division is defined to truncate toward 0
           in C99 and C++98 and later, the remainder of this division
           is positive for positive `n` and negative for negative
           `n`, and its absolute value is the last digit of the
           representation of `n` in base 10.
           Squaring this value yields the expected result for both
           positive and negative `c`. Dividing `n` by 10 effectively
           drops the last digit in both cases.
           The loop will not be entered for `n == 0`, producing the
           correct result `s = 0`.
         */
        int c = n % 10;
        s += c * c;
        n /= 10;
    }
    return s;
}

老师的回答有多个缺陷:

int类型的值范围可能不够。 不需要对值0进行特殊处理。 对负数求反是不必要的,对于n = INT_MIN可能有未定义的行为。

考虑到问题语句中的额外约束(C99和n的值范围),只有第一个缺陷是问题。额外的代码仍然产生正确的答案。

这次考试你应该能拿到好成绩,但是笔试时需要解释,以表明你对- n问题的理解,否则老师可能会认为你不知情,只是运气好。在口试中,你会得到一个问题,你的答案就能解决它。