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

给定一个数字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或更新版本。所以我猜(通过阅读评论)我的版本无论如何都能得到正确答案。


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

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

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


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

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++发生了重大的语言重新定义。


您的代码完全没问题

你完全正确,你的老师错了。完全没有理由增加额外的复杂性,因为它根本不会影响结果。它甚至引入了一个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.

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


注意:当我在写这个答案时,你确实澄清了你使用的是C。我的答案大部分是关于c++的。然而,由于你的标题仍然是c++,问题的标签仍然是c++,我还是选择了回答,以防这对其他人仍然有用,特别是因为到目前为止我看到的大多数答案都是不令人满意的。

在现代c++中(注:我真的不知道C在这方面的立场),你的教授似乎在这两个方面都是错误的。

首先是这部分:

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

在c++中,这基本上等同于:

if (!n) {
        return 0;
}

这意味着你的while相当于这样的东西:

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

这意味着,既然你只是在while不会执行的情况下退出if语句,就没有理由把这个if语句放在这里,因为你在循环之后所做的事情和在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 

唯一的陷阱是最后一句:

如果两个操作数都是非负的,那么余数也是非负的;如果不是,其余部分的符号是实现定义的。

这意味着在这种情况下,似乎只有符号是实现定义的。在你的例子中,这应该不是问题,因为,因为你对这个值平方。

也就是说,请记住,这并不一定适用于早期版本的c++或C99。如果你的教授用的就是这个,那可能就是原因所在。


编辑:不,我错了。这似乎是C99或更高版本的情况:

C99要求当a/b是可表示的时: (a/b) * b + a%b等于a

另一个地方:

When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. Does either ANSI C or ISO C specify what -5 % 10 should be?

所以,是的。即使在C99中,这似乎也不会影响到你。方程是一样的。


这让我想起我失败的一次作业

早在90年代。讲师一直在讲循环,长话短说,我们的作业是写一个函数,返回任意给定整数> 0的位数。

例如,321的位数是3。

虽然作业只是简单地说要写一个返回数字数的函数,但我们期望使用一个循环,将10除到……你们都明白,这是我讲过的。

但是使用循环并没有明确规定,所以I:取log,去掉小数,加1,然后在全班面前被痛骂。

重点是,作业的目的是测试我们对课堂上所学内容的理解。从我所接受的讲座中,我了解到计算机老师有点混蛋(但也许是一个有计划的混蛋?)


在你的情况下:

用C/ c++编写一个函数,返回数字的平方和

我肯定会给出两个答案:

正确答案(先平方数字),和 不正确的答案与例子保持一致,只是为了让他高兴;-)


我不会争论'%'的原始定义还是现代定义更好,但任何在这么短的函数中编写两个return语句的人都不应该教C编程。Extra return是一个goto语句,我们在C中不用goto。 此外,没有零检查的代码也会有相同的结果,额外的返回使其更难阅读。


正如其他人指出的那样,对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问题的理解,否则老师可能会认为你不知情,只是运气好。在口试中,你会得到一个问题,你的答案就能解决它。