[JAVA] Bloodys Mathe-/Optimierungsrunde

BloodyEric · 24. November 2011

Hallo,

nachdem ich mir bereits die letzten Tage etwas den Kopf zerbrochen hab, dachte ich mir, dass vielleicht jemand hier in der Gemeinschaft noch schlauer ist als ich. Ganz kurz zum Thema: Es gilt einen Java-Algorithmus zu entwickeln, der ein mathematisches Problem löst; und das so schnell wie möglich.

Folgendes Problem wird betrachtet:

Man nehme eine Zahl a aus den Stellen ab, die folgende Eigenschaft erfüllt: a^a + b^b = ab. In anderen Worten: Die Summe aller Ziffern mit sich selbst potenziert ergibt wieder unsere ursprüngliche Zahl. Folgendes definieren wir außerdem: 0^0 = 0.

Neben der Zahl 1 gibt es noch die Zahl 3435, die diese Eigenschaften erfüllt sowie noch eine weitere Zahl. Wir brauchen also einen Algorithmus, der per Schleife von 1 anfängt (von mir aus auch 3436) und uns die dritte (und letzte existierende) Zahl, die das erfüllt ausgibt.

Soviel vorne weg: Ich habe einen Algorithmus, der aber relativ langsam ist (55 Sekunden auf einem zentralen Testserver, auf dem ich den Code auf Geschwindigkeit prüfe). Leute behaupten, das ganze in 4-5 Sekunden hinzukriegen. Da die Zahl im mittleren neunstelligen Bereich liegt, haben wir also milliarden Rechenoperationen - Ziel muss es daher sein, Zahlen, die es aus irgendwelchen Mathematischen Gründen nicht sein können, so schnell wie möglich auszuschließen.

Sollte jemand zufällig zu viel Zeit haben, würde ich doch sehr darum bitten, sich darüber mal etwas Gedanken zu machen, einen groben Code zu schreiben, die Zahl (die ich euch von mir aus auch nennen kann) zu finden und danach das Ganze auf Geschwindigkeit zu optimieren.

Wer irgendwas hinkriegt, was auf meiner zentralen Testmaschine in weniger als 10 Sekunden läuft und tatsächlich erstmal alle Zahlen irgendwie ansieht, bekommt...uhm...überleg ich mir dann.

Benutzt werden darf: Grundrechenarten, Schleifen, break/continue, Bitoperationen, IF-Abfragen. Kein Multithreading/SuperCheat/Weißichwas

rEViDE · 24. November 2011

Das mit der Quersumme ist hirnrissig, habs ausprobiert funkt nur für 1:

Code

public class main{

	public static void main(String args[]){
		System.out.println("Wird berechnet...");
		String w;
		int lange;
		int quersumme = 0;
		int r;
		String o;
		for(int i = 0; i <= 10000; i++){
			quersumme = 0;
			w = String.valueOf(i);
			lange = w.length();
			for(int s=0; s<lange; s++){
				o = "" + w.charAt(s);
				r = Integer.parseInt(o);
	        	quersumme += r;
	    	}
			if((int)Math.pow(quersumme, quersumme) == i){
				System.out.println("Gefunden: " + i);
			}
		}
		System.out.println("Fertig.");
	}
}

Alles anzeigen

Wie meinste das mit a^a+b^b = ab? was soll da B sein?

[NeS]Fischer · 24. November 2011

er meint damit das A hoch A + B hoch B = A mal B sein muss

BloodyEric · 24. November 2011

Nene, a und b sind die einzelnen Ziffern.

Die Zahl 12 hätte also a=1 und b=2.

Wobei natürlich die gesuchte Zahl nicht aus 2 Ziffern besteht, das sollte nur beispielhaft dienen.

rEViDE · 24. November 2011

Ach ne, das hab ich wohl gecheckt nur, was ist in dem beispiel B?
wie wäre es mit 356
9 + 25 + 36 oder was?

Funkt, ich find aber 3435 und nicht 3436 oO
:

Code

public class main{

	public static void main(String args[]){
		System.out.println("Wird berechnet...");
		String w;
		int lange;
		int quersumme = 0;
		int r;
		String o;
		int erg2 = 0;
		for(int i = 0; i <= 999999999; i++){
			quersumme = 0;
			erg2 = 0;
			w = String.valueOf(i);
			lange = w.length();
			for(int s=0; s<lange; s++){
				o = "" + w.charAt(s);
				r = Integer.parseInt(o);
	        	quersumme += r;
	        	erg2 += (int)Math.pow(r, r);
	    	}
			if((int)Math.pow(quersumme, quersumme) == i){
				System.out.println("QS^QS|" + i);
			}
			if(erg2 == i){
				System.out.println("a^a+b^b| " + i);
			}
		}
		System.out.println("Fertig.");
	}
}

Alles anzeigen

BloodyEric · 24. November 2011

Fast

3^3 + 5^5 + 6^6

Also Hoch, nicht Mal sich selbst.

rEViDE · 24. November 2011

ja meinte ich siehe beispiel, müsst nurnoch regeln für unwürdige zahlen festlegen

BloodyEric · 24. November 2011

3435 ist ja auch richtig, jetzt fehlt aber noch die 9-stellige groooße Zahl, wegen der die Sache ja effizient und schnell sein muss

rEViDE · 24. November 2011

hast du es schon geschafft? ich wüsste keine effizientsmöglichkeiten Oo

BloodyEric · 24. November 2011

Klar, du musst nur mathematisch rangehen.

Haste die Zahl denn schon gefunden? Und wenn ja wie schnell ungefähr?

rEViDE · 24. November 2011

nochnet er rattert noch xxxD

BloodyEric · 24. November 2011

Dein Code (sofern er noch derselbe von oben ist) kann die Zahl aber nicht finden, da sie eine Null enthält, und die Standard-Mathe-Power Funktion für hoch 0 Eins ausgibt.

Wir haben aber oben gesagt, 0^0 soll ebenfalls 0 sein

rEViDE · 24. November 2011

Stimmt, einen moment :D:D

//Edit: wei soll man das denn noch optimieren, die schleife an sich dauert ja solange bis zum 9 stelligen bereich, optimierumg hin oder her oO
oder kann man das irgendwie "rückwärtsrechnen oO" :D?

//Edit 2:

Code

public class main{
 
public static void main(String args[]){
System.out.println("Wird berechnet...");
String w;
int lange;
int r;
String o;
int erg2 = 0;
for(int i = 0; i <= 999999999; i++){
erg2 = 0;
w = String.valueOf(i);
lange = w.length();
for(int s=0; s<lange; s++){
o = "" + w.charAt(s);
r = Integer.parseInt(o);
        if(r != 0)erg2 += (int)Math.pow(r, r);
        if(erg2 > i) s = s+1;
    }
if(erg2 == i){
System.out.println("a^a+b^b| " + i);
}
if(i == (int)999999999/4)System.out.println("25% done...");
if(i == (int)999999999/2)System.out.println("50% done...");
if(i == (int)999999999/2+(int)999999999/4)System.out.println("75% done...");
}
System.out.println("Fertig.");
}
}

Alles anzeigen

BloodyEric · 24. November 2011

Du kannst bei der dritten Zahl (die mit der 4 vorne) abbrechen.

Das ermitteln haste also, jetzt geht es also darum, das ganze zu optimieren. Und:

o = "" + w.charAt(s);
r = Integer.parseInt(o);

das hier ist nicht erlaubt, lass dir dafür mal was anderes einfallen.

rEViDE · 24. November 2011

wieso ist das nicht erlaubt?
da würden mir nurnoch pozentsätze einfallen und das ding durch teilen, wäre vlt. schneller...

BloodyEric · 24. November 2011

Gehört nicht zu den Grundrechenarten

Außerdem ists noch viel zu langsam

@ alle anderen: Ihr seid auch eingeladen, mal rumzuprobieren und was vorzuzeigen!

rejooh · 24. November 2011

Jap, eine ähnliche Lösung wie ReVide habe ich auch schon rausbekommen... Jetzt geht es ans überlegen.

//edit: Neuer Ansatz, auch nicht besser: enthält zusätzlich % und ist nur unwesentlich schneller:
Checken aller Zahlen zwischen: 1,1000000 mit String-Integer Gedöns: 14858 millisek. und mit meiner neuen Variante: 14287 millisek. | Auf meinen schrabbelligen Laptop.
//edit: Und mit Konsolenausgabe nach jeder Zahl, richtige Ergebnisse kommen gleich.

Code

public static boolean isIntegerValid(int integer) {
		int finalVal = 0;
		int integerCopy = integer;

		while (integer > 0) {
			int character = integer % 10;	
			if(character != 0) {
				finalVal += (int)Math.pow(character, character);
			}
			integer = integer / 10;
		}

		if(finalVal == integerCopy) {
			return true;
		} else {
			return false;
		}	
	}

Alles anzeigen

BloodyEric · 24. November 2011

Wir brauchen aber alle Zahlen zwischen 1 - 450.000.000

Und bei dir fehlt auch der spezielle hoch-null Fall

rejooh · 24. November 2011

Der hoch-null Fall ist drin siehe: "if(character != 0)"

BloodyEric · 24. November 2011

Ah, tatsächlich.

Aber du berechnest damit jede Zahl in dieser Funktion? Ich vermute jetzt einfach mal, dass der Funktionsaufruf (plus das zusätzliche erstellen der Variablen bei jedem Durchgang) enooorm viel Zeit frisst

Am schnellsten ging bei mir alles in der main-Funktion. Und dann noch einige weitere Optimierungen...