Forumet - Finna största resultat av alla möjliga summor

Finna största resultat av alla möjliga summor

104 0 12
Jag har en tabell vid namn num, som består av 6 stycken slumpmässigt utvalda heltal. Jag har en annan tabell vid namn operators som består av fyra operatorer ( + - * / ), slumpmässigt ordnade.

Tanken är att dessa objekt ska ordnas enligt följande exempel:
num[1] operator[1] num[2] operator[2] num[3] = sum[1]
num[4] operator[3] num[5] operator[4] num[6] = sum[2]

Ett exempel på en konfiguration skulle kunna vara:

5 + 9 * 2 = sum[1]
2 / 8 * 6 = sum[2]

Nu är saken den att num kan flyttas runt obegränsat (dock uppkommer varje objekt endast en gång, så num[2] är endast med på ett ställe, även om num[2] och num[5] kan ha samma värde), medan operatorerna behåller sin position.

Vad jag behöver är nu att finna den konfiguration av num som ger största möjliga differens mellan sum1 och sum2.

För att göra detta så måste (antar jag) varje möjlig konfiguration av num utvärderas och dess resultat sparas i en lista, för att sedan plocka ut det största respektive minsta resultat på båda sidor.

Vad jag behöver hjälp med är hur jag ska kunna utvärdera alla möjliga kombinationer. Kom ihåg att det är alla möjliga kombinationer av num som ska utvärderas. operators behåller sin plats.
Citerar någon som vet allt (lite som Dhagor, fast inom andra ämnen).

AndersLkpg:

HJELPE


- - - - - - - - - - - - - - - - - Sammanslagning 1 - - - - - - - - - - - - - - - - -


anonymous:

Är extrem nybörjare på detta, men du menar att num[x] slumpas vilket heltal som helst? Ingen som helst begränsning utom just att det måste vara heltal?


Mja. För tillfället så är num[x] endast ett positivt heltal, men detta kan komma att ändras. Hur som helst så ska det väl ändå inte spela någon roll, eller?

Spana också in:

Låt störst = 0
Låt störstarr vara den tomma listan
För varje permutation p av slumptalslistan
Låt a = p[0] op[0] p[1] op[1] p[2]
Låt b = p[3] op[2] p[4] op[3] p[5]
Om abs(a - b) > störst
Låt störst = abs(a - b)
Låt störstarr = p


Lösningsförslag i Haskell:
import Data.List (permutations)
import System.Random (randomR, newStdGen)

main = do g <- newStdGen
putStrLn $ (show . values) g
putStrLn $ (show . largestDiff . values) g

values g = snd $ foldl f (g, []) [1..6] :: [Int]
where f (g, l) x = let (n,g') = randomR (0,100) g in (g', n:l)

ops = [(+), div, (*), (-)]

largestDiff = foldl each (0, []) . permutations :: [Int] -> (Int, [Int]) where
(o0,o1,o2,o3) = (ops !! 0, ops !! 1, ops !! 2, ops !! 3)
each (old, l) x = case abs( ((x!!0) `o0` (x!!1) `o1` (x!!2))
- ((x!!3) `o2` (x!!4) `o3` (x!!5))) of
new | new > old -> (new, x)
_ -> (old, l)


Komplexitet O(n^n), men vafan. Om det finns en effektiv algoritm så orkar jag i vart fall inte tänka ut den.
Gentlernen:

Lösningsförslag i Haskell:


Pseudokoden ovan tror jag att jag förstår, då det är ungefär så som jag och Anders gör för tillfället. Däremot ditt förslag i Haskell finner jag fullständigt oläsligt, då jag aldrig förr sysslat med Haskell, och verkligen inte är någon matematiker. Tror du att du skulle kunna skriva om det i valfritt annat högnivåspråk? Förslagsvis Python eller någonting annat med god läsbarhet. [smile]