Funktion gesucht

lustig

Oops, stimmt. Hast natürlich recht...

freakC++

Hallo,

das alles ist eigentlich nur ein Spiel. Die oben genannten Zahlen sind der ASCII Code für "Abitur 2011". Diese Werte sollen aber nicht einfach in das Programm eingegeben werden (also kein if...else), sondern durch eine Funktion erhalten werden. Daher ist es mir egal, ob sie nach + / - unendlich abhaut und welche Werte dazwischen liegen. Ich muss sie nur auf überschaubarem Platz implementieren können!

Ich habe nochmal nachgerechnet, aber mein Polynom ist leider genau so falsch wie das des Th69

edit: Mit diesen Koeffizienten geht es gut bis zu x=7. Danach wird es wieder sehr falsch

a = -0,0011983764
b = 0,0356794186
c = -0,4230109513
d = 2,5261147453
e = -7,7646214585
f = 10,1947424088
g = 1,295983848
h = -12,6432139065
i = 5,7311643364
j = 2,0483599357

lg, freakC++

Th69

Hallo freakC++,

dann mußt du falsch gerechnet haben.

Ich habe es mit meinem MathParser-Beispielprogramm (FctParser) Parser für mathematische Formeln nachgerechnet und bis auf Rundungsfehler kommen die richtigen Funktionswerte raus.
Hier meine Expression (Punkt anstatt Komma !):

-0.0039916777 * x^10 + 0.1961488646 * x^9 - 4.1201058201 * x^8 + 48.3324983466 * x^7 - 347.1109085648 * x^6 + 1572.8069733796 * x^5 - 4462.3756090168 * x^4 + 7569.5600143298 * x^3 - 6870.3893849206 * x^2 + 2494.1043650794 * x^1 + 65

SeppJ

Ich schließe, du willst einfach Obfuscation? Wie wäre es damit? Ich war so frei, das Nullzeichen durch eine 32 für Leerzeichen zu ersetzen.

#include<iostream>
#include<cmath>

using namespace std;

char getchar(unsigned depth)
{ 
  const unsigned long magic1=117004UL;
  const unsigned long magic2=2576719UL;
  unsigned long magic=magic1;
  if (depth>3){
    depth-=4;
    magic=magic2;
  }

  return magic/static_cast<unsigned long>(pow(53, depth)) - 53*(magic/static_cast<unsigned long>(pow(53, depth+1))) + 32;
}

int main()
{
  for (unsigned i=0; i<11; ++i) cout << getchar(i);
  cout<<endl;
}

Leider habe ich nicht alles in eine einzige Zahl bekommen (zumindest ohne den Standard zu verletzen), daher die unschöne Fallabfrage. Wenn du größere Zahlen benutzen kannst (zum Beispiel eine Bib für große Zahlen benutzen) kannst du auch alles in eines packen.

Das ganze ist ein 53er-System (da 85-32=53) in dem einfach die gewünschten Zahlen minus 32 die depth'ste Stelle sind. Die Formel am Ende ist aus Wikipedia zur Berechnung der depth'sten Stelle einer b-adischen Zahl mit b=53.

edit: Das Polynom würde ich nicht nehmen, da es numerisch extrem instabil ist. Du musst auf zig-Nachkommastellen genau rechnen, um am Ende die Werte zu treffen, ansonsten liegt das Ergebnis weit daneben.

edit2: Falls es dein Compiler kann (vermutlich kann er es) ist hier der schönere Code:

#include<iostream>

using namespace std;

unsigned long long my_pow(unsigned long long base, unsigned exponent)
{
  unsigned long long result=1;
  for (unsigned i=0; i<exponent; ++i) result*=base;
  return result;
}

char getchar(unsigned depth)
{ 
  const unsigned long long magic=20331552428843ULL;
  return magic/my_pow(53, depth) - 53*(magic/my_pow(53, depth+1)) + 32;
}

int main()
{
  for (unsigned i=0; i<11; ++i) cout << getchar(i);
  cout<<endl;
}

edit3: Ups, ich habe versehentlich "Abi 2001" statt "Abi 2011" geschrieben. Die Korrektur der Zahlen sollte nicht schwer sein.

Du kannst z.B. die Lagrange-Interpolation benutzen. Um das auszurechnen, würde ich aber an deiner Stelle auf maple oder mathematica oder so etwas benutzen. Per Hand macht das sonst ziemlich viel Spass:-).

Die andere Möglichkeit, Du programmierst den Algorithmus direkt. Das sähe in Java z.B. etwa so aus:

public class lagrange {
	lagrange() {
		for(int i=0; i<11;++i)
			System.out.println("f("+i+") = " + f(i));	
	}

	public double f(double x) {
		double knots[] = {65.0, 66.0, 73.0, 84.0, 85.0, 82.0, 0.0, 80.0, 48.0, 49.0, 49.0};
		double result = 0.0;
		double lagrange = 1.0;
			for(int i=0; i<knots.length;++i) {
				for(int j=0; j<knots.length;++j) {
					if(i!=j) 
						lagrange *= (x - j)/(i - j);						
				}
				result += lagrange*knots[i];
				lagrange =1.0;		
			}
		return result;	
	}

	public static void main(String args[]) {
		new lagrange();	
	}
}

P.S:Im zweifelsfall sollte sich die Funktion f(x) ziemlich leicht in jede andere Programmiersprache übersetzen lassen.

nimm doch gnuplot.

mit einem Interpolationspolynom vom Grad 10 komme ich auf die selben Koeffizienten wie Th69.

natürlich kann man auch mit raffinierteren Funktionen interpolieren, z.B. mit a*sin(x)+ ... +j*sin(10*x)+k:

set term postscript
set output "blub.ps"
set multiplot

f(x)=a*sin(x)+b*sin(2*x)+c*sin(3*x)+d*sin(4*x)\
+e*sin(5*x)+f*sin(6*x)+g*sin(7*x)+h*sin(8*x)+i*sin(9*x)+j*sin(10*x)+k

fit f(x) "blub.dat" using 1:2 via a,b,c,d,e,f,g,h,i,j,k
plot "blub.dat" using 1:2 notitle pointtype 7, f(x)

freakC++

Th69 schrieb:

dann mußt du falsch gerechnet haben.

Das habe ich! Fehler beseitigt!

SeppJ schrieb:

Ich schließe, du willst einfach Obfuscation?

Du bist Hellseher!? Ja, genau das möchte ich haben ! Dein Codeschnipsel gefällt mir aber sehr! Doch ich kann ihn nicht so ganz nachvollziehen.

Ich habe von Obfuscation nicht nie was gehört! DAs ist aber hammer cool! Danke auch an alle anderen! Ich denke aber, dass ich SeppJs Vorschlag nehme (sobald ich ihn verstanden habe)

edit: Rest gelöscht, weil ich mir selber nicht einig war, was ich erst fragen soll!

Vielen Dank
lg, freakC++

freakC++

Ich erstelle lieber noch einen neuen Post, bevor ich den Rekord der meisten Änderungen knacke!

Ich habe mich ein bisschen informiert! SeppJ hat anscheinend die Formel der Wikipedia Seite "Stellenwertsystem" genutzt. Diese habe ich nun auch gefunden.

Mir sind jetzt eigentlich nur drei Sachen nicht klar.

1.) Welche Aufgabe hat "magic" und wie errechne ich diese Zahl?

2.) Ist das Stellensystem 53 beliebig oder hat es einen Grund, warum Du dich dafür entschieden hast?

3.) Warum kommen gerade die Zahlen heraus, die ich gerne hätte, wenn ich x mit 1 inkrementiere. Warum erscheint gerade die Folge 65, 66, 73....?

Danke
lg, freakC++

SeppJ

freakC++ schrieb:

1.)
magic1=117004UL;
  const unsigned long magic2=2576719UL;
Was sind das für Zahlen und wie kommst Du darauf?

Das ist vielleicht einfacher an dem zweiten Codeschnipsel nachzuvollziehen:

20331552428843 = (65-32)*53^0 +
                 (66-32)*53^1 +
                 (73-32)*53^2 +
                 (32-32)*53^3 +
                 (50-32)*53^4 +
                 (48-32)*53^5 +
                 (48-32)*53^6 +
                 (49-32)*53^7

Und da ich mich bei der vorletzten Zeile vertan habe (da sollte ja eigentlich eine 49 statt 48 stehen) kommt ABI 2001 und nicht ABI 2011 raus, aber das kannst du ja leicht ändern.
Wenn du "ABITUR 2011" willst, musst du entsprechen noch was dazwischen fügen. Da 53^11 < 2^64 sollte das aber noch gehen, vorausgesetzt ein long long ist bei dir ebenfalls (mindestens) 64 Bit groß.

Die beiden kleineren Zahlen sind jeweils

117004 = (65-32)*53^0 +
         (66-32)*53^1 +
         (73-32)*53^2 +
         (32-32)*53^3

und

2576719 = (50-32)*53^0 +
          (48-32)*53^1 +
          (48-32)*53^2 +
          (49-32)*53^3

da ich sonst nicht genug Platz hatte, wenn ich mich streng an die Mindestgröße eines long im C++-Standard halte.

2.) Du sprichst von einem 53er-System mit der Begründung 85-32=53!!

Da ich die 0 durch eine 32 ersetzt habe, hast du Werte zwischen 32 (für das Leerzeichen) und 85 (für das U). Um Platz zu sparen, kann ich daher immer erst 32 abziehen und erhalte dann maximal Werte bis 53 (siehe Rechnung oben). Und hier finde ich auch einen Fehler bei mir: Damit "Ziffern" in meinem Zahlensystem Werte zwischen 0 und 53 haben können, müsste ich ein 54er System nehmen. Die Rechnung muss dementsprechend geändert werden, wenn du "ABITUR 2011" haben willst.

Ich habe nach der sogenannten "depth'sten" Zahl gegoogelt, aber man findet gar nichts. Was ist das? Wie kommst Du auf 32? Und was macht "depth"?

Ja, depth ist ein schlechter Bezeichner. Wollte das Programm ursprünglich rekursiv machen. Aber so wie es jetzt ist, sollte ich das depth wohl eher N nennen. Das get_char liefert dann die N'te Stelle der Zahl magic im 53er-System.

3.) Welchen Wikipedia Artikel meinst Du?

Die Formel findet man hier:
http://de.wikipedia.org/wiki/Stellenwertsystem#Formeln_f.C3.BCr_Ziffern_und_Operationen_mit_Ziffern

Für b habe ich 53 (Die Basis des Zahlensystems), x ist das magic also die Zahl deren Stelle man wissen will und k ist das depth, also die wievielte Stelle man wissen will.

4.) Ich muss gestehen, dass ich Abi 2001 nicht in "Abitur 2011" umwandeln kann. Das liegt daran, dass momentan da noch nicht so richtig durchblicke! Ich verstehe nicht, wie die Buchstaben erzeugt werden!

Mit der ausführlichen Rechnung oben sollte das klappen. Wenn du Schwierigkeiten hast, sag Bescheid. Du wirst aber einen guten Taschenrechner brauchen, Google calc stellt solch große Zahlen nicht mehr exakt dar. Wolfram Alpha sollte das können oder auch jedes etwas bessere Rechenprogramm auf deinem Computer. Oder ein selbst geschriebenes Programm.
Und falls die Zahlen zu groß werden ("ABITUR 2011" sollte gehen, aber "Abitur 2011" ist zu groß für 64-Bit longs), musst du eventuell auf eine BigInt Bibliothek ausweichen.

freakC++

Ich danke dir! Ich werde nun einiges ausprobieren und mich dann nochmal melden!

lg, freakC++

freakC++

Mir ist noch nicht ganz klar, warum Du gerade 32 als Leerzeichen gewählt hast. Wenn ich beispielsweise 20 als Leerzeichen nehme, dann kann ich auch ein 65 System nehmen, oder?

lg, freakC++

Th69

Weil das Leerzeichen (SPACE) den ASCII-Code 32 hat!?

freakC++

Th69 schrieb:

Weil das Leerzeichen (SPACE) den ASCII-Code 32 hat!?

ups...wenns auch einfach geht! Klar, ich habe bis jetzt 0 dafür verwendelt, aber das ist ja einfach NULL.

Ich habe nun versucht die Zeile "Abitur 2011" zu erzeugen. Dazu habe ich folgende Rechnungen durchgeführt:

(65-32)*53^0 + (66-32)*53^1 + (73-32)*53^2 + (84-32)*53^3 + (82-32)*53^3

(32-32)*53^0 + (50-32)*53^1 + (48-32)*53^2 + (49-32)*53^3 + (4982-32)*53^3

Die Ergebnisse habe ich mit wolfram alpha erhalten. Die Ergebnisse lauten:

const unsigned long magic1=15302458UL; 
const unsigned long magic2=739517957UL;

Bei den obigen Rechnungen habe ich ausschließlich die fehlenden Buchstaben ergänzt. Meine getchar Methode sieht jetzt so aus:

char getchar(unsigned depth) 
{ 
  const unsigned long magic1=15302458UL; 
  const unsigned long magic2=739517957UL; 
  unsigned long magic=magic1; 
  if (depth>3){ 
    depth-=4; 
    magic=magic2; 
  } 

  return magic/static_cast<unsigned long>(my_pow(53, depth)) - 53*(magic/static_cast<unsigned long>(my_pow(53, depth+1))) + 32; 
}

Das Programm spuckt aber nicht "Abitur 2011" aus, sondern "ABIQ 20FHy" - also völliger Blödsinn (nur der Anfang stimmt).

Habe ich das System doch noch nicht durchblickt, SeppJ? Was mache ich falsch bzw was muss ich ändern, damit "Abitur 2011" erscheint?

lg, freakC++

lustig

freakC++ schrieb:

Dazu habe ich folgende Rechnungen durchgeführt:
(65-32)*53^0 + (66-32)*53^1 + (73-32)*53^2 + (84-32)*53^3 + (82-32)*53^3

Schau dir die Zeile nochmal genau an... dann siehst du was falsch ist.

SeppJ

Zunächst einmal muss der jeweils letzte Term natürlich mit 53^4 multipliziert werden. Weiterhin habe ich keine Ahnung, wo die Zahl 4982 herkommt. Schreibfehler?

Und da du jetzt in magic1 die ersten 5 statt 4 Zeichen hast, musst du bei der Abfrage natürlich auf >4 prüfen und gegebenenfalls auch 5 von depth abziehen.

Und du hast das U vergessen.

freakC++

SeppJ schrieb:

Schreibfehler?

Ja, das war ein Schreibfehler.

Ich habe nun zunächst in die eine Gleichung die Buchstaben "ABITU" gesteckt. Es ergibt sich folgende Gleichung:

(65-32)*53^0 + (66-32)*53^1 + (73-32)*53^2 + (84-32)*53^3 + (85-32)*53^4 = 426054101

In die zweite Gleichung kommt dann "R 2011":

(82-32)*53^0 + (32-32)*53^1 + (50-32)*53^2 + (48-32)*53^3 + (49-32)*53^4 + (49-32)*53^5 = 7245894202

Das Ergebnis stimmt aber wieder nur bis "ABIT" . Danach ist alles falsch! Diesmal stimmen aber alle Potenzen und es gibt keine Schreibfehler mehr. Warum erscheint beispielsweise das "UR" nicht?

Depth muss auch nicht angepasst werden, weil in der ersten Zahl die ersten 4 Buchstaben gespeichert werden!?!

Was sehe ich da nicht?

lg, freakC++

lustig

freakC++ schrieb:

Ich habe nun zunächst in die eine Gleichung die Buchstaben "ABITU" gesteckt.
[...]
Depth muss auch nicht angepasst werden, weil in der ersten Zahl die ersten 4 Buchstaben gespeichert werden!?!

Aus meiner Sicht sind "ABITU" nicht 4 Buchstaben...

Edit:
Hast du SeppJs Beitrag durchgelesen?

SeppJ schrieb:

Da ich die 0 durch eine 32 ersetzt habe, hast du Werte zwischen 32 (für das Leerzeichen) und 85 (für das U). Um Platz zu sparen, kann ich daher immer erst 32 abziehen und erhalte dann maximal Werte bis 53 (siehe Rechnung oben). Und hier finde ich auch einen Fehler bei mir: Damit "Ziffern" in meinem Zahlensystem Werte zwischen 0 und 53 haben können, müsste ich ein 54er System nehmen. Die Rechnung muss dementsprechend geändert werden, wenn du "ABITUR 2011" haben willst.

freakC++

lustig schrieb:

[Aus meiner Sicht sind "ABITU" nicht 4 Buchstaben...

Da stimme ich dir zu! Verzählt. Also habe ich noch schnell depth angepasst und ein 54 System erstellt. Nun habe ich endlich "ABITUR". Doch im Gegenzug gibts jetzt Probleme mit der Zahl. Die letzte 1 kommt nicht. Dast ist auch klar, weil ich sie in dieser Formel nicht berücksichtigt habe:

(82-32)*54^0 + (32-32)*54^1 + (50-32)*54^2 + (48-32)*54^3 + (49-32)*54^4

Wenn ich sie nun noch anhänge, sieht es so aus:

(82-32)*54^0 + (32-32)*54^1 + (50-32)*54^2 + (48-32)*54^3 + (49-32)*54^4 + (49-32)*54^5

Jetzt kommt aber wieder Mist raus? Ist die Zahl zu groß oder warum klappts mit der letzten 1 nicht? Eigentlich müsste doch alles stimmen.

lg, freakC++

SeppJ

freakC++ schrieb:

Jetzt kommt aber wieder Mist raus? Ist die Zahl zu groß oder warum klappts mit der letzten 1 nicht? Eigentlich müsste doch alles stimmen.

Zeig mal bitte den Code so wie er jetzt ist und sag auch was sizeof(long) und sizeof(long long) bei dir sind (falls es bei dir long long gibt).

Th69

Rechne mal 54^5 aus und schau mal nach, ob diese noch in ein ulong (32bit) paßt