4. Algorithmus gesucht: nächstgrößere Zahl, die bestimmter Regel entspricht

Algorithmus gesucht: nächstgrößere Zahl, die bestimmter Regel entspricht

  • ?

    Äh ja mein Algorithmus war Banane, hab um ehrlich zu sein auch nicht wirklich darüber nachgedacht 😃

    Allerdings ist das KEINE Studienaufgabe, ich brauche das für eine eigene Hash-Datenstruktur, die ich schreiben will. Es geht um effizientes Sondieren bei Kollision.

    Vielen Dank für die Tipps!

    0
  • Mod

    Darf ich vorschlagen zu schummeln die Aufgabenstellung kreativ zu interpretieren?

    Du suchst dir eine möglichst große Primzahl mit der genannten Bedingung. Ist die Eingabe kleiner, dann gibst du diese aus. Ist die Eingabe größer, fällst du auf einen anderen Algorithmus zurück. Da nicht die kleinste Primzahl > i gesucht ist, kann man sich so für sehr viele Eingaben die Rechnung sparen.

    Optimal wäre es natürlich, wenn die Eingabe irgendwie nach oben beschränkt wäre.\

    edit: Ok, dadurch dass es keine Schulaufgabe ist, hätte sich dieser Vorschlag wohl erledigt 😞 .

    edit2: Eine andere Methode die mir vorgeschwebt hätte, wäre mal zu gucken, ob Mersenne-Primzahlen die genannte Bedingung erfüllen können, dann hatte man einfach die nächsten Kandidaten prüfen können bis man eine Primzahl findet. Ist wohl auch für diese Aufgabe ungeeignet.

    Was aber geeignet sein könnte: Du sagst, es wäre für eine Hashfunktion? Dann ist die Eingabemenge doch sicherlich nicht zu groß (32 Bit?) Da kannst du doch alle Primzahlen mit deiner Bedingung im Voraus suchen und im Programm einbauen. So viele können das doch nicht sein.

    0
  • V

    CStoll schrieb:

    j=4*(i/4)+3;
if(j<i) j+=4;//warning C4711: condition is always false, isn't it?
for(;!isPrim(j);j+=4);
    0
  • C

    @volkard: Sorry, dann sollte das wohl eher <= sein

    0
  • V

    SeppJ schrieb:

    Darf ich vorschlagen zu schummeln die Aufgabenstellung kreativ zu interpretieren?
    Du suchst dir eine möglichst große Primzahl mit der genannten Bedingung.

    Cool! 👍
    Mersenne-Primzahlen haben die Form 2n−1 also 42n-2-1 also 4(2n-2-1)+3.
    Und da gibt es große im Netz. Ich verzichte darauf, alle 12978189 Stellen der größten derzeit bekannten zu posten.

    0
  • ?

    @SeppJ:
    Sorry, gesucht ist die KLEINSTE Primzahl j >= i, für welche die Regel gilt. j - i ist nämlich Zusatzspeicher, den ich verbrate, nur mit dem Sinn, dass j obiger Regel entspricht. Von daher ... 😉

    0
  • V

    algomat schrieb:

    Hash-Datenstruktur, die ich schreiben will.

    Und wie sind die Vollstandsbedingungen? Soll sie dynamisch wachsen?
    Mal feste Zahlen genommen, mit 11 angefangen und immer die nächsthöhere ist ca 50% mehr.
    Solche vorberechneten Arrays werden gerne benutzt.

    int main(){
    using namespace std;
    cout<<"possibleHashSizes[]={";
    for(int j=11;j>0;j=findNextFunnyPrime(j+j/2))
        cout<<j<<',';
    cout<<"};\n";
}

    Ausgabe:

    int possibleHashSizes[]={11,19,31,47,71,107,163,251,379,571,859,1291,1951,
2927,4391,6599,9907,14867,22303,33479,50227,75347,113023,169567,254383,
381607,572419,858631,1287947,1931927,2897959,4347011,6520519,9780787,
14671183,22006843,33010343,49515547,74273327,111410003,167115019,250672547,
376008823,564013283,846019963,1269029947,1903544939,};
    0
  • ?

    Das ist natürlich auch eine Idee, volkard. Tatsächlich ist der Speicher der Datenstruktur von Beginn an begrenzt, was in diesem Fall auch vollkommen ausreichend ist. In diesem Fall wäre es wohl echt effizienter, ein Array mit möglichen Werten zu halten.

    Danke nochmal.

    0
  • V

    algomat schrieb:

    Das ist natürlich auch eine Idee, volkard. Tatsächlich ist der Speicher der Datenstruktur von Beginn an begrenzt, was in diesem Fall auch vollkommen ausreichend ist. In diesem Fall wäre es wohl echt effizienter, ein Array mit möglichen Werten zu halten.

    Danke nochmal.

    Nicht nur das. Wenn wie bei meinem Beispiel der Füllstand zwischen 66% und 100% liegen darf, ist das ja ein exponentielles Wachstum der Zhalen im Array. Für 64 Bit wird das Array nur doppelt so lang wie für 32 Bit. Es bleibt lächerlich klein.

    Oder zwischen 50% und 75% oder zwischen 53% und 80%, um die magische 80 zu benutzen.

    0
  • C

    Gibt es für die Aufgabe keine fertige Bibliothek?

    0
  • ?

    int possibleHashSizes[]={11,19,31,47,71,107,163,251,379,571,859,1291,1951,
    2927,4391,6599,9907,14867,22303,33479,50227,75347,113023,169567,254383,
    381607,572419,858631,1287947,1931927,2897959,4347011,6520519,9780787,
    14671183,22006843,33010343,49515547,74273327,111410003,167115019,250672547,
    376008823,564013283,846019963,1269029947,1903544939,};

    Wie wäre es alle Primzahlen in dem endlichen Bereich von Integer vorzuberechnen die diese Bedingung erfüllen und dann einfach mit binärer Suche die kleinste die größer ist als deine Zahl i, in dieser Tabelle zu suchen?
    (Es scheinen doch relativ ewenige zu sein die gespeichert werden müssten)

    0
  • V

    MisterX schrieb:

    Wie wäre es alle Primzahlen in dem endlichen Bereich von Integer vorzuberechnen die diese Bedingung erfüllen und dann einfach mit binärer Suche die kleinste die größer ist als deine Zahl i, in dieser Tabelle zu suchen?
    (Es scheinen doch relativ ewenige zu sein die gespeichert werden müssten)

    Hoffnungslos.
    Es gibt unter n circa n/ln(n) Primzahlen, vermutlich n/ln(n)/2 Primzahlen mit dieser Bedingung.
    Bis 1000000 also schon mehr als 36000. Bis 4Mrd für 32 Bit mag ich es gar nicht ausrechnen. Und ich strebe 64 Bit an.

    0
Anmelden zum Antworten