Preciso lidar explicitamente com números negativos ou zero ao somar dígitos ao quadrado?




(6)

Recentemente, fiz um teste na minha turma. Um dos problemas foi o seguinte:

Dado um número n , escreva uma função em C / C ++ que retorne a soma dos dígitos do número ao quadrado . (O seguinte é importante). O intervalo de n é [- (10 ^ 7), 10 ^ 7]. Exemplo: Se n = 123, sua função retornará 14 (1 ^ 2 + 2 ^ 2 + 3 ^ 2 = 14).

Esta é a função que eu escrevi:

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

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

    return s;
}

Parecia certo para mim. Então agora o teste voltou e eu descobri que o professor não me deu todos os pontos por um motivo que eu não entendi. Segundo ele, para que minha função seja concluída, eu deveria ter adicionado os seguintes detalhes:

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

O argumento para isso é que o número n está no intervalo [- (10 ^ 7), 10 ^ 7], portanto pode ser um número negativo. Mas não vejo onde minha própria versão da função falha. Se eu entendi corretamente, o significado de while(n) é while(n != 0) , não while (n > 0) ; portanto, na minha versão da função, o número n não deixaria de entrar no loop. Funcionaria da mesma forma.

Então, tentei as duas versões da função no meu computador em casa e recebi exatamente as mesmas respostas para todos os exemplos que tentei. Portanto, sum_of_digits_squared(-123) é igual a sum_of_digits_squared(123) (que novamente é igual a 14 ) (mesmo sem os detalhes que eu aparentemente deveria ter adicionado). De fato, se eu tentar imprimir na tela os dígitos do número (do menor ao maior em importância), no caso 123 , recebo 3 2 1 e no caso -123 , -123 -3 -2 -1 (que é realmente interessante). Mas, neste problema, não importaria, uma vez que arredondamos os dígitos.

Então quem está errado?

Edição : Meu mal, eu esqueci de especificar e não sabia que era importante. A versão do C usada em nossa classe e nos testes deve ser C99 ou mais recente . Então eu acho (lendo os comentários) que minha versão obteria a resposta correta de qualquer maneira.


Isso me lembra uma tarefa que eu falhei

Nos anos 90. O palestrante estava brotando sobre loops e, resumindo, nossa tarefa era escrever uma função que retornasse o número de dígitos para qualquer número inteiro> 0.

Assim, por exemplo, o número de dígitos em 321 seria 3 .

Embora a tarefa simplesmente dissesse escrever uma função que retornasse o número de dígitos, a expectativa era que usássemos um loop que divide por 10 até ... você a entende, conforme abordado na palestra .

Mas o uso de loops não foi explicitamente declarado, então eu: took the log, stripped away the decimals, added 1 e foi subseqüentemente criticado na frente de toda a classe.

A questão é que o objetivo da tarefa era testar nossa compreensão do que aprendemos durante as palestras . Na palestra que recebi, aprendi que o professor de informática era um idiota (mas talvez um idiota com um plano?)

Na sua situação:

escreve uma função em C / C ++ que retorna a soma dos dígitos do número ao quadrado

Definitivamente, eu teria fornecido duas respostas:

  • a resposta correta (ao quadrado do número primeiro) e
  • a resposta incorreta de acordo com o exemplo, apenas para mantê-lo feliz ;-)

Seu código está perfeitamente bem

Você está absolutamente correto e seu professor está errado. Não há absolutamente nenhuma razão para adicionar essa complexidade extra, pois não afeta o resultado. Ele ainda apresenta um bug. (Ver abaixo)

Primeiro, a verificação separada se n é zero é obviamente completamente desnecessária e isso é muito fácil de realizar. Para ser sincero, na verdade questiono a competência de seus professores se ele tiver objeções a isso. Mas acho que todo mundo pode ter um peido cerebral de vez em quando. No entanto, acho que while(n) deve ser alterado para while(n != 0) porque adiciona um pouco de clareza extra, sem nem mesmo custar uma linha extra. É uma coisa menor, no entanto.

O segundo é um pouco mais compreensível, mas ele ainda está errado.

Isto é o que o padrão C11 6.5.5.p6 diz:

Se o quociente a / b for representável, a expressão (a / b) * b + a% b será igual a; caso contrário, o comportamento de a / be% b é indefinido.

A nota de rodapé diz o seguinte:

Isso geralmente é chamado de "truncamento em direção a zero".

Truncamento em direção a zero significa que o valor absoluto para a/b é igual ao valor absoluto para (-a)/b para todos os a e b , o que, por sua vez, significa que seu código está perfeitamente correto. No entanto, seu professor tem um ponto em que você deve tomar cuidado, porque o fato de você estar obtendo o resultado é realmente crucial aqui. Calcular a%b acordo com a definição acima é fácil, mas pode ser contra a sua intuição. Por exemplo, 7%3==1 mas (-7)%(-3)==(-1) . Aqui está um trecho de demonstração:

$ 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

Então, ironicamente, seu professor provou o que estava errado.

O código do seu professor está com defeito

Sim, é mesmo. Se a entrada é INT_MIN e a arquitetura está usando o complemento de dois E se o padrão de bits em que o bit de sinal é 1 e todos os bits de valor são 0 NÃO é um valor de trap (o uso do complemento de dois sem valores de trap é muito comum), o código do professor será gera comportamento indefinido na linha n = n * (-1) . Seu código é - ainda que um pouco - melhor que o dele. E, considerando a introdução de um pequeno bug, tornando o código desnecessário complexo e ganhando absolutamente zero valor, eu diria que seu código é MUITO melhor.

Mas, novamente, seu professor diz explicitamente que n deve estar no intervalo [- (10 ^ 7), 10 ^ 7]. Portanto, isso poderia tê-lo salvo, se não fosse o caso que int não é necessariamente um número inteiro de 32 bits. Se você compilá-lo para uma arquitetura de 16 bits, ambos os trechos de código são defeituosos. Mas seu código ainda é muito melhor porque esse cenário reintroduz o bug com INT_MIN mencionado acima. Para evitar isso, você pode usar por long . Então você estará seguro. Um long é garantido para poder manter todos os valores no intervalo [-2147483647; 2147483647]. Norma C11 5.2.4.2.1

Que alterações eu faria no seu código?

Seu código está correto, portanto não são realmente reclamações. É mais assim que, se eu realmente precisar dizer algo sobre o seu código, existem algumas pequenas coisas que podem torná-lo um pouco mais claro.

  • Os nomes das variáveis ​​podem ser um pouco melhores, mas é uma função curta e fácil de entender, por isso não é grande coisa.
  • Você pode alterar a condição de n para n!=0 . Semanticamente, é 100% equivalente, mas torna um pouco mais claro.
  • Mova a declaração de c (que renomei para digit ) para dentro do loop while, uma vez que é usada apenas lá.
  • Altere o tipo de argumento para long para garantir que ele possa lidar com todo o conjunto de entradas.
int sum_of_digits_squared(long n) 
{
    long sum = 0;

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

    return sum;
}

Na verdade, isso pode ser um pouco enganador porque - como mencionado acima - o digit variável pode obter um valor negativo, mas um dígito nunca é, por si só, positivo ou negativo. Existem algumas maneiras de contornar isso, mas isso é MUITO interessante, e eu não me importaria com detalhes tão pequenos. Especialmente a função separada para o último dígito está levando muito longe. Ironicamente, essa é uma das coisas que o código de seus professores realmente resolve.

  • Altere sum += (digit * digit) para sum += ((n%10)*(n%10)) e pule o digit variável completamente.
  • Mude o sinal do digit se negativo.
  • Crie uma função separada que extraia o último dígito. int last_digit(long n) { int digit=n%10; if (digit>=0) return digit; else return -digit; }
  • Apenas nomeie-o como você faz originalmente. Esse nome de variável não fornece informações úteis, mas, por outro lado, também não é enganoso.

Mas, para ser sincero, nesse ponto você deve seguir para um trabalho mais importante. :)


Eu não discutiria se a definição original ou moderna de '%' é melhor, mas quem escreve duas declarações de retorno em uma função tão curta não deve ensinar programação C. Retorno extra é uma instrução goto e não usamos goto em C. Além disso, o código sem a verificação zero teria o mesmo resultado, o retorno extra dificultou a leitura.


Geralmente nas tarefas, nem todas as marcas são atribuídas apenas porque o código funciona. Você também recebe marcas para facilitar a leitura, a eficiência e a elegância da solução. Essas coisas nem sempre são mutuamente exclusivas.

Uma coisa que eu não posso dizer o suficiente é "usar nomes de variáveis ​​significativos" .

No seu exemplo, não faz muita diferença, mas se você estiver trabalhando em um projeto com milhões de linhas de legibilidade de código, isso se tornará muito importante.

Outra coisa que costumo ver com o código C são as pessoas que tentam parecer inteligentes. Em vez de usar while (n! = 0) , mostrarei a todos como sou inteligente escrevendo while (n) porque significa a mesma coisa. Bem, isso acontece no compilador, mas, como você sugeriu, a versão mais antiga do professor não a implementou da mesma maneira.

Um exemplo comum é referenciar um índice em uma matriz e incrementá-lo ao mesmo tempo; Números [i ++] = iPrime;

Agora, o próximo programador que trabalha com o código precisa saber se eu sou incrementado antes ou depois da tarefa, apenas para que alguém possa se exibir.

Um megabyte de espaço em disco é mais barato que um rolo de papel higiênico, procure mais clareza do que tentar economizar espaço; seus colegas programadores ficarão mais felizes.


Resumindo uma discussão que tem percolado nos comentários:

  • Não há uma boa razão para testar antecipadamente n == 0 . O teste while(n) lidará com esse caso perfeitamente.
  • É provável que seu professor ainda esteja acostumado a épocas anteriores, quando o resultado de % com operandos negativos foi definido de maneira diferente. Em alguns sistemas antigos (incluindo, principalmente, o Unix inicial em um PDP-11, onde Dennis Ritchie originalmente desenvolveu C), o resultado de a % b estava sempre no intervalo [0 .. b-1] , o que significa que -123% 10 era 7. Nesse sistema, o teste prévio para n < 0 seria necessário.

Mas o segundo marcador se aplica apenas a épocas anteriores. Nas versões atuais dos padrões C e C ++, a divisão inteira é definida para truncar em direção a 0; portanto, n % 10 é garantido para fornecer o último dígito (possivelmente negativo) de n mesmo quando n for negativo.

Portanto, a resposta para a pergunta "Qual é o significado de while(n) ?" é "Exatamente o mesmo que while(n != 0) " e a resposta para "Esse código funcionará corretamente para n negativo e positivo n ?" é "Sim, em qualquer compilador moderno, em conformidade com os padrões". A resposta para a pergunta "Então por que o instrutor anotou?" Provavelmente, eles não estão cientes de uma redefinição significativa de linguagem que aconteceu com o C em 1999 e com o C ++ em 2010, aproximadamente.


NOTA: Enquanto escrevia esta resposta, você esclareceu que está usando C. A maioria da minha resposta é sobre C ++. No entanto, como seu título ainda possui C ++ e a pergunta ainda está marcada como C ++, decidi responder de qualquer maneira, caso isso ainda seja útil para outras pessoas, principalmente porque a maioria das respostas que eu vi até agora não é satisfatória.

No C ++ moderno (Nota: eu realmente não sei onde C está), seu professor parece estar errado em ambos os aspectos.

Primeiro é esta parte aqui:

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

Em C ++, isso é basicamente a mesma coisa que :

if (!n) {
        return 0;
}

Isso significa que seu tempo é equivalente a algo assim:

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

Isso significa que, como você está apenas saindo do seu if quando o tempo não seria executado de qualquer maneira, realmente não há uma razão para colocar isso se aqui, pois o que você está fazendo após o loop e no if é equivalente de qualquer maneira. Embora eu deva dizer que, por alguma razão, essas eram diferentes, você precisaria disso se.

Realmente, essa declaração if não é particularmente útil, a menos que eu esteja enganado.

A segunda parte é onde as coisas ficam peludas:

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

O cerne da questão é qual é a saída do módulo de um número negativo.

No C ++ moderno, isso parece estar bem definido :

O operador binário / produz o quociente e o operador% binário produz o restante da divisão da primeira expressão pela segunda. Se o segundo operando de / ou% for zero, o comportamento será indefinido. Para operandos integrais, o operador / produz o quociente algébrico com qualquer parte fracionária descartada; se o quociente a / b é representável no tipo de resultado, (a / b) * b + a% b é igual a a.

E depois:

Se ambos os operandos não são negativos, o restante é não-negativo; caso contrário, o sinal do restante é definido pela implementação.

Como o pôster da resposta citada corretamente indica, a parte importante desta equação aqui:

(a / b) * b + a% b

Tomando um exemplo do seu caso, você obteria algo como isto:

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

O único problema é a última linha:

Se ambos os operandos não são negativos, o restante é não-negativo; caso contrário, o sinal do restante é definido pela implementação.

Isso significa que, em um caso como esse, apenas o sinal parece estar definido para implementação. Isso não deve ser um problema no seu caso porque, porque você está elevando esse valor de qualquer maneira.

Dito isto, lembre-se de que isso não se aplica necessariamente a versões anteriores do C ++ ou C99. Se é isso que seu professor está usando, talvez seja por isso.

EDIT: Não, eu estou errado. Esse também parece ser o caso do C99 ou posterior :

C99 exige que quando a / b é representável:

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

E outro lugar :

Quando os números inteiros são divididos e a divisão é inexata, se os dois operandos forem positivos, o resultado do operador / é o maior número inteiro menor que o quociente algébrico e o resultado do operador% é positivo. Se um dos operandos for negativo, se o resultado do operador / é o maior número inteiro menor que o quociente algébrico ou o menor número inteiro maior que o quociente algébrico é definido pela implementação, como é o sinal do resultado do operador%. Se o quociente a / b for representável, a expressão (a / b) * b + a% b será igual a.

O ANSI C ou o ISO C especificam o que -5% 10 deve ser?

Então sim. Mesmo em C99, isso não parece afetá-lo. A equação é a mesma.




c  

c