Springen naar inhoud

Java: recursie methode "segment max"


  • Log in om te kunnen reageren

#1

Struiks

    Struiks


  • >25 berichten
  • 30 berichten
  • Gebruiker

Geplaatst op 31 oktober 2007 - 16:10

Beste forumleden,

Mijn eerste bericht op dit forum.

Probleem:

Gegeven is een verzameling S met n>0 geheeltallige elementen. Deze verzameling wordt gerepresenteerd door een array s met:

int [] s; // s.length = n
Gevraagd wordt een recursieve methode die het aantal deelveramelingen van S berekent, waarvan de som van de elementen gelijk is aan een gegeven som.

Ik heb er op zitten puzzelen, maar kwam niet snel tot een goede oplossing. Als antwoord vond ik in een soort van uitwerkingsdocument het volgende:

/* We schrijven een hulpfunctie ssSumHelp met de volgende specificatie: 

int ssSumhelp(int[] rij, int som, int k){
PRE : 0 <= k < rij.length
RETURN: Aantal deelverzamelingen DV van rij[0..k) waarvoor geldt: som(DV) = sum

In onze 'hoofdfunctie' doen we nu de aanroep:
   int aantal = ssSumHelp(rij, sum, rij.length)

De daadwerkelijke code:
int ssSumhelp (int[] rij, int sum, int k){
   if ( k == 0){
	  return (sum == 0);
   }
   else {
	  return (ssSumhelp(rij, k-1, sum - rij[k-1]) + ssSumhelp(rij, k-1, sum));
  }
}

int ssSum (int[] rij, int sum) {
   return ssSumHelp(rij, sum, rij.length);
}


Mijn vraag:
1. Hoe moet ik de notatie van PRE en RETURN opvatten? (ik zie het wel vaker, en weet niet precies wat ik ermee kan):
PRE : 0 <= k < rij.length
   RETURN: Aantal deelverzamelingen DV van rij[0..k) waarvoor geldt: som(DV) = sum

2. Klopt deze methode uberhaubt wel? Ik heb het gevoel dat in de aanroep van de methode verkeerde parameters worden meegegeven...



Alvast bedankt!

groeten, Struiks

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 31 oktober 2007 - 18:30

1. Hoe moet ik de notatie van PRE en RETURN opvatten?

Als commentaar. De PRE geeft aan wat er van te voren geldt, de RETURN vertelt wat er teruggegeven wordt.

2. Klopt deze methode uberhaubt wel?

Heb je het al geprobeerd te compileren?

#3


  • Gast

Geplaatst op 31 oktober 2007 - 21:55

Als commentaar. De PRE geeft aan wat er van te voren geldt, de RETURN vertelt wat er teruggegeven wordt.
Heb je het al geprobeerd te compileren?


Het ging me niet om het daadwerkelijk afspelen van het programma, het is meer een oefening.

Bij nader inzien zie ik dat de parameters verkeerd door worden gegeven, sum en int k moeten omgewisseld worden.

Bedankt in ieder geval voor het kijken ernaar.

#4

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 01 november 2007 - 07:53

Het ging me niet om het daadwerkelijk afspelen van het programma, het is meer een oefening.

Dat snap ik en ik zeg je dat het 'afspelen van het programma' een goede oefening is.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures