Algorithmus herausfinden von Zahlenfolge?

Ich habe eine Zahlenfolge, wie z.B. 5, 10, 18, 32, 52. Die mehr oder weniger eine Kurve darstellen. Hab bei Log,Sin,Cos aber nicht so wirklich aufgepasst...

Wie kann ich den zugrundeliegenden Algorithmus herausfinden?

Edit:

Es geht um Exp/Lvl bei einem Videospiel. Wie das System funktioniert weiß ich leider nicht, aber ich habe ziemlich viele Werte:

5, 10, 18, 32, 52, 81, 119, 168, 231, 307, 400, 510, 639, 788, 959, 1154, 1375

Ich würde die Zahlenreihe gern erweitern ohne die Kurve zu verändern. Sie ist leider nicht linear.

2 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet

Alzurana

29.01.2019, 18:48

Also bei sowas am besten erst einmal plotten. Also so:

Bild zum Beitrag

Das sieht nach einer einfachen Exponentialfunktion aus. 2. Grades.

Spiele machen so etwas aber auch gerne unnoetig kompliziert. Aber wir koennen ja mal versuchen eine einfache Quadratische Funktion aus den Punkten zu bilden, vielleicht haben wir ja Glueck und unsere Annaeherung ist gut genug.

Da ich jetzt nicht viel manuell rechnen will mache ich das mal fix mit einem online Rechner aber allgemein braucht man nur 3 Punkte in die allgemeine Formel einer Quadratischen einzusetzen und dann die Unbekannten aufloesen: http://www.analyzemath.com/parabola/three_points_para_calc.html

Um die Genauigkeit zu erhoehen nehme ich Punkte, die weiter auseinander liegen. (Also nicht direkt nebeneinander sind) Ich nehme auch nicht den ersten, da es dort vielleicht durch Rundungsfehler wegen der niedigen Zahlen auch zu Problemen kommen koennte.
Also z.B.
3|18
10|307
17|1375

Die Website gibt mir nun dieses Ergebnis:

Bild zum Beitrag

Das ist mit Sicherheit nicht genau was das Game tut, da es doch sehr schiefe Zahlen sind. Aber nimmt man dies nun sollte es genau genug sein um ungefaehr die Erfahrung fuer Level 18 vorherzusagen. Also x = 18 einsetzen.

Das ergibt nun 1591,176, wir runden ab und kommen auf wahrscheinlich 1591 XP.

Das ist nicht 100% genau, da man nicht wissen kann was fuer eine Funktion die Devs da genau verwenden, dafuer braucht man genauere Analysemethoden aber es ist schon genug um eine relativ genaue Vorhersage treffen zu koennen. Man kann auch probieren ob bei einem schon bekannten Wert auch das Gleiche wieder herauspurzelt:

z.B. x = 13
Das ergibt dann 669.331 anstatt der tatsaechlichen 639.

Nun faellt schon auf, dass es wohl keine Quadrahtische Funktion ist, sondern vielleicht eine Kubische. Leider gibt es eine unendliche Anzahl von Funktionen, die auf eine Zahlenfolge passen koennten. Somit weiss man nicht genau welche Funktion es sein muss nur anhand der Zahlen. Da hilft nur Erfahrung und ausprobieren. Wenn man eine gefunden hat, die mit absolut glatten Zahlen heraus kommt dann hat man auch "den code geknackt" sozusagen.

Es gibt ein Tool, das dies erleichtert, das findet sich hier:

https://mycurvefit.com/

Da kann man seine Punkte eingeben und versuchen verschiedene Funktionen zu "passen" um zu sehen ob eine doch geht.

Woher ich das weiß:Studium / Ausbildung

Alzurana

29.01.2019, 19:09

Habe aus langeweile mit dem Tool ein bisschen rumgespielt. Die genaue Funktion habe ich immer noch nicht aber eine doch sehr genaue Annaeherung nun

y = 2.088235 + 2.334967*x + 0.2577399*x^2 + 0.256106*x^3

RIDDICC

29.01.2019, 15:33

man müsste schon n bisschen über das System wissen, das diese Zahlenfolge gemacht hat...
oder man braucht viel mehr Zahlen...
ein Polynom n-ten Grades kann man perfekt durch (n-1) Punkte biegen...
aber sowas suchst du wohl nich...
bei ner Geraden könnte man die Summe der Quadrate des Fehlers in jedem Punkt minimieren...
das geht wohl so ähnlich auch bei log, exp, sin, cos, ... aber nach ner Schwingung sehn die Beispiel-Zahlen ja nun wirklich nich aus...

Woher ich das weiß:Studium / Ausbildung

Tannibi

29.01.2019, 16:03

ein Polynom n-ten Grades kann man perfekt durch (n-1) Punkte biegen...

Durch n+1 Punkte.

RIDDICC

29.01.2019, 16:56

@Tannibi

ja... blush... hab extra vorher drüber nachgedacht an dem Beispiel einer Geraden... *heul* :)

obwohl: n-1 ist auch nich ganz falsch... bloß eben bisschen doof... gacker

Tannibi

29.01.2019, 16:58

@RIDDICC

Die du durch 0 Punkte legen willst.... ;-)

RIDDICC

29.01.2019, 17:11

@Tannibi

ja... da hat man dann viele Freiheiten und macht trotzdem nix falsch... LOL so wie Zap Brannigan als er einmal den Kurs festgelegt hat... https://www.reddit.com/r/futurama/comments/onfiw/apparently_the_captain_of_costa_concordia_the/

Alzurana

29.01.2019, 19:15

@RIDDICC

Ich will ja nicht angeben ihr beiden aber ich hab als ich fuer meinen Beitrag nach Tools online geschaut hab das hier gefunden: https://mycurvefit.com/

LEIDER gibts nur nen kostenlosen Test, das ist schon sehr bloed. Sowas braeuchte man in openSource und kostenlos. Einfach zu geil, mir ging sofort die Hose auf als ich es ausprobiert hatte. ;-;

Ähnliche Beiträge

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zum Beitrag

Sortieren von doppelt verketteter Liste?

Guten Tag,

ich soll einen simplen Algorithmus schreiben, der eine doppelt verkettete Liste, in der sich nur Nullen und Einsen befinden, sortiert (zuerst Nullen, dann Einsen).

Da ich schon ziemlich müde bin und mir immer gerne Leichtsinnsfehler passieren wollte ich fragen, ob vielleicht noch jemand ein paar kontrollierende Blicke auf meinen (Pseudo-)Code werfen kann.

Vielen Dank im Voraus!

function sort(List binList)
    begin
        pntr <- binList.head
        for (i=1, i<=n, i++){
            if(pntr.value = 0){
                pntr <- pntr.next
            }
            else{
                pntr.next.prev <- pntr.prev
                pntr.prev.next <- pntr.next
                pntr.next <- null
                pntr.prev <- tail
                tail <- pntr
            }
        }

...zum Beitrag

Binärer Suchbaum und seine Merkmale?

Wir haben einen binären Suchbaum und eine Suche, die bei einem Blatt y enden soll.

Der Pfad von der Wurzel bis y teilt die Menge aller Schlüssel in folgende 3 disjunkte Mengen X,Y,Z

Dabei enthält X alle Schlüssel die links vom Suchpfad liegen, Y ist der Suchpfad und Z enthält alle, die rechts vom Pfad liegen.

nun sollen wir ein Gegenbeispiel für diese Behauptung suchen: Für jede Wah von x in X, y in Y und z in Z gilt x<=y<=z.

Nur leider fällt mir keins ein, weil es für mich komplett logisch klingt.

ein binärer Suchbaum ist ja bekannt dafür, links immer Schlüssel zu haben, die kleiner sind und rechts immer welche zu haben, die größer sind.

...zum Beitrag

Mathematische Schreibweise einer Formel mit "Summe wenn"?

Hallo zusammen!

Stellt euch folgenden Algorithmus vor: ihr betrachtet jede Stunde des Tages die Temperatur. Wenn die Temperatur größer als 30°C ist (und nur dann), wird sie aufaddiert. So etwas würde ich praktisch in Excel mit einer "=SUMMEWENN" Funktion lösen. Wie aber schreibt man die Formel mathematisch auf? Es ist ja eher sowas wie ein Algorithmus.

Ich hatte es mir so vorgestellt wie auf dem angehängten Bild, aber die Verwendung des Ungleichungszeichen ist so wahrscheinlich eher nicht zulässig.

Und als Nebenfrage: wie würde ich eine Wenn/Dann-Funktion umsetzen? z.B. wenn T > 30°C, dann wird es aufaddiert, ansonsten multipliziert.

Bitte stört euch nicht daran, dass das Beispiel unrealistisch wirkt, es geht mir nur ums Prinzip.

Vielen Dank!

...zum Beitrag

C++ Code für LGS?

Ich möchte mit einen C++-Programm alle LGS lösen können (endlich, unendlich und keine Lösungen). Ich habe auch einen Code. Endlich viele und keine Lösungen kann er recht gut (bisher), aber unendlich viele Lösungen kann er nicht anzeigen lassen (soll dann auch t einführen, nicht einfach einen Wert einsetzen).

Wo liegt der Fehler?

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Funktion zur Berechnung des Determinanten einer Matrix
double determinant(vector<vector<double>>& matrix, int n) {
  double det = 0;

  if (n == 1) {
    return matrix[0][0];
  }

  if (n == 2) {
    return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
  }

  for (int i = 0; i < n; i++) {
    vector<vector<double>> subMatrix(n - 1, vector<double>(n - 1));

    for (int j = 1; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (k < i) {
          subMatrix[j - 1][k] = matrix[j][k];
        }
        else if (k > i) {
          subMatrix[j - 1][k - 1] = matrix[j][k];
        }
      }
    }

    det += pow(-1, i) * matrix[0][i] * determinant(subMatrix, n - 1);
  }

  return det;
}
 
// Funktion zur Durchführung der Gauss-Jordan-Elimination
void gaussJordan(vector<vector<double>>& matrix, vector<double>& constants) {
  int n = matrix.size();

  for (int i = 0; i < n; i++) {
    int maxIndex = i;

    for (int j = i + 1; j < n; j++) {
      if (abs(matrix[j][i]) > abs(matrix[maxIndex][i])) {
        maxIndex = j;
      }
    }

    if (maxIndex != i) {
      swap(matrix[maxIndex], matrix[i]);
      swap(constants[i], constants[maxIndex]); // Korrektur hier
    }

    double factor = matrix[i][i];

    for (int j = i; j < n; j++) {
      matrix[i][j] /= factor;
    }

    constants[i] /= factor;

    for (int j = 0; j < n; j++) {
      if (j != i) {
        double factor = matrix[j][i];

        for (int k = i; k < n; k++) {
          matrix[j][k] -= factor * matrix[i][k];
        }

        constants[j] -= factor * constants[i];
      }
    }
  }
}

// Funktion zur Überprüfung der Invertierbarkeit und zur Lösung des LGS
vector<double> solveLinearSystem(vector<vector<double>>& matrix, vector<double>& constants) {
  int n = matrix.size();
  double det = determinant(matrix, n);

  // Überprüfung auf unendlich viele Lösungen
  bool allZero = true;

  for (double constant : constants) {
    if (constant != 0) {
      allZero = false;
      break;
    }
  }

  if (det == 0) {
    if (allZero) {
      cout << "Das LGS hat unendlich viele Lösungen." << endl;
      return {}; // Leerer Vektor, da unendlich viele Lösungen existieren
    }
    else {
      cout << "Das LGS hat keine Lösung." << endl;
      return {}; // Leerer Vektor, da keine Lösung existiert
    }
  }

  // Anwendung der Gauss-Jordan-Elimination
  gaussJordan(matrix, constants);

  vector<double> solution(n);

  for (int i = 0; i < n; i++) {
    solution[i] = constants[i];
  }

  return solution;
}

int main() {
  vector<vector<double>> matrix = {
    { 1, -3,  5 },
    { 2, -5,  12 },
    { 3, -11,  11 }
  };
  vector<double> constants = { 2, 1, 12 };

  vector<double> solution = solveLinearSystem(matrix, constants);

  if (!solution.empty()) {
    cout << "Die Lösung des LGS ist: ";

    for (int i = 0; i < solution.size(); i++) {
      cout << "x" << i + 1 << " = " << solution[i] << ", ";
    }

    cout << endl;
  }
  else {
    cout << "Das LGS hat keine Lösung." << endl;
  }

  return 0;
}

...zum Beitrag

Gibt es mehrere Werte für d bei der Schlüsselberechnung des RSA-Algorithmus mit dem erweiterten euklidischen Algorithmus. Wie berechne ich diese?

Ich muss gerade eine Seminararbeit über den RSA-Algorithmus schreiben und habe mich heute in die Schlüsselerzeugung eingearbeitet. Aber bei dieser Aufgabe habe ich Probleme. Die Werte sind:
e = 3
n = 253
Darauf habe ich dann den erweiterten euklidischen Algorithmus angewandt und bekam für d = -84 raus. Ich habe das auch nochmal mit einem Rechner im Internet nachgeprüft. Eigentlich rauskommen müsste: d = 147, was ja auch Sinn macht, da
d > 1 sein muss. Soweit ich es verstanden habe, gibt es wohl mehrere Werte für d, allerdings verstehe ich nicht wie ich auf diese komme.
Ich danke schonmal für jede Hilfe.

...zum Beitrag

Bei Djkstra mit negativen Kantengewichten positive Konstante addieren?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

...zum Beitrag

Wurzel 2 = irrational - Frage?

Hallo Com,

ich bekam die Aufgabe, zu beweisen, dass die Wurzel aus 2 irrational ist. Ich fand auch entsprechende Infos im Internet.
Allerdings ist mir nicht klar, weshalb 2q^2 gerade ist und damit auch p^2.

Danke!

...zum Beitrag

Was denkt ihr über Informatiker?

Sie kennen sich ja mit Themen wie künstlicher Intelligenz, Algorithmen, Verschlüsselung, Mathematik und Programmierung sehr gut aus. Was denkt ihr über sie?

...zum Beitrag

Boolesche Algebra, Frage zur DNF?

Ich habe versucht eine DNF zu kürzen, dank der Wahrheitstabelle kann ich erkennen, dass A und (B oder C) als Ergebnis rauskommt, nur komm ich durch die Zwischenschritte nicht zum Ergebnis:

Könnte mir vielleicht jemand sagen, was ich falsch gemacht habe oder wie man weiter kürzen könnte, um darauf zu kommen?

Vielen Dank im Voraus!!!!

...zum Beitrag

Algorithmus für gleichmäßige Punkteverteilung auf Kreis?

Angenommen ich habe einen Kreis und möchte darauf n Punkte möglichst gleichmäßig verteilen, aber habe bereits m dieser Punkte an gewissen Stellen vorgegeben.

Was wäre ein Algorithmus, welcher nun die gleichmäßigste Verteilung berechnet, d.h. die Minimaldistanz zwischen zwei (nicht bereits festgelegten) Punkten maximiert.

Z.B. wäre ein Problem n = 10, m = 4:

Wäre auch froh über Code in beliebiger Sprache.

...zum Beitrag

P/NP-Problem?

Beim P/NP-Problem geht es soweit ich weiß darum das ein effizienter Algorithmus für ein Problem zum Beispiel die Färbung von Graphen, die Existenz von effizienten Algorithmen für alle anderen Probleme der selben Komplexität impliziert, korrigiert mich gerne falls ich das falsch verstanden habe. Ich verstehe nur gerade nicht wie man die Komplexität eines Problems definiert wenn man nicht den effizientesden Algorithmus kennt? "Ein Problem ist K-schwer wenn sich alle anderen Probleme der Klasse K auf den Algorithmus zur diesem Problem zurückführen lassen", damit beißt sich die Katze aber in den Schwanz du definierst die Komplexität eines Problems K dadurch daß sich alle anderen Probleme der Klasse K auf den den selben Algorithmus zurückzuführen wie unseres Anfangsproblems lassen. Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?

...zum Beitrag

Algorithmen Informatik Struktogramm?

Könnte mir jemand erklären warum bei "Deklaration und Zuweisung" summe=0 steht? Also was bedeutet das genau und was bringt es

...zum Beitrag

Wie kann ich mit den Eckpunkten a,b,c berechnen, ob ein Punkt innerhalb oder außerhalb eines Dreiecks liegt?

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen