Newsgroup: it.comp.lang.pascal
Titolo: aiutone per esame di domani !!!

vi sarei molto grato se rispondeste a questa domanda d'esame
che dovrei discutere domani all'orale :
Calcolare la complessità computazionale del seguente frammento di codice,
considerando n parametro di input.
...
a:=n;
while a>0 do
 begin
  b:=0;
  while b >= a do
   begin
    b := b + 1
   end;
  a := a + 1
 end;
 ...
spero che possiate rispondere al + presto, altrimenti domani
non so cosa rispondere al professore :(
grazie mille
claudio


Suppongo che il codice contenga errori di trascrizione... scritto cosi' non
ha nessun significato, in pratica se n e' positivo, a viene incrementato
indefinitamente senza mai arrivare alla fine del ciclo while (almeno, non in
modo "naturale", ma con un wrap-around). Se n e' negativo, il codice non
viene mai eseguito.
Se il codice e' scritto ESATTAMENTE in questo modo e' sbagliato, e la
complessita' non dipende da n (a causa del wrap-around di a e di b, di cui
non conosciamo le dimensioni). Se ci sono errori di trascrizione, controlla
ed eventualmente manda un altro messaggio con il codice giusto.

  ...
Sicuro del codice?
Forse era un "a := a - 1" ?

 Forse era un "a := a - 1" ?
Mi autorispondo... ho scritto al volo ma ripensandoci,
anche con quel decremento il codice non ha comunque
troppo senso... :)

Vedo di analizzare in diretta il tuo codice, così se compio eventuali errori
mi puoi correggere...
...
a:=n;    {assegno ad una variabile a il valore di n, valore deciso
              dall'utente}
while a>0 do {qui poi poni come condizione del ciclo che a sia
                     positivo... e fin qua niente di difficile =))}
 begin
  b:=0;           {ora assegni ad una variabile b il valore 0}
  while b >= a do {e qui cominciano le ambiguità...è logico che b non
                            sarà mai maggiore di a,   perchè a deve essere
                            maggiore di 0 mentre b è uguale a 0... ora non
ci
                            vuole molto a capire che in questo ciclo non si
                            entreràmai...}
   begin
    b := b + 1
   end;
  a := a + 1    {e qui mi incrementi nuovamente a... perciò questo ciclo
                      sarà necessariamente infinito... a meno che tu non
                      aspetti che a raggiunga valore 32768, m non penso che
                      questo sia il tuo scopo...}
 end;
 ...
credo e spero di essere stato chiaro... fammi sapere se ho sbagliato io ad
interpretare le poche righe di codice che hai postato

...

scusami tanto, ma la paura dell'esame mi ha annebbiato la vista :)
questo è il codice che sta scritto sul testo d'esame e che ho
controllato varie volte :
---------------------------------------
...
a:=n;
while a>0 do
 begin
  b:=0;
  while b <= a do
   begin
    b := b + 1
   end;
  a := a - 1
 end;
 ...
 
---------------------------------------

  end;
poco formalmente... il while su a viene eseguito da n a 1 cioe` n volte.
Per ogni iterazione esegui il while interno da 0 ad a, quindi a+1 volte.
quindi
  sommatoria per  i  che va` da  1  a  n  di  ( i+1 )
tiri fuori il +1 e ottieni
  n + sommatoria per  i  da  1  a  n  di  ( i )
la sommatoria che ti rimane e' notevole e ti da'  n*(n+1) / 2  quindi
  n + n * (n+1) / 2
cioe'
  n + (n * n) / 2 + n / 2
arrotondando e approssimando sull'operaz. piu' costosa
 (n^2) / 2
...questo se a) mi ricordo ancora come si fa' e b) il tuo prof non ha
spiegato strane cose...
-- 
Dreadnaut
(Life would be easier if I had the source code)

  (n^2) / 2
direi che ormai e' troppo tardi, comunque aggiungo i miei 2 centesimi (di
Euro):
in linea generale la spiegazione e' esatta, ma secondo me non ha senso la
divisione per 2, quindi la complessita' dell'algoritmo e' O(n^2).

 e' O(n^2).
mmh hai ragione... cmq dipende dal livello di pignoleria del prof:
a volte e' utile tenere l'ultimo fattore moltiplicativo, per poter
confrontare due algoritmi simile e.g.  (n^2)/2 e (n^2)/6


grazie a tutti ,
cmq alla fine ho preso un bel 30/30 !!!
bastava dire che la complessità era O(n^2).
ciao
claudio

 cmq alla fine ho preso un bel 30/30 !!!
Fanculo! :-)
(amichevole)
-- 
     __         ____         | We don't need no education.
 __ / /__  ___ / __/__ __ __ | We don't need no thought control.
/ // / _ \/ -_) _// _ \\ \ / | All we need is another brick in the wall
\___/\___/\__/_/  \___/_\_\  | ICQ UIN: 61571298

 bastava dire che la complessità era O(n^2).
Avevo ragione io! :-) :-)