Oefening 5: paranoïde androïde

Doel

Methodes ontwerpen en implementeren. Recursieve methodes bestuderen.

Opdracht

  1. Maak methodes voor code om een kredietkaartnummer te controleren.
  2. Implementeer een recursieve methode om de faculteit van een getal te berekenen.

Methodes

  1. Een kredietkaartnummer volgt bepaalde regels waardoor typfouten gemakkelijk achterhaald kunnen worden.
    1. Een kredietkaartnummer bestaat uit 13 tot 16 cijfers.
    2. Een kredietkaartnummer begint met:
      1. Een 4 voor VISA
      2. Een 5 voor Mastercard
      3. 37 voor American Express
      4. Een 6 voor Discover kaarten
    3. Een mod10 check die de volgende regels volgt:
      1. Tel alle cijfers op een oneven positie (van rechts naar links) op.
      2. Verdubbel elk cijfer op een even positie (van rechts naar links). Indien het resultaat bestaat uit twee cijfers, tel deze dan met elkaar op.
      3. Tel de sommen van stap 3.1 en 3.2 met elkaar op.
      4. Indien het resultaat van stap 3.3 deelbaar is door 10 dan is de mod10 check geslaagd.
  2. Een voorbeeld: 4388576018410707
    1. Bestaat uit 16 cijfers: ✓
    2. Begint met een 4: ✓
    3. mod 10 check: ✓ kredietkaartnummer validatie mod10 check

  3. Maak een analyse van het algoritme om een kredietkaartnummer te valideren. Probeer uit het algoritme methodes te distilleren.

    1. Beschrijf eerst in woorden hoe de methode gebruikt wordt. Welke parameters worden gebruikt? Welke waarde wordt teruggegeven? Wat is de naam van deze methode? Schrijf deze uit als Javadoc, zie Java oef. 2
    2. Bedenk vervolgens hoe deze methode zou moeten werken. Bedenk een eenvoudig voorbeeldje die je met de hand kan berekenen. Deze waarden kan je gebruiken om de methode te testen.
    3. Schrijf de implementatie van de methode.

    4. Een voorbeeld:

      1. In het algoritme voor de validatie van een kredietkaartnummer wordt heel veel het cijfer op een bepaalde positie in een getal gevraagd. Het getal is een parameter, de positie ook. Het cijfer op de positie is het resultaat van de methode, i.e. de terugkeerwaarde. Doordat met grote getallen wordt gewerkt, wordt het type long gekozen voor het getal. Een positie en een cijfer kunnen met een int voorgesteld worden.
        /**
* Haalt het cijfer op een bepaalde positie in een getal op
* @param getal
* @param positie > 0 && positie < aantal cijfers in het getal
* @return het cijfer op de positie in het getal
*/
public static int haalCijferOp(long getal, int positie) {
  return 0;
}
      2. Neem een willekeurig getal, kies een aantal posities en bedenk welk cijfer dit zou moeten opleveren. Om een long literal te gebruiken moet hoofdletter L op het einde van het getal aangegeven worden.
        haalCijferOp(4388576018402626L, 1); //resultaat = 6
haalCijferOp(4388576018402626L, 2); //resultaat = 2
haalCijferOp(4388576018402626L, 5); //resultaat = 0

      3. Schrijf een implementatie om een cijfer uit een decimaal getal te halen. Probeer met enkele voorbeelden het algoritme hiervoor te achterhalen.

        1. Om de eenheden te achterhalen volstaat het om de restdeling met 10 uit te voeren. bvb. 4564 % 10 = 4
        2. Om de 10-tallen, 100-tallen en verder te achterhalen is het nodig om het cijfer op de gewenste positie op te schuiven naar de positie van de eenheden om met de vorige bewerking het cijfer zelf te achterhalen. Dit kan bereikt worden door een gehele deling uit te voeren met een macht van 10. bvb. 4564 / 10 = 456 => 456 % 10 = 6

        3. Een mogelijke oplossing wordt typisch in verschillende stappen gevonden, bvb.

          1. De positie die als parameter wordt meegegeven moet met 1 verminderd worden, als dit vergeten zou zijn dan wordt telkens het cijfer van een andere positie teruggegeven.
          2. De compiler zal zeggen dat er een int als terugkeertype beschreven staat, maar een deling van een long levert terug een long op. Voer een cast uit om dit probleem te verhelpen.
          /**
* Haalt het cijfer op een bepaalde positie in een getal op
* @param getal
* @param positie > 0 && positie < aantal cijfers in het getal
* @return het cijfer op de positie in het getal
*/
public static int haalCijferOp(long getal, int positie) {
 return (int)(getal / Math.pow(10, positie-1)%10) ;
}

          Vraag 1

          De methode haalCijferOp werkt voor decimale getallen. Welke wijzigingen zijn nodig om dit voor alle talstelsels (bvb. binair, octaal, etc.) te laten werken?
  4. Maak de nodige methodes om kredietkaartnummers te valideren.

Vraag 2

Wat is de som van alle even verdubbelde cijfers (zie stap 1.3.2) van het nummer 4388576018402626?

Vraag 3

Wat is de reden waarom het nummer 576018470706 geen geldig kredietkaartnummer is?

Recursie

  1. Een recursieve methode is een methode die zichzelf aanroept. Zie Blokken opdracht 4.
    1. Maak een methode die de faculteit van een getal recursief berekent.
    2. Maak een methode die de grootste gemene deler van een getal recursief berekent.
    3. Maak een methode die een getal van Fibonacci op een gegeven positie recursief berekent.

Vraag 4

  Waar zit de fout in deze code om de grootste gemene deler te berekenen?

/**
 * Recursieve berekening van de grootste gemene deler
 * @param x
 * @param y
 * @return grootste gemene deler van x en y
 */
public static int ggd(int x, int y) {
    if(y==0) return x;
    else return ggd(y, y%x);
}

Extra

  1. Bepaal of een String een palindroom is met een recursieve methode.
    1. Tip: Gebruik 2 parameters om de indices van de te vergelijken letters aan te duiden.

results matching ""

    No results matching ""