¿Necesito manejar explícitamente números negativos o cero al sumar dígitos cuadrados?

Question

Recientemente tuve una prueba en mi clase. Uno de los problemas fue el siguiente:

Dado un número n , escriba una función en C / C ++ que devuelva la suma de los dígitos del número al cuadrado . (Lo siguiente es importante). El rango de n es [- (10 ^ 7), 10 ^ 7]. Ejemplo: si n = 123, su función debería devolver 14 (1 ^ 2 + 2 ^ 2 + 3 ^ 2 = 14).

Esta es la función que escribí:

int sum_of_digits_squared(int n)
{
int s = 0, c;
while (n) {
c = n % 10;
s += (c * c);
n /= 10;
}
return s;
}

Me pareció bien. Así que ahora regresó la prueba y descubrí que el maestro no me dio todos los puntos por una razón que no entiendo. Según él, para que mi función esté completa, debería haber agregado el siguiente detalle:

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;
}

El argumento para esto es que el número n está en el rango [- (10 ^ 7), 10 ^ 7], por lo que puede ser un número negativo. Pero no veo dónde falla mi propia versión de la función. Si entiendo correctamente, el significado de while(n) es while(n != 0) , no while (n > 0) , por lo que en mi versión de la función el número n no dejaría de entrar en el bucle. Funcionaría igual.

Luego, probé ambas versiones de la función en mi computadora en casa y obtuve exactamente las mismas respuestas para todos los ejemplos que probé. Entonces, sum_of_digits_squared(-123) es igual a sum_of_digits_squared(123) (que de nuevo, es igual a 14 ) (incluso sin el detalle que aparentemente debería haber agregado). De hecho, si trato de imprimir en la pantalla los dígitos del número (de menor a mayor importancia), en el caso 123 obtengo 3 2 1 y en el caso -123 obtengo -3 -2 -1 (que es en realidad un poco interesante). Pero en este problema no importaría ya que cuadramos los dígitos.

Entonces, ¿quién está equivocado?

EDITAR : Mi mal, olvidé especificar y no sabía que era importante. La versión de C utilizada en nuestra clase y pruebas tiene que ser C99 o más reciente . Así que supongo (al leer los comentarios) que mi versión obtendría la respuesta correcta de cualquier manera.

Answer 1

Esto me recuerda una tarea que fallé

Allá por los años 90. El profesor había estado surgiendo sobre bucles y, para resumir, nuestra tarea consistía en escribir una función que devolviera el número de dígitos para cualquier número entero> 0.

Entonces, por ejemplo, el número de dígitos en 321 sería 3 .

Aunque la tarea simplemente decía que escribiera una función que devolviera el número de dígitos, la expectativa era que usaríamos un bucle que se dividiera por 10 hasta que ... lo obtenga, como lo cubre la conferencia .

Pero el uso de bucles no se indicó explícitamente, así que: took the log, stripped away the decimals, added 1 y posteriormente fui criticado frente a toda la clase.

El punto es que el propósito de la tarea era evaluar nuestra comprensión de lo que habíamos aprendido durante las conferencias . De la conferencia que recibí, supe que el profesor de informática era un poco idiota (¿pero quizás un idiota con un plan?)

En su situación:

escribe una función en C / C ++ que devuelva la suma de los dígitos del número al cuadrado

Definitivamente habría proporcionado dos respuestas:

• la respuesta correcta (cuadrando el número primero), y
• la respuesta incorrecta de acuerdo con el ejemplo, solo para mantenerlo feliz ;-)

Answer 2

Tu código está perfectamente bien

Tienes toda la razón y tu maestro está equivocado. No hay absolutamente ninguna razón para agregar esa complejidad adicional, ya que no afecta el resultado en absoluto. Incluso introduce un error. (Vea abajo)

Primero, la verificación por separado si n es cero es obviamente completamente innecesaria y esto es muy fácil de realizar. Para ser honesto, en realidad cuestiono la competencia de tus maestros si tiene objeciones al respecto. Pero supongo que todos pueden tener un pedo cerebral de vez en cuando. Sin embargo, SÍ creo que while(n) debería cambiarse a while(n != 0) porque agrega un poco más de claridad sin siquiera costar una línea adicional. Sin embargo, es algo menor.

El segundo es un poco más comprensible, pero todavía está equivocado.

Esto es lo que dice el estándar C11 6.5.5.p6 :

Si el cociente a / b es representable, la expresión (a / b) * b + a% b será igual a; de lo contrario, el comportamiento de a / by a% b no está definido.

La nota al pie dice esto:

Esto a menudo se llama "truncamiento hacia cero".

El truncamiento hacia cero significa que el valor absoluto para a/b es igual al valor absoluto para (-a)/b para todos b , lo que a su vez significa que su código está perfectamente bien. Sin embargo, tu maestro tiene un punto que debes tener cuidado, porque el hecho de que estés cuadrando el resultado es realmente crucial aquí. Calcular a%b según la definición anterior es matemática fácil, pero puede ir en contra de su intuición. Por ejemplo, 7%3==1 pero (-7)%(-3)==(-1) . Aquí hay un fragmento que lo demuestra:

$ 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

Entonces, irónicamente, tu maestro demostró su punto al estar equivocado.

El código de tu maestro es defectuoso

Sí, en realidad lo es. Si la entrada es INT_MIN y la arquitectura está utilizando el complemento de dos Y si el patrón de bits donde el bit de signo es 1 y todos los bits de valor son 0 NO es un valor de trampa (es muy común usar el complemento de dos sin valores de trampa) produce un comportamiento indefinido en la línea n = n * (-1) . Su código es, aunque sea ligeramente, mejor que el suyo. Y considerando la posibilidad de introducir un pequeño error al hacer que el código sea innecesario complejo y obtener un valor absolutamente cero, diría que su código es MUCHO mejor.

Pero, de nuevo, su maestro dice explícitamente que n debe estar en el rango [- (10 ^ 7), 10 ^ 7]. Entonces eso podría haberlo salvado, si no fuera por el caso de que int no es necesariamente un número entero de 32 bits. Si lo compila para una arquitectura de 16 bits, ambos fragmentos de código tienen fallas. Pero su código sigue siendo mucho mejor porque este escenario volvería a introducir el error con INT_MIN mencionado anteriormente. Para evitar esto, puede usar long lugar. Entonces estarás a salvo. Un long está garantizado para poder mantener todos los valores en el rango [-2147483647; 2147483647]. C11 Norma 5.2.4.2.1

¿Qué cambios haría en su código?

Su código está bien tal como está, por lo que estas no son realmente quejas. Es más así si realmente necesito decir algo sobre su código, hay algunas pequeñas cosas que podrían aclararlo un poco más.

• Los nombres de las variables podrían ser un poco mejores, pero es una función corta que es fácil de entender, por lo que no es gran cosa.
• Puede cambiar la condición de n a n!=0 . Semánticamente, es 100% equivalente, pero lo hace un poco más claro.
• Mueve la declaración de c (que cambié de nombre a digit ) dentro del ciclo while ya que solo se usa allí.
• Cambie el tipo de argumento a long para garantizar que pueda manejar todo el conjunto de entrada.

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

En realidad, esto puede ser un poco engañoso porque, como se mencionó anteriormente, el digit variable puede obtener un valor negativo, pero un dígito en sí mismo nunca es positivo o negativo. Hay algunas maneras de evitar esto, pero esto es REALMENTE quisquilloso, y no me importarían esos pequeños detalles. Especialmente la función separada para el último dígito lo lleva demasiado lejos. Irónicamente, esta es una de las cosas que el código de tu maestro realmente resuelve.

• Cambie sum += (digit * digit) a sum += ((n%10)*(n%10)) y omita el digit variable por completo.
• Cambia el signo del digit si es negativo.
• Cree una función separada que extraiga el último dígito. int last_digit(long n) { int digit=n%10; if (digit>=0) return digit; else return -digit; }
• Solo nómbrelo c como lo hace originalmente. Ese nombre de variable no proporciona información útil, pero por otro lado, tampoco es engañoso.

Pero para ser honesto, en este punto debes pasar a un trabajo más importante. :)

Answer 3

Como otros han señalado, el tratamiento especial para n == 0 no tiene sentido, ya que para cada programador de C serio es obvio que "while (n)" hace el trabajo.

El comportamiento para n <0 no es tan obvio, por eso preferiría ver esas 2 líneas de código:

if (n < 0)
n = -n;

o al menos un comentario:

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

Honestamente, ¿a qué hora comenzaste a considerar que n podría ser negativo? ¿Al escribir el código o al leer los comentarios de tu maestro?

Answer 4

En general, en las asignaciones no todas las marcas se dan solo porque el código funciona. También obtiene calificaciones por hacer que una solución sea fácil de leer, eficiente y elegante. Estas cosas no siempre son mutuamente excluyentes.

Uno que no puedo entender lo suficiente es "usar nombres de variables significativos" .

En su ejemplo, no hace mucha diferencia, pero si está trabajando en un proyecto con un millón de líneas de legibilidad de código se vuelve muy importante.

Otra cosa que tiendo a ver con el código C es que las personas intentan parecer inteligentes. En lugar de usar while (n! = 0), les mostraré a todos lo inteligente que soy al escribir while (n) porque significa lo mismo. Bueno, lo hace en el compilador que tiene, pero como sugirió, la versión anterior del profesor no lo ha implementado de la misma manera.

Un ejemplo común es hacer referencia a un índice en una matriz mientras lo incrementa al mismo tiempo; Números [i ++] = iPrime;

Ahora, el próximo programador que trabaja en el código tiene que saber si me incrementan antes o después de la tarea, solo para que alguien pueda presumir.

Un megabyte de espacio en disco es más barato que un rollo de papel higiénico. Si busca claridad en lugar de tratar de ahorrar espacio, sus compañeros programadores estarán más felices.

Answer 5

No discutiría si la definición original o moderna de ''%'' es mejor, pero cualquiera que escriba dos declaraciones de retorno en una función tan corta no debería enseñar la programación en C. El retorno adicional es una declaración de goto y no usamos goto en C. Además, el código sin la verificación de cero tendría el mismo resultado, el retorno adicional hizo que sea más difícil de leer.

Answer 6

No me gusta por completo ni tu versión ni la de tu profesor. La versión de tu profesor hace innecesarios los exámenes adicionales que señalas correctamente. El operador mod de C no es un mod matemático adecuado: un número negativo mod 10 producirá un resultado negativo (el módulo matemático adecuado siempre es no negativo). Pero como lo estás cuadrando de todos modos, no hay diferencia.

Pero esto está lejos de ser obvio, por lo que agregaría a su código no los controles de su maestro, sino un gran comentario que explica por qué funciona. P.ej:

/ * NOTA: Esto funciona para valores negativos, porque el módulo se eleva al cuadrado * /

Answer 7

Resumiendo una discusión que se ha filtrado en los comentarios:

• No hay una buena razón para probar por adelantado para n == 0 . La prueba while(n) manejará ese caso perfectamente.
• Es probable que su maestro aún esté acostumbrado a épocas anteriores, cuando el resultado de % con operandos negativos se definió de manera diferente. En algunos sistemas antiguos (incluido, en particular, Unix temprano en un PDP-11, donde Dennis Ritchie desarrolló originalmente C), el resultado de a % b siempre estuvo en el rango [0 .. b-1] , lo que significa que -123% 10 era 7. En dicho sistema, la prueba por adelantado para n < 0 sería necesaria.

Pero la segunda viñeta se aplica solo a tiempos anteriores. En las versiones actuales de los estándares C y C ++, la división de enteros está definida para truncarse hacia 0, por lo que resulta que n % 10 está garantizado para darle el último dígito (posiblemente negativo) de n incluso cuando n es negativo.

Entonces, la respuesta a la pregunta "¿Cuál es el significado de while(n) ?" es "Exactamente igual que while(n != 0) " , y la respuesta a "¿Funcionará este código correctamente para n negativo y positivo n ?" es "Sí, en cualquier compilador moderno que cumpla con los estándares". La respuesta a la pregunta "¿Entonces por qué el instructor lo marcó?" es probable que no estén al tanto de una redefinición significativa del lenguaje que le sucedió a C en 1999 y a C ++ en 2010 más o menos.

Answer 8

NOTA: Mientras escribía esta respuesta, usted aclaró que está usando C. La mayoría de mi respuesta es sobre C ++. Sin embargo, dado que su título todavía tiene C ++ y la pregunta aún está etiquetada como C ++, he elegido responder de todos modos en caso de que esto sea útil para otras personas, especialmente porque la mayoría de las respuestas que he visto hasta ahora son en su mayoría insatisfactorias.

En C ++ moderno (Nota: Realmente no sé dónde se encuentra C en esto), su profesor parece estar equivocado en ambos aspectos.

Primero es esta parte aquí:

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

En C ++, esto es básicamente lo mismo que :

if (!n) {
return 0;
}

Eso significa que tu while es equivalente a algo como esto:

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

Eso significa que dado que simplemente está saliendo de su if cuando el while no se ejecuta de todos modos, realmente no hay una razón para poner esto si aquí, ya que lo que está haciendo después del ciclo y en el if son equivalentes de todos modos. Aunque debería decir que es por alguna razón, estos eran diferentes, necesitarías tener esto si.

Entonces, realmente, esta declaración if no es particularmente útil a menos que me equivoque.

La segunda parte es donde las cosas se ponen difíciles:

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

El corazón del problema es cuál es la salida del módulo de un número negativo.

En C ++ moderno, esto parece estar bien definido :

El operador / binario produce el cociente, y el operador% binario produce el resto de la división de la primera expresión por la segunda. Si el segundo operando de / o% es cero, el comportamiento es indefinido. Para operandos integrales, el operador / produce el cociente algebraico con cualquier parte fraccional descartada; si el cociente a / b es representable en el tipo del resultado, (a / b) * b + a% b es igual a a.

Y después:

Si ambos operandos no son negativos, el resto no es negativo; si no, el signo del resto está definido por la implementación.

Como el cartel de la respuesta citada señala correctamente, la parte importante de esta ecuación aquí:

(a / b) * b + a% b

Tomando un ejemplo de su caso, obtendría algo como esto:

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

El único inconveniente es esa última línea:

Si ambos operandos no son negativos, el resto no es negativo; si no, el signo del resto está definido por la implementación.

Eso significa que en un caso como este, solo el signo parece estar definido por la implementación. Eso no debería ser un problema en su caso porque, porque de todos modos está cuadrando este valor.

Dicho esto, tenga en cuenta que esto no necesariamente se aplica a versiones anteriores de C ++ o C99. Si eso es lo que está usando su profesor, ese podría ser el motivo.

EDITAR: No, estoy equivocado. Este parece ser el caso para C99 o posterior también :

C99 requiere que cuando a / b sea representable:

(a / b) * b + a% b será igual a

Y otro lugar :

Cuando los enteros se dividen y la división es inexacta, si ambos operandos son positivos, el resultado del operador / es el entero más grande menor que el cociente algebraico y el resultado del operador% es positivo. Si cualquiera de los operandos es negativo, si el resultado del operador / es el entero más grande menor que el cociente algebraico o el entero más pequeño mayor que el cociente algebraico está definido por la implementación, como lo es el signo del resultado del operador%. Si el cociente a / b es representable, la expresión (a / b) * b + a% b será igual a a.

¿ANSI C o ISO C especifican qué -5% 10 debería ser?

Así que sí. Incluso en C99, esto no parece afectarlo. La ecuación es la misma.