BASE CINQUE FORUM

Ciao a tutti,
vi propongo il seguente problema che mi pare interessante:

considerate il seguente diagramma di flusso Vi chiedo:
1) Al variare di N, qual'è il valore raggiunto da k ?
2) Esistono valori di N per cui il valore di k si incrementa ad ogni ciclo ? Che caratteristica hanno questi valori ?
3) Provate a generalizzare il problema.

Ciao,

Diego

Ciao Diego, grazie per il quesito.
Per ora ti rispondo soltanto con un saluto perché ho appena finito di leggerlo ma nei prossimi giorni proverò a scrivere un programmino per vedere che cosa succede...
Magari, si può risolvere anche senza sperimentarlo su un computer...
Buon fine settimana.

per intanto direi di escludere il caso n=0

$\begin{tabular}{ c c c c } N& K&& \\ 0& 1& -1& 1\\ -1& 1& -2& 0\\ -2& 2& -4& 2\\ -4& 2& -6& 0\\ -6& 3& -9& 3\\ -9& 3& -12& 0\\ -12& 4& -16& 4\\ -16& 4& -20& 0\\ -20& 5& -25& 5 \end{tabular}$

ecco la sequenza che si avrebbe

Ciao Info,
ho scritto che le variabili N e k sono intere e positive, quindi maggiori di zero.
Pertanto, il caso N = 0 risulta escluso.

Diego

Esistono valori di N per cui il valore di k si incrementa ad ogni ciclo?

Se ho ben capito il diagramma di flusso, credo che la risposta sia negativa.
Infatti, se k si incrementa ad ogni ciclo allora diventa:
k=1, 2, 3, 4, 5, ...
quindi N deve variare così:
N-1 è divisibile per 2?
N-3 è divisibile per 3?
N-6 è divisibile per 4?
N-10 è divisibile per 5?
...
e così via.
Affinché N-1 sia divisibile per 2, N deve essere dispari.
Ma allora N-6 non sarà divisibile per 4.
In conclusione, k può incrementarsi ad ogni ciclo solo con i valori 1, 2, 3.

Ciao Gianfranco,
la tua risposta alla seconda domanda è corretta.
Ma io ritengo assai più interessanti la prima e la terza domanda; specialmente la prima.


Diego

Decisamente un bel quesito che viene purtroppo snobbato dai più.
Il diagramma di flusso appare, a prima vista innocuo, facile da studiare: in fin dei conti ha solo due variabili, un ciclo e due controlli, uno dei quali è quello d'arresto.
Però solo grazie a due colpi di fortuna sono riuscito a risolverlo. Risolverlo? Forse risolverlo è una parola grossa. Sono riuscito, se non ho sbagliato, a trovare una maniera per passare dal valore finale di K ai possibili valori iniziali di N (sono molteplici) che lo generano. Tuttavia non riesco ad esprimere questi valori in una forma chiusa che consenta il passaggio inverso da N a K. Diciamo che è ancora vantaggioso eseguire banalmente l'algoritmo proposto o, al più, migliorarne la velocità di esecuzione. Ho allora cercato un'approssimazione accettabile e credo di averla in parte trovata.
Ma andiamo con ordine.
L'abitudine, che mi porto appiccicata da quando all'Università si programmava con le schede perforate e gli addetti al cervellone (era davvero grosso) ti guardavano con commiserazione se, dopo la trafila precompilatore – compilatore, nell'esecuzione mandavi in loop la macchina; è quella di verificare immediatamente se un algoritmo è davvero tale: se termina sempre in un numero finito di passaggi.
Guardando il diagramma mi son detto: perché non aggiungere un minore all'uguale del controllo di uscita? E se lo zero per qualche valore di N venisse saltato, passando direttamente da un valore positivo di n ad uno negativo?
[Ah! Sono abituato a usare lettere minuscole per le variabili e maiuscole per valori particolari di queste. Diciamo che la variabile n ha un valore iniziale N e uno finale 0, k vale invece 1 all'inizio e K alla fine dell'iterazione. Non è indispensabile, ma mi pare renda più chiara la comunicazione.]
La risposta all'ultima domanda è sicuramente no! Qualunque sia N, n arriverà sempre al valore 0.
Infatti durante tutta l'esecuzione n assume sempre valori che sono multipli di k, perché, solo quando k+1 è un divisore di n, k viene incrementato per diventare k+1. Il quel momento n è un multiplo del nuovo valore di k e lo resterà fino a quando, a suon di sottrazioni di k, che lasciano immutata la proprietà di esserne multiplo, non si arriva all'incremento successivo.
I valori di n in cui avviene l'incremento di k sono pertanto multipli tanto di k quanto di k+1 e siccome k e k+1 differiscono di 1 il loro mcm è semplicemente il loro prodotto.
Per oggi mi fermo qui sperando che qualcuno voglia partecipare alla discussione.

Non spingete! C'è posto per tutti.
Sperando di suscitare un qualche interesse per questo problema veramente originale, inserisco un confronto fra grafici che dovrebbe stupire, spero.
La relazione che lega K e N è del tipo uno-molti. Ad un valore di K corrisponde un intervallo di valori di N che lo generano. Nella figura sono riportati il grafico di quanti N generano il medesimo K, al variare di quest'ultima da 1 a 1000; comparato con quello generato da una parabola moltiplicata per funzione random con distribuzione gaussiana $\frac{k^2} {14} \cdot sqrt {-ln {(random(1))}$. Ad uno dei due e stato poi cambiato il segno per poterli confrontare. Qual è il grafico casuale? Scusate la qualità ma ho dovuto ridurne le dimensioni, perché non veniva accettato.