[C] Scomposizione di un numero

[LiLyblack]

Ciao a tutti, sono alle prese con un problema ricorsivo.
Devo scrivere una funzione RICORSIVA di prototipo int contaScomp (int N, int v[], int T)
che riceve in input N operazioni per ottenere il totale a partire dagli N+1 operandi.
Gli operatori considerabili sono solo + - * / (solo la divisione intera ovvero 15/5 ammessa 15/6 non ammessa).
In pratica conta in quanti modi è possibile ottenere quel totale (senza cambiare l'ordine degli operandi)

Esempio:
v[3] = 2, 3, 8
T = 26
N = 2

risultato 1 ovvero 8*3 + 2 = 26 (26 è ottenibile solo in qusto modo).


Allora...

ho provato a ragionare in questo modo:


1) se ho 0 operazioni confronto solo se v[0] = T
2) se ho una sola operazione avro avrò al massimo 4 alla 1 combinazioni massime possibili, ciascuna che daràun risultato conrontabile con il mio totale.
3) se ho due operazioni avrò massimo 4 alla 2 combinazioni
4) se ho n operazioni avrò 4 alla n combinazioni di cui 0,1 o più possono essere il mio T.


Ragazzi, io francamente non so come si possa risolvere questo problema, non so nemmeno se il discorso sulle combinazioni è pertinente....

Il professore ci ha detto di considerare il vettore da dx a sx che è più semplce... io francamente non vedo differenza...

Spero di essere stata chiara, non chiedo che mi venga risolto il problema ma che qualcuno mi possa dare una mano a capire il ragionamento giusto da fare e a impostarlo se possibile...

Grazie.

[LiLyblack]

Nessuno è in grado di darmi una dritta?

[LiLyblack]

E' che non capisco come andare avanti, fare un tentativo, arrivare alla fine, vedere che è sbagliato e tornare indietro e riniziare da 0...

[king64]

Supposto che hai N+1 elementi , la cui configurazione non cambia , devi generare 4^N espressioni , dove 4 è il numero delle operazioni che puoi utilizzare e N è il numero dei posti delle singole operazioni , calcolare i rispettivi risultati e scegliere quella con il risultato uguale a quello di riferimento . Es:
elementi :3,3
risultato :9
N+1=2,N=1
Avremo:
3+3=6
3-3=0
3*3=9 <-- Espressione cercata
3/3=1

Saluti

[LiLyblack]

Ciao, grazie per aver risposto.
Più o meno questo l'avevo capito.. ma come posso formalizzarlo in codice e/o pseudocodice?
Quello che mi sfugge è: come possoare un tentativo, capirese è giusto, fare un'operazione, arrivare alla fine, vedere che il ris è sbagliato ed eventualmente rifare tutto da 0?

:master:

[bigmickey]

Non mi è ben chiaro l' esercizio...

I parametri che vengono passati sono consistenti?
Ossia sai già a priori che gli operandi passati , combinati in un unico modo,
ti daranno un risultato?

Mi spiego:
Se uno passa N=2 v[]=1,1,1 T=3
C'è niente da fare le operazioni sono 2 addizioni

Ma se al posto di T si passa 10 non sarà possibile trovarle...

E in questo caso particolare... N=2 v[]=1,2,3 T=6
Puoi fare sia due addizioni che due moltiplicazioni...

[LiLyblack]

Ciao e grazie per aver risposto.
Posso passare qualsiasi valore per gli operandi e qualsiasi valore per il risultato.

Per farti comprendereil testo, negli esempi che hai fatto, ti dico i risultati

Se uno passa N=2 v[]=1,1,1 T=3
C'è niente da fare le operazioni sono 2 addizioni

In questo caso la funzione deve restituire 1 in quanto le due addizioni, ovvero una sola espressione è il modo per ottenere il totale T.

Ma se al posto di T si passa 10 non sarà possibile trovarle...

In questo caso la funzione deve restituire 0 in quanto combinando in tutti i modi possibili gli operatori non c'è modo di ottenere quel totale.

in questo caso particolare... N=2 v[]=1,2,3 T=6

Proprio perché il risultato è ottenibile mediante due espressioni diverse, la funzione deve restituire 2.

Spero di essere stata chiara.
Hai qualche idea di come risolverlo?
Io ho proprio problemi a capire come generare le 4 alla n espressioni possibili.
Ho pensato ad una cosa del genere:

int contaScomp (int v[], int N, int T)
{
  if (N==0) return v[0] == T;
 else //passo induttivo - ricorsione che non ho idea di come trovare

} 

Grazie

[king64]

Una possibile struttura ricorsiva potrebbe essere implementata nel seguente modo , guardando l'espressione come una struttura arborea . Nell'esempio

v[3] = 2, 3, 8
T = 26
N = 2

avremo quindi

                               26
                             /  +  \
                           2        24
                                   / * \
                                  3      8

per cui partendo dal nodo-radice avremo , nel caso dell'esatta sequenza :

26 2 -
24 3 /
8 8 -> match=1
Ovviamente in questo caso avremo ottenuto la "duale" della sequenza cercata . Nel caso in cui volessimo la sequenza originaria , basterà scambiare + con - e * con / e viceversa . Spero di esserti stato di aiuto . Saluti

[LiLyblack]

Grazie per aver risposto.

Mmm non mi è chiara una cosa: ogni livello dell'albero (in questo caso binario) corrisponde ad un'operazione?

per cui partendo dal nodo-radice avremo , nel caso dell'esatta sequenza :

26 2 -
24 3 /
8 8 -> match=1
Ovviamente in questo caso avremo ottenuto la "duale" della sequenza cercata .

Questo potrebbe essere la chiave per risolvere il mio problema ma sono troppo dura di comprendonio...
io posso scegliere l'operazione 26-2 perchè so che fa 24 ed è il risultato giusto... ma come faccio a capire quali operatori devo scegliere?

[king64]

Originariamente inviato da LiLyblack
Grazie per aver risposto.

Mmm non mi è chiara una cosa: ogni livello dell'albero (in questo caso binario) corrisponde ad un'operazione?

Si

......
io posso scegliere l'operazione 26-2 perchè so che fa 24 ed è il risultato giusto... ma come faccio a capire quali operatori devo scegliere?

Non devi scegliere la particolare operazione . E' la tua procedura che deve farsi carico di generare l'operazione in maniera combinatoria ed aumentare il livello . Giunto all'ultimo livello se si ha un match allora si incrementa la variabile che tiene conto della numero di scomposizioni , altrimenti si torna indietro (backtracking) di un livello e si genera un'altra espressione . E cosi via fino all'esaurimento di tutte le possibili espressioni . Nell'esempio ho volutamente evidenziato quella giusta , ma in effetti è difficile che si abbia un match al primo tentativo . Potrebbe essere il caso in cui i fattori siano 3,2,1 dell'altro esempio . Spero di essere stato più chiaro . Saluti