Lehrzeit

Schule & Informatik

Informatikaufgabe 7

Aus privaten Gründen leider mit Verspätung, aber immerhin.

Aufgabe
Schreibe eine Methode erzeugeZahlPalindrom(int n), die bei Eingabe einer Zahl n eine zufälliges Palindrom der Länge n ausgibt. Als Buchstaben des erzeugten Wortes können die Ziffern 0,1,…9 benutzt werden.

 

Beispiel

erzeugeZahlPalindrom(7) ergäbe 8374738

erzeugeZahlPalindrom(10) ergäbe 0139449310

Das Ganze lässt sich natürlich auch mit Buchstaben programmieren, dann muss man „nur noch“ die Zahlen in Buchstaben umrechnen oder die Buchstaben in einem Feld verwalten.

Gedacht ist es als Übung zum Thema Zählwiederholung. Es kann aber auch rekursiv programmiert werden. Interessant wäre dann ein Laufzeitvergleich (Zeit in Nanosekunden oder Rechenschritte). Dann würde das Thema in Bayern in den letzten Abschnitt von 12/2 fallen.

4 Kommentare

  1. Sehr hübsch! Die Laufzeitmessung kann man sicher in jeder Klasse durchführen, die die Palindrom-Aufgabe bearbeiten kann (ist ja nur ein unkomplizierter Befehl + vorher-nachher-Subtraktion).
    Wie stellst du dir die Erhebung der Rechenschritte vor? Es sind ja unterschiedlich komplexe Rechenoperationen beteiligt, ich wüsste nicht, wie ich einen validen Vergleich zweier Schülerprogramme anstellen könnte. Gibt es da eine sinnvolle Möglichkeit?

    • Na ja, die „Rechenschrittmessung“ ist auch nur so eine circa Angabe. Ich führe eine gloable Variable ein, die pro Rechenschritt hochgezählt wird. Das ist zwar recht ungenau, aber immer noch besser als die ganzen störenden anderen Prozesse, wenn ich eine zeitliche Messung mache. Da habe ich oft das Problem, dass irgendwelche regelmäßig auftauchenden Systemprozesse die Messung total verfälschen.
      Ich würde also mit den Schülern definieren „was ist überhaupt“ ein Rechenschritt, das dann von den Schülern anwenden lassen und eine Messung für unterschiedliche große Palindrome automatisiert machen lassen. Wenn man die Ergebnisse ausgeben lässt, kann man sie recht einfach in Excel oder so importieren und auswerten: Ist das Wachstum linear oder exponetiell oder …. So bekomme die Schüler ganz gut einen Einblick, ob sie ordentlich programmiert haben oder nicht. U sie merken, das kryptische Variablen kein gutes und damit schnelles Programm ausmachen 😉

  2. Ich glaube, dieses Vorgehen ist problematisch (ich weiß natürlich auch kein besseres 🙂 ), da du nicht sagen kannst, dass eine Addition genau so aufwändig/zeitintensiv ist wie die Erzeugung einer Zufallszahl (-> Elementaroperationen). Letztlich geht es ja immer um die Frage der Zeitkomplexität (wie verändert sich die Rechenzeit bei zunehmendem Eingabe-/Datenvolumen).

    Deshalb würde ich nach reiflicher Überlegung zum Vergleich verschiedener Schülerlösungen doch auf die Zeitmessung zurückgreifen. Voraussetzung ist eben, dass alle die gleiche Hardware-Konfiguration haben. Das Problem der Verzerrungen kannst du minimieren, indem du die Zeitmessung einfach mehrfach durchführst, also die Zeit, die ein Prozess braucht, z.B. 10.000 mal misst und dann den Durchschnitt errechnest. Das führt für den aktuellen Kontext zu brauchbaren Werten. Beispiel in Java:

    import sun.security.util.BigInt;

    /**
    *
    * @author bnetz
    */
    public class Schleife
    {
    // rounds: Wie oft wird der prozess gemessen?
    protected int rounds = 1000000;
    // runden: Wie oft wird im Prozess eine Schleife ausgeführt?
    protected int runden = 100;
    // sammlung: Array mit allen Messergebnissen (in Nanosekunden)
    protected long[] sammlung;

    /**
    * Konstruktor
    */
    public Schleife()
    {
    sammlung = new long[this.rounds];
    }

    /**
    * Ruft den Prozess rounds mal auf und misst jedes mal die Zeit
    */
    public void mehrfachmessung()
    {
    for (int r = 0; r < this.rounds; r++)
    {
    long start = System.nanoTime();
    this.prozess();
    long endzeit = System.nanoTime();
    long dauer = endzeit - start;
    // syso-Ausgabe verzerrt Ergebnisse, deshalb besser nicht:
    // System.out.println("DAUER: " + dauer);

    // Sammlung d. Messergebnisse im Array benötigt natürlich auch Rechenzeit
    this.sammlung[r] = dauer;
    }
    this.auswerten();
    }

    /**
    * Der Prozess
    */
    public void prozess()
    {

    double dings = 0;
    for (int i = 0; i < this.runden; i++)
    {
    // Prozess, wird runden mal ausgeführt
    dings = dings + Math.random();
    }
    }

    public void auswerten()
    {
    // durchschnitt
    long sum = 0;
    for (int ind = 0; ind < this.sammlung.length; ind++)
    {
    sum += this.sammlung[ind];
    }
    long durchschnitt = sum / this.sammlung.length;
    System.out.println("durchschnittliche Dauer der Messung in Nanosekunden: " + durchschnitt);
    }
    }

    Um die von dir angesprochenen Verzerrungen durch unkontrollierbare System-/Netzwerkaktivität auszuhebeln, empfiehlt es sich wahrscheinlich, die Anzahl der Messungen sehr hoch zu setzen und den zu messenden Prozess sehr „kurz“ zu gestalten (also z.B.: 1.000.000 Messungen einer 100er-Schleife ist besser als 100 Messungen einer 1.000.000er-Schleife).

  3. Ich habe meine Schüler zuerst mal mit dem Sekundenzeiger der Armbanduhr messen lassen, wie lang der Methodenaufruf dauert. Ganz konkret. Als das zu unbefriedigend wurde, haben wir beide Varianten ausprobiert, die Zählvariable und das Zeitmessen mit System.nanoTime() – haben beide Vor- und Nachteile. Eine Messreihe hat ergeben, dass bei wachsendem n einer Funktion (weiß nicht auswendig, welche das war) die Differenz zwischen *minimaler* Zeit für den Durchlauf und der *durchschnittlichen* Zeit immer größer wurde. Bei längerer Laufzeit proportional mehr Zeit für Unterbrechung durch andere Prozesse oder Threads?

    In der theoretischen Informatik interessiert ja nur die Anzahl der Schleifendurchläufe, mehr oder weniger, da ist eine Zählvariable praktischer.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.

*

© 2017 Lehrzeit

Theme von Anders NorénHoch ↑