TOPIC
PROBLEM 1029 - URI Fórum 1.0
This topic was solved and cannot recieve new replies.
-
gmarini replied 7 years ago
MODVocê pode utilizar uma função recursiva um pouco diferente pra isso:
int fib(int n){ cont++; if(n<2) return n; else return fib(n-1)+fib(n-2); }
sem utilizar vetor pra armazenar, e sem o parâmetro das chamadas. E aliás, pra fazer a contagem das chamadas (cont++), declare uma variável global, ai depois é só zerar ela no programa principal:
inter=fib(b); printf("fib(%d) = %d ",b,cont-1); printf("calls = %d\n",inter); cont=0;
-
jsilver replied 7 years ago
Meu código está dando TIme Limit Exceeded, o que fazer para consertar?
def calls(n): if n==0: return 1 elif n==1: return 1
return calls(n-1) + calls(n-2) + 1
def fibonnaci(n): if n==0: return 0 elif n==1: return 1
fib1 = 0 fib2 = 1 for x in range(n-1): fib3 = fib1 + fib2 fib1 = fib2 fib2 = fib3 return fib3
Casos de teste
qtd_testes = int(input())
for y in range(qtd_testes): valor = int(input())
print ("fib(%d) = %d calls = %d" %(valor, calls(valor) - 1, fibonnaci(valor)))
-
tonyaps13880 replied 7 years ago
def fib(x): if x == 0: return 0 elif x == 1: return 1 else: return fib(x - 1) + fib(x - 2) def chamadas(x): if x > 1: return x**2 - 3 * x + 4 #Programa Principal N = int(input()) if N > 1: print("fib(%d) = %d calls = %d"%(N,chamadas(N),fib(N)))
Meu programa está dando w/a 20% mas passa pelo debbug do python. Qual será o problema? Além do mais, o exercício tem como entrada a associação: 2 ------> fib(5), 5 ------> fib(4) e 4 --------> sem associação. Não entendi. Poderiam esclarecer? Desde já, agradeço.
-
ggroth replied 9 years ago
Você não precisa usar programação dinâmica, mas irá melhorar o tempo. Dê uma pesquisada sobre programação dinâmica, conceito, e alguns algoritmos (é bem interessante e muito útil). Tem muito material na web, basta pesquisar. Nesse caso, é mais o conceito que você precisa, ou seja, basicamente pré-calcular todas as possibilidades válidas e depois apenas acessar a posição do vetor correspondente, sem precisar recalcular nada.
Voltando ao teu código. Se você imprimir como
cout << "fib(" << x << ") = " << (call - 1)<< " calls = " << counter << endl;
irá passar ;)
-
rjsrodrigues replied 9 years ago
ta dando Wrong answer nao sei pq alguém pode me ajudar
#include <iostream> #include <cstdio> using namespace std; int cont=0; int segfib(int n){ int f; cont++; if(n==1){ return 1; } if(n==0) return 0; f=(segfib(n-1)+segfib(n-2)); } int main() { int x,y,c; cin>>c; for(int i=0;i<c;i++){ cin>>x; y=segfib(x); printf("fib(%d) = %d calls = %d\n",x,cont-1,y); cont=0; } }
-
Lamartine replied 7 years ago
Poxa, era só isso mesmo. Acho que meu compilador sempre inicializava com zero, aí por isso que sempre dava certo no meu pc e errado no uri. Valeu!!!
-
Lamartine replied 7 years ago
alguem sabe me dizer pq isso ta dando errado? Já testei todos de 1 a 39 no udebug e tudo dá certo
Problema resolvido.
-
mdspereira1 replied 7 years ago
int fib(int n,int* cont,int V[]){ (*cont)++; if((n == 0) || (n == 1)){ V[n] = n; return n; } if(V[n] == 0){ V[n] = fib(n-1,cont,V)+fib(n-2,cont,V); } return V[n]; } int main() { int a = 0,inter; scanf("%d",&a); int b; for(int i=0;i<a;i++){ int V[100] = {0}; int cont =0; scanf("%d",&b); inter = fib(b,&cont,V); printf("fib(%d) = %d ",b,cont); printf("calls = %d\n",inter); } return 0; }
Ta dando WORNG ANSWER 100%, o codigo funciona porem o numero de vezes que ocorre a recursão ta dando diferente do site, alguem pode ajudar ?
-
gduarte replied 7 years ago
MODUma forma de passar sem tem muita modificação é vc pré-calcular todos os valores e salvar em um vetor, depois a cada input vc simplesmente imprime o que está no vetor. O máximo da entrada é 39 então basta um vetor de 40 posições que da certo.
Quando for postar um código aqui fórum, use a tag [ code] [ /code], assim facilita nossa visualização.
-
mlaian replied 7 years ago
No CodeBlocks funciona iqualzinho no exemplo, mas quando posto deu um w.a. 80%
#include <stdio.h> // Assinaturas int fibonacci(int num, int *pChamadas); void main(void){ int N; // caso de teste int X; // inteiro para desenvolver int i; int resultado; int nChamadas, *pChamadas; pChamadas = &nChamadas; *pChamadas = 1; scanf("%i", &N); for(i=0; i<N; i++){ scanf("%i", &X); resultado = fibonacci(X, pChamadas); printf("fib(%i) = %i calls = %i\n",X, nChamadas, resultado); *pChamadas = 1; } } int fibonacci(int num, int *pChamadas){ if(num == 1 || num == 2){ *pChamadas += 1; return 1; }else{ *pChamadas += 2; return fibonacci(num-1, pChamadas) + fibonacci(num-2, pChamadas); } }
-
MiguelAraujo replied 9 years ago
Olá, estou com dois problemas e queria a ajuda de alguém para resolver este problema. Primeiro, queria pedir alguma referência e/ou material para solucionar esta questão com PD (é necessário PD nela?) Segundo, estou com um pequeno problema nas minhas saídas: o número de chamadas está resultando um valor acima da saída do site. SAÍDA DO SITE MINHA SAÍDA
Segue o link contendo meus códigos: http://pastebin.com/0QAHddsU
Grato pela paciência! :)
-
oman10 replied on Nov 19 2013
Me desculpe, mas não entendi sua dica. Porém eu usei ponteiro para pegar as chamadas e deu certo. Não sei se é válido.
Valeu pelas dicas.
-
crbonilha replied on Nov 18 2013
O seu algoritmo está muito próximo de ser aceito, você só precisa mudar uma coisa.
Pense na sua função de fibonacci. Para descobrir o valor de fib(n), você precisa somar fib(n-1) e fib(n-2), certo? Existe também os casos bases. fib(0) sempre será 0 e fib(1) sempre será 1.
Agora esqueça os valores, você quer saber o número de chamadas. Na operação normal de fib(n), você chama fib(n-1) e fib(n-2), então como eu descubro o número de chamadas de fib(n)? E quais são os casos bases?
-
oman10 replied on Nov 18 2013
Desculpe minha ignorância Cristhian, mas não entendi a dica. Pode me citar qual assunto devo estudar para resolver este tipo de problema. Desde já obrigado.
-
crbonilha replied on Nov 18 2013
Você poderia modificar o retorno para retornar o número de chamadas, e não o valor do fibonacci.
Por exemplo, o fib(0) é chamado uma vez, certo? Por mais que o seu valor seja 0. O fib(2) chama ele mesmo, o fib(1) e o fib(0), isso seriam 3 chamadas.
-
oman10 replied on Nov 17 2013
Eu fiz o código, mas não consigo achar uma forma de contar quantas vezes ele faz.
Se for permitido me dizer como faço, pois realmente não consegui pensar em uma forma.
Olha o código ai, onde está escrito "vezes", é onde quero colocar o valor se eu conseguir achar uma forma de contar.
#include <stdio.h> int fib(int x){ if(x==0){ return(0); }else if(x==1){ return(1); }else{ return(fib(x-1)+fib(x-2)); } } int main(void){ int n, i, x; scanf("%d", &n); i=0; while(i<n){ scanf("%d", &x); printf("fib(%d) = %d calls = %d\n", x, vezes, fib(x)); i++;} return(0); }
-
Joe101 replied on Jul 12 2013
Safadinhos hein vcs nesse problema kkkk o jeito de resolver tá na cara mas passa despercebido
-
ggroth replied on Jun 5 2013
Para a entrada
2 2 3
Teu algoritmo está imprimindo
fib(2) = 1 calls = 1 fib(3) = 3 calls = 2
mas o correto seria:
fib(2) = 2 calls = 1 fib(3) = 4 calls = 2