Stern-Brocot numbers

Sequenza di Stern-Brocot

Spiegazione in inglese. Stern-Brocot e' molto simile alla sequenza di Fibonacci. Infatti, si parte con i primi due numeri uguali a 1, si fa la loro somma e aggiunge alla sequenza. La cosa in piu' e' che dopo la somma aggiungiamo alla sequenza il secondo addendo.

Es.:

1, 1 -> 1, 1, 2, 1 -> 1, 1, 2, 1, 3, 2 -> 1, 1, 2, 1, 3, 2, 3, 1 -> ecc.

La funzione prende in input un solo numero positivo.

main.c

typedef struct n {						// Nodo lista
	int num;							// Numero della successione
	struct n *next;
}nodo;

int main(int argc, char *argv[]) {
	if(argc!=2) {						// Controllo se il programma riceve esattamente un input
		printf("Devi inserire UN argomento!\n");
		exit(1);
	}

	nodo *r;							// Root, puntatore alla testa della lista
	nodo *f;							// Variabile d'appoggio

	nodo *p;							// Elemento numero uno
	nodo *s;							// Elemento numero due

	nodo *t;							// Elemento numero tre
	nodo *q;							// Elemento numero quattro

	int i;								// Contatore
	int k= atoi(argv[1]);				// Numero di passi che la sequenza deve compiere

        if(k<1) {
		printf("L'input deve essere maggiore di zero!\n");
		exit(1);
	}

	p= (nodo*) malloc(sizeof(nodo));
	s= (nodo*) malloc(sizeof(nodo));
	r= (nodo*) malloc(sizeof(nodo));

	r->next= p;
	p->next= s;
	s->next= NULL;

	for(i= 0; i<k; i++) {
		if(i==0) {									// Alla prima iterazione
			t= (nodo*) malloc(sizeof(nodo));
			q= (nodo*) malloc(sizeof(nodo));

			s->next= t;
			t->next= q;
			q->next= NULL;

			p->num= 1;
			s->num= 1;

			t->num= p->num+s->num;					// Salvo la somma s+t
			q->num= s->num;							// Copio il secondo elemento nel quarto

			printf("%i - %i - %i - %i - ", p->num, s->num, t->num, q->num);
		}
		else {										// Iterazione successive
			f= (nodo*) malloc(sizeof(nodo));		// Alloco nuovo spazio in memoria
			p= s;
			s= s->next;

			q->next= f;								// 
			t= f;									// 
			f= (nodo*) malloc(sizeof(nodo));		// Questo pezzo alloca e lega due nuove aree di memoria (nodi) al resto della lista
			q= f;									//
			t->next= q;								//
			q->next= NULL;							//

			t->num= p->num+s->num;					// Salvo la somma s+t
			q->num= s->num;							// Copio il secondo elemento nel quarto

			printf("%i - %i - ", t->num, q->num);	// Stampo il terzo e il quarto elemento
		}
	}
	printf("\n\n\n");

	f= r->next;										// Parto dal primo elemento della lista

	while(f->next != NULL) {						// Stampo tutte le frazioni composte con i numeri della sequenza
		printf("%i/%i  ", f->num,f->next->num);
		f= f->next;
	}
	printf("\n");

	free(r);
	free(p);
	free(s);
	free(t);
	free(q);
	free(f);										// Durante esecuzione, liberando questo puntatore ricevo il messaggio "pointer being freed was not allocated". Non trovo il motivo di questo messaggio.
}

Cosa c'e' di speciale in questa sequenza? Se mettiamo la barra della divisione tra ogni elemento della sequenza, otteniamo delle frazioni. Queste frazioni rappresentano TUTTI numeri razionali, in ordine, nella loro forma piu' semplice, una sola volta.