Aiuto con programmone in C. ps:c'è la ricorsione

[lucas87]

Ragazzi ci ho provato e riprovato ho scritto algoritmi su algoritmi ma non mi viene proprio in mente come fare.Non sono uno di quelle persone che usa il forum sempre per farsi fare direttamente l'esercizio, ma di questo ne ho bisogno per domani e quindi vi chiedo se per questa volta potete fare un eccezzione e postarmi direttamente il codice. Vi ringrazio anticipatamente. L'esercizio è il seguente:

Scrivere una funzione ricorsiva di nome is_fib_prime() che verifichi se l’n-esimo numero di Fibonacci è primo.

Suggerimento: tale funzione dovrebbe chiamare nel suo corpo altre due: una funzione fibonacci() che calcola il numero di Fibonacci per qualche numero intero n non-negativo, e una funzione is_prime() che verifica se un numero intero m non-negativo è primo.

[shinya]

Il tuo professore si meriterebbe due sberle.
NON calcolare MAI la serie di fibonacci con la ricorsione senza nessun accorgimento (tipo variante con dynamic programming...).

falla seguendo questa traccia in pseudo-codice:

is_fib_prime(n):
  f[0] = 0; f[1] = 1;
  for i in 2..n:
    f[i] = f[i-1] + f[i-2];

  for i in 2..sqrt(f[n]):
    if f[n] % i == 0:
      return false;
  return true;

Non calcolare i numeri primi come ho fatto io comunque. Cerca di usare il crivello di eratostene se ti è possibile.

[lucas87]

Forse non hai capito bene, la funione per calcolare il numero di fibonacci è senza ricorsione, mentre la ricorsione va nella funzione per dire se il numero è primo o no.

[shinya]

No no ho capito benissimo. Ma è una cosa molto stupida usare la ricorsione per un esercizio del genere. E' un _pessimo_ esercizio sull'uso della ricorsione.

In questo caso la ricorsione non serve e rende il codice peggiore. Rifiutati di usarla!

[lucas87]

Magari potessi, sono esercizi detti homewrok, se non li faccio mi abbassa il voto e se lo faccio senza ricorsione me lo da sbagliato. quindi chi me lo riesce a fare?

[shinya]

Come i professori rovinano gli alunni...

Cmq, alcuni consigli (la funzione non te la scrivo perchè sono 3 righe di codice, ed è meglio insegnare ad un uomo a pescare che dargli un pesce - anche se stai pescando l'amo sbagliato)...

Per scrivere una funzione ricorsiva devi fare due cose:
1) risolvere un caso singolo
2) passare un insieme di parametri ridotto nelle chiamate successive

Puoi fare in questo caso una funzione che prenda due parametri, il numero di fibonacci calcolato e un altro numero che farà da divisore.
Il divisore lo fai partire dalla radice quadrata del numero di fibonacci, e ad ogni iterazione decrementi il divisore di 1. Se arrivi a 1 torni false. Se il resto della divisione fa 0 non è primo e torni true.
Ma ripeto...fa cagare come soluzione...chiedi al tuo prof di provare con il 100esimo numero di fibonacci per vedere quanto tempo aspettate la risposta...

[wingman87]

Apparentemente l'esercizio è semplice xò c'è una cosa che non capisco. Se la funzione is_fib_prime() in realtà è solo l'unione di 2 funzioni ricorsive (fibonacci(), is_prime()) può dirsi anch'essa ricorsiva?

[shinya]

Originariamente inviato da wingman87

Apparentemente l'esercizio è semplice xò c'è una cosa che non capisco. Se la funzione is_fib_prime() in realtà è solo l'unione di 2 funzioni ricorsive (fibonacci(), is_prime()) può dirsi anch'essa ricorsiva?

No.

[wingman87]

Allora o il testo dell'esercizio è sbagliato oppure io non vedo soluzioni al problema

[shinya]

Originariamente inviato da wingman87

Allora o il testo dell'esercizio è sbagliato oppure io non vedo soluzioni al problema

Il testo dell'esercizio è semplicemente idiota.

[mamo139]

scusate l'ignoranza ma visto che studio programmazione per hobby nn so cosa vuol dire "ricorsivo"... se qualcuno me lo puo spiegare in modo chiaro e veloce poi potrei provare ad aiutare...

grazie mille ciao

[Volutomitra]

Originariamente inviato da mamo139

scusate l'ignoranza ma visto che studio programmazione per hobby nn so cosa vuol dire "ricorsivo"... se qualcuno me lo puo spiegare in modo chiaro e veloce poi potrei provare ad aiutare...

grazie mille ciao

In parole povere, un algoritmo ricorsivo è un algoritmo che richiama se stesso. Esempio, fattoriale (n * n - 1 * n - 2 * ... * 1) in c:

int fattoriale (int n)
{
if (n == 0 || n == 1)
return 1;
else
return (n * fattoriale(n - 1));
}

[akyra]

scusa...forse sei tu che non sei stato molto chiaro nell'esposizione dell'esercizio, infatti nella consegna non è scritto che tu debba implementare la funzione is_prime in modo ricorsivo, ma solo che la funzione is_fib_prime deve essere ricorsiva (anche se non vedo nessuna logica a riguardo)...
ad ogni modo, l'implementazione di fibonacci in modo ricorsivo è molto semplice, anzi, direi che è più semplice anche della versione iterativa.
per quanto riguarda il controllo del numero primo...beh, come ti è stato detto devi utilizzare il crivello di eratostene, che è un algoritmo molto conservativo e poco performante che esegue quanto detto....non so a che livello di programmazione tu sia ma mi sembra strano che il tuo prof ti faccia svolgere proprio quella funzione in modo ricorsivo e non quella di fibonacci, visto che è un classico esercizio che viene dato a chi si approccia alla ricorsione nella programmazione per la prima volta.

più che darti il codice della funzione is_prime, vorrei che tu esponessi quali sono i problemi che non riesci a risolvere, così che possiamo aiutarti a capire, e magari a farti svolgere l'esercizo passo passo con le tue forze....ti assicuro che l'utilità della cosa sarà enormemente maggiore che non darti la soluzione in blocco.
All'indirizzo:

http://it.wikipedia.org/wiki/Crivello_di_Eratostene

puoi trovare la spiegazione dell'idea che sta alla base dell'algoritmo, che non è nulla di trascendentale...
se poi ti trovi con l'acqua alla gola e proprio non riesci ad uscirne...allora possiamo provare un'altra via

[lucas87]

L'esercizio è uscito sulla pgaina del professore, io ho questo per fare l'esercizio niente altro.

[shinya]

Guarda che la soluzione te l'ho già data. Se non riesci a scrivere il programma è segno che devi studiare di più.

[mamo139]

Originariamente inviato da Volutomitra

In parole povere, un algoritmo ricorsivo è un algoritmo che richiama se stesso. Esempio, fattoriale (n * n - 1 * n - 2 * ... * 1) in c:

int fattoriale (int n)
{
if (n == 0 || n == 1)
return 1;
else
return (n * fattoriale(n - 1));
}

ahhhhhhhh
allora l'ho spesso usata senza sapere che si chiamasse così... grazie

[Volutomitra]

Originariamente inviato da mamo139

ahhhhhhhh
allora l'ho spesso usata senza sapere che si chiamasse così... grazie

Prego