4

estou tentando montar um algorítimo em C para encontrar números inteiros que mudam de lugar ao multiplicar-se por outro.

Não encontrei problemas como esse na internet, nem mesmo sei se tem como fazer isso com números inteiros. Mas um breve exemplo com números fracionários é: 12 * 1,75 = 21

Para números de quatro dígitos; 1489, deveria ficar 9148.

Queria ajuda de vocês não para receber um código completo, mas sim, um caminho/lógica a seguir para desenvolver o código.

A maneira que estou pensando é a seguintes:

uma variável "contador = 1". um corpo while para encontrar os números que mudam de lugar entre 1 e 1 milhão. Os números de multiplicação para testes são somente 2, 3, 4, 5, 6, 7, 8 e 9. Ao invés de usar contador++, usar contador += nTeste;

Observações

Sou iniciantes em programação. Não consigo encontrar qual condição usar para saber se o número mudou de posição ou não. Ainda não estudei array's em C, sendo assim o meu código só encontrará um único número e exibirá ele. Se eu soubesse array's, poderia ir armazenando todos os números que encontrar até um milhão e depois exibir todos eles. Tentei explicar a minha dúvida, mas caso vocês não entenderem alguma parte, é só deixar um cometário.

Obrigado.

O seguinte código é algo bem inicial de como estou tentando fazer;

#include <stdio.h>
#include <locale.h>

int main(int argc, char const *argv[]) {

    setlocale(LC_ALL, "");

    //Número inteiros.
    int u, d, c, m, md, mc, mi, contador;

    //Números de testes para multiplicação.
    int nTeste;


    /*int iU, iD, iC, iM, iMD, iMC, iMI, total;*/


    /*Variáveis para extrair os dígitos de cada posição.
    Ex: Para extrair "2" de "21"; "tempDecimal = 21 / d".*/
    u = 1;          //Unidades
    d = 10;         //Dezenas
    c = 100;        //Centenas
    m = 1000;       //Milhar
    md = 10000;     //Dezenas de milhar
    mc = 100000;    //Centenas de milhar
    mi = 1000000;   //Milhão


    while (nTeste >= 2 && nTeste <= 9) {
        printf("Digite um número para teste: [2 a 9]");
        scanf("%d", &nTeste);
    }

    while (contador <= mi) {

        if (contador <= u) {

        }

        if (contado > u && contador <= d) {

        }

        if (contado > d && contador <= c) {

        }

        if (contado > c && contador <= m) {

        }

        if (contado > m && contador <= md) {

        }

        if (contado > md && contador <= mc) {

        }

        if (contado > mc && contador <= mi) {

        }



    }

    return 0;
}
2
  • 1
    Você já aprendeu a escrever funções (que não a main())?
    – user25930
    Commented 4/06/2015 às 15:02
  • Sim, estou lendo o Como Programar em C - Deitel. Commented 4/06/2015 às 18:12

2 Respostas 2

3

A sua ideia de fazer divisões por potências de 10 pra extrair cada dígito do número está essencialmente certa; você não precisa guardar os números que você achou num array pra imprimir só no final: não tem problema nenhum ter um if (/* número é válido */) { printf("%d\n", contador); } no meio do seu while; assim seu programa vai imprimindo os números cíclicos à medida que eles forem encontrados.

A parte que normalmente se faria com arrays seria, como você deve ter imaginado, comparar se e.g. 1489 e 9148 têm os mesmos dígitos. Com arrays, você pode colocar cada dígito no array, ordenar e comparar os dois arrays.

Um truque que funciona pra esse caso particular é usar numeração de Gödel para encontrar esses casos. Especificamente, considere os “primos”

p_0 = 1
p_1 = 2
p_2 = 3
p_3 = 5
p_4 = 7
p_5 = 11
p_6 = 13
p_7 = 17
p_8 = 19
p_9 = 23

Você vai representar o número 1489 pelo produto p₁ × p₄ × p₈ × p₉ = 2 × 7 × 19 × 23 = 6118; já o número 9148 = p₉ × p₁ × p₄ × p₈ = 23 × 2 × 7 × 19 = 6118. Esses produtos são o número de Gödel do número original.

Você deve ter aprendido em algum momento do seu Ensino Fundamental, todo número inteiro (positivo) tem uma fatoração única como produto de números primos (e.g. 120 = 2³ × 3 × 5). Como a operação de multiplicação é comutativa, isso implica que dois inteiros X e Y têm o mesmo número de Gödel se e somente se X e Y têm os mesmos dígitos (esse é o fato chave da ideia — se você não entendeu porque isso é verdade, grite nos comentários).

Como você vai implementar isso em código? Você vai, tanto para o número original, quanto para o número multiplicado por nTeste, fazer algo tipo

int goedel = 1;
int digito;

/* extrai um dígito do número, guarda em digito */

if (digito == 0) { goedel *= 1; }
if (digito == 1) { goedel *= 2; }
if (digito == 2) { goedel *= 3; }
if (digito == 3) { goedel *= 5; }
if (digito == 4) { goedel *= 7; }
if (digito == 5) { goedel *= 11; }
if (digito == 6) { goedel *= 13; }
if (digito == 7) { goedel *= 17; }
if (digito == 8) { goedel *= 19; }
if (digito == 9) { goedel *= 23; }

Depois que você terminar de rodar esse bloquinho de ifs pra cada dígito, você pode comparar os dois valores de goedel — se eles forem iguais, você pode concluir que contador e contador * nTeste têm os mesmos dígitos (ainda que em ordens diferentes).

(Um fato importante pra essa ideia funcionar, cuja relevância você não vai entender hoje, mas cuja relevância você vai entender quando você tiver estudado mais programação, e em particular microarquitetura de processadores, é que 23⁷ é menor que 2³².)

1
  • Nossa, impressionante a resposta :). Vai ajudar muito a terminar esse algorítimo e também a simplificar mais o que eu estava pensando em fazer. No momento não tenho pontos suficientes para positivar. Obrigado também por mencionar Gödel. Commented 4/06/2015 às 18:14
2

Seja x um número natural e y um outro número natural que seja anagrama de x na base 10, sendo xy.

Para encontrarmos o multiplicador m que multiplicado por x resulta em y, temos que:

m * x = y
m = y / x

Uma vez que tanto x quanto y são naturais e x é diferente de zero*, então y/x é um número racional.

(*) x é diferente de zero porque se x fosse zero, y também seria zero, o que violaria a condição xy.

A conclusão é que para TODOS os números naturais x e y tal que y é um anagrama de x e xy, então existe um número racional que multiplicado por x resulta em y.

Logo, os únicos números que não se transformam em um anagrama quando multiplicados por algum outro, são aqueles números que não possuem anagramas, tais como 11, 2222, 33, 5, 77, etc. Todos os demais podem mudar de lugar quando multiplicados por alguma coisa.

1
  • Na verdade o problema é encontrar números inteiros.
    – mathiasfk
    Commented 5/06/2015 às 4:06

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 .