Esercitazione undicesima

tecnica

Esercitazione undicesima

In questa esercitazione è presentata la codifica in Pascal di un programma che, data in ingresso una sequenza di numeri interi, tramite un algoritmo iterativo detto di " brute force " stampa tutte le possibili sottosequenze crescenti e restituisce il valore della ISS massima .

Programma ricerca sottosequenza massima ( XI )

program sottosequenza ;

uses crt ;

type vet = array [ 1..9 ] of integer ;

var i, n, m, s, c, h, lung, lungmax : integer ;

var v, w : vet ;

procedure find (var w :vettore ; x :integer ) ;

begin

f := 0 ;

repeat f := f + 1 ;

until    b [ f ] = 0 ;

b [ f ] := x ;   

end ;

begin

clrscr ;

for i := 1 to 9 do begin

writeln ( ' Inserire il ', i,' numero ' ) ;

readln ( h );

v [ i ] := h ;

end ;

for i:=1 to 9 do w [ i ] := 0 ;

lungmax := 1 ;  

writeln (' Tutte le possibili sottosequenze ordinate sono: ') ;

for i := 1 to 9   do begin

n := v [ i ] ;

w [ 1 ] := n ;

lung := 1 ;

for s := i+1 to 9 do begin

m := v [ s ] ;

if n < m then begin

find ( w, m ) ;

n := m ;

lung := lung + 1 ;

end ;

if lungmax < lung then lungmax := lung ;

end ;

for c := 1 to 9 do if w [ c ] < > 0 then write ( w [ c ], ' ' ) ;

writeln ( ' ' )

for c := 1 to 9 do w [ c ] := 0 ;

end ;

writeln ( 'La più grande sottosequenza crescente ha lunghezza = ', lungmax ) ;

readln ;

end .

Esempi pratici

Inserire il 1 valore :

Input

Inserire il 2 valore :

Input

Inserire il 3 valore :

Input

Inserire il 4 valore :

Input

Inserire il 5 valore :

Input

Inserire il 6 valore :

Input

Inserire il 7 valore :

Input

Inserire il 8 valore :

Input

Inserire il 9 valore :

Input

Tutte le possibili sottosequenze ordinate sono :

Output

4, 7, 10, 11, 12, 45

3, 7, 10, 11, 12, 45

7, 10, 11, 12, 45

10, 11, 12, 45

11, 12, 45

12, 45

La più grande sottosequenza crescente ha lunghezza 6