Nekromanti Programmering - är jag helt efterbliven?

[krank]

Jag läser Programmering och datastrukturer nu. Skoj och utmanande kurs, men nu har jag stött på en uppgift jag tydligen är för efterbliven för att kunna få ihop:

Skriv ett program SumMain som innehåller en rekursiv metod som beräknar summan av heltalen 1+2+3+4+ ... +N. Beräkningen skall ske enligt följande: summan 1-till-N är lika med summan 1-till-(N/2) plus summan (N/2+1)-till-N.

Jag får inte ihop det här. Alls.

Alltså, det enklaste sättet att räkna ut 1+2+3+4+...+N finns i boken. Det är ganska straightforward. Typ, n + sum(n-1) och så rekursivt på det. Där är jag med, fattar hur det funkar, och så.

Men... jag ser inte hur jag ska kunna använda EN metod för att både beräkna 1-till-(N/2) och (N/2+1)-till-N. Antingen behövs två metoder, eller en överladdad metod, eller så måste jag ha en extra extern variabel som håller reda på original-N. Och det känns ju sisådär.

Någon som känner sig manad att fatta var jag tänker fel? Kom igen, det finns väl programmerare här? Jag är inte helt pantad liksom, jag vill inte ha en komplett lösning. jag vill bara fatta hur det är tänkt.

 

[Gurgeh]

Spontant: Om grundfunktionen är att räkna ut summan från 1 till N på det angivna sättet så krävs det även en annan funktion som räknar ut summan från M till N.

Men jag har inte programmerat på flera år. (Och är beredd att erkänna att jag mycket väl kan ha tänkt extremt fel.)

/tobias

 

[krank]

Spontant: Om grundfunktionen är att räkna ut summan från 1 till N på det angivna sättet så krävs det även en annan funktion som räknar ut summan från M till N.

Det är pretty much min tanke också, ja. Plus att jag inte kommer på hur man gör det heller utan att ha med en extern variabel som minns värdet av M (kan inte räkna ut det i den rekursiva funktionen, för då minskar ju M hela tiden).

Så... Jag tycker inte att det här verkar vara en så kul uppgift. Eller, öh, lösbar.

 

[hakanlo]

Typ så här tror jag:

sum(int from, int to)
{
if (from == to)
return to;
else
return sum(from, to/2) + sum(to/2+1, to);
}

anropas som sum(1, N)

Edit: krävdes några ändringar på vägen...
Edit 2: Nu då!
/Håkan

 

[krank]

Typ så här tror jag:

sum(int from, int to)
{
if (from == to)
return to;
else
return sum(from, to/2) + sum(to/2+1, to);
}

anropas som sum(1, N)

Edit: krävdes några ändringar på vägen...
Edit 2: Nu då!
/Håkan

Får det inte att funka... Stack overflow.

 

[hakanlo]

Host. Körde torrkod nu.... Men alltså, du har ju rätt i det du skrev om problemet, som jag tolkar det. Poängen jag egentligen ville göra var väl att funktionen anropas som sum(1,N) i stället för sum(N), vilket jag tyckte kändes som en rimlig tolkning av uppgiften.

Äh, tusan, har ingen programmeringsmiljö just nu, men nytt försök:

sum(int from, int to)
{
if (to > from)
throw new FuskException()
if (from == to)
return to;
else
return sum(from, from + (to - from)/2) + sum( from + (to - from)/2 +1, to);
}

Nu har jag säkert dragit iväg från din uppgift... men det var värt ett försök.

 

[Gurgeh]

Får du stack overflow även om N är en jämn multipel av 2?

Edit: Glöm det som står här.

/tobias

 

[Gurgeh]

Funktionen fungerar inte.

Exempel: sum(3,4) kommer att ge det rekursiva anropet att räkna ut sum (3,2) samt sum(3,4). Vilket kommer överflöda stacken så det bara sjunger om det.

/tobias

 

[hakanlo]

Jo.... i version två försökte jag fixa det, om jag nu inte dragit utanför uppgiften...

 

[krank]

Jo.... i version två försökte jag fixa det, om jag nu inte dragit utanför uppgiften...

Jag har mailat lärarinnan och bett om ett förtydligande och/eller ledtråd, samt postat på kursens forum.

Under tiden har jag lagt ner för dagen (tror jag) och fortsätter med nästa uppgift imorgon.

 

[Ram]

Meh, jag är iofs mjukis men vet ändå inte vad du menar med en metod...

Denna funktion funkar dock:
int SumMain(int start, int end)
{
if (start != end)
{
return SumMain(start, ((start+end)/2)) + SumMain(((start+end)/2)+1, end);
}
return start;
}

(Dvs exakt det som hakanlo sa fast i c och verifierat )

 

[claes]

Meh, jag är iofs mjukis men vet ändå inte vad du menar med en metod..

Metod är samma sak som funktion. En metod tillhör en klass (ett objekt) och används alltså i objektorienterade språk.

 

[krank]

Meh, jag är iofs mjukis men vet ändå inte vad du menar med en metod...

Denna funktion funkar dock:

Skrev om den till Java (krävdes inte mycket), och den funkar där också. Rent tekniskt tycker ju jag att den inte riktigt följer uppgiften (eftersom den inte räknar ut 1+2+3+...+N utan N1 + (N1+1) + (N1+2) + ... + N2) - just för att den kräver två variabler.

(Dessutom är jag för dum för att fatta hur den funkar, men det ska jag nog kunna styra upp under dagen...)

 

[Ram]

Meh, jag är iofs mjukis men vet ändå inte vad du menar med en metod..

Metod är samma sak som funktion. En metod tillhör en klass (ett objekt) och används alltså i objektorienterade språk.

Oki. C++ var ganska nytt när jag tog examen (länge sedan...) och jag har bara programmerat C sedan dess, men för att inte se ut som en inkompetent pajas så är det inte utan att jag tycker att jag borde googlat först...

 

[Ram]

Skrev om den till Java (krävdes inte mycket), och den funkar där också. Rent tekniskt tycker ju jag att den inte riktigt följer uppgiften (eftersom den inte räknar ut 1+2+3+...+N utan N1 + (N1+1) + (N1+2) + ... + N2) - just för att den kräver två variabler.

(Dessutom är jag för dum för att fatta hur den funkar, men det ska jag nog kunna styra upp under dagen...)

Ehm, jag förstår inte vad du menar med N1+(N1+1) osv... Det ser ut som det enda du behöver göra för att räkna ut 1 - N är att sätta N1 till 1 och N2 till N när metoden anropas för första gången...

 

[krank]

Ehm, jag förstår inte vad du menar med N1+(N1+1) osv... Det ser ut som det enda du behöver göra för att räkna ut 1 - N är att sätta N1 till 1 och N2 till N när metoden anropas för första gången...

Men alltså; vad vi har är en funktion för att räkna ut N1 till N2. Sedan KAN den användas för att räkna ut 1 till N också, men det är inte det den "gör"... om du förstår hur jag menar.

Men, jag har beslutat mig för att plocka lösningen (den funkade ju) och fortsätta med nästa uppgift istället... Ligger redan efter.

 

[Ram]

Men alltså; vad vi har är en funktion för att räkna ut N1 till N2. Sedan KAN den användas för att räkna ut 1 till N också, men det är inte det den "gör"... om du förstår hur jag menar.

Ja, men den måste vara generell för att kunna vara rekursiv. Se på 1-4. Första anropet är 1 och 4 men i första rekursionen så måste den hantera 1 och 2 samt 3 och 4 som inparametrar.

 

[krank]

Ja, men den måste vara generell för att kunna vara rekursiv. Se på 1-4. Första anropet är 1 och 4 men i första rekursionen så måste den hantera 1 och 2 samt 3 och 4 som inparametrar.

Jo, jag fattar. Det är därför jag tycker att uppgiften är felskriven. Det går inte att uppfylla både kravet att det ska vara en metod som räknar ut 1+2+3+...+N och att den är rekursiv och att den använder det sätt att räkna ut som anges.

Som det är får den vara "good enough", helt enkelt. Så hoppas jag på ett G.

 

[peta]

Men alltså; vad vi har är en funktion för att räkna ut N1 till N2. Sedan KAN den användas för att räkna ut 1 till N också, men det är inte det den "gör"... om du förstår hur jag menar.

Men då är den mer generell så mycket bättre
Vad du kan göra är en start funktion som tar bara en parameter och sätter igång den rekursiva funktionen om du vill ha en sumMain(N)

Jo, jag fattar. Det är därför jag tycker att uppgiften är felskriven. Det går inte att uppfylla både kravet att det ska vara en metod som räknar ut 1+2+3+...+N och att den är rekursiv och att den använder det sätt att räkna ut som anges.

Men tänkt så här med n+sum(n-1) så kommer du följande om du kör till 8.
(((((((1)+2)+3)+4)+5)+6)+7)+8

Om du kör sum(1, n/2)+sum(n/2+1, n) så får du
((1+2)+(3+4))+((5+6)+(7+8))
Inte så stor skillnad eller hur.

 

[Snow]

Om man är regeladvokat kan man sluta sig till följande:

* Programmet heter SumMain
* Program != metod
* Programmet ska innehålla en rekursiv metod
* Inget annat sägs om eventuellt andra metoder

Min lärare i logik hade varit stolt.

Altså kan du ha en metod som anropar den rekursiva med 1 och N.