Algoritme. Maksimal positiv differanse.

[eshas]

Har problemer med å løse følgende oppgave:

Vi har ei tallrekke som angir forandring i kurs for en aksje fra dag til dag. Vi ønsker å finne hvordan vi kunne fått best fortjeneste, dvs. maksimal positiv differanse mellom kjøpspris og salgspris. Kjøp må selvsagt skje før salg.

Det meste vi kan tjene på ett kjøp fulgt av salg, er 5. Det får vi til ved å kjøpe etter kursfallet på dag 3 og selge igjen etter oppgangen på dag 7.

 

Lag og implementer en algoritme som finner hvilket kjøps- og salgstidspunkt lønner seg best.

 

Dagnr 1, 2, 3, 4, 5, 6, 7, 8, 9

Kurs -1, +3, -9, +2, +2, -1, +2, -1, -5

[qualbeen]

hmm.. hvis jeg forstod det riktig så vet du på forhånd kurs-utviklingen for den enkelte aksje? Dette er altså bare en oppgave, og har lite med den realistiske verden å gjøre?

 

Sikkert mange mulige måter å løse på, men hvordan ville du gjort det for hånd? Jeg ville først sett på Dag1. Da ligger kursen på f.eks. -1. Så titter jeg på resten av dagene, med kjøp når den koster -1, når er det da best fortjeneste? Sammenlign med dag2, så dag3, dag4, osv... hvis fortjenesten øker, så ta vare på den nye fortjenesten. Tilslutt vil du sitte igjen med maks fortjeneste hvis du kjøper på dag1.

 

Samme prosedyre som i sted, men anta at du kjøper på dag2. Finn fortjeneste ved å selge på dag3. Så dag4 osv... hele tiden tar du kun vare på maks fortjeneste. Tilslutt har du beste salgstidspunkt hvis kjøp på dag2.

 

Gjenta nok en gang, nå med utgangspunkt i dag3. osv...

 

Tilslutt har du så en tabell med høyest mulig fortjeneste fra dag1, dag2, dag3 osv. Den verdien som er høyest forteller deg altså når du bør kjøpe!

 

Tips: underveis tar du vare på kjøps- og salgs-tidspunkt, slik at du tilslutt kan printe ut datoene.

 

Håper du forstår poenget mitt. Jeg har bare rablet ned en tanke-måte, koden får du prøve å komme frem til selv. Men står du helt fast, får du spørre på ny!

[eshas]

hmm.. hvis jeg forstod det riktig så vet du på forhånd kurs-utviklingen for den enkelte aksje? Dette er altså bare en oppgave, og har lite med den realistiske verden å gjøre?

 

Sikkert mange mulige måter å løse på, men hvordan ville du gjort det for hånd? Jeg ville først sett på Dag1. Da ligger kursen på f.eks. -1. Så titter jeg på resten av dagene, med kjøp når den koster -1, når er det da best fortjeneste? Sammenlign med dag2, så dag3, dag4, osv... hvis fortjenesten øker, så ta vare på den nye fortjenesten. Tilslutt vil du sitte igjen med maks fortjeneste hvis du kjøper på dag1.

 

Samme prosedyre som i sted, men anta at du kjøper på dag2. Finn fortjeneste ved å selge på dag3. Så dag4 osv... hele tiden tar du kun vare på maks fortjeneste. Tilslutt har du beste salgstidspunkt hvis kjøp på dag2.

 

Gjenta nok en gang, nå med utgangspunkt i dag3. osv...

 

Tilslutt har du så en tabell med høyest mulig fortjeneste fra dag1, dag2, dag3 osv. Den verdien som er høyest forteller deg altså når du bør kjøpe!

 

Tips: underveis tar du vare på kjøps- og salgs-tidspunkt, slik at du tilslutt kan printe ut datoene.

 

Håper du forstår poenget mitt. Jeg har bare rablet ned en tanke-måte, koden får du prøve å komme frem til selv. Men står du helt fast, får du spørre på ny!

7713000[/snapback]

 

God svar, men hvordan skrive det i kode. Har ikke peiling

[Patton]

En lite begynnelse:

 

public void printMostProfitableBuyAndSalesDays(int[] rates) {
    
    // Første løkke fra dag en (array index = 0) til nestsiste dag
    // som tilsvarer alle dagene du kan kjøpe
    for (int buyDay = 0; buyDay < rates.length-1; buyDay++) {

        // For hver dag du kan kjøpe må du teste alle resterende dager
        // tom. siste dag for salg
        for (int sellDay = buyDay+1; sellDay < rates.length; sellDay++) {
               // Sjekk profitt her. Bør deklarere noen 
               // variabler inni løkkene og før løkkene
               // for å beregne den største profitten
        }
    }
}

Endret 14. januar 2007 av Patton

[zissou]

hmm.. hvis jeg forstod det riktig så vet du på forhånd kurs-utviklingen for den enkelte aksje? Dette er altså bare en oppgave, og har lite med den realistiske verden å gjøre?

 

Det har alt å gjøre med den realistiske verden Dette er kjent som the maximum subsequence sum problem. Som qualbeen sier så er det mange løsninger på dette. De fleste algoritmene er like raske på veldig liten input, men varierer ekstremt på større input.

 

Her er en delvis løsning med én for-løkke, opprinnelig skrevet av M.A.Weiss (algoritme-analyse boka hans er å anbefale). Jeg plottet inn kursverdiene fra post 1 inn i et array. Programmet skal skrive ut tallet 5 som blir beste fortjeneste. Det som gjenstår da er å legge til kode som skriver ut kjøp- og salgstidspunkt. Det kan du jo prøve på selv. Beste måten å lære på er å prøve og feile

 

Z.

 

 

/**
 * Linear-time maximum contiguous subsequence sum algorithm
 */

class MaxSubsequenceSum {

public static void main(String[]args) {

   int[]kursArray = {-1, 3, -9, 2, 2, -1, 2, -1, -5};

   System.out.println("Max subsequence sum: " + maxSubSum(kursArray));
}


public static int maxSubSum(int[]a) {

 int maxSum = 0, thisSum = 0;

 for(int j=0; j<a.length; j++) {

 	thisSum += a[j];

 	if (thisSum > maxSum)
   maxSum = thisSum;
 	else if (thisSum < 0)
   thisSum = 0;

 }

 return maxSum;

}

} // slutt klasse MaxSubsequenceSum