HomeWork060701 < Programmazione2pz

Tags: view all tags

---++ Scomposizione di un numero

Supponiamo di avere una sequenza v<sub>0</sub>, v<sub>1</sub>, ..., v<sub>N</sub> 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<sub>N</sub> op<sub>N</sub> w<sub>N-1</sub>)...) op<sub>2</sub> w<sub>1</sub>) op<sub>1</sub> w<sub>0</sub> = T
dove w<sub>0</sub>, w<sub>1</sub>, ..., w<sub>N</sub> è una permutazione degli operandi e ogni operatore op<sub>i</sub> 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<br>
   =int contaScomposizioni1(int N, int v[], int T)= <br>
   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<sub>N</sub> op<sub>N</sub> v<sub>N-1</sub>)...) op<sub>2</sub> v<sub>1</sub>) op<sub>1</sub> v<sub>0</sub> = T
   2 Scrivere una funzione ricorsiva C di prototipo<br>
   =int contaScomposizioni2(int N, int v[], int T)= <br>
   analoga a quella del punto 1, considerando però tutte le possibili permutazioni degli operandi.
   3 Scrivere una funzione ricorsiva C di prototipo<br>
   =int contaScomposizioni3(int N, int v[], int T, int sum, int sub, int mult, int div)= <br>
   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<br>
   =int contaScomposizioni3(int N, int v[], int T, int sum, int sub, int mult, int div)= <br>
   simile alla fuzione del punto 3, considerando però tutte le possibili permutazioni degli operandi.

-- Users.StefanoGuerrini - 03 May 2007