[ALGORITMO]: Calcolo espressione che porta a preciso risultato

[Sephiroth984]

Ciao a tutti!

Come posso fare un programma che dati 6 numeri interi e un risultato mi dicano l'operazione che dà il risultato, oppure quella che più si avvicina (se il risultato esatto non è ottenibile)?

Ad esempio dati 2, 5, 10, 75, 2, 8 e risultato 784 mi dicano che l'operazione da fare è:

(75+5-2)*10+8/2

Non è obbligatorio usare tutti i numeri.

Tenete presente che tutte le divisioni daranno numeri interi approssimati per difetto (quindi 3/2=1)

Mi basta l'algoritmo, poi lo codifico io.. Ci sto sbattendo la testa da un bel po'..

Grazie a tutti

[king64]

Una possibile soluzione sarebbe data dal seguente algoritmo in :

  0 - DIFF=0 ' variabile che tiene conto della differenza tra risultato ottenuto
       e risultato atteso .
  1 - Genera un'espressione algebrica sottoforma di stringa in formato RPN
  2 - Calcola il risultato
  3 - Confronta il risultato ottenuto con quello desiderato
  4 - Se il risultato ottenuto è uguale a quello desiderato salva la stringa e 
       salta al punto 7
  5 - Se la differenza tra risultato desiderato è quello ottenuto è minore di DIFF 
       allora salva la stringa e poni DIFF uguale a questa differenza
  6 - Se ci sono ancora delle espressioni da generare salta al punto 1
  7 - Stampa la stringa memorizzata
  8 - Fine

Considerando che le possibili permutazioni di 6 numeri sono 6! e che le possibili operazioni da effettuare sono circa 4^5 , avremo che il pc dovrà generare circa 6!*4^5 stringhe pari a circa 8*10^5 stringhe . Saluti

[MItaly]

Non è così semplice: e le parentesi dove le mettiamo?

[king64]

L'algoritmo esposto , lungi dall' essere completo , ha bisogno di ulteriori miglioramenti prima di passare all'eventuale codifica . Tuttavia il problema da te sollevato ha già una parziale risposta nel fatto che le espressioni generate sono in formato RPN e quindi non hanno bisogno delle parentesi . Semmai l'oggetto di un'analisi più attenta dovrebbe essere l'algoritmo di generazione dell'espressione , che oltre ai simboli delle operazioni deve considerare anche eventuali livelli all'interno della stessa . Ma questo lo lasciamo al volenteroso autore del programma . Saluti

[MItaly]

Hai ragione: non avevo notato la faccenda dell'RPN (viva i vecchi calcolatori HP: uso tuttora un HP 28C per i piccoli calcoli).

Ma questo lo lasciamo al volenteroso autore del programma

Direi proprio di sì...

[Sephiroth984]

Il generare un tot di espressioni "precodificate" era arrivato anche alla mia mente..

Quello che mi interessava invece era tentare di far *ragionare* il programma.

Ossia: se tra i numeri avrò 75 e 10 ad esempio, e il risultato da ottenere sarà 755, guardando i numeri io so che innanzitutto farò 75*10, come fa la macchina a fare il medesimo ragionamento?

[king64]

L'algoritmo proposto è un algoritmo puramente combinatorio , ossia genera tutte le possibili espressioni e ne calcola il risultato , e in uscita esprime l'espressione che più si avvicina al risultato atteso . Nel momento in cui si tenta di far "ragionare" il programma allora si deve , per forza di cose , usare tecniche di intelligenza artificiale . In questo caso il tuo programma , costituito da una serie di routines , scomporrà il tuo problema in una serie di sottoproblemi , ed ogni routine ne analizzerà uno in particolare . Ci sarà quindi la routine che si occupa di ottenere il risultato come il semplice prodotto tra due fattori "abbastanza" grandi , come accennato nell'esempio da te riportato 75*10=750 , che magari passerà il prodotto ad un'altra routine che con operazioni di addizione e sottrazione cerca di pervenire ad un risultato più vicino a quello atteso , e così via . Sulla rete trovi una miriade di pubblicazioni e tutorial sull'intelligenza artificiale e su alcune tecniche e implementazioni sotto forma di algoritmi . Spero di esserti stato di aiuto . Saluti

[MItaly]

Secondo me per un programma del genere è inutile sbattersi a tirare in ballo l'IA: come ha detto king64 si tratta in tutto di 6!*4^5 (=737'280) possibilità, un numero relativamente piccolo tenendo conto dei processori attuali.

[Sephiroth984]

MItaly come già detto però non avete tenuto conto delle parentesi..

C'è una bella differenza a calcolare 2*3+4*5 oppure 2*(3+4)*5

Con l'introduzione delle parentesi le possibilità aumentano notevolmente (anche se non sono in grado di definire di quanto)

[Habanero]

Originariamente inviato da Sephiroth984
MItaly come già detto però non avete tenuto conto delle parentesi..

C'è una bella differenza a calcolare 2*3+4*5 oppure 2*(3+4)*5

Con l'introduzione delle parentesi le possibilità aumentano notevolmente (anche se non sono in grado di definire di quanto)

come ti è stato detto se usi la notazione Polacca Postifissa (RPN) le parentesi non esistono neppure...

A me quella delle permutazioni sembra la soluzione più semplice e logica. Condivido il pensiero di king64 e di MItaly