[Vincenzo1968]

Originariamente inviato da banryu79

...
Altra cosa... La sintassi dello pseudocodice è a scelta dell'utente che propone il contest (e in caso gli altri partecipanti ne vogliano fare uso devono cercare di aderire alle convenzioni usate dal proponente del contest) oppure si fa tutti riferimento sempre e comunque ad uno "standard" noto? (ad esempio lo pseudocodice usato nel testo "Introduzione agli algoritmi e strutture dati" di Cormen, Leiserson, Rivest e Stein)

Mi pare una buona idea. Riporto le convenzioni di codifica elencate nel libro citato:

Convenzioni di pseudocodifica
Adotteremo le seguenti convenzioni nelle nostre pseudocodifiche.
1. L’indentazione (rientro verso destra delle righe) serve a indicare la struttura a blocchi dello pseudocodice. Per esempio, il corpo del ciclo for, che inizia nella riga 1, `e formato dalla righe 2–8 e il corpo del ciclo while, che inizia nella riga 5, contiene le righe 6–7, ma non la riga 8. Il nostro stile di indentazione si applica anche alle istruzioni if-then-else. Utilizzando l’indentazione, anziché gli indicatori convenzionali della struttura a blocchi, come le istruzioni begin e end, si riduce molto la confusione, preservando o perfino migliorando la chiarezza(nei linguaggi di programmazione reali, in generale, non è consigliabile utilizzare soltanto l’indentazione per indicare la struttura a blocchi, in quanto i livelli di indentazione sono difficili da determinare quando il codice è distribuito su più pagine).

2. I costrutti iterativi while, for e repeat e i costrutti condizionali if, then ed else hanno interpretazioni simili a quelle del Pascal. C'è tuttavia una piccola differenza nei cicli for: nel Pascal il valore del contatore del ciclo è indefinito dopo la conclusione del ciclo, mentre in questo libro il contatore del ciclo mantiene il suo valore dopo la fine del ciclo. Quindi, immediatamente dopo un ciclo for, il valore del contatore del ciclo è quello che ha appena superato il limite del ciclo for. Abbiamo utilizzato questa proprietà nella nostra analisi della correttezza di insertion sort. La prima istruzione del ciclo for (riga 1) è for j ← 2 to lunghezza[A]; quindi, alla fine di questo ciclo, j = lunghezza[A] + 1 (che equivale a j = n +1, in quanto n = lunghezza[A]).

3. Il simbolo “//” indica che il resto della riga è un commento.

4. Un’assegnazione multipla della forma i ← j ← e assegna a entrambe le variabili i e j il valore dell’espressione e; deve essere considerata equivalente all’assegnazione j ← e seguita dall’assegnazione i ← j.

5. Le variabili (come i, j e chiave) sono locali a una determinata procedura. Non dovremmo utilizzare variabili globali senza un’esplicita indicazione.

6. Per identificare un elemento di un array, specifichiamo il nome dell’array seguito dall’indice dell’elemento fra parentesi quadre. Per esempio, A[i] indica l’elemento i-esimo dell’array A. La notazione “. .” `e utilizzata per indicare un intervallo di valori all’interno di un array. Quindi, A[1 . . j] indica il sottoarray di A che `e composto da j elementi: A[1],A[2], . . . ,A[j].

7. I dati composti sono tipicamente organizzati in oggetti, che sono formati da attributi o campi. Un particolare campo è identificato utilizzando il nome del campo seguito dal nome del suo oggetto fra parentesi quadre. Per esempio, noi trattiamo un array come un oggetto con l’attributo lunghezza che indica il numero di elementi contenuti nell’array. Per specificare il numero di elementi di un array A, scriviamo lunghezza[A]. Anche se utilizziamo le parentesi quadre sia per gli indici degli array sia per gli attributi degli oggetti, di solito, è chiaro dal contesto a cosa intendiamo riferirci.
Una variabile che rappresenta un array o un oggetto è trattata come un puntatore ai dati che costituiscono l’array o l’oggetto. Per tutti i campi f di un oggetto x, l’assegnazione y ← x implica che f[y] = f[x]. Inoltre, se poi impostiamo f[x] ← 3, allora non soltanto sarà f[x] = 3, ma anche f[y] = 3. In altre parole, x e y puntano allo stesso oggetto dopo l’assegnazione y ← x.
Un puntatore può non fare riferimento ad alcun oggetto; in questo caso daremo ad esso il valore speciale NIL.

8. I parametri vengono passati a una procedura per valore: la procedura chiamata riceve la sua copia dei parametri e, se viene assegnato un valore a un parametro, la modifica non viene vista dalla procedura chiamante. Quando viene passato un oggetto, viene copiato il puntatore ai dati che costituiscono l’oggetto, ma non vengono copiati i campi dell’oggetto. Per esempio, se x è un parametro di una procedura chiamata, l’assegnazione x ← y all’interno della procedura chiamata non è visibile alla procedura chiamante. L’assegnazione f[x] ← 3, invece, è visibile.

9. Gli operatori booleani “and” e “or” sono operatori cortocircuitati.
Questo significa che, quando valutiamo l’espressione “x and y”, prima dobbiamo valutare x. Se x è FALSE, allora l’intera espressione non può essere TRUE, quindi non occorre valutare y. Se, invece, x è TRUE, dobbiamo valutare y per determinare il valore dell’intera espressione. Analogamente, se abbiamo l’espressione “x or y”, valutiamo y soltanto se x è FALSE. Gli operatori di cortocircuito ci consentono di scrivere espressioni booleane come “x <> NIL and f[x] = y” senza preoccuparci di ciò che accade quando tentiamo di valutare f[x]quando x è NIL.

Esempio:

INSERTION-SORT(A)
1 for j ← 2 to lunghezza[A]
2   do chiave ← A[j]
3     // Inserisce A[j] nella sequenza ordinata A[1 . . j − 1].
4     i ← j − 1
5     while i > 0 and A[i] > chiave
6       do A[i + 1] ← A[i]
7         i ← i − 1
8     A[i + 1] ← chiave