TOPIC

PROBLEM 1029 - URI Fórum 1.0

beecrowd asked on Feb 8 2013

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • gmarini replied 7 years ago

    Você 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;
    MOD

  • 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

    Uma 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.

    MOD

  • 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

    Ninguém pode me ajudar? Abraços.

  • 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

  • Joe101 replied on Jun 5 2013

    nothin'

1 of 2