Pessoal vou propor um desafio aqui se alguém se interessar.
Foi passado em uma prova o seguinte problema que esta sem solução ate então.
Escrever uma função na linguagem c que calcule um numero apocalíptico.
Conceito:
Numero Apocalíptico: todo numero natural n, que cumpre que 2^n (dois elevado a n) contem a sequencia 666. exemplo o numero 157.
estou tentando fazer mas esta muito difícil se alguém quiser se aventurar.
Vamos la
2 ^157 é 182687704666362864775460604089535377456991567872
isso não cabe em um long long int.
vc vai ter que usar uma biblioteca que cuide de numeros arbitrariamente grandes, ou fazer isso na mão ( o que não é nada trivial )
Realmente este é o problema que encontrei. Armazenar um numero muito grande com o suporte que o c dá e impossível, e achar bibliotecas que cuide disso tbm nao esta nada fácil.E criar um programa que atenda este tipo de problema não e nada facil pra quem nao tem muito conhecimento em c.
não é nada facil?
google “C bignum”
agora vc pode implementar a sua versão com um truque bem simples.
ao inves de usar uma variavel numerica, use um array de char
a posição 0 sera o primeiro digito. a posição 1 sera o segundo digito. assim o numero
1234
seria armazenado
char short [8] = { 4,3,2,1,0,0,0,0 };
entretanto vc quer trabalhar com numeros grandes, digamos 1024 digitos ou mais.
como vc usa isso? vc precisa fazer algo como
int quadrado( *numero, *resultado, limite );
exemplo
quadrado( entrada, resultado, 1024 );
e dentro vc vai fazer operacoes como esta
soma( entrada, entrada, resultado, limite /vai ser 1024/);
afinal o quadrado de um numero é ele vezes ele.
o que faz o multiplica:
/* retorna o "vai_um", se for diferente de zero entao o resultado extrapolou o limite */
short soma(short *primeiro, short *segundo, short *resultado, int limit){
int i;
short vai_um = 0;
for(i=0;i< limite;i++){
short a = primeiro[i];
short b = segundo[i];
short r = a + b; /* pode ser 0 ou 18 */;
r += vai_um ; /* soma no maximo 9 */
short digito = r % 10; /* se for 45, isso retorna 5*/
vai_um = r / 10; /* se for 45, isso retorna 4 */
resultado[i] = digito;
}
return vai_um;
}
vc entendeu o que estou fazendo? vc pega a definição de multiplicação e faz digito a digito.
se vc precisar imprimir isso, basta imprimir digito por digito.
vc pode incrementar essa logica, e muito, como usando uma estrutura de dados para armazenar o limite, alocar memoria dinamicamente, etc. porem o seu foco é encontrar este subarray:
6, 6, 6
muito mais simples. não?
EDIT: o que eu apresentei acima é muito ineficiente. com certeza existem formais mais interessantes de calcular isso.
por exemplo, vc calculou a potencia 2^6, nao precisa calcular 2^7 pois isso é 2^(6+1) == 2^6 * 2^1
ou seja se vc ja calculou 2^6, 2^7 vai ser o dobro disso. e o dobro de um numero é a soma dele com ele mesmo.
se vc somar um numero com ele mesmo 157 vezes vc vai ter um numero apocaliptico.
pelo codigo, vc percebeu que existem 3 formas de vc lidar com o tamanho
1- force o LIMITE ser uma macro e assim tudo vai usar esse LIMITE (não precisa passar como argumento)
2- sempre informe o LIMITE em todas as operações
3- crie uma estrutura de dados que tenha o valor do limite + ponteiro para um array de short.
vc deve se perguntar: mas pq um array de shorts. short usa 8 bits. da e sobra pra vc representar um digito. e converter um short para um char e imprimir é moleta ( soma com '0' )
EDIT2: eu fiz um pequeno exercicio onde eu somo um “bignum” com ele mesmo 1000 vezes para encontrar todos os numeros apocalipticos até 1000 ( 2^1000) e isso me custou 1.022.976 operações, forçando um limite de 1024 digitos. portanto não é la muito ineficiente ( rodou em menos de um minuto ).
O ultimo que eu encontrei foi este:
2^994 167423219872854268898191413915625282900219501828989626163085998182867351738271269139562246689952477832436667643367679191435491450889424069312259024604665231311477621481628609147204290704099549091843034096141351171618467832303105743111961624157454108040174944963852221369694216119572256044331338563584
tem 301 digitos.
como isso é para vc aprender, não me sinto confortavel em distribuir a minha solução.
Fico grato pela explicação, teoricamente estava seguindo a mesma logica que você,
porém meu conhecimento e C e muito básico.
Quanto tiver um tempo vou tentar implementar esse execício a teste de
curiosidade para ver se consigo.
Fico grato por sua atenção.