36

Segundo esta definição do priberam.pt, um número capicua é:

Número que se lê igualmente da direita para a esquerda ou vice-versa e ao qual se atribui boa sorte.

Seguindo esse raciocínio, capicua seriam 12521, 37073, 10001, etc...

Como descobrir entre números de 5 dígitos, os que são capicua apenas utilizando cálculos matemáticos, removendo números que possuam todos os 5 dígitos idênticos como 55555, 33333, 00000, etc?

P.S.: Não importa a linguagem, somente a lógica para se desenvolver uma forma de resolver isso.

6
  • tem que ser por método matemático? Commented 21/09/2017 às 18:40
  • 1
    @GuilhermeLautert sim, creio que existam libs que façam isso, mas creio que assim não teria desafio :p
    – user28595
    Commented 21/09/2017 às 18:44
  • 1
    Posso apontar métodos não ortodoxos indiretos que fazem uso desnecessário de features de uma linguagem? Commented 21/09/2017 às 21:06
  • 1
    @JeffersonQuesado se envolver um pouco da matematica na logica, claro que sim :)
    – user28595
    Commented 21/09/2017 às 23:05
  • 1
    @Piovezan é descobrir se um número que possua 5 algarismos é capicua. Essa é a essência da pergunta, apesar de muitas respostas não terem limitado a apenas 5(o que acabou tornando-as ainda mais interessante).
    – user28595
    Commented 23/09/2017 às 23:38

8 Respostas 8

30
+100

Consideremos inicialmente um valor inteiro positivo de 5 dígitos que pode ser escrito como abcde. Da definição, temos que este valor será considerado um capicua se, e somente se, abcde for igual a edcba. Assim, temos a primeira condição que define nosso conjunto:

  • b, c e d pertencem ao conjunto dos números naturais, tal que 0 ≤ b, c, d ≤ 9;
  • a e e pertencem ao conjunto dos números naturais não nulos, tal que 0 < a, e ≤ 9;

Perceba que os dígitos a e e não podem ser 0, pois assim configuraria um número de 4 dígitos, visto que na matemática o zero a esquerda é ignorado.

Assim, considerando a forma polinomial dos números na base decimal, podemos escrever:

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Sendo os números naturais, esta expressão somente é válida se, e somente se, a - e = 0 e b - d = 0; isto é, se a = e e b = d, como já seria esperado. Assim, podemos imaginar uma função:

inserir a descrição da imagem aqui

Sendo x o número abcde. A função f(x) irá retornar 0 para qualquer número capicua, porém não somente eles. Em verdade, retornará 0 para qualquer valor que satisfazer a - e = -(b - d), tal como 65365, pois 6 - 5 = -(5 - 6). Tal problema pode ser contornado se considerarmos o módulo dos valores:

inserir a descrição da imagem aqui

Assim continuará zero para os números capicuas e diferente de zero para qualquer outro valor. Porém, números com dígitos repetidos seriam considerados de igual forma, pois continuam satisfazendo tal condição. Para, então, identificar os números capicuas com dígitos repetidos, podemos imaginar um valor:

inserir a descrição da imagem aqui

Colaboração de Jefferson Quesado.

Onde w será 0 para todos os capicuas de dígitos repetidos e 1 para qualquer outro capicua. Podemos então imaginar uma função g(x) de tal forma que:

inserir a descrição da imagem aqui

retorne 1 para os capicuas não repetidos e qualquer outro valor para outros números, incluindo capicuas repetidos. Neste caso, g(x) será o próprio valor de w, então:

inserir a descrição da imagem aqui

Assim, podemos calcular os valores de a, b, c, d e e com:

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Podemos generalizar, então, para uma função que obtém o n-ésimo dígito de um número:

inserir a descrição da imagem aqui

JavaScript

Farei a implementação em JavaScript para aproveitar que é executável pelo snippet do site.

const digit = n => x => (x % Math.pow(10, n) - x % Math.pow(10, n-1)) / Math.pow(10, n-1);

const a = digit(5);
const b = digit(4);
const c = digit(3);
const d = digit(2);
const e = digit(1);

const g = x => Math.ceil(
    Math.abs(
        (a(x)+1000)/(b(x)+1000) + (b(x)+1000)/(c(x)+1000) + (c(x)+1000)/(d(x)+1000) + (d(x)+1000)/(e(x)+1000) - 4
    )
);

const f = x => Math.abs(a(x) - e(x)) + Math.abs(b(x) - d(x)) + g(x);

let capicuas = 0;

for (let x = 10000; x < 100000; x++) {
    
    // Verifica se é capicua:
    if (f(x) === 1) {
        
        capicuas++;
        
        // Confirma se realmente é invertendo a string:
        if (x.toString() != x.toString().split('').reverse().join('')) {
            console.log(`Não é capicua, mas foi considerado: ${x}.`)
        }
        
    } else {
        
        // O número é capicua, mas foi desconsiderado pela função:
        if (x.toString() == x.toString().split('').reverse().join('')) {
            console.log(`É capicua, mas não foi considerado: ${x}.`)
        }
        
    }
}

console.log(`Foram encontrados ${capicuas} números capicuas de 5 dígitos.`);

3
  • No intervalo 10000-100000 foram encontrados 891 números capicuas, sua função está retornando 810, possivelmente o problema já citado acima. Mas gostei muito da resposta =] Commented 22/09/2017 às 16:14
  • 3
    @RovannLinhalis problema solucionado.
    – Woss
    Commented 22/09/2017 às 17:49
  • 2
    Essa resposta deveria ser impressa e emoldurada em ouro Commented 22/09/2017 às 19:05
25

Basicamente é necessário inverter o número e checar se ele é igual à entrada original.

Essa implementação funciona pra números com qualquer quantidade de dígitos.

Implementação em C#:

using static System.Console;

public class Program
{
    public static void Main()
    {
        int num;
        int original = num = 51315;     
        int rev = 0;

        while (num > 0)
        {
            int dig = num % 10; //Captura cada dígito

            rev = rev * 10 + dig; 
            // (^) Adiciona o dígito na variável 'rev'.
            // Como usamos a base 10, tudo o que já existe 
            // em rev precisa ser mulplicado por 10

            num = num / 10;
            // Controla o loop
        }

        WriteLine(original == rev ? "É capícua" : "Não é capícua");
    }
}

Veja funcionando no .NET Fiddle | Código no GitHub para referência futura

0
16

Para ser capicua, basta separar todos os dígitos e comparar o dígito d_a com seu complemento d_(5-a+1). Note que o dígito do meio é ignorado porque ele é igual a ele mesmo.

Considere // a operação de divisão inteira, conforme descrita pela linguagem Python. Considere linhas que começam por # como comentários.

Dica do @AndersonCarlosWoss, inicialmente eu não havia definido que estava usando divisão inteira

d1 = n // 10000
r1 = n % 10000

d2 = r1 // 1000
r2 = r1 % 1000

d3 = r2 // 100
r3 = r2 % 100

d4 = r3 // 10
r4 = r3 % 10

d5 = r4

# garantia de capicua:
d1 == d5 and d2 == d3

# garantia de que tem algum dígito distinto:
not (d1 == d2 and d2 == d3 and d3 == d4 and d4 == d5)

# portanto, para ser capicua com algum dígito distinto
return d1 == d5 and d2 == d3 and not (d1 == d2 and d2 == d3 and d3 == d4 and d4 == d5)
12
+50

Eu posso definir uma palavra como sendo um conjunto de tuplas formadas por caracter/posição. Assim, a palavra banana teria a seguinte representação matemática:

{
  ('b',0),
  ('a',1),
  ('n',2),
  ('a',3),
  ('n',4),
  ('a',5)
}

Posso mudar um pouco a definição para que cada letra seja mapeada para um conjunto de posições; então, banana ficaria assim:

{
  ('b',{0}),
  ('a',{1,3,5}),
  ('n',{2,4})
}

Algo interessante dessa definição é que, se a minha letra não estiver na palavra, posso associar ela ao conjunto vazio:

{
  ('a',{1,3,5}),
  ('b',{0}),
  ('c',{}),
  ('d',{}),
  ('e',{}),
  ('f',{}),
  ('g',{}),
  ('h',{}),
  ('i',{}),
  ('j',{}),
  ('k',{}),
  ('l',{}),
  ('m',{}),
  ('n',{2,4}),
  ('o',{}),
  ('p',{}),
  ('q',{}),
  ('r',{}),
  ('s',{}),
  ('t',{}),
  ('u',{}),
  ('v',{}),
  ('w',{}),
  ('x',{}),
  ('y',{}),
  ('z',{})
}

Esse tipo de estrutura de dados, de uma chave mapear para um conjunto de elementos, é chamada de multimapa. De modo geral, o multimapa tem duas operações: inserir valor e resgatar conjunto.

Então, no multimapa de banana (doravante denominado de mm_banana), podemos adicionar s na posição 6:

mm_banana.put('s', 6)

// conteúdo de mm_banana modificado sem conjuntos vazios:

{
  ('a',{1,3,5}),
  ('b',{0}),
  ('n',{2,4}),
  ('s',{6})
}

Se adicionamos 's',6, 'e',7 e 's',8 a mm_banana, ficaria assim:

mm_banana.put('s', 6)
mm_banana.put('e', 7)
mm_banana.put('s', 8)

// conteúdo de mm_banana modificado sem conjuntos vazios:

{
  ('a',{1,3,5}),
  ('b',{0}),
  ('e',{7}),
  ('n',{2,4}),
  ('s',{6,8})
}

A representação decimal de um número é um multimapa de palavra (conforme descrito acima), sendo que o alfabeto da chave são os dígitos decimais.

Para, a partir de um número qualquer x, obter sua representação decimal, fazemos divisões sucessivas e armazenamos o resto. Por uma questão de simplicidade, vamos considerar a escrita da palavra decimal em little-endian, onde os menos significativos vem primeiro. Assim, o número 0x10 tem sua representação em palavra decimal little-endian 61. O seguinte código em Python a seguir demonstra isso:

def representacao_base(x, base):
  digit_pos = 0
  while (x > 0):
    digito = x % base
    print("digito %d, posição %d" % (digito, digit_pos));
    x //= base
    digitPos += 1

representacao_base(0x10, 10)

Veja funcionando no ideone.

Notou que eu escrevi de modo generalizado para qualquer base? Pois é, a vantagem disso é que podemos verificar se um número é capicua em qualquer base mais adiante. Então, 12 seria representado como 0011 na base 2 usando little-endian. O endianismo não influi na decisão do número ser capicua ou não, assim como escrever uma palavra ao contrário não influencia no fato de ela ser ou não palíndroma.

Para detectar que um número é capicua, usamos o algoritmo acima para desmembrá-lo e colocar cada dígito como chave do multimapa, cada posição como sendo o valor sendo inserido no multimapa. Em Java, alcancei isso da seguinte maneira:

public class Multimapa {
    Set<Integer>[] pos;
    int size;
    int base;

    private void initPos(int base) {
        pos = new HashSet[base];

        for (int i = 0; i < base; i++) {
            pos[i] = new HashSet<>();
        }
    }

    public Multimapa(int n, int base) {
        this.base = base;
        initPos(base);

        if (n == 0) {
            pos[0].add(0);
            size = 1;
            return;
        }
        if (n < 0) {
            n = -n;
        }
        int digitPos = 0;
        while (n > 0) {
            int digit = n % base;
            pos[digit].add(digitPos);

            n /= base;
            digitPos++;
        }
        size = digitPos;
    }
}

Note que, como a chave é um dígito, e um dígito por sua vez é um número inteiro, o multimapa é fornecido pelo atributo pos; pos[7] vai obter as posições em little-endian que o dígito 7 ocupa na base passada. Detalhe: a chave é um inteiro e o valor é um conjunto (set em inglês significa conjunto em português, no contexto matemático) de inteiros.

Assim, para demonstrar que a classe Multimapa se comporta como a estrutura de dados multimapa descrita acima, preciso mostrar que ela suporta as mesmas operações de inserção e de resgate.

A operação de resgate é simples. Dado um dígito d, pos[d] resgata o conjunto correspondente. Para fazer a adição da posição p ao dígito d, basta fazer pos[d].add(p). Note que essa é uma operação idempotente, então pos[d].add(p); tem o mesmo efeito de pos[d].add(p); pos[d].add(p); pos[d].add(p);.

Lembra da representação da palavra com multimapa usando conjunto vazio para a não existência daquela letra na palavra? Estamos usando o mesmo conceito aqui, para facilitar as operações de resgate e adição sem precisar de tratativas adicionais nem ofender a definição.

Para determinar se o número é repetido, podemos verificar se ele tem mais de um dígito não nulo. Para tal, basta iterar nos dígitos e verificar o tamanho dos conjuntos. Se existir apenas um dígito com tamanho não nulo, então o número é repetido. Para detectar se é não repetido, basta fazer a inversão lógica. Como não há a opção de número sem dígito, então o mínimo de dígitos com pelo menos uma posição no número é 1. Portanto, a negação de ser número com um único dígito é ter a contagem > 1.

private static boolean ehNaoRepetido(Multimapa mm) {
    int nDigitosDistintos = 0;

    for (int i = 0; i < mm.base; i++) {
        nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
    }

    return nDigitosDistintos > 1;
}

Para verificar se um número é capicua na base definida, precisamos garantir que todo dígito na posição p tem outro dígito na posição especular p'. Um caso especial é o número da posição intermediária com números de tamanho ímpar: ele é seu próprio especular, portanto ele pode ser ignorado.

A relação entre p, p' e o tamanho size do número é:

p + p' = size - 1

      ||
      \/

p' = size - 1 - p

A posição intermediária t, que vai ser ignorada, é calculada assim:

t = size % 2 == 1? size/2: -1;

Como só existem posições preenchidas a partir do 0, colocar -1 vai garantir que t sempre será ignorado para números de um tamanho par de dígitos.

Assim, a seguinte verificação trata disso:

private static boolean ehCapicua(Multimapa mm) {
    int somaSimetrica = mm.size - 1;
    int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;

    for (int d = 0; d < mm.base; d++) {
        for (Integer p: mm.pos[d]) {
            // só tenta verificar se tem o complemento se e somente se não é ignorado
            if (p != posIgnorada) {
                int posComplemento = somaSimetrica - p;

                // se não existe o dígito na posição complementar, então não é capicua
                if (!mm.pos[d].contains(posComplemento)) {
                    return false;
                }
            }
        }
    }
    return true;
}

Segue o código completo usado para verificar se um número é capicua não repetido nas bases determinadas:

package capicua;

import java.util.HashSet;
import java.util.Set;

public class Multimapa {

    Set<Integer>[] pos;
    int size;
    int base;

    private void initPos(int base) {
        pos = new HashSet[base];

        for (int i = 0; i < base; i++) {
            pos[i] = new HashSet<>();
        }
    }

    public Multimapa(int n, int base) {
        this.base = base;
        initPos(base);

        if (n == 0) {
            pos[0].add(0);
            size = 1;
            return;
        }
        if (n < 0) {
            n = -n;
        }
        int digitPos = 0;
        while (n > 0) {
            int digit = n % base;
            pos[digit].add(digitPos);

            n /= base;
            digitPos++;
        }
        size = digitPos;
    }

    public static void main(String... args) {
        int qntNumerosInteressantes = 0;
        for (int i = 0; i < 99999999; i++) {
            if (julga(i, 10)) {
                System.out.println(i + " é capicua não repetido na base " + 10);
                qntNumerosInteressantes++;
            }
        }

        System.out.println("quantidade de números capicua e não repetidos nas base 10: " + qntNumerosInteressantes);

        qntNumerosInteressantes = 0;
        for (int i = 0; i < 99999999; i++) {
            if (julga(i, 16)) {
                System.out.println(i + " é capicua não repetido na base " + 16);
                qntNumerosInteressantes++;
            }
        }

        System.out.println("quantidade de números capicua e não repetidos nas base 16: " + qntNumerosInteressantes);

        meta_julga(0xffeff, 10); // 1048319
        meta_julga(121, 10);
        meta_julga(1221, 10);
        meta_julga(12721, 10);
        meta_julga(12721, 16); // 31b1
        meta_julga(0xffeff, 16);
        meta_julga(0xffdead, 16);
        meta_julga(0101, 8);
        meta_julga(0171, 8);
        meta_julga(01267621, 8);
        meta_julga(01267421, 8);

        meta_julga(5, 2); // 101
        meta_julga(6, 2); // 110
        meta_julga(7, 2); // 111
        meta_julga(4, 2); // 10
        meta_julga(16, 3); // 121
        meta_julga(10, 3); // 101
        meta_julga(12, 3); // 110
    }

    private static void meta_julga(int n, int base) {
        if (julga(n, base)) {
            System.out.println(n + " é capicua não repetido na base " + base);
        } else {
            System.out.println(n + " não é capicua não repetido na base " + base);
        }
    }

    // retorna verdade se todos os dígitos do número passado forem idênticos
    //
    // algoritmo de detecção: se, por acaso, existirem pelo menos dois dígitos com 1 ou mais posições, então é não repetido.
    // caso seja tudo zero exceto por um único dígito, então é repetido
    private static boolean ehNaoRepetido(Multimapa mm) {
        int nDigitosDistintos = 0;

        for (int i = 0; i < mm.base; i++) {
            nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
        }

        return nDigitosDistintos > 1;
    }

    // retorna verdadeiro caso seja capicua
    //
    // algoritmo: verifica cada dígito; se for de tamanho `t` ímpar, então o dígito da posição `floor(t/2)` deve ser ignorado
    // para um dígito `d` na posição `p` não ignorado, é necessário existir um outro dígito `d` na posição complementar `p'`, tal que `p + p' = t - 1`
    private static boolean ehCapicua(Multimapa mm) {
        int somaSimetrica = mm.size - 1;
        int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;

        for (int d = 0; d < mm.base; d++) {
            for (Integer p: mm.pos[d]) {
                // só tenta verificar se tem o complemento se e somente se não é ignorado
                if (p != posIgnorada) {
                    int posComplemento = somaSimetrica - p;

                    // se não existe o dígito na posição complementar, então não é capicua
                    if (!mm.pos[d].contains(posComplemento)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private static boolean julga(int n, int base) {
        Multimapa mm = new Multimapa(n, base);

        if (ehNaoRepetido(mm)) {
            if (ehCapicua(mm)) {
                return true;
            }
        }

        return false;
    }
}

Veja funcionando no ideone.

9

É possível obter-se uma estimativa de quantos dígitos há em um número usando o logaritmo na base 10:

  • (log10 1 = 0)
  • (log10 10 = 1)
  • (log10 100 = 2)
  • (log10 1000 = 3)

O logaritmo é uma função estritamente crescente. Assim sendo, se arredondarmos para baixo o seu valor, teremos isso:

  • De 1 a 9: Resultado é 0.
  • De 10 a 99: Resultado é 1.
  • De 100 a 999: Resultado é 2.
  • De 1000 a 9999: Resultado é 3.
  • ...

Se somarmos 1 a este valor, teremos o número de dígitos na base 10 de um número. Essa fórmula pode ser generalizada para outras bases ao trocar-se a base do logaritmo para a base correspondente. Com isso, podemos montar essa função:

function digitos(numero) {
    return numero === 0 ? 1 : Math.floor(Math.log10(numero)) + 1;
}

É possível determinar-se se um número tem todos os dígitos repetidos com base nisso daqui. Entretanto tomei uma abordagem um pouco diferente:

  • Um número terminado em zero que não seja o próprio zero nunca é uma repetição de dígitos.

  • Qualquer número que consista em uma repetição de dígitos, ao ser multiplicado por 9, terá todos os dígitos resultantes, exceto talvez o primeiro e o último como uma sequência de noves. Isso tem a ver com o fato de que na tabuada do 9, todos os múltiplos de 9 entre 9 até 90 quando têm os seus dígitos somados, produz 9 como resultado. Como consequência, ao fazer a multiplicação de um número que é uma repetição por 9, esses dígitos irão se somar em todas as posições exceto a primeira e a última, produzindo vários noves no meio do número.

  • Seja r o número que é uma repetição de dígitos e seja k=9r. Se r terminar com 1 (vamos chamar esse último dígito de d), o último dígito de k (vamos chamá-lo de m)) vai ser 9. Se terminar com 2, será 8 ((9 x 2 = 18)). Se terminar com 3, será 7 ((9 x 3 = 27)). Ou seja, (m = 10 - d), e portanto (m + d = 10). Logo, ao fazermos k + m, teremos 10 como resultado no último dígito e vamos deslanchar uma sequência de "vai-uns" em todos os noves tendo então um número g tal que g = b x 10^p, 1 <= b <= 9, b e N e p e N.

  • Se r começa com 1, então k começa com 9. Se r começa com 2, então k começa com 1. Se r começa com 3, então k começa com 2... Isso pode ser visto na tabuada do 9. Ao somar-se 1 ao primeiro dígito de k, se tem um número cujo primeiro dígito é o primeiro dígito de r. Isso significa que, após toda a sequência de "vai-uns" do item acima, temos b = d. Logo, ao fazermos g/d, se e somente se o resultado for uma potência de 10, é porque r é uma repetição de dígitos. Podemos verificar se é uma potência de 10 se o logaritmo na base 10 for inteiro.

Juntando tudo isso:

function repetido(numero) {
    if (numero === 0) return true;
    var d = numero % 10;
    if (d === 0) return false;
    var g = numero * 9 + d; 
    var n = Math.log10(g / d);
    return n === Math.floor(n);
}

Um número pode ser verificado se é palíndromo ao separar os dígitos utilizando exponenciação, módulo e arredondamentos (nada de strings) e verificados em pares de fora para dentro.

Juntando tudo isso:

function palindromo(numero) {
    var numDigitos = digitos(numero);
    for (var i = 0; i < numDigitos / 2; i++) {
        var a = Math.floor(numero / Math.pow(10, i)) % 10;
        var b = Math.floor(numero / Math.pow(10, numDigitos - i - 1)) % 10;
        if (a !== b) return false;
    }
    return true;
}

Por fim, um número capicuia é um palíndromo que não é uma repetição:

function capicua(numero) {
    return !repetido(numero) && palindromo(numero);
}

Abaixo está o código que verifica se um número é capicuia (para qualquer quantidade de dígitos). Também tem um teste que verifica se a implementação está correta para todos os números de 0 até 99999. O teste foi feito para mostrar apenas os números que deram errado (e do jeito que está não mostra nenhum, dá certo para todos). Depois disso, ele mostra alguns exemplos para teste.

function digitos(numero) {
    return numero === 0 ? 1 : Math.floor(Math.log10(numero)) + 1;
}

function repetido(numero) {
    if (numero === 0) return true;
    var d = numero % 10;
    if (d === 0) return false;
    var g = numero * 9 + d; 
    var n = Math.log10(g / d);
    return n === Math.floor(n);
}

function palindromo(numero) {
    var numDigitos = digitos(numero);
    for (var i = 0; i < numDigitos / 2; i++) {
        var a = Math.floor(numero / Math.pow(10, i)) % 10;
        var b = Math.floor(numero / Math.pow(10, numDigitos - i - 1)) % 10;
        if (a !== b) return false;
    }
    return true;
}

function capicua(numero) {
    return !repetido(numero) && palindromo(numero);
}

function testeNumero(numero) {

    var numeroStr = "" + numero;
    var numDigitos = numeroStr.length;

    var palindromoStr = numeroStr.split("").reverse().join("") === numeroStr;

    var repetidoStr = true;
    for (var i = 1; i < numDigitos; i++) {
        if (numeroStr.charAt(i) !== numeroStr.charAt(0)) {
            repetidoStr = false;
            break;
        }
    }

    if (digitos(numero) !== numDigitos) {
        document.write("Falhou digitos com " + numero + ".<br>");
    }

    if (palindromo(numero) !== palindromoStr) {
        document.write("Falhou palindromo com " + numero + ".<br>");
    }

    if (repetido(numero) !== repetidoStr) {
        document.write("Falhou repetido com " + numero + ".<br>");
    }

    if (capicua(numero) !== (!repetidoStr && palindromoStr)) {
        document.write("Falhou capicua com " + numero + ".<br>");
    }
}

function teste() {
   document.write("Começando...<br>");
   for (var i = 0; i < 100000; i++) {
        testeNumero(i);
   }
   document.write("Teste concluído.<br>");
}

teste();
document.write("53035 é capicua? " + (capicua(53035) ? "Sim" : "Não") + "<br>");
document.write("53035 é repetido? " + (repetido(53035) ? "Sim" : "Não") + "<br>");
document.write("53567 é capicua? " + (capicua(53567) ? "Sim" : "Não") + "<br>");
document.write("8765678 é capicua? " + (capicua(8765678) ? "Sim" : "Não") + "<br>");
document.write("369 é capicua? " + (capicua(369) ? "Sim" : "Não") + "<br>");
document.write("363 é capicua? " + (capicua(363) ? "Sim" : "Não") + "<br>");
document.write("55555 é capicua? " + (capicua(55555) ? "Sim" : "Não") + "<br>");
document.write("55555 é repetido? " + (repetido(55555) ? "Sim" : "Não") + "<br>");
document.write("55455 é repetido? " + (repetido(55455) ? "Sim" : "Não") + "<br>");

Tentei achar uma fórmula que verificasse se é palíndromo não apenas sem usar strings, mas também sem usar laços e nem recursão. Entretanto, não consegui e tive que me contentar em ficar com um laço. Nesta tentativa, o melhor que consegui é provar que todo o número palíndromo com uma quantidade par de dígitos é múltiplo de 11 (mas nem todo múltiplo de 11 é palíndromo).

0
5

Fiz alguns exemplos em C#, porém convertendo o número para string:

Primeiro:

public static bool Capicua(int x) //0.046s
{
    string s = x.ToString();
    int l = s.Length/2;


    for (int i =0; i<= l; i++)
    {
        if (s[i] != s[s.Length-1-i])
        {
            return false;
        }
    }

    return true;

}

Segundo:

public static bool Capicua2(int x) //0.063s
{
    string s = x.ToString();
    return s == Reverse(s);
}

public static string Reverse(string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}

Método auxiliar para remover os número em que todos os algarismos são iguais:

public static bool TodosIguais(int x)
{
    string s = x.ToString();
    char c = s[0];
    for (int i =1; i< s.Length;i++)
    {
        if (s[i] != c)
        {
            return false;
        }
    }

    return true;

}

Rodando a aplicação:

public static void Main()
{
    int encontrados = 0;
    for (int i =10000; i <= 90000; i++)
    {
        //if (!TodosIguais(i) && Capicua(i))
        //if (!TodosIguais(i) && Capicua2(i))
        if (CapicuaLINQ(i))
        {
            Console.WriteLine("Capicua: "+ i);
            encontrados++;
        }
    }
    Console.WriteLine("Encontrados: "+ encontrados);
}

Resultado:

Capicua: 10001
Capicua: 10101
Capicua: 10201
Capicua: 10301
Capicua: 10401
Capicua: 10501
Capicua: 10601
...
Capicua: 89698
Capicua: 89798
Capicua: 89898
Capicua: 89998
Encontrados: 792

Porém, o código postado pelo LINQ como resposta, não faz a conversão para string, o que é melhor, sendo mais rápido o tempo de execução. Só fiz a alteração para não pegar os números em que todos os algarismos são iguais:

///LINQ
public static bool CapicuaLINQ(int x) //0.019s
{
    int num;
    int original = num = x;     
    int rev = 0;
    int digAnt =  num % 10;
    bool todosIguais = true;

    while (num > 0)
    {
        int dig = num % 10; //Captura cada dígito

        if (dig != digAnt)
        {
            todosIguais = false;
        }

        rev = rev * 10 + dig; 
        // (^) Adiciona o dígito na variável 'rev'.
        // Como usamos a base 10, tudo o que já existe 
        // em rev precisa ser mulplicado por 10

        num = num / 10;
        // Controla o loop
    }

    return original == rev && !todosIguais;

}

Coloquei no .NetFiddle: https://dotnetfiddle.net/IWXftW

3
  • 2
    Sim, estava esperando uma resposta transformando em string xD Por mais ineficiente, acho que é uma alternativa que precisava estar contida aqui Commented 21/09/2017 às 21:40
  • 1
    Faltou os capicuas iniciados por 9, tal como 92529. Commented 22/09/2017 às 13:45
  • 1
    @VictorStafusa o for só vai até 90000, bastaria aumentar o limite dele =] Commented 22/09/2017 às 16:03
4

Uma lógica que encontrei foi a seguinte, separando 3 informações a partir do número com 5 dígitos, que chamo de x:

  1. Pegue os 2 primeiros dígitos (vou chamar de left2).
  2. Pegue os 2 últimos dígitos e reverta a ordem deles (vou chamar de right2_reverse).
  3. Pegue apenas o primeiro dígito (vou chamar de x1).

O número do meio (o terceiro) é irrisório e não entra na questão.

Com essas 3 informações, basta aplicar a comparação:

O left2 é igual ao right2_reverse?

Se SIM, então é capicua.

Mas você não quer números onde todos os dígitos são iguais, tipo 00000, 11111 etc...

Basta dividir o número x pelo seu primeiro dígito x1 (afinal todos são iguais). Se o resultado for diferente de 11.111, então é capicua sem ter todos os dígitos iguais.

Sempre que um número qualquer onde todos os dígitos são iguais for dividido por 1 dígito desse número, o resultado será uma sequência de 1 com o mesmo número de dígitos:

Ex. 99.999 / 9 = 11.111

O problema é o número 00.000, que se for dividido por 0, dá erro, devido à regra matemática onde "nenhum número pode ser dividido por zero".

Neste caso, basta verificar se o valor absoluto do número x é zero. Se for, basta ignorar.

Exemplos:

Seja o número x = 37073

left2 = 37
right2_reverse = 37

São iguais, logo é capicua.


Seja o número x = 37075

left2 = 37
right2_reverse = 57

São diferentes, logo não é capicua.

Fiz um código em JavaScript para verificação:

digitos = 5;

for(x=0;x<=99999;x++){
	if( x.toString().length < digitos ){
		while(x.toString().length < digitos){
			x = "0"+x;
		}
	}
	left2 = x.toString().substring(0,2);
	right2_1 = x.toString().substring(x.toString().length-2,x.toString().length-1);
	right2_2 = x.toString().substring(x.toString().length-1,x.toString().length);
	right2_reverse = right2_2+right2_1;
	
	x1 = parseFloat(x.toString().substring(0,1));

	if(left2 == right2_reverse && x/x1 != 11111 && Math.abs(x) != 0){
		capicua = " capicua!";
	}else{
		capicua = "";
	}
	$("#teste").append(x+capicua+"<br />");
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="teste">
</div>

Outra forma programática seria dividir o número x pelo seu valor espelhado, se o resultado for igual a 1, então é capicua.

10
  • 1
    Nota importante para o leitor: como o número tem cinco dígitos, x1 é garantido ser distinto de zero, portanto a divisão sempre será válida Commented 23/09/2017 às 0:52
  • 2
    Vale comentar que o número 00.000, matematicamente, não possui 5 dígitos, pois será apenas 0. Então o problema de dividir por 0 não existe, de fato. O mesmo vale para os números que você adiciona o 0 à esquerda. No domínio matemático, isso não é necessário, pois um valor como 05650 não é capicua porque ele é, na verdade, 5650 (4 dígitos).
    – Woss
    Commented 23/09/2017 às 0:52
  • 2
    Entendo seu ponto, só não concordo em analisar o número como string em um problema que estamos tratando no domínio matemático. Em programação, seria como se xfosse do tipo int, então fazer x = 01 acaba sendo o mesmo que x = 1.
    – Woss
    Commented 23/09/2017 às 1:03
  • 1
    Por isso que a pergunta pede por "capicuas", que é o equivalente de palíndromo para números, mas não me entenda errado, só achei necessário comentar esse detalhe. Isso não implica, necessariamente, que sua resposta esteja errada e precise correção :D
    – Woss
    Commented 23/09/2017 às 1:08
  • 2
    @AndersonCarlosWoss 01 não é 1 no ES3 huahuehaeuh
    – user37626
    Commented 22/10/2017 às 10:47
3

Já agora uma uma solução batuteira (só sei fazer destas ☺): gerá-los em vez de reconhecê-los.

A ideia geral é: uma capicua de 5 digitos tem a seguinte estrutura abcde em que:

  • ab é o inverso de de ou seja de = b*10+a (ou ainda ab%10*10 + int(ab/10))

    inv(ac)= mod(ab,10)×10 + int(ab/10)
    
  • portanto o conjunto das capicuas de 5 digitos é

    { ab×1000 + c×100 + inv(ab) |  ab ∈ 10..99, c ∈ 0..9 }
    
  • para verificar se um número é capicua: "yes" se ele ∈ conjunto

Para cria um programa concreto, por exemplo Usando Perl, podemos escrever:

perl -E 'say for map {$a=$_; 
                      map {$a*1000+$_*100 +$a%10*10+int($a/10)} 
                          0..9
                     } 
                     10..99 '

para gerar as capicuas de 5 digitos;

Para as reconhecer: BEGIN{calcula conjunto} para cada linha: dizer se pertence

perl -nlE '
  BEGIN{ $p{$_}=1 
         for map {$a=$_;map {$a*1000+$_*100+$a%10*10+int($a/10)} 0..9} 11..99} 
  say "yes" if $p{$_}'
6
  • 2
    Só que a questão é "como identificar" é apenas de números com 5 dígitos. E como não conheço a linguagem, a explicação da lógica aqui é essencial.
    – user28595
    Commented 22/10/2017 às 11:10
  • Eu curti a ideia de gerar, mas estou com o @Articuno : isso para mim é algo arcano e mágico! Se fosse possível inclusive por a saída no ideone você estaria me ajudando a entender Perl Commented 22/10/2017 às 11:24
  • 1
    Falando em gerar número, você me deu uma ideia de como responder em Prolog... Commented 22/10/2017 às 11:34
  • @JeffersonQuesado, juntei uma explicação com conjuntos em compreensão. Acham que se entende?
    – JJoao
    Commented 22/10/2017 às 14:08
  • Entendo sua boa vontade, mas o objetivo da pergunta é identificar numeros capicuas, não gerá-los.
    – user28595
    Commented 22/10/2017 às 14:10

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