Sistemas Concorrentes

Nove ou Menos

Faculdade de Informática – PUCRS

Resumo

O artigo em questão, proposto na disciplina de Algoritmos e Programação III, irá abordar um dos diversos tópicos da matemática, mais precisamente respondendo uma pergunta da Teoria dos Números. Serão exemplificadas duas alternativas com suas respectivas eficiências, com a finalidade de descobrir quantos números existentes possuem 12 dígitos, dentre os quais qualquer grupo de 3 dígitos consecutivos, quando somados, não ultrapassem o valor 9.

Palavras-chave: matemática, teoria, dígitos

Introdução

Dentro do escopo da disciplina de Algoritmos e Programação III, o problema matemático apresentado pode ser resumido da seguinte maneira:

1. Suponha um número de 12 dígitos qualquer, não começao pelo dígito 0: 232 416 889 351

2. Pegamos o primeiro grupo de 3 dígitos consecutivos e somamos para ver se o resultado é menor do que 9:

2+3+2 = 7

Com uma soma igual a 7, conferimos que a sequência está dentro da regra por ser menor que 9, logo nos direcionamos para os próximos 3 números consecutivos:

3+2+4 = 9

Calculando a soma obtemos o resultado do valor 9, vemos que ainda estamos dentro da regra, assim partimos para o próximo conjunto de números de 3 dígitos: 2+4+6 = 12

Sendo a soma maior do que 9, o número apresentado 232 416 889 351 já não é mais válido pois viola a nossa premissa.

Para a resolução serão demostradas duas soluções de como obter esses números, bem como a diferença de tempo gasto em ambos algoritmos.

Primeira Solução

Inicialmente foi analisada a variação das possibilidades dos números, ou seja: o primeiro número de 12 dígitos a ser calculado é 100 000 000 000 e o último, 900 900 900 900. Sendo assim teríamos um laço de repetição com 800.900.900.900 iterações para verificar todas as possibilidades.

A linha de pensamento que utilizamos, para uma primeira solução, foi trabalhar com