Esame Programmazione 1 (Corso di Laurea in Informatica, primo anno) ARGOMENTO Uso del ciclo "while", precondizioni, postcondizioni. DOMANDA while n.1: fattoriale di A2. Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X1:=1; while (X2>0) begin X1:=X1*X2; X2:=X2-1; end; X4:=X1; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=A2!} RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1*A2}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=A1!} DOMANDA while n.1 bis: fattoriale di A2. Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X1:=1; while (X2>0) begin X1:=X1/X2; X2:=X2-1; end; X4:=X1; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=1/A2!} RISPOSTA -1 {X4=A1^(-A2)}. RISPOSTA -1 {X4=A2^(-A1)}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1/A2}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=1/A1!} DOMANDA while n.2: somma A1+(A1-1)+...+2+1. Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X2:=0; while (X1>0) begin X2:=X2+X1; X1:=X1-1; end; X4:=X2; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1*A2}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} DOMANDA while 3 somma A2+1+...+1 (A1 volte) Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X4:=0; while (X1>0) begin X2:=X2+1; X1:=X1-1; end; X4:=X2; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=A1+A2}. RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1*A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} DOMANDA while 3 bis differenza A2-1-...-1 (A1 volte) Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X4:=0; while (X1>0) begin X2:=X2-1; X1:=X1-1; end; X4:=X2; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=A2-A1}. RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi, cambiata di segno}. RISPOSTA -1 {X4=A1-A2}. RISPOSTA -1 {X4=A1*A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} DOMANDA while 4 A2+...+A2 (A1 volte) Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X3:=0; while (X1>0) begin X3:=X3+X2; X1:=X1-1; end; X4:=X3; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=A1*A2}. RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} DOMANDA while 5 A2*...* A2 (A1 volte) Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X3:=1; while (X1>0) begin X3:=X3*X2; X1:=X1-1; end; X4:=X3; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=A2^A1}. RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1*A2}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} DOMANDA while 5 1/(A2*...* A2) (A1 volte) Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X3:=1; while (X1>0) begin X3:=X3/X2; X1:=X1-1; end; X4:=X3; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=A2^(-A1)}. RISPOSTA -1 {X4=A1^(-A2)}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=A1/A2}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} DOMANDA while 6 logaritmo di A2 Supponiamo che le seguenti istruzioni abbiano Precondizione {X1=A1>0 e X2=A2>0} (con A1,A2 parametri). X1:=0; while (X2>=2) begin X2:=X2/2; X1:=X1+1; end; X4:=X1; Quale PostCondizione (=descrizione dei valori in uscita) considereresti corretta di conseguenza? RISPOSTA +2 {X4=log_2(A2) (parte intera)}. RISPOSTA -1 {X4=A1^A2}. RISPOSTA -1 {X4=A2^A1}. RISPOSTA -1 {X4=log_2(A1) (parte intera)}. RISPOSTA -1 {X4=La somma dei primi A1 interi}. RISPOSTA -1 {X4=La somma dei primi A2 interi}. RISPOSTA -1 {X4=A1*A2}. RISPOSTA -1 {X4=A1+A2}. RISPOSTA -1 {X4=A1!} RISPOSTA -1 {X4=A2!} ARGOMENTO Primi programmi con vettori e matrici. DOMANDA 1 Traslazione di un segmento di vettore a destra - errata Sia V un vettore di indici [0 .. N1N2], i cui valori sono gia' stati assegnati. Consideriamo il seguente ciclo "for": for i:=N1 to N1*N2 do V[i+N1]:=V[i]; Che effetto ha tale ciclo sugli elementi di V nel segmento [N1,N1*N2]? RISPOSTA +2 Ricopia molte volte (piu' di una) i primi N1 elementi di tale segmento. RISPOSTA -1 Trasla tutti tali elementi di N1 passi verso destra. RISPOSTA -1 Trasla tutti tali elementi di N1 passi verso sinistra. RISPOSTA -1 Ricopia molte volte (piu' di una) gli ultimi N1 elementi di tale segmento. RISPOSTA -1 Li lascia come prima. RISPOSTA -1 Li cancella tutti, sostituendoli con altri. RISPOSTA -1 Li rende tutti uguali tra loro. RISPOSTA -2 Li rende tutti indefiniti. RISPOSTA -2 Li rende tutti nulli. RISPOSTA -2 Produce un messaggio di errore. DOMANDA 2 Traslazione di un segmento di vettore a sinistra - corretta Sia V un vettore di indici [0 .. N1N2], i cui valori sono gia' stati assegnati. Consideriamo il seguente ciclo "for": for i:=N1 to N1*N2 do V[i-N1]:=V[i]; Che effetto ha tale ciclo sugli elementi di V nel segmento [N1,N1*N2]? RISPOSTA +2 Trasla tutti tali elementi di N1 passi verso sinistra. RISPOSTA -1 Trasla tutti tali elementi di N1 passi verso destra. RISPOSTA -1 Ricopia molte volte (piu' di una) i primi N1 elementi di tale segmento. RISPOSTA -1 Ricopia molte volte (piu' di una) gli ultimi N1 elementi di tale segmento. RISPOSTA -1 Li lascia come prima. RISPOSTA -1 Li cancella tutti, sostituendoli con altri. RISPOSTA -1 Li rende tutti uguali tra loro. RISPOSTA -2 Li rende tutti indefiniti. RISPOSTA -2 Li rende tutti nulli. RISPOSTA -2 Produce un messaggio di errore. DOMANDA 3 Traslazione di un segmento di vettore a destra - corretta Sia V un vettore di indici [0 .. N1N2], i cui valori sono gia' stati assegnati. Consideriamo il seguente ciclo "for": for i:=N1*N2 downto N1 do V[i+N1]:=V[i]; Che effetto ha tale ciclo sugli elementi di V nel segmento [N1,N1*N2]? RISPOSTA +2 Trasla tutti tali elementi di N1 passi verso destra. RISPOSTA -1 Ricopia molte volte (piu' di una) i primi N1 elementi di tale segmento. RISPOSTA -1 Trasla tutti tali elementi di N1 passi verso sinistra. RISPOSTA -1 Ricopia molte volte (piu' di una) gli ultimi N1 elementi di tale segmento. RISPOSTA -1 Li lascia come prima. RISPOSTA -1 Li cancella tutti, sostituendoli con altri. RISPOSTA -1 Li rende tutti uguali tra loro. RISPOSTA -2 Li rende tutti indefiniti. RISPOSTA -2 Li rende tutti nulli. RISPOSTA -2 Produce un messaggio di errore. DOMANDA 4 Traslazione di un segmento di vettore a sinistra - errata Sia V un vettore di indici [0 .. N1N2], i cui valori sono gia' stati assegnati. Consideriamo il seguente ciclo "for": for i:=N1*N2 downto N1 do V[i-N1]:=V[i]; Che effetto ha tale ciclo sugli elementi di V nel segmento [N1,N1*N2]? RISPOSTA +2 Ricopia molte volte (piu' di una) gli ultimi N1 elementi di tale segmento. RISPOSTA -1 Trasla tutti tali elementi di N1 passi verso destra. RISPOSTA -1 Ricopia molte volte (piu' di una) i primi N1 elementi di tale segmento. RISPOSTA -1 Trasla tutti tali elementi di N1 passi verso sinistra. RISPOSTA -1 Li lascia come prima. RISPOSTA -1 Li cancella tutti, sostituendoli con altri. RISPOSTA -1 Li rende tutti uguali tra loro. RISPOSTA -2 Li rende tutti indefiniti. RISPOSTA -2 Li rende tutti nulli. RISPOSTA -2 Produce un messaggio di errore. DOMANDA 5 Traslazione di un segmento di vettore a destra - valori originari Sia V un vettore di indici [0 .. N1N2], i cui valori sono gia' stati assegnati. Consideriamo il seguente ciclo "for": for i:=N1*N2 downto N1 do V[i+N1]:=V[i]; Che effetto ha tale ciclo sui contenuti originari di V[N1], ..., V[2*N1-1]? RISPOSTA +2 Li lascia come prima. RISPOSTA -1 Li cancella tutti, sostituendoli con N1 elementi alla loro destra. RISPOSTA -1 Li cancella tutti, sostituendoli con N1 elementi alla loro sinistra. RISPOSTA -1 Li rende tutti uguali tra loro. RISPOSTA -2 Li rende tutti indefiniti. RISPOSTA -2 Li rende tutti nulli. RISPOSTA -2 Produce un messaggio di errore. DOMANDA 6 Traslazione di un segmento di vettore a sinistra - valori originari Sia V un vettore di indici [0 .. N1N2], i cui valori sono gia' stati assegnati. Consideriamo il seguente ciclo "for": for i:=N1 to N1*N2 do V[i-N1]:=V[i]; Che effetto ha tale ciclo sui contenuti originari di V[0], ..., V[N1-1]? RISPOSTA +2 Li cancella tutti, sostituendoli con N1 elementi alla loro destra. RISPOSTA -1 Li lascia come prima. RISPOSTA -2 Li cancella tutti, sostituendoli con N1 elementi alla loro sinistra. RISPOSTA -1 Li rende tutti uguali tra loro. RISPOSTA -2 Li rende tutti indefiniti. RISPOSTA -2 Li rende tutti nulli. RISPOSTA -2 Produce un messaggio di errore. DOMANDA 1 (Matrici) scambio alto-basso Sia data una matrice M1 di punti di un'immagine, di dimensione A1xA1. Le righe della matrice hanno indice i e rappresentano le righe dell'immagine (i=1 e' la riga piu' in alto, i=A1 quella piu' in basso). Le colonne della matrice hanno indice j e rappresentano le colonne dell'immagine (j=1 quella piu' a sinistra, j=A1 quella piu' a destra). Che effetto hanno su M1 le seguenti righe di codice? for i:= 1 to (A1 div 2) for j:= 1 to A1 begin temp:=M1[i,j]; M1[i,j]:=M1[A1+1-i,j]; M1[A1+1-i,j]:=temp; end; (Si consiglia di sperimentare il programma su una matrice 4x4). RISPOSTA +2 Scambiano l'alto col basso. RISPOSTA -1 Scambiano la sinistra con la destra. RISPOSTA -1 Invertono l'immagine lungo la diagonale principale. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte sinistra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in alto di M1. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte destra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in basso di M1. RISPOSTA -1 Non modificano affatto M1. RISPOSTA -2 Spostano i punti di M1 in modo del tutto casuale e caotico RISPOSTA -2 Rendono indefinito ogni punto di M1 DOMANDA 2 (Matrici) scambio alto-basso errato Sia data una matrice M1 di punti di un'immagine, di dimensione A1xA1. Le righe della matrice hanno indice i e rappresentano le righe dell'immagine (i=1 e' la riga piu' in alto, i=A1 quella piu' in basso). Le colonne della matrice hanno indice j e rappresentano le colonne dell'immagine (j=1 quella piu' a sinistra, j=A1 quella piu' a destra). Che effetto hanno su M1 le seguenti righe di codice? for i:= 1 to (A1 div 2) for j:= 1 to (A1 div 2) begin temp:=M1[i,j]; M1[i,j]:=M1[A1+1-i,j]; M1[A1+1-i,j]:=temp; end; (Si consiglia di sperimentare il programma su una matrice 4x4). RISPOSTA +2 Scambiano l'alto con il basso, ma solo nella parte sinistra di M1. RISPOSTA -1 Scambiano l'alto col basso. RISPOSTA -1 Scambiano la sinistra con la destra. RISPOSTA -1 Invertono l'immagine lungo la diagonale principale. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in alto di M1. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte destra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in basso di M1. RISPOSTA -1 Non modificano affatto M1. RISPOSTA -2 Spostano i punti di M1 in modo del tutto casuale e caotico RISPOSTA -2 Rendono indefinito ogni punto di M1 DOMANDA 3 (Matrici) scambio sinistra-destra Sia data una matrice M1 di punti di un'immagine, di dimensione A1xA1. Le righe della matrice hanno indice i e rappresentano le righe dell'immagine (i=1 e' la riga piu' in alto, i=A1 quella piu' in basso). Le colonne della matrice hanno indice j e rappresentano le colonne dell'immagine (j=1 quella piu' a sinistra, j=A1 quella piu' a destra). Che effetto hanno su M1 le seguenti righe di codice? for i:= 1 to A1 for j:= 1 to (A1 div 2) begin temp:=M1[i,j]; M1[i,j]:=M1[i,A1+1-j]; M1[i,A1+1-j]:=temp; end; (Si consiglia di sperimentare il programma su una matrice 4x4). RISPOSTA +2 Scambiano la sinistra con la destra. RISPOSTA -1 Scambiano l'alto col basso. RISPOSTA -1 Invertono l'immagine lungo la diagonale principale. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte sinistra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in alto di M1. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte destra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in basso di M1. RISPOSTA -1 Non modificano affatto M1. RISPOSTA -2 Spostano i punti di M1 in modo del tutto casuale e caotico RISPOSTA -2 Rendono indefinito ogni punto di M1 DOMANDA 4 (Matrici) scambio sinistra-destra errato Sia data una matrice M1 di punti di un'immagine, di dimensione A1xA1. Le righe della matrice hanno indice i e rappresentano le righe dell'immagine (i=1 e' la riga piu' in alto, i=A1 quella piu' in basso). Le colonne della matrice hanno indice j e rappresentano le colonne dell'immagine (j=1 quella piu' a sinistra, j=A1 quella piu' a destra). Che effetto hanno su M1 le seguenti righe di codice? for i:= 1 to (A1 div 2) for j:= 1 to (A1 div 2) begin temp:=M1[i,j]; M1[i,j]:=M1[i,A1+1-j]; M1[i,A1+1-j]:=temp; end; (Si consiglia di sperimentare il programma su una matrice 4x4). RISPOSTA +2 Scambiano la sinistra con la destra, ma solo nella parte in alto di M1. RISPOSTA -1 Scambiano l'alto col basso. RISPOSTA -1 Scambiano la sinistra con la destra. RISPOSTA -1 Invertono l'immagine lungo la diagonale principale. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte sinistra di M1. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte destra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in basso di M1. RISPOSTA -1 Non modificano affatto M1. RISPOSTA -2 Spostano i punti di M1 in modo del tutto casuale e caotico RISPOSTA -2 Rendono indefinito ogni punto di M1 DOMANDA 5 (Matrici) rotazione lungo la diagonale Sia data una matrice M1 di punti di un'immagine, di dimensione A1xA1. Le righe della matrice hanno indice i e rappresentano le righe dell'immagine (i=1 e' la riga piu' in alto, i=A1 quella piu' in basso). Le colonne della matrice hanno indice j e rappresentano le colonne dell'immagine (j=1 quella piu' a sinistra, j=A1 quella piu' a destra). Che effetto hanno su M1 le seguenti righe di codice? for i:= 1 to A1 for j:= 1 to (i-1) begin temp:=M1[i,j]; M1[i,j]:=M1[j,i]; M1[j,i]:=temp; end; (Si consiglia di sperimentare il programma su una matrice 4x4). RISPOSTA +2 Invertono l'immagine lungo la diagonale principale. RISPOSTA -1 Scambiano l'alto col basso. RISPOSTA -1 Scambiano la sinistra con la destra. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte sinistra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in alto di M1. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte destra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in basso di M1. RISPOSTA -1 Non modificano affatto M1. RISPOSTA -2 Spostano i punti di M1 in modo del tutto casuale e caotico RISPOSTA -2 Rendono indefinito ogni punto di M1 DOMANDA 6 (Matrici) rotazione lungo la diagonale - errata Sia data una matrice M1 di punti di un'immagine, di dimensione A1xA1. Le righe della matrice hanno indice i e rappresentano le righe dell'immagine (i=1 e' la riga piu' in alto, i=A1 quella piu' in basso). Le colonne della matrice hanno indice j e rappresentano le colonne dell'immagine (j=1 quella piu' a sinistra, j=A1 quella piu' a destra). Che effetto hanno su M1 le seguenti righe di codice? for i:= 1 to A1 for j:= 1 to A1 temp:=M1[i,j]; M1[i,j]:=M1[j,i]; M1[i,j]:=temp; (Si consiglia di sperimentare il programma su una matrice 4x4). RISPOSTA +2 Non modificano affatto M1. RISPOSTA -1 Scambiano l'alto col basso. RISPOSTA -1 Scambiano la sinistra con la destra. RISPOSTA -1 Invertono l'immagine lungo la diagonale principale. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte sinistra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in alto di M1. RISPOSTA -1 Scambiano l'alto con il basso, ma solo nella parte destra di M1. RISPOSTA -1 Scambiano la sinistra con la destra, ma solo nella parte in basso di M1. RISPOSTA -2 Spostano i punti di M1 in modo del tutto casuale e caotico RISPOSTA -2 Rendono indefinito ogni punto di M1 ARGOMENTO Variabili locali e globali DOMANDA 1 program prova; var X1, X2, X3 : Integer; procedure P1(X1: Integer); var X2:Integer; begin writeln(X1,X2,X3); X2:=N2N2; X3:=N3N3; writeln(X1,X2,X3); end; begin X1:=N1; X2:=N2; X3:=N3; P1(X1); writeln(X1,X2,X3); end; Questo programma scrive tre righe. Cosa scrive nella PRIMA riga? RISPOSTA -1 N1 N2 N3 RISPOSTA -1 N1N1 N2N2 N3N3 RISPOSTA -2 Tre valori "indefiniti" RISPOSTA -1 N1 e due valori "indefiniti" RISPOSTA +2 N1, un valore "indefinito", poi N3 RISPOSTA -2 X1 N2N2 N3N3 RISPOSTA -1 N1 N2N2 N3N3 RISPOSTA -1 Un valore "indefinito", poi N2N2, N3N3 RISPOSTA -1 N1 N2 N3N3 RISPOSTA -2 Segnala errore perche' X2 e' stata dichiarata due volte. DOMANDA 2 program prova; var X1, X2, X3 : Integer; procedure P1(X1: Integer); var X2:Integer; begin writeln(X1,X2,X3); X2:=N2N2; X3:=N3N3; writeln(X1,X2,X3); end; begin X1:=N1; X2:=N2; X3:=N3; P1(X1); writeln(X1,X2,X3); end; Questo programma scrive tre righe. Cosa scrive nella SECONDA riga? RISPOSTA -1 N1 N2 N3 RISPOSTA -1 N1N1 N2N2 N3N3 RISPOSTA -2 Tre valori "indefiniti" RISPOSTA -1 N1 e due valori "indefiniti" RISPOSTA -1 N1, un valore "indefinito", poi N3 RISPOSTA -2 X1 N2N2 N3N3 RISPOSTA +2 N1 N2N2 N3N3 RISPOSTA -1 Un valore "indefinito", poi N2N2, N3N3 RISPOSTA -1 N1 N2 N3N3 RISPOSTA -2 Segnala errore perche' X2 e' stata dichiarata due volte. DOMANDA 3 program prova; var X1, X2, X3 : Integer; procedure P1(X1: Integer); var X2:Integer; begin writeln(X1,X2,X3); X2:=N2N2; X3:=N3N3; writeln(X1,X2,X3); X1:=N1N1; end; begin X1:=N1; X2:=N2; X3:=N3; P1(X1); writeln(X1,X2,X3); end; Questo programma scrive tre righe. Cosa scrive nella TERZA riga? RISPOSTA +2 N1 N2 N3N3 RISPOSTA -1 N1 N2 N3 RISPOSTA -1 N1N1 N2N2 N3N3 RISPOSTA -2 Tre valori "indefiniti" RISPOSTA -1 N1, poi due valori "indefiniti" RISPOSTA -1 N1, un valore "indefinito", poi N3 RISPOSTA -2 X1 N2N2 N3N3 RISPOSTA -1 N1 N2N2 N3N3 RISPOSTA -1 Un valore "indefinito", poi N2N2, N3N3 RISPOSTA -2 Segnala errore perche' X2 e' stata dichiarata due volte. SPIEGAZIONE Delle tre assegnazioni che avvengono in P1, due, quelle a X1 e X2, non modificano i valori assegnati dal main, perche' X1 e' un parametro e X2 e' una variabile locale. Ma l'assegnazione a X3 modifica il valore del main, dato che X3 e' globale in P1. Dunque: la terza writeline scrive i valori originari di X1, X2 e il valore modificato di X3, quindi N1, N2, N3N3. DOMANDA 4 program prova; var X1, X2, X3 : Integer; function F1(X3:Integer):Integer; var X2:Integer; begin writeln(X1,X2,X3); X2:=N2N2; X1:=N1N1; writeln(X1,X2,X3); end; begin X1:=N1; X2:=N2; X3:=N3; F1(X3); writeln(X1,X2,X3); end; Questo programma scrive tre righe. Cosa scrive nella PRIMA riga? RISPOSTA -1 N1 N2 N3 RISPOSTA -1 N1N1 N2N2 N3N3 RISPOSTA -2 Tre valori "indefiniti" RISPOSTA -1 N1, poi due valori "indefiniti" RISPOSTA +2 N1, un valore "indefinito", poi N3 RISPOSTA -2 N1N1 N2N2 X3 RISPOSTA -1 N1N1 N2N2 N3 RISPOSTA -1 N1N1 N2 N3 RISPOSTA -2 Segnala errore perche' X2 e' stata dichiarata due volte. RISPOSTA -2 Il valore di ritorno di F1 DOMANDA 5 program prova; var X1, X2, X3 : Integer; function F1(X3:Integer):Integer; var X2:Integer; begin writeln(X1,X2,X3); X2:=N2N2; X1:=N1N1; writeln(X1,X2,X3); end; begin X1:=N1; X2:=N2; X3:=N3; F1(X3); writeln(X1,X2,X3); end; Questo programma scrive tre righe. Cosa scrive nella SECONDA riga? RISPOSTA -1 N1 N2 N3 RISPOSTA -1 N1N1 N2N2 N3N3 RISPOSTA -2 Tre valori "indefiniti" RISPOSTA -1 N1, poi due valori "indefiniti" RISPOSTA -1 N1, un valore "indefinito", poi N3 RISPOSTA -2 N1N1 N2N2 X3 RISPOSTA +2 N1N1 N2N2 N3 RISPOSTA -1 N1N1 N2 N3 RISPOSTA -2 Segnala errore perche' X2 e' stata dichiarata due volte. RISPOSTA -2 Il valore di ritorno di F1 DOMANDA 6 program prova; var X1, X2, X3 : Integer; function F1(X3:Integer):Integer; var X2:Integer; begin writeln(X1,X2,X3); X2:=N2N2; X1:=N1N1; writeln(X1,X2,X3); end; begin X1:=N1; X2:=N2; X3:=N3; F1(X3); writeln(X1,X2,X3); end; Questo programma scrive tre righe. Cosa scrive nella TERZA riga? RISPOSTA -1 N1 N2 N3 RISPOSTA -1 N1N1 N2N2 N3N3 RISPOSTA -2 Tre valori "indefiniti" RISPOSTA -1 N1, poi due valori "indefiniti" RISPOSTA -1 N1, un valore "indefinito", poi N3 RISPOSTA -2 N1N1 N2N2 X3 RISPOSTA -1 N1N1 N2N2 N3 RISPOSTA +2 N1N1 N2 N3 RISPOSTA -2 Segnala errore perche' X2 e' stata dichiarata due volte. RISPOSTA -2 Il valore di ritorno di F1 ARGOMENTO Ricerca lineare e binaria in vettori ordinati DOMANDA 1 Ricerca binaria - caso elemento non trovato. Supponiamo di voler cercare un intero in un segmento, di lunghezza 2^E1, entro un vettore ordinato. Supponiamo di utilizzare il seguente procedimento. Confrontiamo l'intero da cercare con quello posto a meta' del segmento. Se l'intero da cercare risulta uguale ad esso, la ricerca e' finita. Altrimenti continua nella meta' sinistra del segmento se l'intero da cercare e' risultato il piu' piccolo, nella meta' destra se e' risultato il piu' grande. Ripetiamo questo procedimento finche' troviamo l'intero o la lunghezza del segmento in cui cercare scende a zero. Con quanti elementi del vettore dobbiamo confrontare l'intero da cercare, nel caso in cui quest'ultimo non si trovi nel vettore? RISPOSTA +2 E1 RISPOSTA -1 E1/2 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 1 bis Ricerca binaria - caso elemento non trovato. Le seguenti righe di codice cercano un intero N1 entro un vettore V1 ordinato, di indici [1..2^E1]. Se N1 e' in V1, la posizione di N1 in V1 viene inserita in X1. X1 := 1; X2 := 2^E1; while (X1 < X2) do begin X3 := (X1+X2) div 2; if (N1 <= V1[X3]) then X2 := X3 else X1 := X3 + 1; end; Con quanti elementi di V1 viene confrontato l'intero N1 da cercare, nel caso in cui quest'ultimo non si trovi in V1? RISPOSTA +2 E1 RISPOSTA -1 E1/2 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 2 Ricerca binaria - caso pessimo elemento trovato. Supponiamo di voler cercare un intero in un segmento, di lunghezza 2^E1, entro un vettore ordinato. Supponiamo di utilizzare il seguente procedimento. Confrontiamo l'intero da cercare con quello posto a meta' del segmento. Se l'intero da cercare risulta uguale ad esso, la ricerca e' finita. Altrimenti continua nella meta' sinistra del segmento se l'intero da cercare e' risultato il piu' piccolo, nella meta' destra se e' risultato il piu' grande. Ripetiamo questo procedimento finche' troviamo l'intero o la lunghezza del segmento in cui cercare scende a zero. Con quanti elementi del vettore dobbiamo confrontare, al massimo, l'intero da cercare, nel caso in cui quest'ultimo si trovi effettivamente nel vettore? RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA +2 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 infiniti DOMANDA 2 bis Ricerca binaria - caso pessimo elemento trovato. Le seguenti righe di codice cercano un intero N1 entro un vettore V1 ordinato, di indici [1..2^E1]. Se N1 e' in V1, la posizione di N1 in V1 viene inserita in X1. X1 := 1; X2 := 2^E1; while (X1 < X2) do begin X3 := (X1+X2) div 2; if (N1 <= V1[X3]) then X2 := X3 else X1 := X3 + 1; end; Con quanti elementi di V1 viene confrontato l'intero N1 da cercare, al massimo, nel caso in cui quest'ultimo si trovi effettivamente in V1? RISPOSTA +2 E1 RISPOSTA -1 E1/2 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 3 Ricerca lineare - caso elemento non trovato. Supponiamo di voler cercare un intero in un segmento, di lunghezza 2^E1 entro un vettore ordinato. Supponiamo di utilizzare il seguente procedimento. Confrontiamo l'intero da cercare con quello posto all'inizio del segmento. Se l'intero da cercare risulta uguale ad esso, la ricerca e' finita. Altrimenti continua nel segmento privato del suo primo elemento. Ripetiamo questo procedimento finche' troviamo l'intero o la lunghezza del segmento in cui cercare scende a zero. Quanti confronti con elementi del vettore dobbiamo fare nel caso peggiore, quello in cui l'elemento non si trova nel vettore? RISPOSTA +2 2^E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 3 bis Ricerca lineare - caso elemento non trovato. Le seguenti righe di codice cercano un intero N1 entro un vettore V1 ordinato, di indici [1..2^E1]. Se N1 e' in V1, la posizione di N1 in V1 viene inserita in X1. X1 := 1; while (X1 <= 2^E1) and not (N1 = V1[X1]) do X1 := X1 + 1; Quanti tests (N1 = V1[X1]) dobbiamo fare nel caso peggiore, quello in cui l'elemento N1 non si trova nel vettore V1? RISPOSTA +2 2^E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 4 Ricerca lineare - caso peggiore elemento trovato. Supponiamo di voler cercare un intero in un segmento, di lunghezza 2^E1 entro un vettore ordinato. Supponiamo di utilizzare il seguente procedimento. Confrontiamo l'intero da cercare con quello posto all'inizio del segmento. Se l'intero da cercare risulta uguale ad esso, la ricerca e' finita. Altrimenti continua nel segmento privato del suo primo elemento. Ripetiamo questo procedimento finche' troviamo l'intero o la lunghezza del segmento in cui cercare scende a zero. Quanti confronti dobbiamo fare nel caso peggiore (con buona approssimazione) se l'elemento si trova effettivamente nel vettore? RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA +2 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 infiniti DOMANDA 4 bis Ricerca lineare - caso peggiore elemento trovato. Le seguenti righe di codice cercano un intero N1 entro un vettore V1 ordinato, di indici [1..2^E1]. Se N1 e' in V1, la posizione di N1 in V1 viene inserita in X1. X1 := 1; while (X1 <= 2^E1) and not (N1 = V1[X1]) do X1 := X1 + 1; Quanti tests (N1 = V1[X1]) dobbiamo fare nel caso peggiore, se l'elemento N1 si trova effettivamente nel vettore V1? RISPOSTA +2 2^E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 6 Ricerca lineare - caso medio elemento trovato. Supponiamo di voler cercare un intero in un segmento, di lunghezza 2^E1 entro un vettore ordinato. Supponiamo di utilizzare il seguente procedimento. Confrontiamo l'intero da cercare con quello posto all'inizio del segmento. Se l'intero da cercare risulta uguale ad esso, la ricerca e' finita. Altrimenti continua nel segmento privato del suo primo elemento. Ripetiamo questo procedimento finche' troviamo l'intero o la lunghezza del segmento in cui cercare scende a zero. Quanti confronti dobbiamo fare nel caso medio (con buona approssimazione) se l'elemento si trova effettivamente nel vettore? RISPOSTA +2 2^E1*(1/2) RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti DOMANDA 6 bis Ricerca lineare - caso medio elemento trovato. Le seguenti righe di codice cercano un intero N1 entro un vettore V1 ordinato, di indici [1..2^E1]. Se N1 e' in V1, la posizione di N1 in V1 viene inserita in X1. X1 := 1; while (X1 <= 2^E1) and not (N1 = V1[X1]) do X1 := X1 + 1; Quanti tests (N1 = V1[X1]) dobbiamo fare nel caso medio, (con buona approssimazione) quando l'elemento N1 si trova nel vettore V1? RISPOSTA +2 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -2 infiniti ARGOMENTO Ordinamento (per inserzione soltanto) - complessita' DOMANDA 1 InsertSort - Confronti nel caso migliore (vettore gia' ordinato). Supponiamo di voler ordinare un vettore di lunghezza 2^E1. Supponiamo di utilizzare il seguente procedimento. Creiamo nel vettore un segmento iniziale ordinato via via piu' ampio. Per aggiungervi un elemento, scorriamo questa zona ordinata da destra a sinistra alla ricerca del posto in cui inserire il nuovo elemento senza alterare l'ordine. Continuiamo finche' sono rimasti elementi nella zona da ordinare. Quanti confronti dobbiamo fare (con buona approssimazione) nel caso in cui il vettore originario sia gia' ordinato? RISPOSTA +2 2^E1 RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA -2 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 infiniti DOMANDA 2 InsertSort - Confronti nel caso peggiore (ordine inverso). Supponiamo di voler ordinare un vettore di lunghezza 2^E1. Supponiamo di utilizzare il seguente procedimento. Creiamo nel vettore un segmento iniziale ordinato via via piu' ampio. Per aggiungervi un elemento, scorriamo questa zona ordinata da destra a sinistra alla ricerca del posto in cui inserire il nuovo elemento senza alterare l'ordine. Continuiamo finche' sono rimasti elementi nella zona da ordinare. Quanti confronti dobbiamo fare (con buona approssimazione) nel caso in cui il vettore originario sia gia' ordinato, ma in ordine decrescente? RISPOSTA +2 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -2 infiniti DOMANDA 3 InsertSort - Confronti nel caso medio. Supponiamo di voler ordinare un vettore di lunghezza 2^E1. Supponiamo di utilizzare il seguente procedimento. Creiamo nel vettore un segmento iniziale ordinato via via piu' ampio. Per aggiungervi un elemento, scorriamo questa zona ordinata da destra a sinistra alla ricerca del posto in cui inserire il nuovo elemento senza alterare l'ordine. Continuiamo finche' sono rimasti elementi nella zona da ordinare. Quanti confronti dobbiamo fare (con buona approssimazione) nel caso medio? RISPOSTA +2 (2^E1)*(2^E1)*(1/4) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 infiniti DOMANDA 4 InsertSort - Assegnazioni nel caso peggiore (ordine inverso). Supponiamo di voler ordinare un vettore di lunghezza 2^E1. Supponiamo di utilizzare il seguente procedimento. Creiamo nel vettore un segmento iniziale ordinato via via piu' ampio. Per aggiungervi un elemento, scorriamo questa zona ordinata da destra a sinistra alla ricerca del posto in cui inserire il nuovo elemento senza alterare l'ordine. Continuiamo finche' sono rimasti elementi nella zona da ordinare. Quante assegnazioni dobbiamo fare (con buona approssimazione) nel caso in cui il vettore originario sia gia' ordinato, ma in ordine decrescente? RISPOSTA +2 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/4) RISPOSTA -2 infiniti DOMANDA 5 InsertSort - Assegnazioni nel caso medio. Supponiamo di voler ordinare un vettore di lunghezza 2^E1. Supponiamo di utilizzare il seguente procedimento. Creiamo nel vettore un segmento iniziale ordinato via via piu' ampio. Per aggiungervi un elemento, scorriamo questa zona ordinata da destra a sinistra alla ricerca del posto in cui inserire il nuovo elemento senza alterare l'ordine. Continuiamo finche' sono rimasti elementi nella zona da ordinare. Quante assegnazioni dobbiamo fare (con buona approssimazione) nel caso medio? RISPOSTA +2 (2^E1)*(2^E1)*(1/4) RISPOSTA -2 0 RISPOSTA -2 (1/2)*E1*E1 RISPOSTA -1 E1/2 RISPOSTA -1 E1 RISPOSTA -1 2^(E1/2) RISPOSTA -1 2^E1*(1/2) RISPOSTA -1 2^E1 RISPOSTA -1 (2^E1)*(2^E1)*(1/2) RISPOSTA -2 infiniti ARGOMENTO Semplici esercizi di programmazione DOMANDA Massimo di un Vettore. Sia A1 una costante. Scrivere una funzione F1 che, dato un vettore V1 di lunghezza A1, ed un intero 1 <= I1 <= A1, restituisca la (una) posizione del massimo valore di V1[1 .. I1] (non il valore del massimo, solo la sua posizione, e sui primi I1 elementi, non su tutti). Nel caso ci siano piu' posizioni possibili, si chiede di restituirne una a scelta. Esempio: se V1 = [N1,N2N2,N3,N4N4,N5N5,...], allora F1(V1,3) = 2, la posizione di N2N2, il massimo tra i primi 3 elementi. Ignoriamo N4N4, N5N5, e tutti i valori successivi. SPIEGAZIONE function massimo (var V : Vettore; i : Integer) : Integer; var j, ris : Integer; begin ris := 1; {| ris = posizione del massimo di V[1..1] |} for j := 2 to i do {| ris = posizione del massimo di V[1..(j-1)] |} if V[ris] < V[j] then ris := j; {| ris = posizione del massimo di V[1..j] |} {| ris = posizione del massimo di V[1..i] |} massimo := ris; {| Postc.: valore di ritorno = posizione del (di un) massimo di V[1..i] |} end; DOMANDA Minimo di un Vettore. Sia A1 una costante. Scrivere una funzione F1 che, dato un vettore V1 di lunghezza A1, ed un intero 1 <= I1 <= A1, restituisca la (una) posizione del minimo valore di V1[1 .. I1] (non il valore del minimo, solo la sua posizione, e sui primi I1 elementi, non su tutti). Nel caso ci siano piu' posizioni possibili, si chiede di restituirne una a scelta. Esempio: se V1 = [N1N1,N2,N3N3,N4,N5,..], allora F1(V1,3) = 2, la posizione di N2, il minimo valore tra i primi tre elementi. Ignoriamo N4, N5, e tutti i valori successivi. SPIEGAZIONE function minimo (var V : Vettore; i : Integer) : Integer; var j, ris : Integer; begin ris := 1; {| ris = posizione del minimo di V[1..1] |} for j := 2 to i do {| ris = posizione del minimo di V[1..(j-1)] |} if V[ris] > V[j] then ris := j; {| ris = posizione del minimo di V[1..j] |} {| ris = posizione del minimo di V[1..i] |} minimo := ris; {| Postc.: valore di ritorno = posizione del (di un) minimo di V[1..i] |} end; DOMANDA. Palindrome. Scrivere una funzione F1 che prenda una stringa X1, e restituisca "vero" se la stringa è palindroma, cioe' se e' uguale letta da sinistra a destra e da destra a sinistra, e "falso" altrimenti. Esempi: F1('osso')=True, F1('orso')=False, F1('kajak')=True. Si consiglia di utilizzare due indici di lettura, uno che parta dall'inizio e uno dalla fine di X1, controllando di volta in volta che i caratteri letti dai due indici siano gli stessi. SPIEGAZIONE function palindroma (s : string) : Boolean; var i, j, L, L2 : Integer; begin L := length(s); L2 := L div 2; i := 1; j := L; while (i <= L2) and (s[i] = s[j]) do begin i := i + 1; {| (i<=L2+1) e (s[1..i-1] = inverso s[j..L]) |} j := j - 1; {| (i<=L2+1) e (s[1..i-1] = inverso s[j+1..L]) e (j=L+1-i) |} palindroma := (i > L2); {| PostCond.: valore di ritorno = true se, e solo se, s e' palindroma.|} end; DOMANDA. Lettura di un intero scritto in forma binaria. Scrivere una procedura P1 che prenda in input una stringa X1 rappresentante un valore intero >= 0 scritto in forma binaria (con eventualmente degli spazi vuoti all'inizio), e depositi tale valore intero in una variabile intera X2 chiamata per referenza. Si consiglia di leggere la stringa dal fondo, sommando 1 al risultato se l'ultima cifra è 1, quindi 2 se la cifra precedente è 1, quindi 2*2 se la cifra precedente ancora è 1, quindi 2*2*2 se la cifra precedente ancora è 1, eccetera. Esempio: P1('111',X2). Eseguendo P1, in X2 viene inserito il valore di '111', ovvero 1+2+4=7. SPIEGAZIONE procedure ReadBinary (var s : string; var x : Integer); var i, pot : Integer; begin pot := 1; x := 0; for i := length(s) downto 1 do begin if s[i] = '1' then x := x + pot; pot := pot * 2; end; {| x = valore numero binario posto in s[i..length(s)], |} {| pot = valore della prossima cifra da leggere se questa e' 1 |} end; DOMANDA. Ricerca del primo elemento in un vettore >= di un dato x. Sia V1 un vettore di interi di lunghezza A1. Scrivere una funzione F1 che prenda V1 ed un intero X1, e restituisca la posizione del primo V1[I1]>= X1, ponendo I1=A1+1 se non ci sono V1[I1]>=X1. Esempi. Siano V1 = [N1,N2,N3N3], V2 = [N1,N2,N3]. Allora F1(V1,N3N3)=3 (I1=3 e' la prima posizione per cui V1[I1]>=N3N3), mentre F1(V2,N3N3)= 4 (non ci sono posizioni I1 per cui V2[I1]>=N3N3). SPIEGAZIONE function PrimoMaggiore (var V : Vettore; x : Integer) : Integer; var i : Integer; trovato : Boolean; begin i := 1; trovato := false; while (trovato = false) and not (i = n + 1) do if V[i] < x then {| V[1], ..., V[i] < x |} i := i + 1 {| i e' tra 1 ed n+1, V[1], ..., V[i-1] < x, trovato=false |} else {| V[1], ..., V[i] < x ma V[i] >= x, cioe' i e' la posizione cercata |} trovato := true; {| i e ' la posizione cercata e trovato=true |} PrimoMaggiore := i; end; DOMANDA Conto degli elementi di un vettore V1 soddisfacenti una proprietà F2. Sia V1 un vettore di interi di lunghezza A1. Scrivere una funzione F1 che prenda V1 e restituisca un intero X1, pari al numero di elementi di V1 soddisfacenti una data proprietà F2. Rappresentare la proprietà F2 con una funzione che vale "vero" su X2 se X2 soddisfa la proprietà F2, e vale "falso" altrimenti. Supporre F2 già definita, e utilizzarla nella definizione di F1. Esempio. Supponiamo F2(X2) = True se X2 è pari, F2(X2) = False se X2 non è pari. Sia V1 = [1,2,3,4,5]. Allora V1 contiene due numeri pari (2 e 4), cioè ci sono due elementi di V1 che soddisfano la proprietà F2. Quindi F1(V1)= 2. SPIEGAZIONE function Count_x_P(var V : Vettore) : Integer; var ris, i : Integer; begin ris := 0; {| count = numero elementi di V[1..i] che soddisfano P, se i=0 |} for i := 1 to n do {| count = numero elementi di V[1..i-1] che soddisfano P |} if P(V[i]) then ris := ris + 1; {| count = numero elementi di V[1..i] che soddisfano P |} Count_x_P := ris; end; ARGOMENTO Esercizi di Programmazione a risposta aperta DOMANDA Prodotto di matrici. Siano M1, M2, M3 tre matrici di dimensioni A1 (un intero positivo). Scrivere una procedura P1, di argomenti M1, M2, M3. Le prime due matrici sono valori in ingresso, la terza e' un valore in uscita. La procedura deve scrivere in M3 il prodotto di M1 ed M2, utilizzando la formula: M3[i,k] = somma di M1[i,j]*M2[j,k], per j=1, ..., A1 = M1[i,1]*M2[1,k] + M1[i,2]*M2[2,k] + M1[i,3]*M2[3,k] + .. SPIEGAZIONE procedure F1(var M1,M2,M3:Matr); var i,j,k,somma:Integer; begin for i:=1 to A1 for k:=1 to A1 begin somma:=0; for j:=1 to A1 do somma:=somma+M[i,j]*M[j,k]; end; end; DOMANDA. Triangolo di Tartaglia. Sia A1 una costante intera >=0. Scrivere una procedura P1 di argomento una matrice M1 di dimensioni [0..A1] X [0..A1]. P1 pone in M1[0,0] il vertice di un triangolo di Tartaglia, in M1[1,0],M1[1,1] la prima riga di tale triangolo, in M1[2,0],M1[2,1],M1[2,2] la seconda, e cosi' via. Utilizzare le seguenti formule, per i=0, ..., A1: M1[i,0]=M1[i,i]=1, e per 0m) then ris:=false else ris:=true; i:=1; while (i<=n) and (ris=true) do begin j:=1; while (j<=m) and (parola1[i]<>parola2[j]) do j:=j+1; if (j<=m) then parola2[j]:='*' else ris:=false; end; F1:=ris; end; DOMANDA 13 (Sostituzione) Siano V1 = array [1..A1] of char, V2 = array [1..A2] of char. Si richiede di scrivere una procedura P1, di argomenti vecchio_testo:V1, s1, s2:string, nuovo_testo:V2 che ricopi il contenuto del vettore di caratteri vecchio_testo nel vettore nuovo_testo, rimpiazzando, ogni volta che viene incontrata, la stringa s1 con la stringa s2. Si supponga che il vettore nuovo_testo sia abbastanza ampio per contenere il risultato della sostituzione, e sia originariamente occupato da caratteri tutti bianchi. Si richiede che P1 utilizzi le procedura match(A,S,i) e Copia(A,S,i) viste a lezione (e che non vanno ridefinite). NOTA. match(A,S,i)=true se S si trova in A nella zona [i,..,i+length(S)-1] di A. Dunque match('abcd','ab',1)=true ('ab' si trova in 'abcd' tra 1 e 2), mentre match('abcd','ab',2)=false ('ab' non si trova in 'abcd' tra 2 e 3). Infine, Copia(A,S,i) copia S in A a partire dalla locazione i. Dunque copia('abcd','xxx',2) trasforma 'abcd' in 'axxx'. SPIEGAZIONE procedure P1(var vecchio_testo:V1, s1, s2:string, nuovo_testo:V2) var i,j,n,m: integer; begin i:=1;j:=1;n:=length(s1);m:=length(s2); {i,j cursori su vecchio e nuovo testo, n,m lunghezze di s1, s2} while (i<=A1) and (j<=A2) do if not match(vecchio_testo,s1,i) then begin nuovo_testo[j]:=vecchio_testo[i]; i:=i+1; j:=j+1; end; else begin copia(nuovo_testo,s2,j); i:=i+n; j:=j+m; end; end; DOMANDA 14 InsertSort Scrivere una procedura che ordini un vettore utilizzando il procedimento per inserzione (detto anche InsertSort). SPIEGAZIONE procedure InsertOrd (var V : Vettore; max, x : Integer); var i, k : Integer; trovato : Boolean; begin i := 1; trovato := false; while (i <= max) and not trovato do if V[i] < x then i := i + 1 else trovato := true; for k := max downto i do V[k + 1] := V[k]; V[i] := x; end; procedure InsertSort (var V : Vettore); var i : Integer; begin for i := 2 to n do InsertOrd(V, i - 1, V[i]); end; DOMANDA Test di primalità. Scrivere una funzione primo(M:Integer):Boolean (con M > 0), che dia una risposta vero/falso alla domanda: "M e' primo?", e che utilizzi il procedimento seguente. Per controllare se N divide M, basta controllare se M mod N = 0. Controllare se N=2 e' 0) do N:=N+2; primo:=(N> RQM) end; end; DOMANDA Funzione di Fibonacci. Scrivere una funzione Fibo(x), con x intero >= 0, tale che Fibo(0)=0, Fibo(1)=1, e: Fibo(2)= Fibo(0)+Fibo(1) Fibo(3)= Fibo(1)+Fibo(2) Fibo(4)= Fibo(2)+Fibo(3) ... Si richiede di non utilizzare la ricorsione (non fa parte di Programmazione 1). Si richiede inoltre di non utilizzare una variabile locale di tipo vettore, ma al piu' quattro variabili locali di tipo integer. SPIEGAZIONE function Fibo (x : Integer) : Integer; var i, a, b, temp : Integer; begin a := 0; b := 1; for i := 2 to x do begin temp := b; b := a + b; a := temp; end; if x = 0 then Fibo := 0 else Fibo := b; end; ARGOMENTO Esercizi di Programmazione a risposta aperta DOMANDA 1 Ricerca dei primi elementi ripetuti. Definire una procedura P1 che prenda in input un vettore V1 di interi di indici [1..A1], due interi i, j e un booleano equal passati per referenza. La procedura pone equal=true se ci sono due interi i, j tra 1 e A1 per cui ii, e in j il primo di tali j>i. Se equal=false, il valore posto in i,j e' irrilevante. Esempio: se V1=[1,2,3,4,5] allora equal=false, mentre se V1=[1,2,3,2,1] allora equal=true,i=1,j=5. Non e' richiesta una soluzione efficiente. SPIEGAZIONE La procedura richiesta, di ricerca dei primi elementi ripetuti di V1. procedure P1(var V1:Vett, var equal:Boolean, var i,j:Integer); Var i: integer; begin i:=1; equal:=false; while (ii, e in j il primo di tali j>i. Se close=false, il valore posto in i,j e' irrilevante. Esempio: se V1=[1,2,3,4,5] e x=1 allora close=false. Se V1=[1,2,3,2.5,1.5] allora close=true,i=1,j=5. Non e' richiesta una soluzione efficiente. SPIEGAZIONE La procedura richiesta, di ricerca punti più vicini di x procedure P1(var V1:Vett, x:Real, var close:Boolean, var i,j:Integer); Var i: integer; begin i:=1; close:=false; while (i1 do j:=j-1; if i= x >= 0, e "ruoti V1 di x passi verso destra ". Esempio: sia V1=[a,b,c]. Eseguiamo P1(V1,x). Se x=0, allora V1 resta [a,b,c]. Se x=1, allora V1 diventa [c,a,b]. Se x=2, allora V1 diventa [b,c,a]. Se x=3, allora V1 ritorna ad essere [a,b,c]. Non e' richiesta una soluzione efficiente. SPIEGAZIONE La procedura richiesta, che ruota V1 di x passi verso destra. procedure P1(var V1:Vett,x:Integer); var i,j:Integer; begin for i:=1 to x do for j:=n downto 2 do swap(V1[j],V1[j-1]); end. DOMANDA. 5 Rotazione sinistra di un vettore. Definire una procedura P1, che prenda in input un vettore V1 di n elementi, un intero n >= x >= 0, e "ruoti V1 verso sinistra di x passi". Esempio: sia V1=[a,b,c]. Eseguiamo P1(V1,x). Se x=0, allora V1 resta [a,b,c]. Se x=1, allora V1 diventa [b,c,a]. Se x=2, allora V1 diventa [c,a,b]. Se x=3, allora V1 ritorna ad essere [a,b,c]. Non e' richiesta una soluzione efficiente. SPIEGAZIONE La procedura P1 richiesta, che ruota V1 di x passi verso sinistra procedure P1(var V1:Vett,x:Integer); var i,j:Integer; begin for i:=1 to x do for j:=2 to n do swap(V1[j-1],V1[j]); end. DOMANDA 6 Conto delle parole Definire una funzione P1, che prenda un vettore V1 di caratteri di lunghezza n, e restituisca come valore di ritorno il numero k delle parole in V1. Per "parola" intendiamo un gruppo di lettere, maiuscole o minuscole, separato dalle altre parole da caratteri che non sono lettere. Per esempio: P1('Ciao come va? Bene, e tu?') = 6 Si noti che la lettera isolata 'e' conta come una parola. Supporre data e utilizzare una funzione lettera(c:Char):Boolean, che restituisca 'true' su una lettera, e 'false' altrimenti. Per esempio: lettera('a') = .. lettera('Z') = 'true, mentre lettera(' ') = lettera('?') = lettera('.') = false. SPIEGAZIONE La funzione che conta le parole in una stringa. Si usa il fatto che le parole sono tante quante le lettere che vengono subito dopo l'inizio stringa o uno spazio bianco. function F1(var V1:Vett):Integer; var p:integer; begin p:=0; if lettera(V1[1]) then p:=1; {esiste almeno una parola} for i:=2 to n do if (lettera(V1[i]) and not lettera(V1[i-1])) then p:=p+1; F1:=p; end; DOMANDA 7 Conto delle espressioni decimali Definire una funzione P1, che prenda un vettore V1 di caratteri di lunghezza n, e restituisca come valore di ritorno il numero k delle espressioni decimali in V1. Per "espressione decimale" intendiamo un gruppo di cifre, separato dalle altre parole da caratteri che non sono cifre. Per esempio: P1('xdvr0101sdver123vre7btgs') = 3 Si noti che la cifra isolata '7' conta come un numero. Supporre data e utilizzare una funzione cifra(c:Char):Boolean, che restituisca 'true' su una cifra, e 'false' altrimenti. Per esempio: cifra('0') = .. = cifra('9') = 'true', mentre cifra('a') = cifra('?') = cifra('.') = 'false'. SPIEGAZIONE La funzione che conta le espressioni decimali in una stringa function F1(var V1:Vett):Integer; var p:integer; begin p:=0; if cifra(V[1]) then p:=1; {esiste almeno un'espressione decimale} for i:=2 to n do if (cifra(V1[i]) and not cifra(V1[i-1])) then p:=p+1; F1:=p; end; DOMANDA 14 Calcolo del valore di un gruppo di cifre Si richiede di scrivere una funzione F1, di argomenti: testo:string, i:integer che consideri l'eventuale gruppo di cifre consecutive da testo[i], testo[i+1],testo[i+2], ..., in poi, e ne restituisca il valore numerico. Nel caso testo[i] non sia una cifra, e quindi il gruppo di cifre consecutive non ci sia, si richiede F1(testo,i) = 0. Esempi: se testo = 'xyz123tu4', allora F1(testo,4) = 123, F1(testo,5) = 23, F1(testo,6)=3, F1(testo,7)=0. Si noti che la cifra isolata 4 viene ignorata (non è consecutiva al gruppo 123). Suggerimento: usare la funzione ord(c:char):Integer, che restituisce la posizione di un carattere nell'alfabeto ascii. Ricordiamo anche che le cifre, nell'alfabeto ascii, sono disposte tutte tra la cifra 0 e la cifra 9. SPIEGAZIONE La funzione F1 richiesta, che legge numero da una lista di caratteri function F1(var testo:Vett, i : Integer):Integer; var x,l:Integer; begin l:=length(testo);i:=1; x := 0; while i<=l and ('0' <= testo[i]) and (testo[i] <= '9') do begin x:=x*10+(ord(testo[i])-ord('0')); i:=i+1; end; F1:= x; end; DOMANDA Prefisso Scrivere una funzione prefisso(var A,B:String):Boolean, che date due stringhe A, B restituisca "vero" se A é un prefisso di B, e "falso" altrimenti. Siano n=length(A) e length(B)=m. Allora A é un prefisso di B se n <= m, ed A[1] = B[1], A[2] = B[2], ..., A[n] = B[n] Per esempio, "breve" é un prefisso di "brevemente". Tra i prefissi di una stringa c'é, come caso limite, la stringa stessa. Non e' consentito riutilizzare la funzione Match. SPIEGAZIONE function Prefisso (var A, B : string) : Boolean; var i,j,n,m: Integer; {i=cursore su A, j=cursore su S1, n=lungh(A), m=lungh(B)} begin i:=1; j:=1; n:=length(A); m:=length(B); if (n<=m) then while (i<=n) and (A[i]=B[j]) do begin i:=i+1; j :=j+1; end; Prefisso:=(i>n); end; DOMANDA Suffisso Scrivere una funzione suffisso(var A,B:String):Boolean, che date due stringhe A, B restituisca "vero" se A é un suffisso di B, e "falso" altrimenti. Siano n=length(A) e length(B)=m. Allora A é un suffisso di B se n <= m, ed A[n]=B[m], A[n-1]=B[m-1], ..., A[1]=B[m-n+1] Per esempio, "mente" é un suffisso di "brevemente". Tra i suffissi di una stringa c'é, come caso limite, la stringa stessa. Non e' consentito riutilizzare la funzione Match. SPIEGAZIONE function Suffisso (var A, B : string) : Boolean; var i,j,n,m: Integer; {i=cursore su A, j=cursore su S1, n=lungh(A), m=lungh(B)} begin i:=n; j:=m; n:=length(A); m:=length(B); if (n<=m) then while (i>=1) and (A[i]=B[j]) do begin i:=i-1; j :=j-1; end; Prefisso:=(i<1); end; DOMANDA 8 Lettura data: giorno mese anno. Si richiede di scrivere una procedura P1, di argomenti data:String, e giorno, mese, anno:Integer P1 prende una data nel formato: giorno-spazio-mese-spazio-anno per esempio: data = '20 Dicembre 1999' e modifica gli argomenti giorno, mese, anno in modo che contengano la stessa data, ma in in cifre. Nell'esempio dato avremo giorno=20, mese=12, anno=1999. Si richiede che P1 utilizzi un ciclo (non un lungo 'if'), e le seguenti variabili e procedure (tutte da supporre gia' definite): (1) un vettore di stringhe Mesi con i nomi dei mesi. (2) La procedura match(var A,S:String;i:Integer):Boolean che verifica se S si trova nella zona [i,..,i+length(S)-1] di A. (3) la funzione val(var data:String, var i:Integer): Integer, che restituisce il valore dell'espressione decimale in 'data' che inizia alla posizione i, e sposta i (chiamato per riferimento) subito dopo tale espressione. Due esempi. Sia data come sopra. Se i=1, allora val(data,i)=20 e i diventa 3. Se i=13, allora val(data,i)=1999 e i diventa 17. SPIEGAZIONE La procedura P1 richiesta, che legge una data scritta in parole. procedure P1(var data:String, var giorno, mese, anno:Integer); var i, j:Integer; begin i:=1; giorno := val(data,i); {i si posiziona dopo il numero dei giorni} i:=i+1; for j:=1 to 12 do if match(data,Mesi[j],i) then mese:=j; i:=i+length(Mesi[mese])+1; anno:= val(data,i); end; DOMANDA 9 Lettura data: giorno della settimana giorno mese. Si richiede di scrivere una procedura P1, di argomenti data:String, e giorno_sett, giorno, mese:Integer P1 prende una data nel formato: nome_giorno-spazio-giorno-spazio-mese per esempio: data = 'Lunedì 20 Dicembre' e modifica gli argomenti giorno_sett, giorno, mese in modo che contengano la stessa data, ma in in cifre. Nell'esempio dato avremo giorno_sett=1, giorno=20, mese=12. Si richiede che P1 utilizzi un ciclo (non un lungo 'if'), e le seguenti variabili e procedure (tutte da supporre gia' definite): (1) due vettori di stringhe Settimana, Mesi con i nomi dei giorni della settimana e dei mesi. (2) La procedura match(var A,S:String;i:Integer):Boolean che verifica se S si trova nella zona [i,..,i+length(S)-1] di A. (3) la funzione val(var data:String, var i:Integer): Integer, che restituisce il valore dell'espressione decimale in 'data' che inizia alla posizione i, e sposta i (chiamato per riferimento) subito dopo tale espressione. Un esempio. Sia data = 'Lunedì 20 Dicembre'. Se i=8, allora val(data,i)=20 e i diventa 10. SPIEGAZIONE La procedura P1 richiesta, che legge una data scritta in parole. procedure P1(var data:String, var giorno_sett, giorno, mese:Integer); var i, j:Integer; begin i:=1; for j:=1 to 7 do if match(data,Settimana[j],i) then giorno_sett:=j; i:=i+length(Settimana[giorno_sett])+1; giorno:= val(data,i); {i si posiziona dopo il numero dei giorni} i:=i+1; for j:=1 to 12 do if match(data,Mese[j],i) then mese:=j; end; DOMANDA 11 Lettura lista della spesa (alimentari) Si richiede di scrivere una procedura P1, di argomenti voce_spesa:String, e merce, quantita, misura:Integer P1 prende una voce di una lista della spesa, nel formato: merce-spazio-quantita-spazio-unita_di_misura per esempio: voce_spesa = 'carne 33 hg' e modifica gli argomenti merce, quantita, misura, in modo che contengano le stesse informazioni, ma espresse mediante numeri. P1 utilizza un vettore Merci:array[1..A1] of string di A1 merci disponibili: Merci[1]='carne', Merci[2]='latte', Merci[3]='uova', ... e un secondo vettore Misure:array[1..A2] of string di A2 unita di misura: Misure[1]='g',Misure[2]='dag', Misure[3]='hg', Misure[4]='kg',.. Nell'esempio dato, 'carne kg' viene convertito nei dati: merce=1, quantita=33, misura=3 (gli hg sono la terza misura nell'elenco) Si richiede che P1 utilizzi un ciclo (non un lungo 'if'), e le seguenti procedure (tutte da supporre gia' definite): (1) La procedura match(var A,S:String;i:Integer):Boolean che verifica se S si trova nella zona [i,..,i+length(S)-1] di A. (2) la funzione val(var data:String, var i:Integer): Integer, che restituisce il valore dell'espressione decimale in 'data' che inizia alla posizione i, e sposta i (chiamato per riferimento) subito dopo tale espressione. Per esempio, se i=7, voce_spesa='carne 33 hg', allora val(voce_spesa,i)=33 e i viene spostato a 9 (subito dopo l'espressione 33). SPIEGAZIONE procedure P1(var voce_spesa:String, var merce,quantita,misura:Integer); var i, j:Integer; begin i:=1; for j:=1 to A1 do if match(voce_spesa,Merci[j],i) then merce:=j; i:=i+length(Merci[merce])+1; quantita:= val(voce_spesa,i); {i si posiziona dopo il numero dei giorni} i:=i+1; for j:=1 to A2 do if match(voce_spesa,Misure[j],i) then misura:=j; end; DOMANDA 12 Lettura lista della spesa (ferramenta). Si richiede di scrivere una procedura P1, di argomenti voce_spesa:String, e oggetto, quantita, misura:Integer P1 prende una voce di una lista della spesa, nel formato: oggetto-spazio-quantita-spazio-unita_di_misura per esempio: 'chiodi 12 scatole' e modifica gli argomenti oggetto, quantita, misura, in modo che contengano le stesse informazioni, ma espresse mediante numeri. P1 utilizza un vettore Elenco:array[1..A1] of string di A1 oggetti disponibili: Elenco[1]='chiodi', Elenco[2]='viti', Elenco[3]='dadi', ... e un secondo vettore Misure:array[1..A2] of string di A2 unita di misura: Misure[1]='unita',Misure[2]='scatole', Misure[3]='casse', .. Nell'esempio dato, 'chiodi 10 scatole' viene convertito nei dati: oggetto=1, quantita=12, misura=2 (le scatole sono la 2a misura nell'elenco) Si richiede che P1 utilizzi un ciclo (non un lungo 'if'), e le seguenti procedure (tutte da supporre gia' definite): (1) La procedura match(var A,S:String;i:Integer):Boolean che verifica se S si trova nella zona [i,..,i+length(S)-1] di A. (2) la funzione val(var data:String, var i:Integer): Integer, che restituisce il valore dell'espressione decimale in 'data' che inizia alla posizione i, e sposta i (chiamato per riferimento) subito dopo tale espressione. Per esempio, se i=8, voce_spesa='chiodi 10 scatole', allora val(voce_spesa,i)= 10, e i viene spostato a 10 (subito dopo l'espressione 12). SPIEGAZIONE procedure P1(var voce_spesa:String, var merce,quantita,misura:Integer); var i, j:Integer; begin i:=1; for j:=1 to A1 do if match(voce_spesa,Elenco[j],i) then oggetto:=j; i:=i+length(Elenco[oggetto])+1; quantita:= val(voce_spesa,i); {i si posiziona dopo il numero dei giorni} i:=i+1; for j:=1 to A2 do if match(voce_spesa,Misure[j],i) then misura:=j; end; ARGOMENTO Domanda di teoria a risposta aperta DOMANDA Chiamate per referenza. Supponiamo di avere: - un main con due variabili globali A1, A2, inizializzate a N1, N2; - una procedura P1, con parametri X1, X2 chiamati per referenza, variabili locali A3,A4 inizializzate a N3, N4. Supponiamo ora che: - il main inizi con l'esecuzione di una riga: P1(A1,A2); - P1 inizi con assegnazioni di X1, X2 a N1N1, N2N2. - P1 continui con l'esecuzione della riga: writeline(A1); Descrivere lo stato dello stack delle variabili in questo particolare momento dell'esecuzione. Spiegare anche come si utilizza tale stack per decidere quale valore scrive l'istruzione writeline(A1). SPIEGAZIONE Prima delle assegnazioni a X1, X2, lo stack include: - i valori globali di A1, A2 cioe' N1, N2; - al posto dei X1, X2 di P1, gli indirizzi di A1, A2 (dato che la chiamata P1(A1,A2) e' avvenuta per referenza). Le assegnazioni a X1, X2, sempre poiche' la chiamata e' avvenuta per referenza, modificano, in realta', i valori delle variabili di cui X1, X2 contengono l'indirizzo. Modificano, quindi, A1 e A2. Dunque: A1, A2 (globali) diventano N1N1, N2N2, e writeline(A1) scrive N1N1. DOMANDA Chiamate di procedura Supponiamo di avere: - un main con due variabili globali A1, A2, inizializzate a N1, N2; - una procedura P1 con parametri X1, X2, variabili locali A1, A2, inizializzate a N1N1, N2N2; (I parametri di P1 sono chiamati per valore). Supponiamo ora che: - il main inizi con l'esecuzione della riga: P1(E1,E2); - P1 inizi con l'esecuzione della riga: writeline(A1,A2,X1,X2) Descrivere lo stato dello stack delle variabili in questo particolare momento dell'esecuzione. Spiegare anche come si utilizza tale stack per decidere quale valore scrive l'istruzione writeline(A1,A2,X1,X2). SPIEGAZIONE In quel particolare momento dell'esecuzione, lo stack include: - i valori globali di A1, A2 cioe' N1, N2; - il valore con cui sono stati chiamati i parametri X1,X2 di P1, cioe' E1, E2; - il valore delle variabili A1,A2 locali a P1, cioe' N1N1,N2N2. La ricerca del valore di X3 inizia nella parte dello stack relativa a P1, e li' ha successo. Dunque: A1, A2, X1, X2 prendono i valori N1N1,N2N2,E1,E2. I valori globali delle variabili A1, A2 sono in questo momento "invisibili" (torneranno visibili terminata la chiamata a P1). DOMANDA Catena di chiamate di procedure. Supponiamo di avere: - un main con un'unica variabile globale A1, inizializzata a N1; - una procedura P2 con un parametro X2 e una variabile locale A1, inizializzata a N1N1; - una procedura P3 con un parametro X3 e una variabile locale A3, inizializzata a N3. (I parametri di P2, P3 sono chiamati per valore). Supponiamo ora che: - il main inizi con l'esecuzione della riga: P2(E2); - il corpo di P2, a sua volta, inizi con l'esecuzione della riga: P3(E3); - il corpo di P3, a sua volta, inizi con l'esecuzione della riga: writeline(A1); Descrivere lo stato dello stack delle variabili in questo particolare momento dell'esecuzione. Spiegare anche come si utilizza tale stack per decidere quale valore scrive l'istruzione writeline(A1). SPIEGAZIONE In quel particolare momento dell'esecuzione, lo stack include: - il valore globale di A1, cioe' N1, - il valore con cui e' stato chiamato il parametro X2 di P2, cioe' E2, - il valore della variabile A1 locale a P2, cioe' N1N1, - il valore con cui e' stato chiamato il parametro X3 di P3, cioe' E3, - il valore della variabile A3 locale a P3, cioe' N3. La ricerca del valore di A1 inizia nella parte dello stack relativa a P3, e li' fallisce. Quindi continua non nella parte dello stack relativa a P2, dato che una procedura non "vede" i parametri e le variabili locali di un'altra. Continua invece nella parte dello stack relativa al main. Li' trova il valore N1 per A1. Dunque: writeline(A1) scrive N1. PARAMETRO A (una costante) a b c d PARAMETRO E (un esponente) 10 15 20 25 30 PARAMETRO F (una funzione) f g h PARAMETRO I (un indice) i j k PARAMETRO M (una matrice) M N P Q PARAMETRO N (un intero) 3 5 7 9 11 PARAMETRO P (una procedura) p q r PARAMETRO T (un tipo del Pascal) Integer Real Char String PARAMETRO V (un vettore) V W Z PARAMETRO X (una variabile) x y z t u FINE DOMANDE DI ANNI PRECEDENTI NON RIPRESE NEL 2001 ARGOMENTO Uso del ciclo "for", precondizioni, postcondizioni. DOMANDA 1 fattoriale di A2 Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X1:=1; for X3:=1 to X2 begin X1:=X1*X3; end; X4:=X1; RISPOSTA +2 A2! RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A1 interi. RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1*A2. RISPOSTA -1 A1+A2 RISPOSTA -1 A1! DOMANDA 1 bis inverso del fattoriale di A2 Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X1:=1; for X3:=1 to X2 begin X1:=X1/X3; end; X4:=X1; RISPOSTA +2 1/A2! RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A1 interi. RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1/A2. RISPOSTA -1 A2/A1 RISPOSTA -1 1/A1! DOMANDA 2 somma A1+(A1-1)+...+2+1 Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X2:=0; for X3:=1 to X1 begin X2:=X2+X3; end; X4:=X2; RISPOSTA +2 La somma dei primi A1 interi. RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1*A2. RISPOSTA -1 A1+A2 RISPOSTA -1 A1! RISPOSTA -1 A2! SPIEGAZIONE Viene eseguito, dopo sostituzione: X2:=0; for X3:=1 to A1 begin X2:=X2+X3; end; X4:=X2; Questo equivale a: X2:=0;X2:=X2+1;X2:=X2+2; ...; X2:=X2+A1; X4:=X2; Dunque: il valore finale di X4 è X2, cioe' la somma dei primi A1 interi. DOMANDA 3 somma A1+1+...+1 (A2 volte) Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X4:=0; for X3:=1 to X2 begin X1:=X1+1; end; X4:=X1; RISPOSTA +2 A1+A2 RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A1 interi. RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1*A2. RISPOSTA -1 A1! RISPOSTA -1 A2! DOMANDA 3 bis sottrazione A1 - 1 -1 -1 ... (A2 volte). Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X4:=0; for X3:=1 to X2 begin X1:=X1-1; end; X4:=X1; RISPOSTA +2 A1-A2 RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A1 interi, cambiata di segno. RISPOSTA -1 A2-A1. RISPOSTA -1 A1/A2. RISPOSTA -1 A1! RISPOSTA -1 A2! DOMANDA 4 A1+...+A1 (A2 volte) Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X5:=0; for X3:=1 to X2 begin X5:=X5+X1; end; X4:=X5; RISPOSTA +2 A1*A2. RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A1 interi. RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1+A2 RISPOSTA -1 A1! RISPOSTA -1 A2! DOMANDA 5 A2*...* A2 (A1 volte) Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X5:=1; for X3:=1 to X1 begin X5:=X5*X2; end; X4:=X5; RISPOSTA +2 A2^A1 RISPOSTA -1 A1^A2 RISPOSTA -1 log_2(A1) (parte intera). RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A1 interi. RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1*A2. RISPOSTA -1 A1+A2 RISPOSTA -1 A1! RISPOSTA -1 A2! DOMANDA 5 bis 1/(A2*...* A2) (A1 volte) Supponiamo che i valori originari delle variabili reali X1, X2 siano dei valori interi A1>2,A2>2. Qual'e' il valore finale assunto da X4 eseguendo le seguenti istruzioni? X5:=1; for X3:=1 to X1 begin X5:=X5/X2; end; X4:=X5; RISPOSTA +2 A2^(-A1) RISPOSTA -1 A1^(-A2) RISPOSTA -1 A1^A2 RISPOSTA -1 A2^A1 RISPOSTA -1 log_2(A2) (parte intera). RISPOSTA -1 La somma dei primi A2 interi. RISPOSTA -1 A1/A2. RISPOSTA -1 A2/A1 RISPOSTA -1 A1! RISPOSTA -1 A2! ARGOMENTO complessita' procedure di ordinamento DOMANDA LeadSort Sia V1 un vettore di indici [1..2^E1], gia' assegnato. Che effetto ha eseguire le seguenti righe? for X1:=2 to 2^E1 do for X2:=2^E1 downto X1 do if V[X2-1]>V[X2] then begin temp:=V[X2-1]; V[X2-1]:=V[X2]; V[X2]:=temp; end; (Si consiglia di sperimentare il programma su un vettore di 3 elementi). RISPOSTA +2 Ordina V1 in ordine diretto usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1) confronti. RISPOSTA -2 Cancella V1. RISPOSTA -2 Produce un ciclo che non termina mai. DOMANDA LeadSort (ordine inverso) Sia V1 un vettore di indici [1..2^E1], gia' assegnato. Che effetto ha eseguire le seguenti righe? for X1:=2 to 2^E1 do for X2:=2^E1 downto X1 do if V[X2-1]V[X2] then begin temp:=V[X2-1]; V[X2-1]:=V[X2]; V[X2]:=temp; end; (Si consiglia di sperimentare il programma su un vettore di 3 elementi). RISPOSTA +2 Ordina V1 in ordine diretto usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1) confronti. RISPOSTA -2 Cancella V1. RISPOSTA -2 Produce un ciclo che non termina mai. DOMANDA LeadSort (versione lenta, ordine inverso) Sia V1 un vettore di indici [1..2^E1], gia' assegnato. Che effetto ha eseguire le seguenti righe? for X1:=2 to 2^E1 do for X2:=2^E1 downto 2 do if V[X2-1]V[X2] then begin temp:=V[X2-1]; V[X2-1]:=V[X2]; V[X2]:=temp; end; (Si consiglia di sperimentare il programma su un vettore di 3 elementi). RISPOSTA +2 Ordina V1 in ordine diretto usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1) confronti. RISPOSTA -2 Cancella V1. RISPOSTA -2 Produce un ciclo che non termina mai. DOMANDA BubbleSort (ordine inverso) Sia V1 un vettore di indici [1..2^E1], gia' assegnato. Che effetto ha eseguire le seguenti righe? for X1:= 2^E1 downto 2 do for X2:=2 to X1 do if V[X2-1]V[X2] then begin temp:=V[X2-1]; V[X2-1]:=V[X2]; V[X2]:=temp; end; (Si consiglia di sperimentare il programma su un vettore di 3 elementi). RISPOSTA +2 Ordina V1 in ordine diretto usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine diretto usando (2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (1/2)*(2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1)*(2^E1) confronti. RISPOSTA -1 Ordina V1 in ordine inverso usando (2^E1) confronti. RISPOSTA -2 Cancella V1. RISPOSTA -2 Produce un ciclo che non termina mai. DOMANDA BubbleSort (versione lenta, ordine inverso) Sia V1 un vettore di indici [1..2^E1], gia' assegnato. Che effetto ha eseguire le seguenti righe? for X1:= 2^E1 downto 2 do for X2:=2 to 2^E1 do if V[X2-1]V[i] then swap(V[i-1],V[i]); end; DOMANDA 2 BubbleSort Scrivere una procedura di ordinamento P1, che scambi il primo elemento con il secondo se questo e' piu' piccolo, poi il secondo con il terzo se questo e' piu' piccolo, fino a portare il massimo di V1[1 .. n] in V1[n]. Portare allo stesso modo il massimo di V1[1 .. n-1] in V1[n-1], il massimo di V1[1 .. n-2] in V1[n-2], e cosi' via, fino ad ordinare V1. SPIEGAZIONE La procedura richiesta, di ordinamento mediante spostamento del massimo. procedure P1(var V1:Vett); var i,j:Integer; begin for j:=n downto 2 do for i:=1 to j-1 do if V[i]>V[i+1] then swap(V[i],V[i+1]); end; DOMANDA MinSort (=ordinamento mediante selezione del minimo). Scrivere una procedura P1 che selezioni la posizione del (di un) minimo di V1[1..n], lo porti in V1[1] tramite uno scambio, poi selezioni il minimo di V1[2..n] e lo porti in V1[2] tramite uno scambio, e continui cosi' finche' V1[1 .. n] non e' ordinato. Definire e utilizzare anche una funzione "minimo(V1,i)", che trovi una posizione del minimo di V1[i..n]. SPIEGAZIONE La procedura richiesta, di ordinamento mediante selezione del minimo. procedure P1(var V1:Vett); var i,j:Integer; begin for i:=1 to n-1 do begin j:=minimo(V,i); swap(V[i],V[j]); end; end; DOMANDA MaxSort (=ordinamento mediante selezione del massimo). Scrivere una procedura P1 che selezioni la posizione del (di un) massimo di V1[1..n], lo porti in V1[n] tramite uno scambio, poi selezioni il massimo di V1[1..n-1] e lo porti in V1[n-1] tramite uno scambio, e continui cosi' finche' V1[1 .. n] non e' ordinato. Definire e utilizzare anche una funzione "massimo(V1,i)", che trovi una posizione del massimo di V1[1...i]. SPIEGAZIONE La procedura richiesta, di ordinamento mediante selezione del minimo. procedure P1(var V1:Vett); var i,j:Integer; begin for i:=n downto 2 do begin j:=massimo(V,i); swap(V[i],V[j]); end; end;