Hjelp til løsing av algoritmeoppgaver.

[Mælm]

Hei, driver med en algoritmeøving i Informatikk-faget ved NTNU. Har slitt en del på denne nå og håper noen kan hjelpe meg med denne?)

 

a) Finn en algoritme for ̊a løse følgende problem: Gitt et positivt heltall n, finn den listen av positive heltall hvis produkt er det største blant alle listene av positive heltall hvis sum er n. For eksempel, dersom n = 4, er listen [2,2] eller [4] siden 4 er større enn 1⇤1⇤1⇤1 og 2⇤1⇤1. Dersom n = 5, er listen [2,3].

 

) Hvordan ser listen ut for n = 2001?

 

Tips anyone?

 

Mange takk:)

[MailMan13]

Noe sånt?

 

Start på begynnelsen av listen og se om det første elementet er starten på en subliste med sum n ved å iterere forover og summère til du når når/kommer over n.

 

Hvis du treffer n, beregn produkt, sammenlign og sett maks.

 

Gjenta for hvert element forover i listen.

 

Når du når enden av listen uten å nå n i sum er du ferdig.

[torbjørn marø]

Det skulle ikke forundre meg om produktet er

 

173730831405132118815373776071865153615300387419065905687710087

166707836623289148702615389784109976552584047205334840526945422

168197137483258697359441655612110654702123680534858213112937504

004339726583101483280773630554712349811625170226070827470568293

321706714611052263643110057953160273766853344255190096347035789

4587

 

Men det har jeg kommet frem til å tenke gjennom problemet og kommet opp med en generell antagelse, og har ingen algoritme klar for å bevise det.

 

Håper du poster løsningen du kommer opp med, for det var en interessant oppgave.

 

Tallet fant jeg slik (i clojure):

 

(reduce * (repeat (/ 2001 3) 3))

 

Selv om hypotesen min holder er ikke dette en god nok algoritme - den fungerer bare her fordi 2001 er delelig på 3.

Endret 18. oktober 2011 av torbjørn marø

[GeirGrusom]

Jeg må bare skrive ut oppgaven slik jeg har forstått den, rett meg gjerne om jeg tar feil:

 

Du har et gitt positivt heltall, n

Utifra dette, må en regne ut alle rekker hvor summen er n, for eksempel for 5:

1 1 1 1 1

1 1 1 2

2 1 2

3 2

1 1 3

1 4

5

 

Utifra denne listen, finn den listen med det høyeste produktet, i dette tilfellet [3, 2]

 

Korrekt?

 

Kanskje ikke en optimal løsning, men en kan danne et uyttrykkstre og redusere det. Det er sikkert en enklere, mer matematisk løsning dog.

Endret 18. oktober 2011 av GeirGrusom

[torbjørn marø]

Korrekt?

Det var slik jeg forstod det også..

[asicman]

En (dum) algoritme kan være å bygge settet av sett slik:

 

f(1) = [1]
f(2) = [1,f(1)]
f(3) = [1,f(2)],[2,f(1)]
f(4) = [1,f(3)],[2,f(2)],[3,f(1)]
f(5) = [1,f(4)],[2,f(3)],[3,f(2)],[4,f(1)]
osv.

 

Deretter beregner man produktet av hvert sett i dette settet og sorterer det.

 

F.eks. noe slik (bruker bare lister)

 

(defun sums (n)
 (if (= n 1) '((1))
     (loop for x from 1 to (1- n) 
        append (mapcar #'(lambda (n) (cons x n)) (sums (- n x))))))

F.eks. for verdien 5 får man:

 

(sums 5)
=> ((1 1 1 1 1) (1 1 2 1) (1 2 1 1) (1 3 1) (2 1 1 1) (2 2 1) (3 1 1) (4 1))

Sorterer man denne etter produkt (jeg tar med den orginale listen i cdr for å finne fram etterpå) får man:

 

(sort (mapcar #'(lambda (l) (cons (apply #'* l) l)) (sums 5)) #'> :key #'first)
=>
((4 2 2 1) (4 4 1) (3 1 3 1) (3 3 1 1) (2 1 1 2 1) (2 1 2 1 1) (2 2 1 1 1)
(1 1 1 1 1 1))

Dvs at verdiene [2,2,1] og [4,1] gir begge det høyeste produktet 4.

 

Algoritmen og implementasjonen er ikke spesielt god, den conser masse så hvis jeg kjørte den for 2001 ville jeg sikkert brukt mer memory enn hva jeg har En optimalisering er å bygge listen på stack'en samt beregne produktet etterhvert som man går og gjøre de mest attraktive veiene først.

 

Hvis man tenker mer på problemet finner man sikkert ut en del matematiske egenskaper som kan hjelpe på en bedre algoritme og implementasjon.

[torbjørn marø]

(sort (mapcar #'(lambda (l) (cons (apply #'* l) l)) (sums 5)) #'> :key #'first)
=>
((4 2 2 1) (4 4 1) (3 1 3 1) (3 3 1 1) (2 1 1 2 1) (2 1 2 1 1) (2 2 1 1 1)
(1 1 1 1 1 1))

Dvs at verdiene [2,2,1] og [4,1] gir begge det høyeste produktet 4.

Hvor er [3,2] som er det riktige høyeste produktet 6?

[asicman]

Hvor er [3,2] som er det riktige høyeste produktet 6?

 

Algoritmen min var helt klart ikke korrekt. Jeg tenkte ikke nøye nok igjennom det. Hvis du ser etter så ser du at jeg alltid har med 1:

 

f(1) = [1]
f(2) = [1,f(1)]
...

 

Det vil derfor alltid være med minst en 1. Det er selvsagt mulig å generere alle permutasjoner av N tall mindre enn N og sjekke om summen er N, men det blir enda værre når det gjelder minneforbruk. Det er sikkert en mer elegant måte å gjøre på.

[asicman]

Er ikke algoritmen bare slik?

 

Dersom N er partall: [N/2,N/2]

Dersom N er oddetall: [(N+1)/2,(N-1)/2]

 

For 2001 er produktet 1001000 og tallene [1001,1000]

 

Eller er forslaget like dumt som mitt forrige?

[D3f4u17]

Det blir vel ikke helt riktig? Du får et høyere produkt dersom listen består av 667 3-tall, for eksempel.

 

 

 

Eller misforstod jeg?

[asicman]

Nei, du har rett. Det er vel det samme som TM skrev tidligere ved ettersyn.

[MailMan13]

Vil ikke alle tallene i rekka være primtall? Produktet av faktorene i et tall være mindre eller lik produktet?

 

Da kan man kanskje generere mulige rekker av primtall som gir riktig sum med mindre ressursbruk...

[srbz]

Vil ikke alle tallene i rekka være primtall? Produktet av faktorene i et tall være mindre eller lik produktet?

 

Da kan man kanskje generere mulige rekker av primtall som gir riktig sum med mindre ressursbruk...

Hmm. For listen som gir høyest produkt vil nok ihvertfall alle tallene være primtall ettersom n*m >= n+m for alle heltall n,m > 1 (åpenbart)

n*m > n+m for alle heltall n,m > 2

Mao. vil et tall i en liste (en addend) som ikke er et primtall kunne deles opp i mindre addender som gir samme sum, men høyere produkt om de ganges sammen.

 

Si at n = 15. Da har vi bl.a. listen [5,10]. 5*10 = 50

Men siden 10 ikke er et primtall vil vi heller ønske å dele 10 opp i mindre addender som er primtall, slik at n = 15 f.eks. får listen [5,5,5]. Da har vi at 5*5*5 = 75

Det vil ikke si at [5,5,5] nødvendigvis gir det høyeste produktet for alle lister der n = 15, men du ser at du kan fullstendig overse listen [5,10], nettopp fordi den inneholder et delelig tall (ikke primtall), når du kun er på jakt etter den ene listen som gir høyest produkt.

[torbjørn marø]

Si at n = 15.

 

user=> (let [lst [3 3 3 3 3]]
        { :sum (reduce + lst)
          :product (reduce * lst) })
{:sum 15, :product 243}

[Horrorbyte]

Jeg hadde faget i fjor, så jeg fant frem besvarelsen min.

 

a)

1: x = n/3

 

2: Hvis x er heltall: gå til steg 3

Eller hvis x har desimaler 33333.... : gå til steg 4

Eller hvis x har desimaler 66666.... : gå til steg 5

 

3: Liste = [3...] med x antall 3-ere

4: Liste = 3...2,2] med x-1 antall 3-ere

5: Liste = [3...2] med x antall 3-ere

 

 

b)

2001/3 = 667

[3...] med 667 3-ere

[torbjørn marø]

Jeg hadde faget i fjor, så jeg fant frem besvarelsen min.

Herlig med pseudokode som bruker goto

 

Det er dette jeg har antatt er en gyldig løsning også. Men skulle gjerne sett et bevis for at algoritmen er riktig...

[asicman]

Svaret var jo enkelt, men sikkert ikke så enkelt å resonnere seg fram til. Enig med TM, skulle gjerne sett et bevis på hvorfor akkurat 3 er det som gir høyest produkt. 2 og 5 er også primtall, men gir ikke høyest produkt.

 

En rekursiv beskrivelse av algoritmen blir ganske enkel (selv om den ikke gir den mest effektive implementasjonen):

 

(defun sums (n)
 (if (<= n 3) (list n)
     (cons 3 (sums (- n 3)))))

 

Eller i Haskell for de som ikke tåler parenteser:

 

sums :: Integer -> [integer]

sums n =  if n <= 3 then [n]
         else 3 : sums (n - 3)

[asicman]

Svaret var jo enkelt, men sikkert ikke så enkelt å resonnere seg fram til. Enig med TM, skulle gjerne sett et bevis på hvorfor akkurat 3 er det som gir høyest produkt. 2 og 5 er også primtall, men gir ikke høyest produkt.

 

En rekursiv beskrivelse av algoritmen blir ganske enkel (selv om den ikke gir den mest effektive implementasjonen):

 

(defun sums (n)
 (if (<= n 3) (list n)
     (cons 3 (sums (- n 3)))))

 

Eller i Haskell for de som ikke tåler parenteser:

 

sums :: Integer -> [integer]

sums n =  if n <= 3 then [n]
         else 3 : sums (n - 3)

 

Leste ikke svaret fra Horrorbyte nøye nok, trodde det ved første øyekast var mer uniformt. Dersom det er 3...,2,2 som gir høyest produkt. Da må man sjekke på (rem n 3).

[asicman]

Alle rem 3 lik 1 vil ha 4 som rest etter subtraksjonen og 2+2=2*2=4 så man kan like godt skrive [4] som [2,2] så det burde bli noe som:

 

 

(defun sums (n)
 (if (<= n 4) (list n)
     (cons 3 (sums (- n 3)))))

 

Eller?

[torbjørn marø]

Eller i Haskell for de som ikke tåler parenteser

Lurer på om det virkelig finnes noen som synes Haskell er enklere å forstå enn Lisp?! Skjønner ikke at det er mulig..