Stern-Brocot numbers - Revision history

Wepik at 10:15, 6 December 2014

2014-12-06T10:15:06Z

Wepik: /* main.c */

2014-12-06T10:08:57Z

main.c

Wepik: /* Sequenza di Stern-Brocot */

2014-12-06T10:07:46Z

Sequenza di Stern-Brocot

Wepik: /* main.c */

2014-12-06T10:05:28Z

main.c

Wepik: Created page with " == Sequenza di Stern-Brocot == [https://www.youtube.com/watch?v=DpwUVExX27E Spiegazione in inglese]. Stern-Brocot e' molto simile alla sequenza di Fibonacci. Infatti, si par..."

2014-12-06T10:03:41Z

Created page with " == Sequenza di Stern-Brocot == [https://www.youtube.com/watch?v=DpwUVExX27E Spiegazione in inglese]. Stern-Brocot e' molto simile alla sequenza di Fibonacci. Infatti, si par..."

New page

== Sequenza di Stern-Brocot ==

[https://www.youtube.com/watch?v=DpwUVExX27E 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 ==

<source lang="text">
#include <stdio.h>
#include <stdlib.h>

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

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.
}
</source>

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 reali, in ordine, nella loro forma piu' semplice, una sola volta.

← Older revision		Revision as of 10:15, 6 December 2014
Line 105:		Line 105:
	</source>		</source>

−	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 ~~reali~~, in ordine, nella loro forma piu' semplice, una sola volta.	+	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.

@@ Line 37: / Line 37: @@
 	int i;								// Contatore
 	int k= atoi(argv[1]);				// Numero di passi che la sequenza deve compiere
 	p= (nodo*) malloc(sizeof(nodo));

@@ Line 4: / Line 4: @@
 [https://www.youtube.com/watch?v=DpwUVExX27E 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, 2, 1 -> 1, 1, 2, 1, 3, 2 -> 1, 1, 2, 1, 3, 2, 3, 1 ->  ecc.

@@ Line 11: / Line 11: @@
 == main.c ==
-<source lang="text">
+<source lang="C">
 typedef struct n {						// Nodo lista