Iterative oder Rekursive? Geschwindigkeit

Ich wieder mit meinen Flüchtigkeitsfehlern...meine natürlich

O = S + 1 + 10 \sum_{i=1}^{6}\sum_{j=a_{i-1} + 1}^{a_i - 1} {{49 - j}\choose{6 - i}}

lottofee2010

Abend zusammen,

@DirkB

Die Überlegung im Source die innerste Schleife für die Superzahl wegzulassen, nur die Tipp Zahlen zu prüfen, statt dessen meinen Zähler immer um 10 zu erhöhen und am Ende die Superzahl einfach drauf zu addieren, habe ich auch schon getestet, es beschleunigt die Angelegenheit zwar, aber leider nicht so viel wie erwünscht.

@seldon
Krass, ich bin mir sicher eine solche mathematische Funktion hätte ich nicht auf Anhieb aus dem Ärmel geschüttelt, nein eher niemals... Respekt.
Wie kamst du so schnell darauf?

Leider kann ich das ganze daheim nicht testen, aber ich habe die Formel schon mal in Java versucht umgesetzt, leider kämpfe ich dort noch mit Fehlern und einem Überlauf einer Variable, aber wenn ich das behoben habe, werde ich es in C versuchen.

Ich vermute, dass ich bei hohen Tipp Zahlen die Fakultät von 48 berechnen will und dabei mein long variable zu kurz ist^^

package bs.edv;

import java.text.DecimalFormat;

public class GetNr {

  public GetNrSave(int[] search) {

    long time = -System.currentTimeMillis();
    long o = this.ordinalzahlErmitteln();
    System.out.println(DecimalFormat.getInstance().format(o));
    time += System.currentTimeMillis();
    System.out.println("Fertig: " + (time) + "ms");

  }

  /*
   * Formel(in LaTeX): O = S + 1 + 10 \sum_{i=1}^{6}\sum_{j=a_{i-1} + 1}^{a_i
   * - 1} {{49 - j}\choose{6 - i}} wobei: O die Ordinalzahl, S die Superzahl,
   * a eine Folge mit a0 = 0, a1 = kleinste gezogene Zahl, a2 = nächsthöhere
   * Zahl... seien.
   */
  public long ordinalzahlErmitteln() {
    int[] gesucht = { 0, 1, 2, 3, 4, 5, 7, 1 }; // Ordinalzahl  = 12
    //int[] gesucht = { 0, 10, 15, 20, 25, 30, 35, 0 }; // Ordinalzahl =104169761
    long ordinalzahl = 0;
    ordinalzahl = gesucht[7] + 1 + 10 * summe(gesucht);
    return ordinalzahl;
  }

  private long summe(int[] gesucht) {
    long summe1 = 0;
    for (int i = 1; i <= 6; i++) {
      long summe2 = 0;
      for (int j = (gesucht[i - 1] + 1); j <= (gesucht[i] - 1); j++) {
        summe2 += berechnungNueberKrekursiv((49 - j), (6 - i));
        // summe2 += nUeberK((49 - j), (6 - i));
      }
      summe1 += summe2;
    }
    return summe1;
  }

  private double nUeberK(int n, int k) {
    int i = 0;
    double ergeb = 0;
    if (k > n) {
      return 0;
    }
    if (k == 0 || k == n) {
      return 1;
    } else {
      ergeb = 1;
      for (int j = 1; j <= k; j++) {
        ergeb = ergeb * (n - j + 1) / i;
      }
    }
    return ergeb;
  }

  public long berechnungNueberKrekursiv(int n, int k) {
    long ergebnis = 0;
    ergebnis = this.fakultaet(n)
        / (this.fakultaet(k) * this.fakultaet(n - k));
    return ergebnis;
  }

  private long fakultaet(int n) {
    if (n == 0 || n == 1)
      return 1;
    else
      return n * fakultaet(n - 1);
  }

  public static void main(String[] args) {
    new GetNrSave(new int[] { 10, 15, 20, 25, 30, 35, 0 });
  }
}

grüße lottofee

Ps.: Ich suche irgendwie eine Spoiler Tag im Posting-Editor^^

Das ist eigentlich ziemlich anschaulich. Ich fange mal bei 0 an zu zählen, das macht die Herleitung etwas einfacher - das "+ 1" in der Formel gleicht das nachher wieder aus.

Die erste Ziehung mit kleinster Zahl 1 hat die Ordinalzahl 0, und es gibt 48 über 5 solche Ziehungen. Die erste Ziehung mit kleinster Zahl 2 hat also die Ordinalzahl (48 über 5), und es gibt 47 über 5 solche Ziehungen. Die erste Ziehung mit kleinster Zahl 3 hat dementsprechend die Ordinalzahl (48 über 5) + (47 über 5), und so weiter. Die erste Ziehung mit kleinster Zahl n hat die Ordinalzahl \sum_{j=1}^{n - 1} {{49 - j} \choose {5}} (wieder in LaTex gesprochen).

Wenn man diesen Offset heraus hat, löst man das selbe Problem für die verbleibenden 5 Ziffern. Da die kleineren Zahlen als die kleinste Zahl (deswegen ist es wichtig, dass die Folge sortiert ist!) ausgeschlossen sind, geht man nicht von 49, sondern von der kleinsten Zahl aus (j läuft also praktisch einfach weiter) und setzt den unteren Teil des Binomialkoeffizienten einen kleiner (man hat ja nur noch 4 weitere Ziffern auszuwählen).

Damit kriegt man die Ordinalzahl der sechs Zufallszahlen. Das mal 10 plus Superzahl ist dann die Ordinalzahl der Ziehung plus Superzahl, und dann halt + 1, um von 1 statt von 0 zu zählen.

Was dein Problem bei der Implementation angeht, so wird das sicherlich an der Fakultät liegen. Du hast aber mit nUeberK ja schon den richtigen Ansatz gefunden, das Problem zu umgehen.

Eine Sache noch: Die Formulierung

seldon schrieb:

(j läuft also praktisch einfach weiter)

ist etwas unglücklich gewählt: die Zahlen, die in der Ziehung enthalten sind, werden dabei übersprungen. Bei der Ziehung (10, 15, 20, 25, 30, 35), die du in deinem Beispiel hast, sind die Bruchstellen

49 - 10 = 39
49 - 15 = 34
49 - 20 = 29
49 - 25 = 24
49 - 30 = 19
49 - 35 = 14

...und werden selbst nicht als n benutzt (die letzte ist eh der Endpunkt). Es ergibt sich

(48 5) + ... + (40 5) + (38 4) + ... + (35 4) + ... + (33 3) + ... + (30 3) + (28 2) + ... + (25 2) + (23 1) + ... + (20 1) + (18 0) + ... + (15 0)

Das dann halt mal 10 + Superzahl + 1.

lottofee2010

Morgen zusammen,
ich habe jetzt mal versucht alles umzusetzen, dabei ist folgendes heraus gekommen:

#include <stdio.h>
#include <string.h>
#include <time.h>

int summe(int *);
double nUeberK(int,int);

int berechneOrdinalzahl(int *gesucht){
 int ordinalzahl = 0;
 ordinalzahl = gesucht[7] + 1 + 10 * summe(gesucht);
 return ordinalzahl;
}

int summe(int *gesucht){
 int summe1=0;
 for (int i = 1; i <= 6; i++) {
   int summe2 = 0;
   for (int j = (gesucht[i - 1] + 1); j <= (gesucht[i] - 1); j++) {
     summe2 += nUeberK((49 - j), (6 - i));
   }
   summe1 += summe2;
 }
 return summe1;
}

double nUeberK(int n, int k){
 double ergeb=0;
 if (k > n) {
  return 0;
 }
 if (k == 0 || k == n) {
   return 1;
 } else {
   ergeb = 1;
   for (int j = 1; j <= k; j++) {
      ergeb = ergeb * (n - j + 1) / j;
   }
 }
 return ergeb;
}

int main()
{
  int gesucht[]={0,44,45,46,47,48,49,9};
  clock_t prgstart, prgende;
  prgstart=clock();
  int o = berechneOrdinalzahl(gesucht);
  printf("Ordinalzahl = %d\n",o);
  prgende=clock();
  printf("Laufzeit %f Sekunden\n",(double)(prgende-prgstart) / CLOCKS_PER_SEC);
  printf("Programm ende.\n");
  return 0;
}

Da mir mitgeteilt wurde, dass mein Programmiersyle nicht der schönste sein, wollte ich nach fragen ob dieser Code, besser aussieht als der aus den ersten Post?

Außerdem wollte ich mich herzlich bei allen bedanken die mir weitergeholfen haben und besonders bei seldon.

mfg eure lottofee

ps.: viel spaß beim lotto spielen xD

Das sieht auf jeden Fall schon deutlich besser aus. Es gibt ein paar Kleinigkeiten, bei denen man sich streiten kann - beispielsweise kann man summe2 in Zeile 17 wegrationalisieren - und ich hätte, wenn es sich um Produktionscode handelte, ein paar Verbesserungsvorschläge (etwa hätte ich die 0 in der Folge implizit dargestellt statt explizit im Speicher verlangt und die Ziehung in einem eigenen Datentypen dargestellt, damit man nicht aus Versehen zu kurze Arrays in die Funktion schmeißen kann), aber für einen Anfänger ist das eine solide Leistung.

Meine Implementation sah so aus:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Das meine ich mit dem eigenem Datentypen: So muss man sich von außen schon
 * ein bisschen anstrengen, um ordinal (s.u.) falsche Parameter zu übergeben.
 */
typedef struct {
  unsigned zahlen[6];
  unsigned superzahl;
} ziehung_t;

unsigned bincoeff(unsigned n, unsigned k) {
  unsigned result = 1, i;

  for(i = 1; i <= k; ++i) {
    result = result * (n - k + i) / i;
  }

  return result;
}

int u_compare(void const *lhs, void const *rhs) {
  return *(unsigned const *)lhs - *(unsigned const*) rhs; 
}

int ordinal(ziehung_t ziehung) {
  unsigned i, j, sum = 0;

  /* Wir haben den Parameter by-value übernommen, also können wir
   * darin herumschreiben, ohne die Eingabedaten zu ändern. qsort
   * sortiert das Eingabearray anhand der angegebenen Vergleichsfunktion,
   * in diesem Fall u_compare. Kurzer Erklärungsversuch dazu unten.
   */
  qsort(ziehung.zahlen, 6, sizeof(unsigned), u_compare);

  /*  6      a(i)-1
   * ---      ---     /       \
   * \        \      ( 49 - j  )
   *  >        >     (         )
   * /        /      (  6 - i  )
   * ---      ---     \       /
   * i=1  j=a_(i-1)+1
   *
   * mit a(0) = 0, a(1 - 6) = Zahlen der Ziehung in aufsteigender Reihenfolge.
   */
  for(i = 0, j = 1; i < 6; ++i, ++j) {
    for(; j < ziehung.zahlen[i]; ++j) {
      sum += bincoeff(49 - j, 5 - i);
    }
  }

  return sum * 10 + ziehung.superzahl + 1;
}

int main(void) {
  /*
    ziehung_t ziehung = { { 44, 45, 46, 47, 48, 49 }, 9 };
    ziehung_t ziehung = { { 1, 2, 3, 4, 5, 6 }, 0 };
  */
  /* ziehung_t ziehung = { { 3, 12, 18, 32, 37, 40 }, 5 }; /* 41488796 */
  ziehung_t ziehung = { { 10, 15, 20, 25, 30, 35 }, 0 }; /* 104169761 */

  printf("%d\n", ordinal(ziehung));

  return 0;
}

Der qsort-Kram geht wahrscheinlich über das hinaus, was ihr bisher gehabt habt. Wahrscheinlich nimmt es dir niemand übel, wenn du dich nicht sofort damit befassen willst, aber es ist später sehr praktisch, das zu verstehen, also für den Fall, dass es dich interessiert:

qsort ist eine Funktion der C-Standardbibliothek, die eine Sortierung (Quicksort) implementiert. Da es in C keine generischen Sprachbestandteile gibt, läuft das über rohen Speicher --

qsort(ziehung.zahlen, 6, sizeof(unsigned), u_compare);

sagt im Grunde: Hier sind sechs Speicherblöcke der Größe sizeof(unsigned), die du bitte sortieren sollst. So eine Sortierung ergibt nur dann Sinn, wenn man eine totale Ordnung über die Wertemenge hat (eine Methode zu bestimmen, welcher von zwei Blöcken den kleineren Wert hat), wofür die Funktion u_compare übergeben wird. Die komische Signatur mit zwei void-Zeigern ist der Tatsache geschuldet, dass qsort ein möglichst allgemeines Interface zur Verfügung stellen will; lass dich davon nicht beeindrucken. Sie kriegt zwei Zeiger auf zwei Zahlen und bestimmt, ob die erste kleiner, gleich oder größer als die zweite ist (vergleichbar mit strcmp).

Ich nehme an, dass es dich überrascht, dass man in C Funktionen einfach so herumreichen kann (ich wäre darauf als Anfänger jedenfalls im Leben nicht gekommen), aber es ist wirklich nicht so richtig schwierig (auch wenn die Syntax furchtbar aussieht). Jede Funktion liegt an einer bestimmten Stelle im Speicher. Darauf kann man einen Zeiger nehmen, den kann man herumreichen, und damit kann man die Funktion dann aufrufen. Mal ein ganz einfaches Beispiel:

#include <stdio.h>

void foo(void) { puts("foo"); }
void bar(void) { puts("bar"); }

void call(void (*func)(void)) {
  func();
}

int main(void) {
  /* func_ptr ist ein Zeiger auf eine Funktion mit Signatur void (void) */
  void (*func_ptr)(void);

  func_ptr = foo;
  func_ptr(); /* ruft foo() auf */

  func_ptr = bar;
  func_ptr(); /* ruft bar() auf */

  /* Und das geht halt auch mit Funktionsparametern */
  call(foo);
  call(bar);

  return 0;
}

Damit kann man dann richtig coole Dinge (und auch viel Schindluder) treiben. Wenn du von Java her kommst, hast du vielleicht von der Strategy-Pattern gehört; wenn man so was in C anfängt, wirft man im Zweifel mit Funktionszeigern um sich.

In der Praxis ist es, wenn man mit Funktions- oder Arrayzeigern hantiert, meistens sinnvoll, typedefs zu benutzen, sonst wird die Syntax schnell sehr unübersichtlich. Das Paradebeispiel dafür ist die Standardfunktion signal, die in Rohform so aussieht:

void (*signal(int signum, void (*handler)(int)))(int);

Da sitzen dann auch Fortgeschrittene davor und kratzen sich ein bisschen am Kopf, bis sie rausgekriegt haben, was das soll. Kontrast dazu: In der Form

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);

ist es auf Anhieb erkennbar.

lottofee2010

Hey,

Wenn das so schonmal besser aussieht bin ich glücklich.
Ich glaube ich bleibe auch bei meinem Code da er ja eigentlich funktioniert aber auch verbesserungswürdig ist.
Mein Ausbilder nimmt mir dann eher ab das ich das geschrieben habe und ich bin auf der sicheren Seite, auch wenn er nichts gegen forumhilfe hat, die er sich selbst gelegentlich holt.

seldon schrieb:

Der qsort-Kram geht wahrscheinlich über das hinaus, was ihr bisher gehabt habt.

Mit dem Quicksort hatte ich schon öfter zu tun und diesen auch schon mehrmals in Java implementiert, nur noch nicht in C.
(Dieses ist mein erstes C Projekt und auch mein erster Kontakt mit der Programmiersprache.)

Das mit dem herrumreichen von funktionen habe ich jetzt leider nicht ganz verstanden, aber ich denke dazu wird es noch kommen.
Aber gut zu wissen das sowas überhaupt geht.

Eine paar fragen hätte ich noch, und zwar wie arbeitet die funktion u_compare:

int u_compare(void const *lhs, void const *rhs) {
  return *(unsigned const *)lhs - *(unsigned const*) rhs;
}

bzw. wo wird da verglichen welcher wert größer oder kleiner ist?

Das mit dem typedef scheint sehr sinnvoll, aber was ist der unterschied zwischen:

typedef struct { } name
typedef void{ } name
/* Ok, alle elemnte von union liegt im selben speicher bereich */
typedef union { } name

Die Vergleichsfunktion gibt per Konvention je nachdem, wie die beiden Werte zueinander stehen, einen negativen Wert (wenn der linke Wert nachher vor dem rechten stehen soll), Null (wenn beide Werte gleich sind) oder einen positiven Wert (wenn der rechte Wert nachher vor dem linken stehen soll) zurückgeben. Wenn ihr strcmp schon gehabt habt, da ist das genau so für Strings.

Das erreicht man bei Zahlen wie hier am einfachsten durch die Differenz.

Ein Struct ist quasi ein Kompositdatentyp. Du kannst es dir (jetzt in Java gesprochen) ein bisschen wie eine Klasse vorstellen, die keine Methoden hat und in der alle Member public sind. Im Gegensatz zur Union hat jeder Member seinen eigenen Speicherbereich, und sie können demnach alle gleichzeitig verwendet werden.

typedef void{ } name

ist in der Form kein gültiges C. Ich nehme an, du beziehst dich auf

typedef void (*sighandler_t)(int);

...wo keine geschweiften, sondern runde Klammern (!) benutzt werden. Das erkläre ich wohl am besten von einer Variablendeklaration her:

void *foo(int); /* deklariert eine Funktion, die int erwartet und void * zurückgibt */
void bar(int);  /* deklariert eine Funktion, die int erwartet und void zurückgibt */
void (*baz)(int); /* deklariert einen Zeiger auf eine Funktion, die int erwartet und void zurückgibt. */

Die Klammern sind da, wenn man so will, als engere Bindung zu verstehen - der Zeiger-* wird ganz eng an baz gebunden, also ist baz ein Zeiger auf etwas, was von dem ganzen Rest drumherum beschrieben wird. Mit typedef ist es dann halt keine Variablendeklaration, sondern eine Typnamendeklaration, d.h.

void foo(int) { }

typedef int zahl_t;
typedef struct { double x; double y; } punkt_t;
typedef void (*sighandler_t)(int);

zahl_t x = 1;
punkt_t p = { 1.2, 3.4 };
sighandler_t func = foo;

Das ist bei allen Typen orthogonal; ich kann auch, wenn ich lustig bin,

struct {
  double x;
  double y;
} p; /* p ist hier eine Variable! */

p.x = 1.2;
p.y = 3.4;

schreiben.

Eine Besonderheit bei structs und unions, die dir sicher noch über den Weg laufen wird: man kann ihnen auch direkt Namen geben. Beispielsweise deklariert man mit

struct ziehung {
  unsigned zahlen[6];
  unsigned superzahl;
};

einen Datentypen struct ziehung, und man könnte dann

int ordinal(struct ziehung z) { ... }

schreiben. Bei einer union hieße der Typ dann analog "union ziehung". Ich bevorzuge in der Regel die typedef-Variante, aber die Geschmäcker sind da verschieden.

Übrigens schließen sich die beiden Varianten nicht aus: Ich kann auch

typedef struct ziehung {
  unsigned zahlen[6];
  unsigned superzahl;
} ziehung_t;

schreiben und habe dann zwei Namen für den selben Typen. Ich könnte auch

struct ziehung {
  unsigned zahlen[6];
  unsigned superzahl;
};

typedef struct ziehung ziehung_t;

schreiben und hätte damit den selben Effekt.

lottofee2010

Morgen zusammen,

seldon schrieb:

[..]Wenn ihr strcmp schon gehabt habt, da ist das genau so für Strings.[..]

Mein Ausbilder bringt mir nichts bei, ich muss das alles selber lerenen. Ich kann ihn nur ab und zu mal in Java Angelegenheiten fragen weil er sich dort auskennt.
C ist nicht sein Fach gebiet, aber ich weiß jetzt schon das ich bestehende Programm für ihn erweitern oder ersetzen soll, die zurzeit noch produktive sind.
Da kommen mir deine erklärungen ganz recht, danke.

Eine Sache noch und zwar, habe ich das richtig verstanden:

typedef int zahl_t; /* einer neuer datentype names "zahl_t", nichts anderes als int */
typedef void (*sighandler_t)(); /* ein zeiger auf eine funktion */

sighandler_t func = foo; 

void foo()
{
zahl_t x = 1;  /* eine Variable vom type "zahl_t" */
printf(" %d ",x); /* ausgabe als int, weil zahl_t ja nichts anderes ist */
}

call(func); /* hier wird die funktion foo() aufgeruffen */

So langsam passt der Titel des Themas nicht mehr...

Das ist so grob korrekt.

Zahl_t ist ein int, wenn es vorher entsprechend definiert wurde, also kann man es wie einen int verwenden, und das schließt printf-Spezifikatoren mit ein. Abhängig vom Anwendungsfall kann es aber guter Stil sein, sich nicht darauf zu verlassen - wenn man etwa damit rechnen kann, dass int irgendwann nicht mehr ausreichen könnte und zahl_t womöglich irgendwann ein long wird. In so einem Fall wäre es besser, nicht überall "%d" direkt zu schreiben, weil man sonst ggf. das halbe Programm umschreiben muss und sich nie sicher ist, alles gefunden zu haben. Ich würde dann einen Mechanismus benutzen, der sich an die PRI-Makros für Datentypen fester Breite aus dem Standard anlehnt:

typedef int zahl_t;
#define PRIzahl "d"

...

printf("Wert: %" PRIzahl " Tobleronen\n", tobleronen);

Dabei kommt einem zugute, dass Stringliterale in Einzeltoken aufgeteilt werden können:

char const *s = "foo" "bar" "baz"; /* s hat den Wert "foobarbaz" */

Wenn man das dann konsequent benutzt, muss man im Fall der Fälle nur an einer Stelle das Makro ändern.

Bei

call(foo);

wird zunächst die Funktion call mit foo als Argument aufgerufen. In dem Code, den ich oben gepostet hatte, ruft call dann die Funktion auf, auf die der übergebene Funktionszeiger zeigt, was in diesem Fall foo ist. Also ja, da wird (indirekt) foo aufgerufen.

Eine Sache übrigens noch, weil auch das nicht offensichtlich ist und einen ggf. etwas überraschen kann:

void foo();

deklariert eine Funktion foo ohne Rückgabewert mit unspezifizierter Parameterliste. Du kannst das mal ausprobieren:

void foo() { }

int main(void) {
  foo(1, 2, 3, 4, 5);
}

wird anstandslos kompilieren. Wenn du dagegen

void foo(void) { }

schreibst, was die korrekte Schreibweise für eine Funktion ohne Parameter ist, wird sich der Compiler über den Aufruf beschweren. foo benutzt die Parameter in diesem Fall nicht, also liegen sie stumpf unbenutzt auf dem Stack herum und schaden nicht groß, aber in solchen Fällen ist es im Zweifel besser, wenn der Compiler sich beschwert, als wenn das Programm nachher stillschweigend das Falsche macht. Daher kann ich dir nur raten, dir die (void)-Schreibweise anzugewöhnen.

Der Mechanismus selbst ist eher selten von Bedeutung, von Zeit zu Zeit läuft einem so etwas aber doch über den Weg. Gtk benutzt beispielsweise Funktionszeiger ohne Parameterspezifikation für Callback-Mechanismen.

lottofee2010

Danke schön, ich denke das wäre es dann erstmal gewesen.
Meine Fragen wurden super beantwortet.