[Java] Costruzione funzione per terminazione

[raffa071292]

Salve ragazzi, qualcuno potrebbe aiutarmi a capire questo esercizio? Ho provato a dare una soluzione, ma non mi sembra proprio adatta a quello che richiede l'esercizio.

Sia dato il metodo:

     public static int f(int n) {
        int i = 0;
        int r = 0;
        while (i < n) {     //(*)
           r = 3 + r;
           i++;
        }
        return r;
     }

* (1) Scrivere la funzione $N(i,n)$ che può essere usata come misura per la dimostrazione della terminazione.
* (2) Dimostrare che la $N(i,n)$ fornita decresce strettamente ad ogni iterazione del ciclo (*).
* (3) Dimostrare che il ciclo termina.

MODIFICATO
Ciao ragazzi, mi sono reso conto che ho sbagliato tutta l'impostazione della funzione perchè per come l'ho costruita funzionerebbe solo per $n=3$. Ci ho pensato un attimo ed ho trovato un altra possibile soluzione però sono sempre incerto. Spero che ci sia qualcuno che mi possa aiutare. (Ho inserito nello spoiler la soluzione sbagliata che avevo dato prima, non si sa mai, magari si riesce a prendere spunto da lì).

La mia seconda possibile soluzione è:

Punto(1) $N(i,n)={(N(i+1,n),if i
Punto(2) $N(0,n) < N(i+1,n)$ (si può affermare che è decrescente? Come lo dimostro?)

Punto(3) Per dimostrare che il ciclo termina, cerco l'invariante del ciclo.
Una possibile invariante è $r=3n$. Lo dimostro per induzione:
- Passo base: $n=0 => r = 3*0 = 0$
- Hp induttiva: $r=3n$
- Tesi: $r = 3(n+1)$

Indico con $r'$ il valore che assumerà $r$ dopo tot iterazioni del ciclo e quindi $r' = 3 + r$
- Dimostro la tesi:
$r' = 3 + r$
$ = 3 + 3n$
$ = 3(n+1)$

può essere una corretta soluzione?

ERRATO
Prima di tutto ho provato ad assegnare alla $n$ che si trova nel parametro del metodo un numero generico per vedere come si comporta il metodo quindi ho notato che per $n=3$, la $i$ assume i valori: $0, 1, 2, 3$ mentre la $r$ assume i valori $0, 3, 6, 9$ quindi ho pensato che la nostra funzione potrebbe essere costruita come $N(i,n) = i * n$ quindi scrivo

$\{(N(0,n)=0),(N(i,n+1)=N(i,n)+ i):}$

E lo dimostro per induzione così:
Passo base: $N(0,n) = 0 * n = 0$
Passo induttivo:
- ipotesi: $N(i,n) = i*n$
- tesi: $N(i,n+1) = i*(n+1) = i*n + i = N(i,n) + i$
ed effettuando delle verifiche risulta sempre corretto.

Una volta però scritto tutto questo mi è venuto un dubbio: come faccio a dimostrare che DECRESCE? quindi ho capito di aver sbagliato a scrivere la dimostrazione della terminazione. Come posso risolvere questo problema?

[agnenga1]

Intanto non ho capito la definizione che hai dato nella soluzione corretta: definisci una funzione "ricorsivamente" 1) senza presentare il caso base e 2) definendo il valore della funzione per un assegnato valore del parametro ($i$) in termini di quello relativo al valore successivo ($i+1$)? Questo non mi sembra corretto.

Invece potresti definire la funzione così

Punto(1) $N(i,n)={(n,if i=0),(N(i-1,n)-1,text{altrimenti}):}$

Punto(2) è immediato dimostrare (relativamente a $i$) che la funzione decresce strettamente; quando raggiunge lo zero si ha terminazione del ciclo.