Wie die Basis einer Nummer zu bestimmen?

Question

Gegeben eine Ganzzahl und ihre Darstellung in einem beliebigen Zahlensystem. Der Zweck ist, die Basis des Zahlensystems zu finden. Zum Beispiel ist die Zahl 10 und die Darstellung ist 000010, dann sollte die Basis 10 sein. Ein anderes Beispiel: Nummer 21-Darstellung ist 0010101 dann Basis ist 2. Ein weiteres Beispiel ist: Nummer ist 6 und die Darstellung ist 10100, dann ist die Basis sqrt (2) . Hat jemand eine Idee, wie man ein solches Problem lösen kann?

Answer 1

Ein Algorithmus wie dies sollte die Basis zu finden, wenn es eine ganze Zahl ist, und für eine nicht-ganzzahligen Basis, um die Auswahl zumindest einschränken sollte:

• N Ihre ganze Zahl sein lassen und R seine Darstellung sein in die geheimnisvolle Basis.
• Suchen Sie die größte Ziffer in R und nennen Sie sie r.
  • Sie wissen, dass Ihre Basis mindestens r + 1 ist.
• Für base == (r+1, r+2, ...), lassen IR in der Basis interpretiert repräsentieren base
  • Wenn IN gleich, dann base ist Ihr Geheimnis Basis. Wenn die Nummer I kleiner als N ist, versuchen Sie die nächste Basis.
  • Wenn I größer als N ist, liegt Ihre Basis irgendwo zwischen base - 1 und base.

Es ist eine Brute-Force-Methode, aber es sollte funktionieren. Sie können es auch etwas beschleunigen, indem Sie base um mehr als eins erhöhen, wenn I wesentlich kleiner ist als N.

etwas anderes, das die Dinge beschleunigen könnte, insbesondere im Fall einer nicht ganzzahligen Basis: Denken Sie daran, dass mehrere Personen eine Zahl in einer beliebigen Basis erwähnt haben, kann als ein Polynom wie

x = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base + a[0] 

erweitert werden

Bei der Bewertung potenzieller Basen müssen Sie nicht die gesamte Zahl konvertieren. Beginnen Sie damit, nur den größten Ausdruck zu konvertieren, a[n]*base^n. Wenn das größer als x ist, dann wissen Sie bereits, dass Ihre Basis zu groß ist. Ansonsten füge jeweils einen Begriff hinzu (von höchst signifikant zu niedrigstwertig). Auf diese Weise verschwenden Sie keine Zeit damit, Begriffe zu berechnen, nachdem Sie wissen, dass Ihre Basis falsch ist.

Auch gibt es einen anderen schnellen Weg, um eine mögliche Basis zu beseitigen. Beachten Sie, dass Sie neu ordnen, das obige Polynom Ausdruck und erhalten

(x - a[0]) = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base 

oder

(x - a[0]) = (a[n]*base^(n-1) + a[n-1]*base^(n-2) + ... + a[2]*base + a[1])*base 

Sie kennen die Werte von x und a[0] (die „Einsen“ Ziffer, können Sie es interpretieren, unabhängig von Base). Was dies gibt Ihnen die zusätzliche Bedingung, die (x - a[0]) muss durch base gleichmäßig teilbar sein (da alle Ihre a[] Werte sind ganze Zahlen). Wenn Sie (x - a[0]) % base berechnen und ein Ergebnis ungleich Null erhalten, dann kann base nicht die richtige Basis sein.

Answer 2

Ich bin nicht sicher, ob dies effizient lösbar ist. Ich würde einfach versuchen, eine zufällige Basis zu wählen, um zu sehen, ob das Ergebnis bei der Basis kleiner, größer oder gleich der Zahl ist. Wenn es kleiner ist, wählen Sie eine größere Basis, falls es größer ist, wählen Sie eine kleinere Basis, ansonsten haben Sie die richtige Basis.

Answer 3

  ___ 
     \ 
number = /__ (digit[i] * base^i) 

Sie wissen number, wissen Sie alle digit[i], man muss nur base erfahren.

Ob eine Lösung dieser Gleichung einfach oder komplex ist, bleibt als Übung übrig.

Answer 4

Dies sollte Ihnen einen Ausgangspunkt geben:

eine Gleichung aus der Anzahl und Darstellung erstellen, Nummer 42 und represenation „0010203“ wird:

1 * base^4 + 2 * base^2 + 3 = 42 

Jetzt lösen Sie die Gleichung den Wert zu erhalten von base.

Answer 5

Ich denke nicht, dass eine Antwort für jeden Fall gegeben werden kann. Und ich habe tatsächlich einen Grund, so zu denken! =)

eine Zahl x, mit Darstellung a_6 a_5 a_4 a_3 a_2 a_1 in Basis B, die Basis zu finden, bedeutet

a_6 b^5 + a_5 b^4 + a_4 b^3 + a_3 b^2 + a_2 b^1 + a_1 = x. 

Diese Lösung kann nicht generell durchgeführt werden, wie von Abel and Ruffini gezeigt. Sie können mit kleineren Zahlen glücklicher sein, aber wenn mehr als vier Ziffern beteiligt sind, werden die Formeln zunehmend hässlich.

Es gibt jedoch eine ganze Reihe guter Approximationsalgorithmen. Siehe here.

Answer 6

Ich denke, Sie müssen versuchen und verschiedene Basen überprüfen. Um effizient zu sein, könnte Ihre Ausgangsbasis max (Ziffer) + 1 sein, da Sie wissen, dass sie nicht weniger sein wird. Wenn das zu klein ist, verdoppeln Sie es, bis Sie es überschreiten, und verwenden Sie dann binäre Suche, um es einzugrenzen. Auf diese Weise sollte Ihr Algorithmus für normale Situationen in O (log n) laufen.

Answer 7

Mehrere der anderen Beiträge schlagen vor, dass die Lösung gefunden werden könnte, indem man die Wurzeln des Polynoms findet, das die Zahl darstellt. Diese werden natürlich im Allgemeinen funktionieren, obwohl sie eine Tendenz haben werden, negative und komplexe Basen sowie positive ganze Zahlen zu erzeugen.

Ein anderer Ansatz wäre, dies als Integer-Programmierungsproblem zu interpretieren und mit Branch-and-Bound zu lösen.

Aber ich vermute, dass der Vorschlag des Ratens und Testens schneller sein wird als jeder der klügeren Vorschläge.

Answer 8

Nur für Ganzzahlen ist es nicht so schwierig (wir können aufzählen).

Schauen wir uns 21 und seine Darstellung .

1 * base^4 <= 21 < (1+1) * base^4 

Lasst uns die Zahlen für einige Basen erzeugen:

base low high 
2  16 32 
3  81 162 

Generell haben wir N als Σ repräsentiert eine _i * Basis ⁱ. Unter Berücksichtigung I die maximale Leistung, für die ein _I ist nicht null haben wir:

a[I] * base^I <= N < (a[I] + 1) * base^I # does not matter if not representable 

# Isolate base term 
N/(a[I] + 1) < base^I <= N/a[I] 

# Ith root 
Ithroot(N/(a[I] + 1)) < base <= Ithroot(N/a[I]) 

# Or as a range 
base in ] Ithroot(N/(a[I] + 1)), Ithroot(N/a[I]) ] 

Im Falle eines ganzzahligen Basis, oder wenn Sie eine Liste der bekannten möglichen Basen, ich bezweifle, dass sie viele sein werden Möglichkeiten, damit wir sie einfach ausprobieren können.

Beachten Sie, dass es schneller sein kann, die Ithroot von N/(a[I] + 1) und iterieren von hier anstelle der Berechnung der zweiten (die nahe genug) sein sollte ... aber ich würde Mathe-Review auf dieses Bauchgefühl brauchen.

Wenn Sie wirklich keine Idee haben (versuchen, eine schwimmende Basis zu finden) ... nun, es ist ein bisschen schwieriger, denke ich, aber Sie können immer die Ungleichheit verfeinern (einschließlich ein oder zwei Begriffe) gleiche Eigenschaft.