Programm zum Finden des größten Integers
lima-city → Forum → Programmiersprachen → Java
betrachten
code
denkfehler
eigentlichen ziel
ergebnis
ersetzen
form
hantieren
interesse
kilometer
programm
schnellere implementierung
sekunde
string
system
testen
theorie
unbekannter faktor
zahl
zuviel
-
Hallo!
Ich wollte ein Programm schreiben, das den größten Integer x findet, für den gilt:
x/1679 ist ein Integer
2,2*x/120 ist ein Integer
x < 1923000
Wie implementiere ich die "ist ein Integer"-Bedingung? -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Die gleiche Frage wurde gerade erst im Basic Forum gestellt: http://www.lima-city.de/thread/ist-die-zahl-n-durch-d-teilbar.
Die Antwort lautet, durch verwenden des Modulo Operators (x % 1769).
Da du eine feste Vorgegeben Obergrenze für x hast würde ich damit anfangen und dann x in jedem Durchgang dekrementieren und die beiden Tests machen und zwar solange bis beide Tests positiv ausfallen -
Hallo auch!
ich würde eine schleife über alle Vielfache von 1679 laufen lassen:
for(int x=1679; x<1923000; x +=1679)
{
//
}
Darin würde ich die zweite Bedingung testen, allerdings nicht unter Verwendung von double (2,2),
sondern durch Erweitern:
2,2*x/120 == 22*x/1200 == 11*x/600
also if(11*x%600 == 0) ...
Sagst Du uns auch, was der Sinn der Übung ist?
&greetinx;
WS
-
wees schrieb:
Hallo auch!
ich würde eine schleife über alle Vielfache von 1679 laufen lassen:
for(int x=1679; x<1923000; x +=1679)
{
//
}
Darin würde ich die zweite Bedingung testen, allerdings nicht unter Verwendung von double (2,2),
sondern durch Erweitern:
2,2*x/120 == 22*x/1200 == 11*x/600
also if(11*x%600 == 0) ...
Sagst Du uns auch, was der Sinn der Übung ist?
&greetinx;
WS
Ohne es getestet zu haben, hört sich deine Lösung wesentlich schneller an...
€dit: Hab's jetzt aus Interesse doch mal schnell getestet, allerdings in C und nicht in Java:
Meine Lösung benötigt 0,021 Sekunden
Die Lösung von wees benötigt nur 0,004 Sekunden
Beitrag zuletzt geändert: 6.10.2009 15:14:37 von kochmarkus -
Vielleicht verstehe ich die Fragestellung auch nicht, aber wäre es nicht möglich das direkt auszurechnen?
x durch Zahl1 und Zahl2 muss glatt aufgehen --> x = f * Zahl1 * Zahl2, wobei f ein noch unbekannter Faktor ist.
Wie wees bereits bemerkt hat, kann man 120*2.2 zu 264 zusammenfassen.
Jetzt muss man eigentlich nur noch Zahlen der Form f * Zahl1 * Zahl2 betrachten, die kleiner als 1923*10^3 sind. Die größte Zahl, für die das in Frage kommt ist
f = abgerundet( 1923*10^3 / ( Zahl1 * Zahl2 ) )
Das Ergebnis wird abgerundet, da wir nur mit ganzen Zahlen hantieren wollen.
Die Lösung ist dann das Ergebnis der letzten Rechnung mal Zahl1*Zahl2
Oder in Java-Code:
public class Biggest{ public static void main( String[] args ) { int a = 1679; int b = (int) ( 120 * 2.2 ); int c = 1923000; int max_koeff = c / ( a * b ); System.out.println( "Die Lösung ist " + max_koeff * a * b ); } }
Und das ergibt 1773024
Beitrag zuletzt geändert: 6.10.2009 17:59:05 von bladehunter -
Ich habs getestet. Ich habe dabei bloß nicht daran gedacht, dass ich die 2.2 wieder rausziehen muss
hm. Ok, dann mal den Denkfehler suchen... -
kochmarkus schrieb:
Ohne es getestet zu haben, hört sich deine Lösung wesentlich schneller an...
€dit: Hab's jetzt aus Interesse doch mal schnell getestet, allerdings in C und nicht in Java:
Meine Lösung benötigt 0,021 Sekunden
Die Lösung von wees benötigt nur 0,004 Sekunden
Obwohl es mittlerweile Kilometer am eigentlichen Ziel des Threads vorbeischießt, hier noch eine schnellere Implementierung (auch in C, aber Java sollte wohl identisch sein, außer anstelle des ! ein == 0, und printf durch system.out.blabla ersetzen):
int main (void) { int i; for (i = 18469; i < 21153000; i += 18469) if (! (i % 600) ) { printf ("%d\n", i / 11); return 0; } return 1; } -
Hallo Bladehunter,
bei diesem Problem handelt es sich im weitesten Sinne um eine "Diophantische" Gleichung
(s. dazu z.b. http://de.wikipedia.org/wiki/Diophantische_Gleichung).
Die Lösung(en) einer solchen Gleichung lassen sich nicht einfach "ausrechnen",
da die wesentliche Nebenbedingung, nämlich die, dass die Lösung ganzzahlig sein soll, nicht durch eine entsprechende numerische Operation ausgedrückt werden kann.
Man kann in solchen Fällen immer nur eine Ergebnismenge bestimmen und muss daraus diejenigen Lösungen herausfinden, die ganzzahlig sind.
Beispiel pythagoräische Zahlentrippel.
In einem rechtwinkligen Dreieck gilt bekanntlich derf olle Pythagoras: a*a + b*b = c*c (gibt hier keinen Exponenten...)
Wenn ich zwei Schenkel, bspw. a = 5 und b=7 vorgegeben habe,kann ich c leicht ausrechnen:
c = Wurzel(5*5 + 7*7)
c = Wurzel(25 + 49)
c = Wurzel(74)
...und die ist leider nicht ganzzahlig
Beispiel für eine ganzzahlige Lösung: a=3, b=4 ==>> c = 5
ich hoffe, das war jetzt nicht zuviel Theorie...
WS
-
census schrieb:
kochmarkus schrieb:
Ohne es getestet zu haben, hört sich deine Lösung wesentlich schneller an...
€dit: Hab's jetzt aus Interesse doch mal schnell getestet, allerdings in C und nicht in Java:
Meine Lösung benötigt 0,021 Sekunden
Die Lösung von wees benötigt nur 0,004 Sekunden
Obwohl es mittlerweile Kilometer am eigentlichen Ziel des Threads vorbeischießt, hier noch eine schnellere Implementierung (auch in C, aber Java sollte wohl identisch sein, außer anstelle des ! ein == 0, und printf durch system.out.blabla ersetzen):
int main (void) { int i; for (i = 18469; i < 21153000; i += 18469) if (! (i % 600) ) { printf ("%d\n", i / 11); return 0; } return 1; }
Gratuliere, auf der gleichen Hardware wie gestern kommst du auf 0,003 Sekunden.
€dit: Allerdings hast du einen Fehler gemacht, du findest nicht die größtmögliche Lösung, sondern die kleinstmögliche... (was in diesem Fall jedoch das selbe ist)
Beitrag zuletzt geändert: 7.10.2009 14:53:04 von kochmarkus -
kochmarkus schrieb:
€dit: Allerdings hast du einen Fehler gemacht, du findest nicht die größtmögliche Lösung, sondern die kleinstmögliche... (was in diesem Fall jedoch das selbe ist)
Das mit der größtmöglichen hatte ich tatsächlich verbummelt, das ist aber Klasse, denn so sparen wir die Substraktion bei jedem Schleifendurchlauf, da wir auf 0 prüfen. Das macht mindestens noch 0,2 us.
int main (void) { int i; for (i = 2153000; i; i -= 18469) if (! (i % 600) ) { printf ("%d\n", i / 11); return 0; } return 1; } -
Leider immer noch falsch, da 21153000 kein vielfaches von 18469 ist...
-
census schrieb:
Ich geb' auf:
int main (void) { printf ("1007400"); }
Auch bei dem Programm bleibt es bei meiner Hardware bei 0,003 Sekunden. Und zusätzlich noch
census.c: In function ‘main’: census.c:6: warning: control reaches end of non-void function
€dit: das #include <stdio.h> hab ich großzügigerweiße mal selbst hinzugefügt
Beitrag zuletzt geändert: 7.10.2009 21:39:34 von kochmarkus -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
