Scomposizione di un numero

Supponiamo di avere una sequenza v₀, v₁, ..., v_N di N+1 numeri interi, che chiameremo operandi, e un numerro intero T, che chiameremo il totale.

Diremo che il totale è ottenibile dagli operandi quando ((...(w_N op_N w_N-1)...) op₂ w₁) op₁ w₀ = T dove w₀, w₁, ..., w_N è una permutazione degli operandi e ogni operatore op_i indica una delle quattro operazioni aritmetiche di base (somma, sottrazione, prodotto e divisione intera), con il vincolo che la divisione puo' eseguita solo se il dividendo è multiplo del divisore; ovvero, 15/5 puo' essere eseguita, mentre 12/5 no). Ad esempio, data la sequenza 3, 10, -2, il totale 24 puo' essere ottenuto con (-2 + 10) * 3 = 24. Si osservi che, data una sequenza di operandi, in generale la sequenza di operazioni che permette di ottenere il totale non è unica (banalmente, 2+2=4 e 2*2=4).

1. Scrivere una funzione ricorsiva C di prototipo
   int contaScomposizioni1(int N, int v[], int T)
   che riceve in input il numero N di operazioni da eseguire per ottenere il totale T a partire dagli N+1 operandi contenuti nel vettore v[] e restituisce il numero di modi in cui può essere ottenuto il totale assumendo però che non sia possibile cambiare l'ordine degli operandi. In pratica, si devono contare le sequenze di N operzioni tali che ((...(v_N op_N v_N-1)...) op₂ v₁) op₁ v₀ = T
2. Scrivere una funzione ricorsiva C di prototipo
   int contaScomposizioni2(int N, int v[], int T)
   analoga a quella del punto 1, considerando però tutte le possibili permutazioni degli operandi.
3. Scrivere una funzione ricorsiva C di prototipo
   int contaScomposizioni3(int N, int v[], int T, int sum, int sub, int mult, int div)
   simile alla fuzione del punto 1 ma che conta solo i modi in cui si può ottenere il totale usando sum addizioni, sub sottrazioni, mult moltiplicazioni e div divisioni (ovviamente, N=sum+sub+mult+div). Come per la funzione del punto 1, l'ordine degli operandi non può essere cambiato.
4. Scrivere una funzione ricorsiva C di prototipo
   int contaScomposizioni3(int N, int v[], int T, int sum, int sub, int mult, int div)
   simile alla fuzione del punto 3, considerando però tutte le possibili permutazioni degli operandi.

-- StefanoGuerrini - 03 May 2007