Esercizio (Sequenza di Solomon-Golomb):

Testo:
La sequenza autodefinente di Solomon-Golomb è l’unica sequenza monotona non decrescente di interi positivi a$$ = a_i$$ tale che in a ci sono esattamente $$a_i$$ elementi di valore $$i\geq $$1. Per chiarire, con un esempio, questo è un segmento iniziale della sequenza:

1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9…

quindi ad esempio vi sono $$a_9 = $$5 elementi consecutivi pari a 9.

  1. Scrivere una funzione con prototipo: 
    void generate(int v[], int n)

    che dato un intero $$n$$ ed un vettore $$v$$ (con numero di elementi $$\geq n$$) riempie $$v$$ con i primi $$n$$ elementi della successione.

  2. Scrivere un programma completo che utilizzando la funzione generate e quante altre lo studente ritiene utili, legge dalla linea di comando la matricola del candidato $$m$$, calcola $$n = $$ la radice quadrata approssimata per difetto delle ultime 5 cifre della matricola aumentata di 16, costruisce una matrice 4×4 con i valori: $$[ a_n, a_{n-1}, a_{n-2}, a_{n-3}; \ldots, a_{n-14}, a_{n-15} ]$$ e stampa: la matrice e la somma dei quadrati degli elementi diagonali.

Soluzione (da leggere solo dopo aver provato a svolgere l’esercizio).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void generate(int v[], int n)
{
	// la sequenza e' definita per i>=1 per comodita
	// ignoriamo il primo elemento del vettore v[0]
	v[0] = 0;
	int i = 1;
	int value = 1;
	do {
		v[i++] = value;    			// scriviamo almeno un valore pari a value
		int count = v[value] - 1;   // value e' ripetuto per v[value]-1 volte
		while (count-- > 0)
			v[i++] = value;
		value++;					// passiamo al successivo.
	} while (i < n);
}
int main(int argc, char *argv[])
{
	if (argc < 2)
	{
		printf("programma matricola\n");
		return 1;
	}
	int m = atoi(argv[1]);
	int	n = sqrt(m % 100000 + 16);
	printf("m = %d\n",m);
	printf("n = %d\n",n);
        // creo un vettore dinamico di dimensione n+2
	int *v = malloc(sizeof(int)*n+2);
	generate(v,n);
	// for (int i=0; i<=n; i++) printf("%d ",v[i]);
	int mat[4][4];
	int count = n;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			mat[i][j] = v[count--];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++)
			printf("%d ", mat[i][j]);
		printf("\n");
	}
	printf("\n");
	int s = 0;
	for (int i=0; i<4; i++)
		s += mat[i][i]*mat[i][i];
	printf("%d\n",s);
        // prima di finire il programma restituiamo la memoria:
    free(v);
	return 0;
}