3

Vi hoje no URI (site de problemas de programação) uma questão na qual o seu programa deveria ler dois valores e dizer quantos carrys (ou "vai um"s) acontecem na soma deles. Ex: 555 + 555 = 3 carrys e 1 + 9999999 = 7 carrys.

Eu fiz um programa pra calcular manualmente, igual um ser humano, primeiro eu igualei a quantidade de casas decimais usando um for e depois eu fiz a soma manual. Ex: 12 999999 = 000012 999999 e depois era efetuada a soma. Porém um pessoal falou que existia uma maneira de responder isso muito mais eficiente e eu gostaria de saber como é, procurei no google mas não achei em lugar algum, acredito que seja parecido com a maneira de descobrir quantos zeros existem em um número fatorial(Determinar zeros de fatorial).

1
  • Olá amigo, sobre dúvidas com o URI você pode acessar direto o fórum do site - urionlinejudge.com.br/forum - , é mais fácil de alguém te ajudar por lá por muitas pessoas já terem resolvido os MESMOS problemas.
    – pmargreff
    Commented 3/07/2016 às 14:11

3 Respostas 3

5

Não entendi 100% a solução matemática do Leo, talvez seja o mesmo que vou mostrar aqui. Encontrei no site Math Overflow uma discussão que indica haver uma relação entre entre o número de carries e as somas dos dígitos de cada operando e do resultado. Esta fórmula é citada:

inserir a descrição da imagem aqui

Sb representa uma soma de dígitos na base b; a e c são os operandos da adição, e k é o número de carries. Rearranjando a fórmula para isolar k, e considerando que você está trabalhando na base 10, teremos:

inserir a descrição da imagem aqui

Uma implementação em C, como exemplo:

#include <stdio.h>

int main(void) {
    int teste1 = carries(9, 1);
    int teste2 = carries(99, 1);
    int teste3 = carries(999, 1);
    int teste4 = carries(999, 10);

    printf("9+1: %i carries\n", teste1);
    printf("99+1: %i carries\n", teste2);
    printf("999+1: %i carries\n", teste3);
    printf("999+10: %i carries\n", teste4);

    return 0;
}

int carries(int a, int b) {
    return (sumDigits(a) + sumDigits(b) - sumDigits(a+b)) / 9;
}

int sumDigits(int num) {
    int sum = 0;
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

http://ideone.com/P8OZ5t

3
  • Ótimo! Tem uma forma melhor ainda de fazer, mas a galera top do URI não quer revelar Commented 6/07/2016 às 16:49
  • Se descobrir, posta uma resposta aqui!
    – bfavaretto
    Commented 6/07/2016 às 16:59
  • vou tentar adicionar algum no facebook! Commented 6/07/2016 às 17:01
1

Se é que eu entendi seu problema, acredito que capturando a expressão como "string" e tratando com um contador, duas variáveis de controle e algumas variáveis auxiliares seja mais eficiente.

Minha sugestão é desenvolver um algoritmo da seguinte forma:

Serão necessárias duas variáveis de controle, uma para registrar o dígito com a maior quantidade de Carrys na expressão (caso ocorra) e outra para registrar o respectivo dígito desta ocorrência.

Devem haver variáveis auxiliares, como para o contador do "loop" que deve "varrer" a "string" da expressão caractere por caracter da esquerda para a direita, de um até a quantidade de caracteres da expressão, por exemplo, para "12 + 999999" será de 1 até 11.

Sempre que ocorrer a sequência de um mesmo digito, registre a quantidade somando 1 em uma variável auxiliar e em outra variável auxiliar registre qual é esse dígito.

Quando o próximo dígito for diferente do anterior, verifique se a quantidade da variável auxiliar é maior que a registrada na variável de controle, se não for, zere as variáveis auxiliares e continue, se for a maior quantidade, registre ela na variável de controle como também na outra variável de controle qual é esse dígito. Se for o mesmo dígito irá sobrepor, então não haverá problema, como é o caso de "555 + 555".

espero ter ajudado!

1
  • Na verdade eu citei ali que eu tinha conseguido resolver o problema recebendo por string, mas ai onde ta, eu queria uma forma matemática de resolver isso, por string já vira um algorítmo de TI Commented 4/07/2016 às 20:40
1

Atenção, posso ter interpretado mal a questão e esta solução pode não apresentar Carrys pelo método matemático.

A solução matemática que deseja e que eu desenvolvi (desconheço se alguém já fez isso antes, pois sou engenheiro e não matemático, se alguém tiver uma referência, favor informar nos comentários, que faço questão de analisar e citar aqui nesta resposta) é essa:

inserir a descrição da imagem aqui

Abaixo um exemplo com as fórmulas das células apresentadas ao lado (neste exemplo, a coluna é "I" e a linha dos dados iniciais é 13)

inserir a descrição da imagem aqui

Como os cálculos funcionam:

inserir a descrição da imagem aqui

Primeiro é preciso calcular a quantidade de dígitos do número a ser analisado, isto é feito por meio da parte inteira do resultado do logaritmo de base 10 desse número mais um.

O logaritmo de base 10, para valores como 10, 100 e 1000 só retorna números inteiros, respectivamente 1, 2 e 3 neste exemplo (suas respectivas potências).

Assim, um valor inteiro que esteja entre 10 ^ 3 (1000) e 10 ^ 4 (10000), terá o resultado de seu logaritmo de base 10 entre 3 e 4, nunca 3 (seria 1000) ou 4 (seria 10000).

Desta forma, acima de 1000 (que tem quatro dígitos, igual à sua potência mais um) e abaixo de 10000 (que tem cinco dígitos, igual à sua potência mais um), todos os valores inteiros neste intervalo obrigatoriamente terão quatro dígitos, e o resultado de seus logaritmos serão sempre maiores do que 3 e menores do que 4.

Portanto, pegando a parte inteira deste cálculo e somando um, obtemos o número de dígitos do número inteiro analisado.

Para ser um Carry, todos os dígitos devem ser iguais, então, obtendo o primeiro dígito deste número podemos gerar um Carry com ele (de mesmo números de dígitos do valor original) e comparar se são iguais.

Pegando a parte inteira do resultado da divisão deste valor por 10 elevado ao seu número de dígitos e multiplicando por 10, obtêm-se um número inteiro que é o primeiro dígito do valor analisado.

Para repetir este dígito pela quantidade de dígitos do valor analisado, é preciso obter o mesmo número de 1s, para que, ao multiplicar por este primeiro dígito, o resultado retorne seu respectivo Carry.

Como 1/9 dá uma dízima de 1s, basta pegar a quantidade de 1s necessária para a multiplicação.

Isto é feito pelo cálculo da parte inteira da dízima vezes 10 elevado ao número de dígitos.

Ao multiplicar o primeiro dígito pelos 1s, obtêm-se o Carry.

Ao subtrair o valor do Carry obtido pelo valor analisado, se o resultado for zero, trata-se de um Carry, senão não é um Carry.

A quantidade de dígitos deve ser considerada quando se obtêm o Carry.

Faça isso para cada parte da sua equação!

11
  • A tabela tinha uma falha na apresentação das respostas, já corrigi.
    – Leo
    Commented 4/07/2016 às 23:24
  • 1
    Oi Leo. Dê uma olhada na minha resposta, veja se bate com o que você disse. Não consegui ter certeza – deve ser porque não sou engenheiro :)
    – bfavaretto
    Commented 5/07/2016 às 14:44
  • kkkkk, boa @bfavaretto, eu não uso esta linguagem, então, gostaria de saber se os resultados bateram, inclusive para os mesmos exemplos que apresentei, no entanto, não há nestas equações os elementos que apresentei em minha solução, portanto, continua sem referência (pode ser que eu tenha criado algo novo...)
    – Leo
    Commented 5/07/2016 às 18:04
  • Então, é que eu não entendi sua resposta, nem a tabela. A pergunta fala de quantos "vai n" (carries) existem numa operação de soma. A sua tabela tem números soltos.
    – bfavaretto
    Commented 5/07/2016 às 19:33
  • Não é isso, está tudo em fórmulas do Excel e a explicação dos cálculos está na própria tabela abaixo de cada legenda de linha. Vou rever mais tarde e editarei, aceito sugestões.
    – Leo
    Commented 5/07/2016 às 19:38

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .