Buonasera,
vorrei chiedervi un suggerimento per risolvere manualmente il quesito 10 della gara scolastica di dicembre 2023 in tempi ragionevoli
Una strategia utile nel risolvere problemi è trovare degli invarianti, cioè delle quantità che restano sempre costanti anche se le altre variabili cambiano.
In particolare per analizzare i cicli è utile considerare i cosiddetti invarianti di ciclo, quantità che sono costanti all’inizio di ogni iterazione del ciclo.
Analizzando la funzione data, possiamo osservare come a+b+k sia un invariante, infatti a seconda del ramo dell’if eseguito possono succedere due cose:
- (a,b,k) \mapsto (2a, b - a - 1, k + 1) e allora a+b+k \mapsto 2a + (b - a - 1) + (k + 1) = a+b+k
- (a,b,k) \mapsto (a-1,b,k+1) e allora a+b+k \mapsto (a-1)+b+(k+1)=a+b+k.
Chiamiamo da qui in poi a' e b' i valori originali di a e b.
Mostriamo ora come all’uscita dal ciclo vale a=b=0.
All’interno del ciclo possono verificarsi due casi:
- a > 0, allora qualunque ramo dell’if preserva la positività di a
- a = 0, allora siccome siamo ancora nel ciclo b > 0 e a \times a < b, dunque viene eseguito il primo ramo dell’if e a resta 0.
Pertanto a non può mai diventare negativo.
Facciamo un ragionamento simile per b, infatti qualora esso venga modificato abbiamo a^2 < b e dunque b - a - 1 \ge b - a^2 - 1 > b - b - 1 = -1, cioè b > -1 e b resta positivo.
Siccome il dato che il programma termina è implicito nel fatto che la domanda sia stata posta, in gara si può tralasciare la seguente verifica:
- Dopo a'+b' iterazioni abbiamo k=a'+b' e per invarianza di a+b+k=a'+b' troviamo a+b=0. Siccome abbiamo mostrato che a,b \ge 0 deve essere a=b=0 e quindi il programma esce dal ciclo.
All’uscita dal ciclo abbiamo a, b\le 0 per la condizione del ciclo e a,b\ge0 per quanto già dimostrato. Dunque a=b=0. Siccome k+a+b = a'+b' è invariante resta che k=a'+b'.
La funzione non fa altro che la somma dei numeri in input.
3 Mi Piace
Ti ringrazio per la spiegazione del quesito