Project Euler problem20 Fakultät von 100

[Fab1]

Hallo Leute,

ich versuche mich gerade am Problem 20 - Project Euler.

long zahl = 1L;
		for (long zähler = 1L; zähler<10; zähler++){
			zahl = zahl * (zähler+1);	
		}
		System.out.println(zahl);

Also wenn ich die Fakultät von 10 berrechnen möchte, dann komme ich auf den richtigen Wert. Bei höheren Fakultäten komme ich entweder auf einen minus Wert oder wie bei 100 auf "0".

Ich hab im Internet einen weiteren code zu berrechnung der Fakultät gefunden, allerdings kommt auch dort bei 100 eine "0" raus.

long ist ja 2^64 also nehme ich mal an die Fakultät von 100 ist zu groß. Ist es dann möglich die Zahl als String auszugeben?

Für weitere alternativen oder Anregungen bin ich natürlich gern zu haben.

Gruß euer

GEEK!

 

[Fu3L]

Das wird dann wohl ein Fall für die Klasse BigInteger aus java.math sein. Einfach mal in die Java API gucken 😉

Edit: Leichter wiederverwendbar wäre der Code, wenn du die übergebende Zahl runterzählen würdest, also einfach 100 * 99 * 98 und wenn du bei 0 angekommen bist, die Schleife verlassen 😉 Aber so gehts natürlich auch, irgendwo muss ja immer die Zahl angegeben werden^^

Edit: Habs selbst mal ausprobiert: Respektable Zahl^^ 😀

 

[Gregorrr]

Zur Kontrolle: sum of digits 100 - Wolfram|Alpha!
Ausführliche Behandlung hier: algorithm - Sum of digits of a factorial - Stack Overflow

 

[Fu3L]

Sollte mein Code gewünscht sein, kann ich den auch gerne posten, aber will ja nich spoilern und den Spaß am Tüfteln verderben 😉

 

[Fab1]

Vielen Dank für die Antworten.

Ich bin jetzt schon eine Weile am tüfteln. Aber es scheint als würde es vorran gehen. Hab jetzt nurnoch ein kleines Problem mit der Multiplikation von " zahl = zahl * (zähler+1)"
aber ich bin voller Zuversicht, dass ich das in den nächsten Minuten noch lösen werde.

Gruß

der (noch) nicht JAVA GEEK 😉

edit: so 4 Minuten später war es gelöst. Ich hoffe es stimmt.

BigInteger zahl = BigInteger.valueOf(1);
		
		for (int zähler = 1; zähler<100; zähler++){
			
			zahl = zahl.multiply((BigInteger.valueOf(zähler+1)));
			System.out.println(zahl);
		}

So jetzt muss ich noch rausfinden wie man die Quersumme berechnet. Danke nochmals.

edit 02:13 So die Quersumme bereitet mir so einige Probleme, denn jetzt fast 2 Stunden später bin ich noch nicht wirklich viel weiter 🙂.

Also ich habe bisher 2 Ansätze es waren mal mehr aber halt nur Ansätze:

Einmal:

public static void main(String[] args) {
		
		BigInteger quersumme = BigInteger.valueOf(0);
		BigInteger zahl      = BigInteger.valueOf(1);
		int        summe     = 0;
		
		for (int zähler = 1; zähler<100; zähler++){
			
			zahl = zahl.multiply((BigInteger.valueOf(zähler+1)));

			
			while (zahl<0){
				quersumme+=zahl.remainder((BigInteger.valueOf(10));
				zahl = zahl.divide(BigInteger.valueOf(10));
			
			}
		
		System.out.println(zahl);
		}
	
/*	 public static BigInteger quersumme(BigInteger zahl){
		
		BigInteger quersumme =BigInteger.valueOf(0);
		while (BigInteger.valueOf(zahl)>0){
			quersumme+=zahl%10;
			zahl = zahl.divide(10);
			
		}
		return quersumme;			*/
	}

Problembereich Zeile 12-13:

Ich weis nicht wie ich "ist kleiner als" bei BigInteger hinbekomme.
Bei Zeile 13 sollte eigentlich "zahl%10" leider hab ich in den zwei Stunden keine Möglichkeit gefunden diese Probleme zu lösen.

Wie man sieht (ist jetzt ein Kommentar) wollte ich die quersumme anfangs per Methode aufrufen da bin ich auch etwas gescheitert.

Meine 2. Lösung wäre gewesen:

public static void main(String[] args) {
		
		BigInteger zahl = BigInteger.valueOf(1);
		
		for (int zähler = 1; zähler<100; zähler++){
			
			zahl = zahl.multiply((BigInteger.valueOf(zähler+1)));
	
			}
		
		System.out.println(quersumme(zahl.intValue()));
		}
	
	 public static int quersumme(int eingabe){
		
		int quersumme = 0;
		while (eingabe>0){
			quersumme+=eingabe%10;
			eingabe = eingabe/10;
			
		}
		return quersumme;
	}

Hier gibt es zwar keinen Compilerfehler, allerdings hab ich hier die "zahl" zu früh zurückgewandelt in "int" und somit kommt wieder "0" raus^^. Hätte ich es anders gemacht, wäre ich wieder auf ähnliche Probleme gestoßen.

Ich bin momentan mit meinen Ideen am Ende, ob das an der Müdigkeit oder an etwas anderem liegt möchte ich jetzt nicht darüber nachdenken, aber wenn ich morgen aufstehe würde ich mich vielleicht auf die ein oder andere idee freuen.

Also Gute Nacht

GEEK

 

[jgh]

ich weiß zwar nicht, wie und warum du beim Berechnen der Quersumme irgendwelche Mod-Rechnungen und Divisionen durchführst...aber du wirst es schon wissen 😉
Eine ganz simple Möglichkeit die Quersumme zu berechnen wäre, das Ergebnis in einen String zu parsen über den man einfach iterieren kann:

BigInteger zahl = BigInteger.valueOf(1);

		for (int zähler = 1; zähler < 100; zähler++) {

			zahl = zahl.multiply((BigInteger.valueOf(zähler + 1)));
			System.out.println(zahl);

		}
		String s = zahl.toString();
		int quersumme = 0;
		for (int i = 0; i < s.length(); i++) {
			quersumme = quersumme + Integer.parseInt(s.substring(i, i + 1));
		}
		System.out.println(quersumme);

edit: und Guten Morgen natürlich 🙂

 

[Fab1]

Guten Morgen,

also ich wusste, dass man es so machen kann, allerdings nicht wirklich wie. Dann sah ich diese von mir vorgestellt Lösung und die hat sich im Kopf eingebrannt.

Ich werde mir deine Variante mal genauer anschauen, aber interessieren würde mich eine Lösung zu meiner Variante trotzdem.

Gruß Geek

 

[despikeexd]

@Fu3L
Das wäre dann die rekursive Variante. TO verwendet hier aber die iterative Variante wie sie auch bei Wikipedia steht.

btw : wenn du mit BigInteger die Rekursive Methode schreibst brauchst du ab ungefähr 65! eine erhöhung des Max-Heaps und der StackSize ... ansonsten bekommste n StackOverflowError ...

 

[Fab1]

ok, dass ist mir für den Anfang zu schwierig. Ich belass es jetzt mal auf der Lösung von jgh, die Problemlos funktioniert hat. Also Problem20 solved 😉

 

[Antoras]

@TO

BigInteger ist ein Objekt, du kannst die Operatoren nicht auf Objekte anwenden. Stattdessen musst du die Methoden der Objekte nutzten. Bei BigInteger wären da neben

multiply

, die du ja schon entdeckt hast, noch

mod

,

divide

und zum Vergleichen

compareTo

:

BigInteger quersumme(BigInteger eingabe) {
	BigInteger res = BigInteger.ZERO;
	while (eingabe.compareTo(BigInteger.ZERO) > 0) {
		res = res.add(eingabe.mod(BigInteger.TEN));
		eingabe = eingabe.divide(BigInteger.TEN);
	}
	return res;

Das wäre die iterative Version und hier noch die rekursive:

BigInteger quersumme(final BigInteger eingabe) {
	return loop(eingabe, BigInteger.ZERO);
}

private BigInteger loop(final BigInteger i, final BigInteger res) {
	return i.compareTo(BigInteger.ZERO) > 0
		? loop(i.divide(BigInteger.TEN),res.add(i.mod(BigInteger.TEN)))
		: res;
}

Was

compareTo

macht findest du in der API heraus: [japi]Comparable[/japi]

 

[Fu3L]

@Fu3L
Das wäre dann die rekursive Variante. TO verwendet hier aber die iterative Variante wie sie auch bei Wikipedia steht.

btw : wenn du mit BigInteger die Rekursive Methode schreibst brauchst du ab ungefähr 65! eine erhöhung des Max-Heaps und der StackSize ... ansonsten bekommste n StackOverflowError ...

Nö, muss nicht^^ 😉

import java.math.BigInteger;

public class Factorial {
	
	public static void main(String[] args) {
		
		BigInteger factor = BigInteger.valueOf(100);
		BigInteger result = BigInteger.ONE;
		
		while(!factor.equals(BigInteger.ONE)) {
			result = result.multiply(factor);
			factor = factor.subtract(BigInteger.ONE);
		}
		
		String str = result.toString();
		System.out.println(str);
		
		long sum = 0;
		for(int i = 0; i < str.length(); i++) {
			sum += Integer.parseInt(str.charAt(i)+"");
		}
		System.out.println(sum);
	} //End main
} //ENd Factorial

Meine Variante könnte dabei geringfügig langsamer sein, wegen der equals-Aufrufe, aber darauf kommts bei 100 oder 1000 Iterationen auch nicht an^^

PS: Hab mich gestern auch bei Project Euler registriert. 😀 Problem 20, 1, 2 und 3 schon gelöst^^

 

[Logaff]

Projekt Euler made my day 😛

 

[despikeexd]

@Fu3L
Ich sprach auch von der REKURSIVEN Variante bei der ein StackOverflow entsteht ... nicht von der ITERATIVEN ...

*wer lesen könnte wäre im vorteil*

 

[Fu3L]

*wer lesen könnte wäre im vorteil*

Jaja, die annonymen poster 😉

von mir selbst:
Edit: Leichter wiederverwendbar wäre der Code, wenn du die übergebende Zahl runterzählen würdest, also einfach 100 * 99 * 98 und wenn du bei 0 angekommen bist, die Schleife verlassen

@Fu3L
Das wäre dann die rekursive Variante. TO verwendet hier aber die iterative Variante wie sie auch bei Wikipedia steht.

Ich wollte dich daraufg hinweisen, dass es sich bei meiner beschriebenen Vorgehensweise nicht um eine rekursive Variante handeln muss. Du siehst die iterative Variante in meinem vorhergehenden Post 😉

PS: 12 Probleme über den Tag verteilt gelöst^^ 😀