C O que esse código faz?

Ater · 23 de janeiro de 2020

Olá. Venho pedir ajuda para entender a lógica de um código que, aparentemente, é um pouco avançado para mim.
Mas, contextualizando, tem um problema no uri que eu tentei resolver alguns meses atrás e não consegui. Voltei a tentar resolver ontem, mas ainda não consegui. É um problema que simplesmente me dá uma exaustão mental muito grande, embora eu consiga montar uma estrutura lógica de resolução na minha cabeça, ela ainda não fica muito clara. Para quem quiser tentar, o problema é este: https://www.urionlinejudge.com.br/judge/pt/problems/view/2846

Então eu fui atrás de uma resposta na internet o seguinte código:

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool Square(long long int x){
	
	long long int s;
	s = sqrt(x);
	return (s * s == x);
}

bool isFib(long long int c){
	return (Square(5 * c * c + 4) || Square(5 * c * c - 4)) ;
}

int main(){
	
	long long int a, i, cont = 0;
	long long int res;
	
	scanf("%lld",&a);
	
	for(i = 4; cont != a ; i++){
		if(!isFib(i)){
			cont++;
			res = i;
		} 
	}
	
	printf("%lld\n",res);
	
	return 0;
	
}

Autor: https://github.com/MN4R4/URI/blob/master/Fibonot.c

Eu achei esse código muito eficiente, diferente do que eu estava fazendo, que era criar um vetor de fibonnaci até um termo N e criar outro vetor para receber os números não existentes nesse vetor. Eu não entendi a lógica do código, então peço ajuda de vocês para me explicar. De quebra, poderiam me dizer o "caminho das pedras" para aprender a escrever um código tão eficiente e enxuto assim? Tem um estudo específico para isso ou é só programar mesmo até a barba bater no peito?

Flávio Pedroza · 23 de janeiro de 2020

A função SQUARE determina se um número de raiz quadrada exata (tirar a raiz quadrada do número e eleva ao quadrado novamente, se o número for igual ao original, então tem raiz exata).

A função ISFIB verifica se o número pertence a séria Fibonacci. Um número é Fibonacci se e somente se o seu quadrado vezes 5, somado com 4 ou subtraido 4 é um quadrado perfeito.

Ex.: o número 4.

Quatro ao quadrado = 16. 16 vezes 5 = 80. 80 -4 =76 ou 80+4 =84. Nem 76 ou 84 é quadrado perfeito, então 4 não pertence a série fibonnaci.

Já 5 é um Fibonacci, pois 5 ao quadrado * 5 = 125. 125 - 4 = 121 (quadrado perfeito, raiz 11).

Finalmente, o laço procura por todos os números ("i") que NÃO são fibonacci (fibonot) até cont == a.

O laço começa em quatro pois não tem sentido em varrer números menores que 4, já que este é o primeiro fibonot.

O laço termina quando são encontrados "a" números fibonot.

arfneto · 24 de janeiro de 2020

8 horas atrás, Ater disse:

De quebra, poderiam me dizer o "caminho das pedras" para aprender a escrever um código tão eficiente e enxuto assim? Tem um estudo específico para isso ou é só programar mesmo até a barba bater no peito?

Bem, o que seria o " caminho das pedras" o @Flávio Pedroza já explicou. E é só usar a fórmula. E se você não conhece a fórmula e não sabe como derivar tal fórmula, seria o caso de estudar matemática, mais precisamente Teoria dos Números, e não programação. E se você conhecesse a fórmula seria tentado a usar esse método afinal. Eu estudei mas não me lembrava dela afinal vergonha

Agora tenho dúvidas de que esse código seja de fato eficiente ou enxuto. Usar um contador para achar o próximo número é inevitável. Mas chamar duas funções, Square() para saber se um número é um quadrado perfeito e IsFib() para saber se ele faz parte da sequência de Fibonacci é exagerado e não enxuto.

Quando der um tempo eu vou escrever e postar uma comparação dos tempos gastos para calcular algo como os primeiros 5000 deles usando esse método e outro mais ortodoxo que vou descrever a seguir. Mas eu acho que essa ideia não é assim o máximo. Talvez seja mesmo meio besta.

Vou explicar

Square()

bool Square(long long int x)
{	
	long long int s;
	s = sqrt(x);
	return (s * s == x);
}

Chamar uma função já sai caro por si só: tem que salvar o contexto, empilhar parâmetros e uma série de coisas. Mas lendo essa aí você vê:

um long long int tem em geral 8 bytes. sqrt() é:

double sqrt (double x);

então você tem uma conversão de x para double: sqrt(x)
depois tem outra conversão de double, o retorno de sqrt() para long long int: s = sqrt(x)
depois tem uma multiplicação de dois long long int, de 8 bytes cada um (s*s)
e esse resultado é guardado em uma variável temporária long long int para ser comparado com x: (s*s == x)

Nada eficiente na verdade. Nadinha.E numa série baseada em simples somas...

IsFib()

bool isFib(long long int c)
{
	return (Square(5 * c * c + 4) || Square(5 * c * c - 4)) ;
}

aqui você tem uma expressão complexa, e alguém vai pagar a conta.

O mais tosco nesse caso é calcular potencialmente duas vezes 5 * c * c em metade dos casos. Sério? Quando a gente trata programação numérica de sequências --- que como se sabe são infintas --- em geral se pensa com mais cuidado ao escrever código que vai rodar milhões de vezes.

Seria claro mais esperto calcular 5*c*c uma vez, já que não vai mudar em uma linha ou em uma vida. E depois retornar 1 para + ou - 4 ser um quadrado perfeito. Algo como

bool isFib(long long int c)
{	long long int produto = c * c * 5;
	if( Square(produto-4) ) return true;
	if( Square(produto+4) ) return true;
	return false;
	//return (Square(5 * c * c + 4) || Square(5 * c * c - 4)) ;
}

Mas o melhor é nem escrever isFib() ou Square()

Exemplo para 233, o #13 na sequência

5*233*233 = 271.445. E 521*521 = 271.441. Claro, 271.441 = (271.445 - 4).
E a função claro iria mostrar isso porque é apenas a fórmula.
Ou seja, vai fazer duas vezes a conta toda, incluindo chamar duas vezes Square() já que ela testa por +4 primeiro.

Mais um pouco de teoria

Conforme aumenta o valor de c, o número na sequência de Fibonacci, os números vão ficando muito, mas muito mais distantes entre si., o que se pode ver na própria fórmula, que estará pertinho de sqrt(5*c*c) já que o 4 vai ser cada vez menos significativo. Em apenas 13 números o produto já está em 271.000 afinal. E o 4 não muda.

Afinal o próximo número é dado pela soma dos anteriores, certo? Conforme os tais anteriores aumentam...

Pensando em C ou FORTRAN ou qualquer outra linguagem

Se

o próximo número na sequência é dado pela soma dos dois números anteriores, nesse caso dois inteiros de 8 bytes. Simples assim. Em termos de CPU é a conta mais barata. Sem funções de biblioteca, sem doubles, nada.
Conforme segue a sequência os números vão se afastando rapidamente.
Não importa quantos já foram. Importa o próximo. E entre eles temos um certo número de alvos não Fibonacci que são o nosso objetivo. Um número grande, crescente.Sabe qual é né? O penúltimo na sequência, por definição. Ex: 89, 144, 233 na sequência. entre 144 e 233 tem... 88. É a definição da série.

Então

se tivermos uma função que devolve o próximo número da sequência ela já serve como limitante naquele for em main(). Não precisa de mais nada exceto contar de um em um até esse próximo número. Sem chamar mais funções, chamar funções de biblioteca com argumentos e retorno double, sem chamar uma OUTRA função para saber se um inteiro é um quadrado perfeito....

Semanas atrás postei uma função aqui que faz exatamente isso: devolvia o próximo número na sequència, mas você não deve ter dificuldade em escrever uma. Pode pesquisar aqui por isso entre as coisas que eu postei. Não estou agora com esse material. Estou de férias mas depois vou escrever esse programa de comparação para a gente ver a diferença ao calcular para digamos 100.000 números e ter uma noção da diferença de tempo entre um caso e outro.

Mas provavelmente é como estou dizendo. Essa solução não é enxuta. Nem eficiente.

9 horas atrás, Ater disse:

eu estava fazendo, que era criar um vetor de fibonnaci até um termo N e criar outro vetor para receber os números não existentes nesse vetor

essa ideia não era boa não: esse problema não tem memória. Você não precisa de um vetor. Só precisa do valor de N. Em especial porque estamos falando de uma série infinita. Você só precisa do valor do próximo número da sequência de Fibonacci, e de um indicador de quantos elementos não Fibonacci já passaram pelo seu programa. Se teve paciência de ler o que eu escrevi até aqui já deve ter entendido isso... Ou pergunte de novo e vamos escrever juntos um programa que compara.

adicionado 8 minutos depois

Ok, uma ajuda do Google: pesquisando por

fibonacci + "Clube do Hardware" arfneto

E temos o post

E lá tem mais um pouco de números, e a função de que eu falei. E um programa de teste

Ater · 24 de janeiro de 2020

@arfneto Muito obrigado, sua resposta foi mais que satisfatória. Como pôde ver, eu ainda não sei diferenciar um código eficiente de um não eficiente, hehe. No estudo da programação, ainda estou na parte da lógica, mas estou pegando um livro de Arquitetura e Estrutura de Dados e logo vou entender mais sobre complexidade de algoritmos. Porém esse código em questão, certamente é melhor do que eu estava pensando em fazer.

13 horas atrás, arfneto disse:

Você só precisa do valor do próximo número da sequência de Fibonacci, e de um indicador de quantos elementos não Fibonacci já passaram pelo seu programa.

Eu pensei nisso logo após ter criado este tópico. Contar quantos elementos existem entre um termo N e N + 1 da série de fibbonacci: que resultaria no enésimo termo de fibonot. Mas quando pensei nisso já estava exausto e decidi deixar pra outra hora. Incrível como tem vezes que a solução mais simples está bem na nossa frente mas acabamos recorrendo a resoluções mais ineficazes (bem, ao menos é o que acontece comigo de vez em quando).

arfneto · 25 de janeiro de 2020

22 horas atrás, Ater disse:

No estudo da programação, ainda estou na parte da lógica, mas estou pegando um livro de Arquitetura e Estrutura de Dados

No caso desse problema estruturas de dados não se aplicam.

Por outro lado esse é um exemplo clássico para introduzir uma estrutura de dados, e acho que já foi até discutido aqui: implementar uma classe ou uma biblioteca para tratar números de, digamos, 1.000 dígitos para poder usar com essas sequências numéricas, já que são sequências infinitas e um int não vai assim muito longe

22 horas atrás, Ater disse:

Contar quantos elementos existem entre um termo N e N + 1 da série de fibbonacci: que resultaria no enésimo termo de fibonot

Não. Não. Leu mesmo os post anteriores ?

Por definição existem (fib(N-1) -1) elementos aí. É a simples definição da série!

Esse desenho vai te dar uma ideia melhor de como seria um programa desses. Na primeira linha está o início da sequência de Fibonacci para manter o foco neles.

Na segunda linha você tem a sequência dos inteiros até 21 inclusive, com os números da sequência de Fibonacci em vermelho e os outros em preto.

E nas linhas 3 4 e 5 você vê que o comprimento da sequência de números não-Fibonacci cresce com uma regra bem clara. A que eu disse.

Então um programa mais simples e barato em termos de recursos para calcular o n-ésimo valor não Fibonacci simplesmente vai passando pelos números inteiros e acompanhando a série: ao atingir um valor "Fibonacci" calcula o próximo. Ao atingir um valor "Não-Fibonacci" verifica a contagem. Se achou o tal n-ésimo mostra e encerra. Só isso.

E quando para? Sem a estrutura de dados tem que parar quando estourar o valor de long long int

arfneto · 28 de janeiro de 2020

Olá!

Como eu imaginava fiquei curioso e escrevi uma função simples para calcular o n-ésimo inteiro "não-Fibonacci", para comparar com aquela folclórica função-título que discutimos. E escrevi uma função para tabular os tempos para alguns milhares de execuções e comparar.

Sem surpresas, a função abaixo é algo como 40X mais rápida para os mesmos cálculos:

uint64_t non_fib_nova(uint64_t target)
{
    uint64_t        non_fib_count = 0, fib_count = 0;
    uint64_t        prev_prev_fib = 0, prev_fib = 1;
    uint64_t        next_fib = 0;
    uint64_t        next_non_fib = 0;
    uint64_t        limit = 0x7fffffffffffffff, i = 0;

	while (limit > prev_prev_fib)
	{	// segue em frente ate atingir o limite do teste
		if (i == next_fib)
		{	next_fib = prev_fib + prev_prev_fib;
			prev_prev_fib = prev_fib;
			prev_fib = next_fib;
			fib_count += 1;
		}
		else
		{	next_non_fib = i;
			non_fib_count += 1;
		};	// if()
		if (non_fib_count == target) return next_non_fib;
		i = i + 1;
	};	// while()
	return 0;
};	// non_fib_nova()

A ideia aqui é a mais simples: segue a figura do post anterior. Como se fosse o Crivo de Eratóstenes para um único fator primo:

- os números vão passando

- se é um número da sequência de Fibonacci passa para o próximo

- se não é conta esse número como não-Fibonacci

- se é o n-ésimo retorna

- se vai estourar o valor retorna zero: só temos 8 bytes

Antes de começar a comparar os tempos, o programa chama as duas funções, a original e a "nova" para valores de 1 a 3000 e compara os resultados para ver se está tudo certo: eles devem ser claro os mesmos. Se não forem avisa onde deu diferença para ajudar a testar. Só que não deu.

Depois o programa marca o tempo necessário para calcular o n-ésimo não-Fibonacci para N indo de 1 até o limite especificado na linha de comando, ou o padrão na constante _LIMITE_ que aqui era de 50.000, usando primeiro a função original e depois a função "nova". Eis a original e as funções acessórias:

uint64_t non_fib_original(uint64_t a)
{
	uint64_t cont = 0, i, res = 0;
	for (i = 4; cont != a; i++)
	{
		if (!isFib(i))
		{
			cont++;
			res = i;
		};	// if()
	};	// for()
	return res;
};	// non_fib_original()

bool isFib(uint64_t c)
{
	return (
		Square(5 * c * c + 4) ||
		Square(5 * c * c - 4)
		);
};	// isFib()

bool Square(uint64_t x)
{
	unsigned long long int s;
	s = (unsigned long long int) sqrt((double)x);
	return (s * s == x);
};	// Square()

Tem os problemas já discutidos. A única alteração foi usar o tipo

typedef unsigned long long int uint64_t; // como em C++

que é o simples int de 8 bytes sem sinal mas com o nome curtinho de C++ e é claro o mesmo usado na outra função.

Essa é a função que compara os resultados:

bool resultado_identico(int limite)
{
    for (uint64_t i = 1; i < limite; i += 1)
    {
        uint64_t original = non_fib_original(i);
        uint64_t novo = non_fib_nova(i);
        if (novo != original)
        {
            printf(
              "valores diferentes retornados para N=%llu\n", i);
            printf("original: %llu\n", original);
            printf("  \"nova\": %llu\n", novo);
            return false;
        }; // if()
    };	// for()
    return true;
};	// resultado_identico()

Nada especial mesmo: apenas chama as duas funções e compara o valor de retorno.

A função de teste

double testa_funcao(uint64_t(*funcao)(uint64_t), uint64_t limite)
{
	uint64_t v;
	clock_t  tempo = clock();
	for (uint64_t target = 1; target <= limite; target += 1)
		v = (*funcao)(target);
	tempo = clock() - tempo;
	return (double)(tempo) / CLOCKS_PER_SEC;
};	// testa_funcao()

A lógica é primária: um loop de 1 até o limite chama a função cujo endereço veio por parâmetro, e retorna o tempo decorrido em segundos...

Um resultado

Eis o simples main() para o programa de teste

int main(int argc, char** argv)
{
	double					secsA, secsB;
	uint64_t				limite = _LIMITE_;

	if (argc > 1) limite = (uint64_t) atoll(argv[1]); 
	printf(
		"\nARFNeto 2020\nSequencias de 1 a %llu inteiros non-Fibonacci\n",
		(uint64_t) limite);
	printf("Comparando resultados das duas funcoes. Aguarde\n");

	if (resultado_identico(3000))
		printf("Primeiros 3000 valores identicos. Prosseguindo\n");
	else
	{
		printf("Valores nao coincidem. Verifique. Abortando\n");
		exit(-1);
	};	// if()

	printf("Usando a funcao original...\n");
	secsB = testa_funcao(non_fib_original, limite);
	printf("Tempo usando a funcao original = %6.3fs\n", secsB);
	printf("Usando a funcao \"nova\"...\n");
	secsA = testa_funcao(non_fib_nova, limite);
	printf("Tempo  usando a  funcao  nova  = %6.3fs\n", secsA);
	printf(
      "\nTempo nova/original = %6.3g. Performance da nova = %6.2fX da original\n",
		secsA/secsB, (secsB/secsA));

};	// end main()

O programa de teste inteiro

#pragma once
#include "math.h"
#include <stdbool.h>
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define _LIMITE_ (50000)

typedef unsigned long long int uint64_t; // como em C++

bool		isFib(uint64_t);
uint64_t	non_fib_nova(uint64_t);
uint64_t	non_fib_original(uint64_t);
bool		resultado_identico(int);
bool		Square(uint64_t);
double		testa_funcao(uint64_t (*f)(uint64_t), uint64_t l);


int main(int argc, char** argv)
{
	double					secsA, secsB;
	uint64_t				limite = _LIMITE_;

	if (argc > 1) limite = (uint64_t) atoll(argv[1]); 
	printf(
		"\nARFNeto 2020\nSequencias de 1 a %llu inteiros non-Fibonacci\n",
		(uint64_t) limite);
	printf("Comparando resultados das duas funcoes. Aguarde\n");

	if (resultado_identico(3000))
		printf("Primeiros 3000 valores identicos. Prosseguindo\n");
	else
	{
		printf("Valores nao coincidem. Verifique. Abortando\n");
		exit(-1);
	};	// if()

	printf("Usando a funcao original...\n");
	secsB = testa_funcao(non_fib_original, limite);
	printf("Tempo usando a funcao original = %6.3fs\n", secsB);
	printf("Usando a funcao \"nova\"...\n");
	secsA = testa_funcao(non_fib_nova, limite);
	printf("Tempo  usando a  funcao  nova  = %6.3fs\n", secsA);
	printf(
      "\nTempo nova/original = %6.3g. Performance da nova = %6.2fX da original\n",
	  secsA/secsB, (secsB/secsA));

};	// end main()


//
// retorna 0 se passou dos limites, ou o N-esimo inteiro
// nap-Fibonacci
//
uint64_t non_fib_nova(uint64_t target)
{
	uint64_t		non_fib_count = 0, fib_count = 0;
	uint64_t		prev_prev_fib = 0, prev_fib = 1;
	uint64_t		next_fib = 0;
	uint64_t		next_non_fib = 0;
	uint64_t		limit = 0x7fffffffffffffff, i = 0;

	while (limit > prev_prev_fib)
	{	// segue em frente ate atingir o limite do teste
		if (i == next_fib)
		{
			next_fib = prev_fib + prev_prev_fib;
			prev_prev_fib = prev_fib;
			prev_fib = next_fib;
			fib_count += 1;
		}
		else
		{
			next_non_fib = i;
			non_fib_count += 1;
		};	// if()
		if (non_fib_count == target) return next_non_fib; // achou!
		i = i + 1;
	};	// while()
	return 0;
};	// non_fib_nova()


uint64_t non_fib_original(uint64_t a)
{
	uint64_t cont = 0, i, res = 0;
	for (i = 4; cont != a; i++)
	{
		if (!isFib(i))
		{
			cont++;
			res = i;
		};	// if()
	};	// for()
	return res;
};	// non_fib_original()


bool resultado_identico(int limite)
{
	for (uint64_t i = 1; i < limite; i += 1)
	{
		uint64_t original = non_fib_original(i);
		uint64_t novo = non_fib_nova(i);
		if (novo != original)
		{
			printf("valores diferentes retornados para N=%llu\n", i);
			printf("original: %llu\n", original);
			printf("  \"nova\": %llu\n", novo);
			return false;
		}
	};	// for()
	return true;
};	// resultado_identico()


bool isFib(uint64_t c)
{
	return (
		Square(5 * c * c + 4) ||
		Square(5 * c * c - 4)
		);
};	// isFib()


bool Square(uint64_t x)
{
	uint64_t s;
	s = (uint64_t) sqrt((double)x);
	return (s * s == x);
};	// Square()


double testa_funcao(uint64_t(*funcao)(uint64_t), uint64_t limite)
{
	uint64_t v;
	clock_t  tempo = clock();
	for (uint64_t target = 1; target <= limite; target += 1)
		v = (*funcao)(target);
	tempo = clock() - tempo;
	return (double)(tempo) / CLOCKS_PER_SEC;
};	// testa_funcao()


// fim de compare.c

Não tive tempo de testar isso, mas parece que Square() pode ter um erro de arredondamento e dar erro na comparação no return em algum caso. Se alguém puder testar e postar o compilador e as opções em uso...

De todo modo não há razão para usar Square() afinal

bool Square(uint64_t x)
{
	uint64_t s;
	s = (uint64_t) sqrt((double)x);
	return (s*s == x);
};	// Square()

Ater · 2 de fevereiro de 2020

@arfneto
Olá. Desculpe o sumiço, necessitei ficar ausente por alguns dias.

Rapaz, achei muito interessante o seu código. É visível a diferença de processamento de um para o outro já na comparação do código-fonte. O mais legal é que você conseguiu deduzir a definição de fibonot, que foi algo que eu tentei bastante mas não consegui. O máximo em que consegui chegar, foi em duas funções recursivas onde uma hora o termo n pode ser definido por f(n) = f(n-1) + 1 e em outra hora é f(n) = f(n-1) + 2. E eu nem sei se está certo, já que não testei ou provei. Mas mesmo assim, funções recursivas são custosas demais em questão de processamento (constatei isso fazendo fibonacci por recursão e outro por laço).

O que eu provavelmente faria, antes de ver sua resolução, seria algo como:

Acha um numero fibonacci N.
Incrementa uma var. contadora até encontrar N-1.

Provavelmente seria bem ineficiente. Sua resolução é bem profissional.

arfneto · 2 de fevereiro de 2020

47 minutos atrás, Ater disse:

É visível a diferença de processamento de um para o outro já na comparação do código-fonte

O código original parecia um "código muito eficiente", mas com aquelas contas todas e funções demora quase 40 vezes mais, então é algo pra pensar.

Mas o resultado está certo nos dois casos.

Os não-Fibonacci

Talvez o jeito mais simples de considerar a lógica de achar o n-ésimo não-Fibonacci seja simplesmente considerar que você conta todos os números, exceto os que estão na sequência de Fibonacci, e nesse caso você avança para o próximo. Então ou faz uma coisa ou outra para todos os números. E assim deve ser um if dentro de um loop. E é mesmo.

As contas

A função

double testa_funcao(uint64_t(*funcao)(uint64_t), uint64_t limite){}

recebe o endereço (nome) da função que você quer testar e retorna o tempo gasto então dá um número mais objetivo da diferença de tempo

adicionado 15 minutos depois

Note que você pode escrever sua função e testar usando esse programa aí, chamando

bool resultado_identico(int limite){}

Para comparar com a original e usando testa_função() como declarada acima para comparar os tempos entre sua solução e essas duas que discutimos aqui. Ou mudar o programa e tabelar as 3 claro...

Ater · 2 de fevereiro de 2020

@arfneto

36 minutos atrás, arfneto disse:

O código original parecia um "código muito eficiente"

Eu imaginei que fosse, por que, aos meus olhos de principiante, o código parecia uma só definição matemática usada para encontrar o enésimo termo da sequência. Mas eu não esperava chamar as funções desse jeito implicasse na perda de desempenho, isso foi um aprendizado novo. O que mais estou gostando na programação atualmente são problemas de computação, como os problemas do Caixeiro Viajante, Josephus, Torre de Hanói et cetera. Mas ainda me falta um bom conhecimento para me meter com isso.

Enfim, segue a minha resolução.

#include <stdio.h>

int main ()
{
    int fib1 = 0, fib2 = 1;
    int fib = 0, cont = 0;
    int n;

    scanf ("%d", &n);

    for (int i = 0; i < i + 1; i++)
    {

		for (int j = fib1 + 1; j < fib2; j++)
		{
			cont++;
			if (cont == n)
			{
				printf ("%d\n", j);
				return 0;
			}
			
		}
		
		fib = fib1 + fib2;
		fib1 = fib2;
        fib2 = fib;
		
    }
    
    
}

Amanhã vou usar o seu algoritmo para comparar com as outras duas funções. Obrigado por tudo, aprendi mais sobre complexidade.

arfneto · 2 de fevereiro de 2020

1 hora atrás, Ater disse:

Eu imaginei que fosse, por que, aos meus olhos de principiante, o código parecia uma só definição matemática usada para encontrar o enésimo termo da sequência

Na verdade a fórmula dá 2 possibilidades para algum número estar na sequência de Fibonacci e daí a encontrar o n-ésimo não-Fibonacci é um grande salto... E sai caro esse salto porque a maioria dos números está fora dessa sequência e não o contrário.

Sobre o círculo de Josephus por coincidência postei duas soluções nesse forum, semanas atrás. Se quiser ver estão em

adicionado 0 minutos depois

Bom trabalho em sua solução!