Funzione progressiva

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Diego
Livello 2
Livello 2
Messaggi: 31
Iscritto il: sab mar 29, 2014 10:43 am

Funzione progressiva

Messaggio da Diego » sab ott 11, 2014 2:05 pm

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

considerate il seguente diagramma di flusso
Flusso.JPG
Flusso.JPG (21.86 KiB) Visto 1388 volte
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

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 984
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Funzione progressiva

Messaggio da Gianfranco » sab ott 11, 2014 4:36 pm

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.
Pace e bene a tutti.
Gianfranco

Info
Livello 5
Livello 5
Messaggi: 323
Iscritto il: lun nov 21, 2005 1:11 pm
Contatta:

Re: Funzione progressiva

Messaggio da Info » sab ott 11, 2014 5:56 pm

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
Fai sorridere il tuo HD diventando opensource oriented, scopri come

Diego
Livello 2
Livello 2
Messaggi: 31
Iscritto il: sab mar 29, 2014 10:43 am

Re: Funzione progressiva

Messaggio da Diego » sab ott 11, 2014 8:45 pm

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

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 984
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Funzione progressiva

Messaggio da Gianfranco » lun ott 13, 2014 11:14 pm

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.
Pace e bene a tutti.
Gianfranco

Diego
Livello 2
Livello 2
Messaggi: 31
Iscritto il: sab mar 29, 2014 10:43 am

Re: Funzione progressiva

Messaggio da Diego » mar ott 14, 2014 5:39 pm

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

gnugnu
Livello 4
Livello 4
Messaggi: 121
Iscritto il: dom set 07, 2014 1:00 pm

Re: Funzione progressiva

Messaggio da gnugnu » gio ott 16, 2014 10:38 pm

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.

gnugnu
Livello 4
Livello 4
Messaggi: 121
Iscritto il: dom set 07, 2014 1:00 pm

Re: Funzione progressiva

Messaggio da gnugnu » dom ott 19, 2014 9:17 pm

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?
Grafico 2D 1-1.jpg
Grafico 2D 1-1.jpg (87.7 KiB) Visto 1309 volte
Scusate la qualità ma ho dovuto ridurne le dimensioni, perché non veniva accettato.

Rispondi