Guido Krüger's Web Service

Programming Asssignments 4 - 6

---

(This page is available in German only. )

Aufgaben zu den Kapiteln 4 bis 6

1. [A] (Namenskonventionen). Beschreiben Sie die formalen Namenskonventionen für Bezeichner in Java. Neben den formalen Namenskonventionen gibt es informelle Konventionen (Groß-/Kleinschreibung, Verwendung von Verben, etc.), die bei der Benennung von Paketen, Klassen und Methoden eingehalten werden sollten. Studieren Sie die Ihnen bisher bekannten Quelltexte und beschreiben Sie die informellen Namenskonventionen von Java.
Aufg0401.java

2. [A] (Die Länge von Bezeichnern). Die meisten Compiler unterscheiden Bezeichner nur bis zu einer festen Maximallänge. Versuchen Sie, die signifikante Länge von Bezeichnern in Java zu bestimmen. Verwenden Sie dazu den Buchtext, die Sprachspezifikation und führen Sie eigene Experimente durch.

3. [A] (Unicode). Beschreiben Sie mögliche Besonderheiten, die ein Java-Programmierer durch die Verwendung des Unicode-Zeichensatzes für Zeichentypen und Bezeichner in Java zu beachten hat.

4. [A] (Gültige Literale finden). Beschreiben Sie, welche der folgenden literalen Konstanten in Java gültig sind und welche nicht. Geben Sie bei den gültigen Literalen deren Datentyp und bei den ungültigen den Grund für den Fehler an):

• 42
• -17
• 2+3
• 1.1*10^3
• 2.3
• 2,3
• 20
• 'Hello'
• "a"
• TRUE
• b
• false
• 3.141592
• 1.000.000
• 0,524
• 214089067
• 1.1e-10
• +13
• "Test\u000a"
• 1d
• 0x1d

5. [A] (Definite Assignment). Was versteht man unter "definite assignment" und warum handelt es sich dabei um ein bemerkenswertes Konzept?

6. [A] (Lebensdauer und Sichtbarkeit). Erläutern Sie die Begriffe "Lebensdauer" und "Sichtbarkeit" von Variablen.

7. [A] (Bindungskraft der logischen Operatoren). In der Sprache Pascal ist die Bindungskraft der logischen Operatoren UND und ODER höher als die der relationalen Operatoren. Dies hat sich in der Praxis nicht durchsetzen können. Erläutern Sie, warum diese Vorgehensweise zu Problemen führen kann und vergleichen sie sie mit der Realisierung in Java.

8. [A] (Unterschied zwischen den Operatoren >> und >>>). Worin besteht der der Unterschied zwischen den Operatoren >> und >>>? Verdeutlichen Sie dies an einem Beispiel.
Aufg0408.java

9. [A] (Verwendung des Operators +). Wie lautet die Ausgabe des folgenden Programms:

public class Test1
{
   public static void main(String args[])
   {
      System.out.println("3 + 4 = " + 3 + 4);
   }
}

10. [A] (Short Circuit Evaluation). Erläutern Sie das Konzept der Short Circuit Evaluation und seine Umsetzung in Java. Welche Rolle spielt sie beim Exklusiv-ODER-Operator?
Aufg0410.java

11. [A] (Einschränkende Konvertierungen). Was ist eine einschränkende Konvertierung? Geben Sie ein Beispiel für dabei möglicherweise auftretende Datenverluste.
Aufg0411.java

12. [A] (Divisionsoperator). Der Operator / kann sowohl für Ganz- als auch für Fließkommazahlen verwendet werden. Erläutern Sie, wie beide Varianten funktionieren und wodurch sie sich unterscheiden. Welches Verhalten zeigt der Divisionsoperator bei der Anwendung auf gemischt-typisierte Operanden?

13. [A] (Fließkommazahlen einlesen und ausgeben). Schreiben Sie ein Programm, das fünf Fließkommazahlen einliest und in umgekehrter Reihenfolge wieder ausgibt.

14. [A] (Tabellarische Ausgabe). Schreiben Sie ein Programm, das folgende Tabelle von Quadrat- und Kubikzahlen ausgibt:

          n          n^2          n^3
+++++++++++++++++++++++++++---------
          1            1            1
          2            4            8
          3            9            27

15. [A] (Berechnung der Kreisfläche). Schreiben Sie ein Programm zur Berechnung der Kreisfläche. Es soll den Radius eines Kreises vom Anwender erfragen und anschließend seine Fläche ermitteln und ausgeben.

16. [A] (Summenberechnung). Schreiben Sie ein Programm zur Berechnung der Summe der Zahlen von 1 bis n. Ihr Programm soll bis n = 1000 korrekt arbeiten. Verwenden Sie zur Berechnung nicht die Formel n * ( n + 1) / 2, sondern ermitteln Sie das Resultat durch Summierung innerhalb einer Schleife.
Aufg0416.java

17. [A] (Berechnen der Fakultät). Die Fakultät n! einer Zahl n ist definiert als Produkt der Zahlen 1 * 2 * 3 * ... * n. Schreiben Sie ein Programm, das nach Eingabe der Zahl n deren Fakultät berechnet und ausgibt.

18. [A] (Quadrat ausgeben). Schreiben Sie ein Programm, daß die Seitenlänge eines Quadrats erfragt und dann im Textmodus ein Quadrat dieser Größe ausgibt. Gibt der Anwender beispielsweise 5 ein, so soll die Ausgabe wie folgt aussehen:

*****
*   *
*   *
*   *
*   *
*****

19. [A] (Dreieck ausgeben). Schreiben Sie ein Programm, daß die Höhe eines Dreiecks erfragt und dann im Textmodus ein Dreieck dieser Höhe ausgibt. Gibt der Anwender beispielsweise 7 ein, so soll die Ausgabe wie folgt aussehen:

      *
     * *
    *   *
   *     *
  *       *
 *         *
*************

20. [B] (Datenverluste bei erweiternder Konvertierung). Kann es bei der erweiternden Konvertierung eines int in ein float Datenverluste geben? Geben ggfs. Sie ein Beispiel und begründen Sie Ihre Antwort.
Aufg0420.java

21. [B] (Darstellungsfehler). Als Programmierer wird man manchmal von Darstellungs- und Rundungsfehlern bei Fließkommazahlen überrascht. Diese entstehen dadurch, daß Fließkommazahlen nur eine begrenzte Genauigkeit und einen begrenzten Wertebereich aufweisen und zudem aufgrund ihrer internen Darstellung bestimmte rationale Zahlen gar nicht genau repräsentieren können. So ist es beispielsweise eine wichtige, aber oftmals vergessene Tatsache, daß die zwischen zwei aufeinanderfolgenden Fließkommazahlen liegenden Lücken mit zunehmender Größe der Zahl ebenfalls anwachsen. Schreiben Sie ein Programm, daß für den Datentyp float ermittelt, ab welchem Wert zwei aufeinanderfolgende float-Werte sich um mehr als 1.0 unterscheiden.

22. [B] (Kenntnisse des Compilers über die Klassenbibliothek). In Java kommt es verschiedentlich vor, daß bereits der Compiler Kenntnisse über den Aufbau von Teilen der Klassenbibliothek hat. Beschreiben Sie am Beispiel der Klasse String, welche Kenntnisse der Compiler benötigt, um String-Objekte zu instanzieren und die für Strings verfügbaren Operatoren darauf anzuwenden. Beschreiben Sie, welche Konsequenzen es hätte, wenn der Compiler keine Kenntis über den inneren Aufbau von Strings hätte.

23. [B] (Referenztypen). Alle Objekte werden in Java als Referenztypen, also als Zeiger auf das jeweilige Objekt, dargestellt. Benennen Sie die relevanten Unterschiede zwischen primitiven und Referenztypen und begründen Sie am Beispiel des Operators == exemplarisch, welche Konsequenzen die Verwendung von Referenztypen hat.

24. [B] (Dangling Else). Das folgende (sehr häßliche) Programm soll testen, ob eine Zahl 0 ist oder ob sie kleiner als 0 ist und eine entsprechende Meldung ausgeben:

public class Test1
{
   public static void main(String args[])
   {
      for (int n = -1; n <= 1; ++n) {
         if (n >= 0)
            if (n == 0) System.out.println(n + " ist 0");
         else
            System.out.println(n + " ist kleiner 0");
      }
   }
}

25. [B] (deMorgan'sche Regeln). Die deMorgan'schen Regeln gehören zu den wichtigsten Umformungsregeln logischer Ausdrücke. Tatsächlich werden Sie auch in der Praxis häufig benötigt und ein als Programmierer sollte man sie sicher beherrschen. Die Regeln beschreiben, wie UND- oder ODER-verknüpfte Ausdrücke invertiert werden können. Sie lauten:

• NICHT(a UND b) <==> (NICHT a) ODER (NICHT b)
• NICHT(a ODER b) <==> (NICHT a) UND (NICHT b)

26. [B] (Schleifen). Schreiben Sie ein Programm, das mit Hilfe geschachtelter Schleifen folgende Ausgabe erzeugt:

1 abcdefg
12 abcdef
123 abcde
1234 abcd
12345 abc
123456 ab
1234567 a

27. [B] (Primzahlbestimmung). Eine Primzahl ist eine positive Ganzzahl, die nur durch 1 und sich selbst ohne Rest teilbar ist. Schreiben Sie ein Programm, das zu einer eingegebenen Zahl bestimmt, ob es sich um eine Primzahl handelt oder nicht.

28. [A] (Perfekte Zahlen). Schreiben Sie ein Programm, das für eine eingegebene Zahl n bestimmt, ob n eine perfekte Zahl ist. Mathematiker bezeichnen alle positiven Ganzzahlen, deren Wert gleich der Summe ihrer echten Teiler ist, als perfekte Zahlen. So ist beispielsweise 6 eine perfekte Zahl, denn 6 = 1 + 2 + 3. Eine andere perfekte Zahl ist 28, denn es gilt 28 = 1 + 2 + 4 + 7 + 14. Bestimmen Sie auch die nächstgrößere perfekte Zahl über 28.
Aufg0428.java

29. [B] (Addition und Multiplikation). Schreiben Sie ein Programm, das zwei vom Anwender eingegebene Zahlen x und y addiert und multipliziert und das Ergebnis ausgibt. Verwenden Sie zur Berechnung jedoch nicht die arithmetischen Operatoren für Addition und Multiplikation, sondern lediglich die Operatoren ++ und --.

30. [B] (Primfaktorzerlegung). Schreiben Sie ein Programm, das zu einer gegebenen positiven Ganzahl eine Primfaktorzerlegung durchführt. Wird beispielsweise 120 eingeben, so soll die Ausgabe des Programms "120 = 2 * 2 * 2 * 3 * 5" lauten.

31. [B] (Bitweise Operatoren und Multiplikation mit 2). Erläutern Sie an einem Beispiel die Äquivalenz zwischen bitweisen Operatoren und der Multiplikation bzw. Division mit Zweierpotenzen.

32. [B] (GGT mit dem euklidischen Algorithmus). Ein Standardverfahren zur Berechnung des größten gemeinsamen Teilers zweier positiver Ganzzahlen ist der Euklidische Algorithmus, der in verschiedenen Varianten existiert. Eine Möglichkeit, ihn zu implementieren, besteht darin, solange die jeweils kleinere von der größeren Zahl abzuziehen, bis beide gleich sind. Der gemeinsame Wert ist dann der größte gemeinsame Teiler. Schreiben Sie ein Programm, das diese Variante des euklidischen Algorithmus implementiert.

33. [B] (Zahl im Wortlaut). Schreiben Sie ein Programm, das eine eingegebene Ganzzahl im Wortlaut ausgibt. Es reicht, wenn ihr Programm beispielsweise die Zahl 345 als "Drei Vier Fünf" ausgibt. Sorgen Sie dafür, daß alle auftretenden Sonderfälle korrekt behandelt werden. Eine interessante Erweiterung dieser Aufgabe besteht darin, die Zahl so auszugeben, wie sie tatsächlich ausgesprochen wird, in obigem Beispiel also als "Dreihundertfünfundvierzig". Dadurch würde sich der Schwierigkeitsgrad auf C erhöhen.

34. [B] (Sieb des Eratosthenes). Eine seit über 2000 Jahren bekannte Form der Primzahlbestimmung wird als "Sieb des Eratosthenes" bezeichnet. Angenommen, Sie sollen alle Primzahlen im Bereich von 1 bis 1000 bestimmen. Gehen Sie dazu wie folgt vor:

• Erstellen Sie ein boolsches Array mit 1000 Elementen und initialisieren Sie alle Elemente auf true.
• Ändern Sie das erste Element auf false.
• Nun führen Sie in einer Schleife folgende Schritte aus:
  • Suchen Sie das nächste Element, dessen Wert true ist. Falls kein weiteres Element diese Bedngung erfüllt, beenden Sie die Schleife.
  • Ändern Sie den Wert aller Elemente, deren Position ein ganzzahliges Vielfaches der aktuellen Position ist, auf false. Haben Sie beispielsweise das fünfte Element gefunden, so werden auf diese Weise die Elemente 10, 15, 20, ... ,995 und 1000ausgestrichen.
• Geben Sie nun die Positionen aller Arrayelemente aus, deren Wert true ist. Es sind die Primzahlen zwischen 1 und 1000.

35. [B] (Weltbevölkerung ermitteln). Für die Jahre 1650 bis 1972 kann die Weltbevölkerung näherungsweise mit Hilfe der folgenden Formel berechnet werden:

       1.85477 * 1011
P(t) = --------------
       2021.55 - t

36. [B] (Einkommensteuerberechnung). Schreiben Sie ein Programm, welches nach der Eingabe Ihres zu versteuernden Einkommens die von Ihnen zu zahlende Einkommensteuer berechnet. Zur Berechnung verwenden Sie folgendes Verfahren, wie es im EStG, § 32a (Stand 1996) beschrieben ist.

Die Einkommensteuer beträgt jeweils in DM für zu versteuerndes Einkommen:

1. bis 12095 DM (Grundfreibetrag): 0;
2. von 12096 bis 55727 DM: (86,63 * y + 2590) * y;
3. von 55728 bis 120041 DM: (151,91 * z + 3346) * z + 12949;
4. von 120042 an: 0,53 * x - 22842;

37. [C] (Pyramidenförmiges Array). Geben Sie die Deklaration und den Code zur Initialisierung eines dreidimensionalen, pyramidenförmigen Arrays an. Die erste (oberste) Ebene soll dabei ein Element enthalten. Für n >= 2 soll die n-te Ebene n*(n+1) Elemente (im Rechteck) enthalten. Alle Elemente der n-ten Ebene sollen mit dem Wert n vorbelegt werden. Überlegen Sie sich ein Möglichkeit, den Inhalt des Arrays zur Kontrolle auszugeben.

38. [C] (Quadratwurzel). Schreiben Sie ein Programm, daß die Quadratwurzel einer vom Anwender eingegeben Fließkommazahl mit 6 Stellen Genauigkeit berechnet. Verwenden Sie zur Berechnung nicht die entsprechende Methode der Klassenbibliothek, sondern implementieren sie einen eigenen iterativen Ansatz.
Aufg0438.java

39. [C] (Histogramm). Computer werden oft zur statistischen Aufbereitung und graphischen Darstellung von großen Datenmengen verwendet. Schreiben Sie ein Programm, das Ganzzahlen zwischen 1 und 20 einliest und anschließend eine pseudographische Darstellung der Werte realisiert. Falls der Anwender beispielsweise die fünf Werte 13, 7, 6, 10 und 2 eingibt, soll das Programm folgende Ausgabe erzeugen:

13| *
12| *
11| *
10| *        *
 9| *        *
 8| *        *
 7| *  *     *
 6| *  *  *  *
 5| *  *  *  *
 4| *  *  *  *
 3| *  *  *  *
 2| *  *  *  *  *
 1| *  *  *  *  *
--+--------------
  |13  7  6 10  2

40. [C] (Nachbildung der Division). Angenommen, in Java gäbe es keinen Operator, um Fließkommazahlen zu dividieren. Eine Alternative, den Quotienten a / b zu berechnen, würde dann darin bestehen, zuerst den Kehrwert 1.0 / b von b zu berechnen und diesen dann mit a zu multiplizieren. Zur Berechnung des Kehrwerts kann beispielsweise der nachfolgend beschriebene iterative Algorithmus verwendet werden, der nur Multiplikationen und Subtraktionen verwendet:

Um für eine beliebige Zahl x den Kehrwert 1.0 / x zu berechnen, wird zunächst mit einem Schätzwert p begonnen. Dieser wird nun iterativ durch Einsetzen in die folgende Formel verbessert:

pn+1 = pn * (2 - x * pn)

41. [C] (Aktienhandel). Der Handel mit Aktien oder anderen Wertpapieren ist ein riskantes Geschäft, weil man die zukünftige Entwicklung des Kurses nicht kennt. Interessanterweise ist das Ermitteln der besten Einkaufs- und Verkaufsstrategie selbst dann gar nicht so einfach, wenn dies für einen vergangenen Zeitraum erfolgen soll, für den alle Kurse bekannt sind.

Angenommen, Sie kennen den detaillierten Kursverlauf einer Aktie während des gesamten vergangenen Jahres. Ihre Aufgabe ist es nun, denjenigen An- und Verkaufstag zu finden, der Ihren Verkaufserlös maximiert hätte, bei dem also die Differenz zwischen Kaufpreis und Verkaufspreis maximal gewesen wäre. Dazu steht Ihnen in einem Array die Veränderung des Aktienkurses für jeden Tag des Jahres zur Verfügung. Positive Werte zeigen dabei eine Erhöhung des Wertes an, negative eine Verminderung.

Gehen Sie davon aus, daß Sie Ihr Aktienpaket komplett an einem Tag kaufen und ebenfalls komplett an einem späteren Tag verkaufen. Weitere Einflußfaktoren wie Gebühren, kalkulatorische Zinsen oder Schwankungen innerhalb eines Tages sollen unberücksichtigt bleiben. Schreiben Sie nun ein Programm, das den optimalen Ankaufs- und Verkaufstag berechnet. Ihre Lösung sollte keinesfalls einere schlechtere als quadratische Laufzeit haben. Es sind sogar Lösungen mit der Laufzeit von O(n log n) und O(n) möglich.

42. [C] (Phythagoras ohne Wurzel). Der Satz des Pythagoras definiert die Beziehungen der Seitenlängen in einem rechtwinkligen Dreieck zu a^2+b^2=c^2. Die Formel für die Berechnung der Hypothenuse bei gegebenen Katheten ist demnach c=sqrt(a^2+b^2). Es ist eine bemerkenswerte Tatsache, daß die Hypothenusenlänge auch berechnet werden kann, ohne explizit die Wurzel zu ziehen.

Das folgende Verfahren wurde 1983 von C. Moler und D. Morrison beschrieben. Zunächst berechnen sie:

c := maximum(a, b);
q := minimum(a, b);

r := (q / c) ^ 2;
s := r / (4.0 + r);
c := c + (2.0 * s * c);
q := s * q;

43. [C] (d'Hondtsches Höchstzahlverfahren). Die Bundestagswahlen in Deutschland werden nach einem kombinierten Mehrheits- und Verhältniswahlsystem durchgeführt. Bei der Mehrheitswahl werden mit der Erststimme die Direktkandidaten in 328 unterschiedlichen Wahlkreisen gewählt. Mit der Zweitstimme dagegen wird die Landesliste einer bestimmten Partei gewählt und aus der sich ergebenden Stimmverteilung resultiert die weitere Sitzverteilung. Während seit 1985 das Hare-Niemeyer-Verfahren zur Bestimmung der Sitzverteilung der Zweitstimmen verwendet wird, erfolgte dies früher auf der Basis des d'Hondtschen Höchstzahlverfahrens.

Bei diesem Verfahren, das von dem Niederländer Victor d'Hont entwickelt wurde, werden die für die einzelnen Parteien abgegebenen gültigen Stimmen zunächst durch 1, 2, 3, 4, 5, usw. geteilt. Dadurch entsteht eine Matrix, in der jede Partei eine Spalte enthält, in der die einzelnen Zeilen von oben nach unten die durch 1, 2, 3 usw. dividierte Stimmenzahl enthalten. Nun bekommt zunächst die Partei einen Sitz, in deren Spalte die größte Zahl steht und dieses Element wird anschließend gestrichen. Der nächste Sitz geht an die Partei, in deren Spalte die höchste unter den verbleibenden Zahlen steht und auch diese wird anschließend gestrichen. Dies geht nun solange weiter, bis alle Sitze vergeben sind. Das folgende Beispiel mag dies verdeutlichen:

Teiler	Partei 1	Partei 2	Partei 3	Partei 4
1	44321 (1)	39269 (2)	9480 (9)	6930 (13)
2	22160 (3)	19634 (4)	4740	3465
3	14773 (5)	13089 (6)	3160	2310
4	11080 (7)	9817 (8)	2370	1732
5	8864 (10)	7853 (11)	1896	1386
6	7386 (12)	6544 (14)	1580	1155
7	6331 (15)	5609	1354	990

Angenommen, es wurden insgesamt 100000 gültige Stimmen für vier verschiedene Parteien abgegeben. Die Parteien haben 44321, 39269, 9480 bzw. 6930 Stimmen erhalten. Ingsgesamt seien 15 Sitze zu verteilen. Die Tabelle listet nun die Stimmen für die einzelnen Parteien für die Teiler 1 bis 7 auf. Die erste Höchstzahl ist 44321 und der erste Sitz geht an Partei 1. Die nächste Höchstzahl ist 39269 und der zweite Sitz geht an Partei 2. Dann folgt wieder Partei 1, denn die nächsthöchste Zahl ist 22160. Der neunte Sitz schließlich geht an Partei 3 und der 13. an Partei 4. Insgesamt erhält Partei 1 sieben Sitze, Partei 2 sechs und die Parteien 3 und 4 jeweils einen Sitz.

Schreiben Sie ein Programm, daß eine Wahlauswertung nach dem d'Hondtschen Höchstzahlverfahren implementiert. Der Anwender soll dabei die Möglichkeit haben, die Anzahl der zu vergebenden Sitze und die Anzahl der gültigen Stimmen für jede Partei anzugeben. Das Programm soll die jeweilige Sitzzahl für jede Partei berechnen und zur Kontrolle eine Tabelle analog der hier gezeigten erzeugen.
Aufg0443.java