[c]programma su fibonacci

[simone1988]

/*Fibonacci
Si vuole implementare un algoritmo che, dato in input un numero intero positivo,
verifichi se esso è un numero di Fibonacci; nel caso affermativo, l’algoritmo calcola
anche l’indice del numero di Fibonacci. L’algoritmo deve essere organizzato come
una function. Scrivere un main che per 10000 volte genera a caso un numero intero
nell’insieme {0,1,2,..,20000}, chiama la function e visualizza il numero solo nel caso
sia un numero di Fibonacci (e visualizza l’indice); alla fine il main visualizza il
numero di volte in cui è stato generato un numero di Fibonacci, anche la percentuale
di successo, il numero di Fibonacci generato il maggior numero di volte (se sono più
di uno, devono essere visualizzati tutti), il numero di Fibonacci generato il minor
numero (positivo) di volte (se sono più di uno, devono essere visualizzati tutti).
Usare sempre la srand() per rendere automatica la scelta iniziale del seed della
sequenza di numeri casuali. Nella Relazione si deve riportare l’analisi della
complessità di tempo dell’algoritmo (operazione dominante: confronto)
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void fibo(int array[]);
int appartiene(int chiave,int a[],int n);
void main()
{int n=24,array[25],k[25],h=0,i,app=0,chiave;
fibo(array);
for (i=0;i<=25;i++){ k[i]=0;}
  srand ((unsigned int)time(0));
  for(i=1;i<=10000;i++){
	  chiave = rand() % 20001;  
	  app=appartiene(chiave,array,n);
	  h=app+h;	 
	  if (app!=25) 
		k[app]=k[app]+1;}//contattore si incrementa all'indice del fibonacci trovato
 for (i=0;i<=25;i++)
	 printf(" %d %d \n",i,k[i]);

}



void fibo(int array[])
   {
	 int i;
	array[0]=0;	array[1]=1;
    
    for( i = 2 ; i <= 22 ; i = i + 1 )
		array[i]=array[i-1]+array[i-2];
   }

int appartiene(int chiave,int a[],int n)
 { 
  int i;
  i = 0;
  while(chiave != a[i] && i < n-1 ) 
  {	 // printf(" \na %d ",a[i]);
  i = i+1;}
  if (chiave == a[i]) 
     return i;
  else
	  return 25;
   }

questo è il programma che ho fatto ora ho una perplessità su come trovare il numero di fibonacci che è uscito piu volte(se ne sono piu di uno) e anche quello uscito meno volte,mi sapete dare na mano?
bastano pure solo idee ,io avevo pensato di controllare l'array creato di supporto dove ad ogni indice corrisponde l'indice della serie di fibonacci,incrementando la variabile ogni volkta che usciva il numero

[MrX87]

guarda, come idea mi sembra quella giusta! devi sfruttare il vettore k che hai costruito con le ricorrenze dei numeri che hai generato! quindi per trovare il numero, o eventualmente i numeri, con maggiore frequenza, basta secondo me fare prima una semplice ricerca del massimo nel vettore k, dopodicchè scandire il vettore k e stampare tutti quei numeri uguali al massimo! allo stesso modo potresti ragionare per il minimo!
spero di essermi spiegato...altrimenti chiedi che magari ti faccio un esempio con il codice!

[simone1988]

mrx la stassa idea lho avuta anchio però in questo modo si va a benedire una regola fondamentale di programmazione,cioè la velocità e quindi l'ottimizzazione del programma.

stamani mi sono svegliato e la prima cosa che ho pensato guardando il programma è che potrei fare un ciclo su cui effettuo sia la ricerca del massimo che del minimo,mi salvo i valori e poi nella seconda ricerca faccio il confronto per trovare gli indici che corrispondono al massimo e al minimo.

[simone1988]

void max_min_arrayI(int a[],int array[],int n)
{
 int i,
 max = a[0],
 min = 100;
 for (i=1;i<n;i++)
    if(a[i] > max)
          max = a[i] ;
       else if(a[i]!=0 && a[i] < min)
	         min = a[i] ;
printf("max and min %d %d\n",max,min);
for (i=0;i<n;i++){
if(a[i] = max){
	printf("\nmax fibo "/*%d ,array[i]*/);}
if(a[i] = min){
	printf("\nmin fibo ");}
}}

questa è la procedura che ho fatto per il max e min però negli ultimi 5 righi quegli if non mi funzionano bene,mi esce sempre che la prima condizione è verificata,anche se max ha assunto il giusto valore e a[i](è l'array che contiene il numero di volte che è uscito un fibo)contiene altri valori





PS ho trovato l'errore forse però se avete altri suggerimenti sono ben accetti

[oregon]

== e non = nelle if

[MrX87]

ti posto la mia soluzione, che alla fine è la tua solo un pò modificata! fammi sapere se va bene questo ragionamento...per quanto riguarda la complessità, bhè penso che questo algoritmo sia lineare, anche se mi sa che nel caso tuo si deve tenere conto dei confronti che si effettuano! giusto?

Nella Relazione si deve riportare l’analisi della
complessità di tempo dell’algoritmo (operazione dominante: confronto)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define KO -1

void fibo(int array[]);
int appartiene(int chiave,int a[],int n);
int findMax ( int* a, int n, int* );

int main()
{
    int n=24,array[25],k[25],h=0,i,app=0,chiave, max, min=10000;
    fibo(array);
    
    for (i=0;i<=25;i++) k[i]=0;
    
    srand ((unsigned int)time(0));
    
    for(i=1;i<=10000;i++){
       chiave = rand() % 20001;  
	   app=appartiene(chiave,array,n);
	   h=app+h;	 
	   if (app != KO) k[app]=k[app]+1; //contattore si incrementa all'indice del fibonacci trovato
    }  
          
    for (i=0;i<=25;i++)
	    printf(" %d\t %d \n",i,k[i]);

    max = findMax ( k, n, &min ); 
    
    if ( max == 0 ) {
         printf ("Non e uscito nessun numero di Fibonacci!\n");
         return KO;
    }
    
    printf ("Frequenze:\n");
    for ( i=0; i<=25; i++ ) {
        if ( k[i] == max ) {
             printf ("Massima frequenza: %d \t %d\n", i, array[i] );
        }
        if ( k[i] == min ) {
             printf ("Minima frequenza:  %d \t %d\n", i, array[i] );
        }
    }
    
    system ("pause");
    return 1; 
}

void fibo(int array[])
{
    int i;
	array[0]=0;	
    array[1]=1;
    
    for( i=2; i<=22; i=i+1 )
		array[i]=array[i-1]+array[i-2];
}

int appartiene(int chiave,int a[],int n)
 { 
  int i;
  i=0;
  while ( i < n-1 ) {
        if (chiave == a[i]) return i;      
        i = i+1;
  }
  return KO;
}

int findMax ( int* a, int n, int* min )
{
    int i, max=0;
    for ( i=0; i<=n; i++ ) {
        if ( a[i] > max  ) max = a[i];
        if ( a[i] < *min && a[i]>0 ) *min = a[i];
    }
    return max;
}

[simone1988]

ok grazie faccio le opportune modifiche e migliorie