Problema 24 - Permutações lexicográficas

Qual é a permutação lexicográfica (ie, "ordem alfabética") número 1 milhão do vetor (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)? É isso que o problema quer que respondamos. Considero, claro, que o próprio vetor inicial já seja sua primeira permutação. A segunda é (0, 1, 2, 3, 4, 5, 6, 7, 9, 8).

Escrevi um algoritmo que gera sempre a próxima permutação lexicográfica de um vetor trocando posições de elementos apropriados. Acho que vi na Wikipedia, mas não importa. O importante é entender o mecanismo. :o)

O problema é que, pelo menos em R, a resolução é lenta, foram 51,33 segundos na minha máquina. Deve haver alguma maneira mais inteligente de resolver o problema, ao invés de simplesmente gerar um milhão de permutações. Mas não creio que isso seja grave.

Problema 23 - Soma não-abundante

Chamamos um número de abundante se a soma de seus divisores próprios for maior que ele mesmo. Por exemplo, os divisores próprios de 24 são 1, 2, 3, 4, 6, 8 e 12 e a soma deles resulta em 36, portanto 24 é um número abundante. Sabe-se que todos os inteiros maiores que 28123 podem ser escritos como a soma de dois números abundantes. O problema pede para que calculemos a soma de todos os números naturais que não podem ser escritos como a soma de dois números abundantes.

Implementei um método de força bruta, primeiro gerando todos os números abundantes até 28123, depois gerando todas as somas destes números, então removendo entradas duplicadas e maiores que 28123 e, por fim, somando os elementos do conjunto complementar com relação à seqüência 1, ..., 28123. Segue:

Se alguém souber de um método melhor, agradeço. Não, eu não sei usar hash tables ou coisas do tipo.

Problema 22 - Pontuação de nomes

Temos uma lista de nomes num arquivo e a missão de calcular uma pontuação para cada nome, da seguinte maneira:

1. Colocar a lista em ordem alfabética;
2. Dar um valor ao nome somando-se as posições de seus caracteres (A = 1, B = 2 etc);
3. Finalmente, a pontuação do nome será esse valor multiplicado por sua posição na ordem alfabética.

Pede-se para calcular a soma disso tudo.

A variável global LETTERS contém justamente "A", "B", ..., "Z". Isso facilita muito o processo. Usando a biblioteca stringr fica fácil fazer as manipulações de string necessárias.

Não tem segredo. That's it.

Problema 21 - Números amigáveis

Um probleminha muito interessante! Seja d(n) a soma dos divisores próprios de um natural n. Se existirem dois números a e b tais que d(a) = b e d(b) = a, então a e b são chamados de números amigáveis. Pede-se, então, para calcular a soma de todos os números amigáveis abaixo de 10000.

O xis da quetão é, apenas, calcular a soma dos divisores de um dado número.

• O primeiro método a ser naturalmente pensado é: dado n, ir testando de 2 até raíz(n) se o candidato é divisor e, caso positivo, somar divisor e (por simetria) o resultado da divisão. Para acelerar, caso o número seja ímpar, testo a partir de 3 indo de 2 em 2. Lembrando, aí, que 1 é sempre divisor próprio e que n obviamente não o é.
• O segundo método foi usar a função divisor (ou função sigma), que como corolário provê a soma dos divisores através da decomposição de n em fatores primos. Aparentemente, um método mais inteligente... Mas, agora, vamos à realidade.

Ao invés de apenas rodar para n = 10.000 (e ter a resposta para o problema proposto), também rodei para n = 100.000 e para n = 1.000.000, a fim de comparar os dois métodos.

Código 1:

Código 2:

Desempenhos (respectivamente, método 1 e método 2), para comparação:

• n = 10.000: 1,28seg contra 9,40seg - tempo 7,3x maior
• n = 100.000: 24,30seg contra 1,77min - tempo 4,4x maior
• n = 1.000.000: 10,93min contra 18,83min - tempo 1,7x maior

Conclusão: o método mais simples, neste caso, ao contrário da (minha humilde) expectativa, é mais rápido que o método mais "elegante", embora essa diferença caia conforme aumentemos o tamanho do problema. Possivelmente, em algum momento o segundo método passe a levar vantagem. Até o momento, não resolvi pagar pra ver...

Problema 20 - Soma dos dígitos de um fatorial

Neste problema, pede-se para encontrar a soma dos dígitos de 100!, isto é, 1 x 2 x 3 x ... x 99 x 100.

O método lógico/ingênuo (oxímoro?) seria calcular 100! e, então, simplesmente somar os dígitos. Mas não foi como eu fiz: o número é muito grande! Muito grande para o R manipulá-lo adequadamente (é maior que 2^500, inclusive, ou seja, bem maior que 2^31, e tem 158 algarismos). O que fiz, então? Ao invés de apelar para bibliotecas que lidem adequadamente com números arbitrariamente grandes, lancei mão do meu método de se multiplicar/somar números "manualmente", calculando 100! desta maneira.

Tá aí.

Problema 19 - Contando domingos

Objetivo: contar quantos meses, começando em 01/jan/1901 e terminando em 31/dez/2000, começam num domingo.

Método: uma "trapaça". Gerei todos os dias 01 de todos os meses e, usando a função weekdays do R, contei quantos eram domingos.

Quick and dirty.

Feliz dia da mentira, pessoal.

Problema 18 - Caminho com soma máxima I

Eis aí um problema interessantíssimo. Leia a descrição. É melhor. :o)

Meu método não foi usar força-bruta. Utilizei, ao contrário, uma abordagem de ir gerando a solução para o menor triângulo (começando da extremidade superior) e, então, ir aumentando até atingir o triângulo completo. Primeiro, salvar o triângulo num arquivo de texto. Depois, agi da seguinte maneira a cada linha do triângulo (tente visualizar olhando para o mesmo):

• Os elementos extremos da esquerda e da direita recebem, respectivamente, o seu próprio valor somado ao extremo correspondente da linha anterior.
• Os outros elementos, os que não são extremos, recebem o seu próprio valor somado ao maior elemento da linha anterior imetidamente à sua esquerda ou direita.
• No final, na última linha, o maior elemento desta será a resposta pedida na descrição do problema.

Engenhoso e eficiente. Tanto que também resolvi o Problema 67 com exatamente o mesmo método, sem tirar nem pôr, em pouco mais que um piscar de olhos. Se fosse usar força bruta, o Problema 67 levaria mais que uma eternidade.