Come dimostrare che questo ciclo while calcola n ^ 2

Il ciclo calcola 1 + 3 + 5 + 7 + ... + (2n-1). Il modo più semplice per visualizzare che questo somme a n ^ 2 è

Utilizzando la formula della progressione aritmetica possiamo ricavarla direttamente:

numero di elementi è n , il primo elemento è 1 ultimo elemento è 2*n-1

n*(1 + 2*n-1)/2 = n*(2*n) /2 = n*n

Le risposte esistenti hanno perso un punto importante: l'OP ha già dimostrato alcune cose, e la domanda dell'esame di pratica gli ha chiesto di provare queste cose prima. Presumibilmente, questo è dovuto al fatto che le cose che ha già dimostrato sono destinate a essere utili trampolini di lancio verso la conclusione della dimostrazione.

Vogliamo dimostrare che il programma emette n ^ 2. Poiché non ci sono istruzioni di output, presumibilmente una delle variabili è l'output, e non è i , quindi deve essere s .

Abbiamo già s = i ^ 2, quindi siamo davvero molto vicini; non sarebbe bello se io = n alla fine del ciclo? Risulta, i = n è vero alla fine del ciclo. E abbiamo finito.

Quando provi le cose, è molto spesso utile guardare ad altre cose che abbiamo già dimostrato e che stiamo cercando di dimostrare. Le somiglianze tra ciò che abbiamo e ciò che vogliamo può essere indicativo di cose da provare.

Potresti anche provarlo con un metodo chiamato "induzione matematica", che funziona per interi positivi.

Per dirla semplicemente: si presuppone che l'istruzione relativa al ciclo sia vera per una "n" arbitraria e quindi è anche vera per "n + 1" e quindi per ogni intero più grande del bordo inferiore (che normalmente è 1 , ma nel tuo caso, 0 funziona pure.

È un approccio più matematico e quindi potrebbe piacerti o lo odi. Ma eccoci:

Senonhaifamiliaritàconl'operatoresigmainmatematica,questoèilmodoincuifunziona.Èsemplicementeunciclo"per", con "a" come valore iniziale e "b" come limite superiore incluso. Aumenta di un 'ogni' iterazione 'di uno e somma i valori insieme.

Quindi matematicamente, il tuo problema potrebbe essere scritto in questo modo:

Ora,perchél'induzionematematicafunzioni,dobbiamoprimadimostrarechequestaaffermazioneèveraperilvalorepiùbassodi"n" (normalmente sarebbe 1, ma anche 0 funziona qui):

Chesicuramenteèvero.

E anche questo è vero.

Bene, passiamo alla parte "eccitante" ... Provando questa affermazione per qualsiasi (intero positivo) 'n' sostituendo 'n' con 'n + 1':

Ora,sembraabbastanzacomplicato,maanalizziamolopassodopopasso.Laprimaparteèesattamentelastessadellasecondaimmagine,maoraogni'n'èsostituitada'n+1'.Lasecondaparte(dopoil'->'einparticolareillatosinistrodell'equazione)potrebbenonessereevidenteaprimavista.Madalpuntodivistadeiprogrammatoripotrebbeessereunpo'piùfaciledacapire,perché

for(inti=0;i<=n;i++){...Dosthhere.}

èesattamenteugualea

for(inti=0;i<=l;i++){...Dosthhere(part1)}for(inti=l+1;i<=n;i++){...Dosthhere(part2)}

Sullatodestrodell'equazionehosemplicementeesteso'(n+1)^2'a'n^2+2n+1'.Oral'ultimoscatto:

Poiché per il nostro secondo 'ciclo' (= operatore sigma) il valore superiore è uguale al valore più basso, non ne abbiamo affatto bisogno. C'è una sola iterazione con questo particolare valore, quindi possiamo semplicemente sostituire 'k' con 'n + 1', che poi ci dà '2 * (n + 1) - 1'. Quindi abbiamo ancora la stessa sigma rimasta, che avevamo all'inizio e volevamo dimostrare di essere "n" al quadrato. Quindi, per eliminarlo, possiamo semplicemente sostituirlo con 'n ^ 2' nella seconda parte (dopo '- >'), perché se la nostra ipotesi è vera, non c'è differenza tra loro. Ora abbiamo 'n ^ 2' su entrambi i lati, quindi possiamo semplicemente sottrarlo per sbarazzarci di esso.

Quindi, ora che abbiamo lasciato, possiamo semplicemente moltiplicare e alla fine ottenere un'equazione, che è anche vera. Pertanto abbiamo dimostrato che un loop che somma tutti i numeri dispari (a partire da 1 fino a '2n - 1') è uguale a 'n ^ 2'.