Rekursjon for å finne største par av summen

Her kan du stille spørsmål vedrørende matematikken som anvendes i fysikk, kjemi, økonomi osv. Alle som har kunnskapen er velkommen med et svar.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Leonhard_Euler
Noether
Noether
Innlegg: 24
Registrert: 26/03-2018 18:50

Jeg er litt usikker på om det er greit å spørre om dette her fordi er en algoritme-oppgave som jeg lurte på hvordan man løser.

Oppgaven: Hvis du har en liste med tall (array av int) f. eks : {1,2,3,4,6,100} hva er den største "par av summen" du kan få?
Med par av sum menes sum av to delmengder som er like store. Det er ikke nødvendig å bruke opp alle elementer, så du kan la være å bruke noen av tallene dersom det er gunstig.
For eksempel fra listen over er største par av summen {2,6} og {1,3,4}. Fordi 2+6 = 1+3+4. Da er 8 største par av summen det går an å lage og da er svaret 8 i dette tilfellet.

Jeg trenger bare hjelp med å sette opp den rekursive relasjonen.

Jeg skjønner at det er tre valg: inkludere et element i 1. delmengde, inkludere elementet i 2. delmengde, ikke inkludere i noen av delmengdene. Men jeg skjønner ikke helt hvordan det skal føre fram noen steder.

Setter stor pris på all slags hjelp :)
[tex]\ln(-1)=i\pi[/tex]
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Det finnes flere måter å angripe dette på, men mye av koding handler om å ta et problem, og bryte det opp i mindre problemer.

Fint eksempel her:

1. Lag en algoritme som finner alle delmengde-summer
2. Sorter resultatene etter sum i synkende rekkefølge
3. Løp gjennom resultatlista og stopp så fort du finner en repetert sum

Steg 1 her kan brytes opp i enda mindre steg.

Steg 1 er der vi kan introdusere rekursjon, fordi det vi er ute etter er å finne mengdesummen av alle mengdene i potensmengden til tallsettet du starter med. Og potensmengden til en mengde kan defineres rekursivt.

Så det kan se ut som:

1a. Lag en funksjon som gir deg potensmengden til en mengde, definert rekursivt
1b. Finn mengdesummen av alle mengdene i potensmengden
Bilde
Leonhard_Euler
Noether
Noether
Innlegg: 24
Registrert: 26/03-2018 18:50

Tusen takk for svaret. Trengte bare litt oppklaring på det med en potensmengde. Jeg visste ikke hva en potensmengde var, så jeg søkte det opp. Usikker på om jeg har forstått det riktig, men hvis jeg har forstått dette riktig, så ser jeg et problem.

La listen være {1,2,3,3}.

Da vil {1,2,3} og {3,3} vil være i potensmengden. 1+2+3 = 3+3, så svaret ifølge denne algoritmen være 6.
Men problemet er at vi bruker samme 3-ern i begge delmengder. Så fasit svar er egentlig 3, mens vi får 6.

Noen forslag til hvordan man kan løse dette? (hvis det i det hele tatt er et problem).
[tex]\ln(-1)=i\pi[/tex]
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Ah, ja jeg tror ikke du nevnte det kriteriet innledningsvis.

Du må i så fall skille de to 3erne ved hjelp av indeksen de ligger på. I lista [1, 2, 3, 3] vil de ha indeks på 2 og 3 respektivt.

Men du må være forsiktig med terminologien her. Slik du har presentert oppgaven, så ser det ut som en oppgave innen mengdelære. Du bruker også {krøllparentes} som er slik vi representerer mengder på listeform. Men repeterte elementer er ikke en ting i mengder. De har per definisjon kun unike elementer.

Hvis du har "oversatt" oppgaven med egne ord, så kan det være nyttig å copy/paste oppgaven ordrett i stedet.
Bilde
Svar