Sottoarray e Sottoinsieme di Somma Fissata¶

Sottoarray di Somma Fissata¶

Dato un intero b e un array di n interi, individuare se esiste un sottorray (elementi adiacenti) di elementi che ha somma b.

Esempio: Dato b=3 e l’array seguente -1 5 8 -9 4 1, dobbiamo rispondere “True” perché la sequenza 8,-9,4 ha somma 3.

Questo problema lo sappiamo risolvere per esempio variando le soluzioni 1 e 2 del problema del sottoarray di somma massima, ovvero per ogni coppia di indici (i,j) determinando la somma del sottoarray che comincia in i e finisce in j e controllando se tale somma è uguale a b.

Analizzando tutte le sottosequenze, otteniamo l’algoritmo seguente.

def sommafissata( a, b ):
    for i in range(0, len(a)):
        for j in range(i,len(a)):
            somma=0;
            for z in range(i,j+1):
                somma=somma+a[z]
            if(somma==b):
                return True
    return False;

print(sommafissata([-1,5,8,-9,4,1],3))

(sola)

Riusando le somme (come visto per il sottoarray di somma massima), otteniamo l’algoritmo seguente.

def sommafissata( a, b ):
    for i in range(0, len(a)):
        somma=0;
        for j in range(i,len(a)):
            somma=somma+a[j]
            if(somma==b):
                return True
    return False;

print(sommafissata([-1,5,8,-9,4,1],3))

(solb)

Sottoinsieme di Somma Fissata¶

Dato un intero b e un array di n interi, individuare se esiste un sottoinsieme (elementi non adiacenti) di elementi che ha somma b.

Esempio: Dato b=0 e il seguente array -1 5 8 -9 4 1

Dobbiamo rispondere True perché il sottinsieme di elementi 8,-9,1 ha somma 0.

def cerca( a, b ):
    for i in range(0, len(a)):
            if a[i]==b:
                    return True
    return False

def sommasottoinsieme( a, b ):
    if cerca(a, b):
            return True
    else:
            if len(a) == 1:
                    return False
            else:
                    return sommasottoinsieme( a[1:], b-a[0] ) or sommasottoinsieme( a[1:], b )

print(sommasottoinsieme([-1,5,8,-9,4,1], 0))

(solc)

La funzione con input l’array di dimensione n effettua due chiamate passando degli array di dimensione n-1. Queste chiamate al loro interno fanno lo stesso. Dunque, rappresentando l’albero delle chiamate, otteniamo un albero binario (ogni nodo interno ha due figli) di altezza n. Dunque il numero di chiamate nel caso peggiore è O(2^n).

Next Section - Performance delle Strutture Dati Python