Giuga Programm

[Edinita]

Hallo!
Ich bin ganz neu hier und auch blutige Java-Anfängerin - falls die Frage hier also fehl am Platz ist, sagt einfach Bescheid

Erstmal kurz zur Aufgabe:
In der ersten Teilaufgabe (a) sollte gezeigt werden, dass folgendes gilta+b) mod m = (( a mod m) + (b mod m)) mod m
(ab) mod m = (( a mod m) (b mod m)) mod m

Soweit so gut.. anschließend soll ein Programm Giuga.java geschrieben werden, welches alle Zahlen n <= 1000 findet, die folgende Bedingung erfüllen:

Als Tipp stand noch dabei (und ich vermute, dass ich den einfach missachte und mein Programm daher nicht tut was es soll):
"Verwenden Sie beim Bilden der Summen und Potenzen das Ergebnis aus Teilaufgabe a, andernfalls reicht der Zahlenbereich von int (oder auch long) bei weitem nicht aus.

Mein Quellcode sieht jetzt wie folgt aus:

Compilieren funktioniert, aber beim Ausführen ergeben sich die Zahlen 2, 3, 5 und 26.
2, 3 und 5 sind ja schon mal super, aber erst mal hat die 26 hier nichts zu suchen und es fehlen ja auch noch jede Menge weitere Primzahlen.
Wie schon gesagt, denke ich dass das Programm erst mal grundsätzlich tun würde was es soll, aber die Zahlen beim Rechnen einfach zu groß werden. Versuch hier schon seit ewigen Zeiten die Rechnungen dementsprechend zu verändern, komme aber einfach nicht mehr weiter.

Kann mir vielleicht jemand weiterhelfen?
Vielen Dank schon mal

 

[Dompteur]

Die beiden Aussagen aus dem ersten Teil der Aufgabe helfen dir die Zahlen klein zu halten.

Die Aussage : (a+b) mod m = (( a mod m) + (b mod m)) mod m
kannst du verwenden um die Summe, die du bilden musst, klein zu halten.
Also anstatt die Potenzen einfach zu summieren, kannst du zuerst die Potenzen modulo n nehmen und dann die nun kleinere Zahlen aufsummieren. Die Summe muss dann natürlich auch noch einmal mod n genommen werden, da sie ja >n sein könnte.

zB für n=4

==> (k**0 + k**1 + k**2 + k**3) mod 4 = 3
==> ( (k**0 mod 4) + (k**1 mod 4) + (k**2 mod 4) + (k**3 mod 4) ) mod 4 = 3


Die andere Aussage : (ab) mod m = (( a mod m) (b mod m)) mod m
hilft dir die Potenzen klein zu halten.

So wird beispielsweise aus (k**3 mod 4) dann ( ( k mod 4 ) * (k mod 4) * (k mod 4) ) mod 4
oder auch ( ( ( ( k mod 4 ) * (k mod 4) ) mod 4 ) * (k mod 4) ) mod 4

D.h.: Du kannst die Potenz in einer Schleife berechnen und dabei jedes Teilergebnis mod n nehmen. So bleibt dein Zwischenergebnis immer < n.

 

[klauskarambulut]

Der Code hat darüber hinaus noch ein paar kleine Nachteile, die man leicht beheben kann.

Ich empfehle das ganze in zusätzliche Funktionen aufzuteilen.
Das macht die Implementierung einfacher, übersichtlicher und testbarer.

/** @return (base^exponent) mod modus
*/
static int modPow(int base, int exponent, int modus)

/** @return giuga-number for n
*/
static int giuga(int n)

Zudem wird es viel einfacher und entspannter die Optimierungen die Dompteur vorschlägt einzubringen und auf Korrektheit zu überprüfen.

Dann kannst du in der main Methode statt while eine in diesem Fall lesbarere for-Schleife nutzen

for(int n = 1; n < 1000; n++) {
  int giuga = giuga(n);
  int nMinus1 = n - 1;
  if(giuga == nMinus1) {
    System.out.println(n);
  }
}

Spoiler: Ist das das erwartete Ergebnis?

1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997

 

[Dompteur]

Kleine Korrektur: Ich habe bei meinem Beispiel die Formel falsch gelesen.
Es wird natürlich nicht über die Potenzen iteriert, sondern über die Basis

Die Summierung sieht dann für beiuspielsweise n=4 so aus:
==> (1**a + 2**a + 3**a) mod 4 = 3
==> ( (1**a mod 4) + (2**a mod 4) + (3**a mod 4)) mod 4 = 3

Hinweise: Ich habe der Einfachheit halber statt "(n-1)" "a" einsetzt.

So wird beispielsweise aus (3**a mod 4) dann ( ( 3 mod 4 ) * (3 mod 4) * (3 mod 4) ) mod 4
oder auch ( ( ( ( 3 mod 4 ) * (3 mod 4) ) mod 4 ) * (3 mod 4) ) mod 4

 

[Edinita]

Super cool - danke schonmal für die Antworten! Ich setz mich jetzt mal ran und versuch nochmal mein Glück.

 

[Edinita]

Also ich hab mich nochmal rangesetzt und versucht eure Tipps anzuwenden - es ist folgender Wirrwarr rausgekommen:


Hoffentlich checkt ihr einigermaßen was was sein soll ... hab versucht es mit Kommentaren etwas deutlicher zu machen.
Was schonmal gut ist, ist dass er jetzt Zahlen bis 1000 ausgibt und nicht wie vorher bei 5 aufhört, weil die Exponenten zu groß werden.
Nicht gut ist leider das Ergebnis.
Ich weiß der Code wirkt wahrscheinlich ziemlich wirr ^^ - hab mir aber lange Gedanken gemacht und versucht zunächst einmal alles ordentlich aufzuschreiben - und eigentlich hat es Sinn gemacht.

Vielleicht habt ihr noch einen Tipp?
Danke schonmal

 

[strußi]

was dir helfen kann ist die fragestellung
http://www.java-forum.org/thema/iterative-programmierung.170411/

 

[Edinita]

Sind denn die Bedingungen bei den Schleifen überhaupt so richtig gewählt? Ich hab grad nochmal while Schleifen ausprobiert... aber da kommt dann noch mehr Unsinn raus :/

 

[klauskarambulut]

Es ist schon reichlich unverschämt zu schreiben, "habe eure Tipps angewendet" und dann sowas zu liefern.

Was ist so schwierig daran einfache Funktionen zu schreiben?

Schreibe einfach eine Funktion die "n hoch m" berechnet! (public static int pow(int base, int exp) {...})
Dann schreibst du etwas Code der die Funktion aufruft, das Ergebnis ausgibt und überprüfst dies.

Dies kannst du auch gerne bleiben lassen, aber dann solltest du auch das Programmieren sein lassen.
Schritt für Schritt vorgehen.

Und wenn du "n hoch m" kannst, dann schreibst du eine Funktion "(n hoch m) modulo k". (public static int modPow(int base, int exp, int mod) {...}
Aufrufen überprüfen, das ganze Prozedere.

Die Kommentare die du verwendest interessieren keinen. Bezeichner, die aus einem Buchstaben bestehen interessieren keinen. Ineinander verschachtelte Schleifen interessieren keinen.

Kleine Funktionen, die wohldefinierte Aufgaben erfüllen interessieren.

Screenshots interessieren keinen, wenn du was möchtest dann kopiere den Code und für ihn ein oder lass es bleiben.

Diesen Code schaut niemand an. Der Code wird kommentarlos gelöscht. Egal ob das richtige Ergebnis rauskommt oder nicht. Das ist Müll.

Kleine Funktionen, die wohldefinierte Aufgaben erfüllen!

 

[Edinita]

Also wie ich es ganz zu Anfang auch erwähnt habe, habe ich erst vor sehr kurzer Zeit - ungefähr 1 Woche - angefangen mich mit Java zu beschäftigen.

Außerdem handelt es sich hier um eine Aufgabe aus der Uni mit einer explizit formulierten Aufgabenstellung, bei der leider nicht nach deiner Funktion (public static int pow ..etc) gefragt ist. Vielmehr soll nur mit +, -, *, / und % gearbeitet werden und es geht allgemein um verschachtelte Schleifenanweisungen. Daher kann ich nicht einfach irgendwelche Funktionen, die ich irgendwoher habe dort mit einbringen.

Für mich ist das alles wie gesagt neu und ich habe noch einige Probleme, das ist trotzdem kein Grund so unfreundlich zu sein. Ich habe gedacht, dass man hier auch als Anfänger Fragen stellen darf, ohne halbwegs beleidigt zu werden..

Wenn dich meine Anfängerfehler so zur Weißglut bringen, dann kannst du meine Einträge auch gerne ignorieren..

 

[strußi]

explizit formulierten Aufgabenstellung, bei der leider nicht nach deiner Funktion (public static int pow ..etc) gefragt ist. Vielmehr soll nur mit +, -, *, / und % gearbeitet werden und es geht allgemein um verschachtelte Schleifenanweisungen

es wird doch gesagt, schreibe eine Methode =Funktion mit den Parametern int base int exp
das was dann in die geschweiften klammern soll, ist der Teil wo das Hirn anfangen soll zu rauchen

schritt eins
summe von k bis n-1 von k^(n-1) =klarer fall für eine schleife
schritt zwei
nach der schleife summe durch Modulo n teilen und prüfen ob das ergebnis =n-1 ist
suchwörter: modulo java

==> (k**0 + k**1 + k**2 + k**3) mod 4 = 3
==> ( (k**0 mod 4) + (k**1 mod 4) + (k**2 mod 4) + (k**3 mod 4) ) mod 4 = 3


Die andere Aussage : (ab) mod m = (( a mod m) (b mod m)) mod m
hilft dir die Potenzen klein zu halten.

So wird beispielsweise aus (k**3 mod 4) dann ( ( k mod 4 ) * (k mod 4) * (k mod 4) ) mod 4
oder auch ( ( ( ( k mod 4 ) * (k mod 4) ) mod 4 ) * (k mod 4) ) mod 4

D.h.: Du kannst die Potenz in einer Schleife berechnen und dabei jedes Teilergebnis mod n nehmen. So bleibt dein Zwischenergebnis immer < n.

das gibt dir doch schon die lösung vor, das ganze nur noch so umschreiben, dass es in einer schleife funktioniert.
tipp: feste variablen sind nicht von schleifen betroffen

 

[Edinita]

Ok danke für eure ganzen Tipps! Ich setz mich jetzt nochmal ganz in Ruhe ran und fang nochmal von vorne an.