Funktionenproblem

Vicious Falcon

knivil schrieb:

Fuer 4150 ist n = 4 bei mir.

4[h]4[/h]+1[h]4[/h]+5[h]4[/h] != 4150

knivil schrieb:

Und sie taucht beispielsweise nicht in der Tabelle bei Wikipedia auf.

Oh, dann kann die Rechnung meines letzten Posts ja gar nicht richtig sein

SeppJ

knivil schrieb:

Wird ein bisschen brauchen, alle Kombinationen durchzuprobieren

Ich haette binaere Suche verwendet ... Alle Zahlen bis 2^53 durchzuprobieren bei 1GHz dauert wohl 9007199s bzw. 2501 Stunden.

Doh! Das hätte ich vorher mal abschätzen sollen. Aber binäre Suche würde glaube ich nichts bringen, weil ich ja nicht weiß, ob alle Werte oberhalb einer bestimmten Basis fehlerhaft wären, wenn diese fehlerhaft ist. Mittlerweile ist mein Programm aber auch weit jenseits der dritten Wurzel von 2^53 angelangt, das heißt es wird bloß die ganze Zeit nur noch (basis hoch 2) getestet. Wenn wir mal annehmen, dass pow da keinen Fehler mehr macht (eventuell eine spezielle Implementierung für diesen Fall), dann wird da auch nichts mehr kommen.

Vicious Falcon

Ich habe es einmal auf templates umgestellt, da ich die größte Zahl im Dezimalsystem ebenfalls berechnen lassen wollte:

template<typename T>
T mypow(const T& val,size_t exp)
{
	if(!exp)
		return 1;
	T ret=val;
	for(size_t i=1;i<exp;++i)
		ret*=val;
	return ret;
}

template<typename T>
int IsArmstrong(const T& val)
{
	const int MaxExp = 10; // bis wohin soll getestet werden?
	T i; // wird immer auf den Wert von val gebracht, val dürfen wir nicht verändern
	T res; // der berechnete Wert
	for(int exp=1;exp<=MaxExp;++exp)
	{
		res = 0;
		i = val;
		do
		{
			res+=mypow(i%10,exp);
		}while ((i/=10)>0);
		if(res==val)
			return exp;
	}
	return 0;
}

Der Returnwert gibt jetzt auch (sinnigerweise) den Exponenten zurück.
Für den 32 Bit Bereich:

1       0
1       1
1       2
1       3
1       4
1       5
1       6
1       7
1       8
1       9
3       153
3       370
3       371
3       407
4       1634
5       4150
5       4151
4       8208
4       9474
5       54748
5       92727
5       93084
5       194979
6       548834
7       1741725
7       4210818
7       9800817
7       9926315
7       14459929
8       24678050
8       24678051
8       88593477
9       146511208
9       472335975
9       534494836
9       912985153

@ SeppJ Ncht alles annehmen, testen!

knivil

4       1634
5       4150
5       4151
4       8208

Hmm ... warum ist der Exponent 5? Zwar gilt fuer 5 das alle Ziffern hoch 5 zusammen addiert wieder die gleiche Zahl ergeben, aber es ist dennoch keine Armstrongzahl. Dazu muss der Exponent mit der der Anzahl der Ziffern uebereinstimmen. Ich habe es so gemacht: (highly advanced solution, nicht abschreiben, das faellt auf)

unsigned int power(unsigned int n, unsigned int expo)
{
    return expo ? n * power(n, expo-1) : 1;
}

unsigned int length(unsigned int n)
{
    return (n < 10) ? 1 : 1 + length(n/10);
}

unsigned int armstrongHelper(unsigned int n, unsigned int len)
{
    return n ? power(n%10,len) + armstrongHelper(n/10,len) : 0;
}

bool armstrong(unsigned int n)
{
    return n == armstrongHelper(n,length(n));
}

Die Rekursion sollte vom Compiler wegoptimiert werden, habe mir aber den Assemblercode nicht angesehen.

Vicious Falcon

Alles klar, jetzt erst weiß ich was du meinst:
Es ist vom Wert der ersten Ziffer abhängig, desto einfacher sollte die Auswertung sein.
Wie geschrieben, Armstrong-Zahlen waren mir unbekannt.