Java: recursie methode "segment max"

[Struiks]

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:

Code: Selecteer alles

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:

Code: Selecteer alles

/* 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:

Code: Selecteer alles

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):

Code: Selecteer alles

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

[EvilBro]

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?

[*gast_Struiks_*]

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.

[EvilBro]

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.