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 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.




(sola)

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




(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.




(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