Frage Mindestanzahl der Schritte, um die Anzahl auf 1 zu reduzieren


Gegeben eine beliebige Anzahl n und drei Operationen auf n:

  1. füge 1 hinzu
  2. subtrahiere 1
  3. dividiere durch 2 wenn die Zahl gerade ist

Ich möchte die minimale Anzahl der obigen Operationen finden, um n auf 1 zu reduzieren. Ich habe versucht, dynamische Progammierung Ansatz, auch BFS mit Beschneidung, aber n kann sehr groß sein (10 ^ 300) und ich weiß nicht, wie ich meinen Algorithmus machen schneller. Der gierige Ansatz (dividiere durch 2 falls gerade und subtrahiere 1 wenn ungerade) ergibt ebenfalls nicht das optimale Ergebnis. Gibt es eine andere Lösung?


19
2017-09-20 07:52


Ursprung


Antworten:


Es gibt ein Muster, mit dem Sie den optimalen nächsten Schritt in konstanter Zeit erfahren können. Tatsächlich kann es Fälle geben, in denen es zwei gleichermaßen optimale Möglichkeiten gibt - in diesem Fall kann einer von ihnen in konstanter Zeit abgeleitet werden.

Wenn Sie sich die Binärdarstellung von nund seine niedrigstwertigen Bits können Sie einige Rückschlüsse darauf ziehen, welche Operation zur Lösung führt. Zusamenfassend:

  • Wenn das niedrigstwertige Bit Null ist, dividiere durch 2
  • ob n ist 3, oder die 2 niedrigstwertigen Bits sind 01, dann subtrahieren
  • In allen anderen Fällen: hinzufügen.

Beweis

Wenn das niedrigstwertige Bit Null ist, sollte die nächste Operation die Division durch 2 sein. Wir könnten stattdessen 2 Additionen und dann eine Division versuchen, aber dann kann dasselbe Ergebnis in zwei Schritten erreicht werden: Teilen und Addieren. Ähnlich mit 2 Subtraktionen. Und natürlich können wir die nutzlosen nachfolgenden Add & Subtract-Schritte ignorieren (oder umgekehrt). Wenn also das letzte Bit 0 ist, ist Division der richtige Weg.

Dann sind die restlichen 3-Bit-Muster ähnlich **1. Es sind vier von ihnen. Lass uns schreiben a011 um eine Zahl zu bezeichnen, die mit Bits endet 011 und hat eine Reihe von Präfix-Bits, die den Wert darstellen würden ein:

  • a001: Hinzufügen würde man geben a010, nach dem eine Teilung erfolgen sollte: a01: 2 Schritte genommen. Wir würden jetzt keinen abziehen wollen, denn das würde dazu führen a00, die wir in zwei Schritten von Anfang an hätten erreichen können (subtrahieren 1 und teilen). Also fügen wir wieder hinzu und teilen uns, um zu bekommen a1und aus dem gleichen Grund wiederholen wir das noch einmal und geben: a+1. Dies dauerte 6 Schritte, führt aber zu einer Zahl, die in 5 Schritten erreicht werden konnte (subtrahiere 1, teile 3 mal, füge 1 hinzu), also sollten wir die Addition nicht durchführen. Subtraktion ist immer besser.

  • a111: Addition ist gleich oder besser als Subtraktion. In 4 Schritten bekommen wir a+1. Subtraktion und Division würden geben a11. Jetzt zu addieren wäre im Vergleich zum ursprünglichen Additionspfad ineffizient, also wiederholen wir diese Subtraktion / Division zweimal und erhalten a in 6 Schritten. Ob a endet in 0, dann hätten wir das in 5 Schritten tun können (addieren, dividieren, subtrahieren), if a endet in einer 1, dann sogar in 4. So ist die Addition immer besser.

  • a101: Subtraktion und doppelte Division führt zu a1 in 3 Schritten. Addition und Division führt zu a11. Subtrahieren und Dividieren wäre im Vergleich zum Subtraktionspfad ineffizient, also addieren und dividieren wir zweimal a+1in 5 Schritten. Aber mit dem Subtraktionsweg konnten wir dies in 4 Schritten erreichen. Subtraktion ist also immer besser.

  • a011: Addition und Doppelteilung führt zu a1. Bekommen a würde 2 weitere Schritte (5) machen, um zu bekommen a+1: ein mehr (4). Subtraktion, Division, Subtraktion, Doppelteilung führt zu a (5), um zu bekommen a+1 würde einen weiteren Schritt machen (6). Also ist Addition mindestens so gut wie Subtraktion. Es gibt jedoch einen Fall nicht zu übersehen: Wenn ein ist 0, dann erreicht der Subtraktionspfad die Lösung in zwei Schritten, während der Additionspfad drei Schritte dauert. Also führt Addition immer zur Lösung, außer wenn n ist 3: dann sollte die Subtraktion gewählt werden.

Bei ungeraden Zahlen bestimmt das zweitletzte Bit den nächsten Schritt (außer 3).

Python-Code

Dies führt zum folgenden Algorithmus (Python), der für jeden Schritt eine Iteration benötigt und somit haben sollte O (logn) Komplexität:

def stepCount(n):
    count = 0
    while n > 1:
        if n % 2 == 0:             # bitmask: *0
            n = n // 2
        elif n == 3 or n % 4 == 1: # bitmask: 01
            n = n - 1
        else:                      # bitmask: 11
            n = n + 1
        count += 1
    return count

Sieh es laufen repl.it.

JavaScript-Snippet

Hier ist eine Version, in die Sie einen Wert für eingeben können n und lassen Sie das Snippet die Anzahl der Schritte erzeugen:

function stepCount(n) {
    var count = 0
    while (n > 1) {
        if (n % 2 == 0)                // bitmask: *0
            n = n / 2
        else if (n == 3 || n % 4 == 1) // bitmask: 01
            n = n - 1
        else                           // bitmask: 11
            n = n + 1
        count += 1
    }
    return count
}

// I/O
var input = document.getElementById('input')
var output = document.getElementById('output')
var calc = document.getElementById('calc')

calc.onclick = function () {
  var n = +input.value
  if (n > 9007199254740991) { // 2^53-1
    alert('Number too large for JavaScript')
  } else {
    var res = stepCount(n)
    output.textContent = res
  }
}
<input id="input" value="123549811245">
<button id="calc">Caluclate steps</button><br>
Result: <span id="output"></span>

Bitte beachten Sie, dass die Genauigkeit von JavaScript auf etwa 10 begrenzt ist16, so werden die Ergebnisse für größere Zahlen falsch sein. Verwenden Sie stattdessen das Python-Skript, um genaue Ergebnisse zu erhalten.


25
2017-09-20 08:44



Ich mag die Idee durch zimperliche ossifrage des gierigen Blicks (für den Fall von ungeraden Zahlen) ob n + 1 oder n - 1 sieht vielversprechender aus, aber ich denke, dass es besser ist, zu entscheiden, was vielversprechender aussieht, als wenn man die Gesamtzahl der gesetzten Bits betrachtet.

Für eine Nummer x,

bin(x)[:: -1].index('1')

gibt die Anzahl der niedrigstwertigen 0 bis zur ersten 1 an. Die Idee ist dann zu sehen, ob diese Zahl höher ist n + 1 oder n - 1, und wählen Sie die höhere der beiden (viele aufeinanderfolgende niedrigstwertige 0s weisen auf eine weitere Halbierung hin).

Dies führt zu

def min_steps_back(n):
    count_to_1 = lambda x: bin(x)[:: -1].index('1')

    if n in [0, 1]:
        return 1 - n

    if n % 2 == 0:
        return 1 + min_steps_back(n / 2)

    return 1 + (min_steps_back(n + 1) if count_to_1(n + 1) > count_to_1(n - 1) else min_steps_back(n - 1))

Um die beiden zu vergleichen, rannte ich

num = 10000
ms, msb = 0., 0.
for i in range(1000):
    n =  random.randint(1, 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999)

    ms += min_steps(n)
    msb += min_steps_back(n)

print ms / num, msb / num

Welche Ausgänge?

57.4797 56.5844

Dies zeigt, dass dies im Durchschnitt weniger Operationen erfordert (wenn auch nicht so sehr).


1
2017-09-20 10:32



Um das obige Problem zu lösen, können Sie entweder Rekursion oder Schleifen verwenden Eine rekursive Antwort ist bereits gegeben, also würde ich versuchen, eine while-Schleife Ansatz zu geben.

Logik: Wir sollten uns daran erinnern, dass das Zahlenvielfache von 2 immer weniger gesetzte Bits haben würde als die, die nicht durch 2 teilbar sind.

Um Ihr Problem zu lösen, verwende ich Java-Code. Ich habe es mit ein paar Nummern versucht und es funktioniert gut, wenn es keinen Kommentar hinzufügt oder die Antwort bearbeitet

while(n!=1)
    {
        steps++;
        if(n%2 == 0)
        {
            n=n/2;

        }
        else
        {
            if(Integer.bitCount(n-1) > Integer.bitCount(n+1))
            {
                n += 1;
            }
            else
            {
                n -=1;
            }
        }
    }

    System.out.println(steps);

Der Code ist in einer sehr einfachen Form geschrieben, damit er von jedem verstanden werden kann. Hier n ist die eingegebene und Schritte sind die Schritte erforderlich, um 1 zu erreichen


1
2017-09-20 11:34



Die von Ami Tavoy angebotene Lösung funktioniert, wenn die 3 berücksichtigt wird (würde zu 4 addieren) 0b100 und count_to_1 gleich 2, was größer ist als Subtrahieren auf 2 für 0b10 und count_to_1 entspricht 1). Sie können zwei Schritte hinzufügen, wenn wir keine n = 3 haben, um die Lösung zu beenden:

def min_steps_back(n):
count_to_1 = lambda x: bin(x)[:: -1].index('1')

if n in [0, 1]:
    return 1 - n

if n == 3:
    return 2

if n % 2 == 0:
    return 1 + min_steps_back(n / 2)

return 1 + (min_steps_back(n + 1) if count_to_1(n + 1) > count_to_1(n - 1) else min_steps_back(n - 1))

Sorry, ich weiß, ich würde einen besseren Kommentar abgeben, aber ich habe gerade angefangen.


0
2018-05-03 22:34