Berechne die Anzahl der Einsen im Ergebnis von 11 ^ n
Das folgende Problem wurde in einem Interview gestellt. Geben Sie eine Zahl 11 n (wobei n ∈ [0, 1000] ) die Anzahl von 1 s im Ergebnis an. Zum Beispiel, n = 3, 11 3 = 1331, so würde das erwartete Ergebnis 2 sein. Oder gegeben n = 6, 11 6 = 1771561, wäre das erwartete Ergebnis 3.
Mein erster Gedanke war, dass es etwas mit dem Pascal-Dreieck und binomiale Koeffizienten (weil wir einfach wissen, dass pow(11, 1000) nicht funktioniert, zumindest in C).
Ich dachte, indem ich einfach über die Spalten im Pascal-Dreieck iterierte, sollte mir das Ergebnis geben, aber das funktioniert eindeutig nicht.
Ich bin jetzt irgendwie festgefahren. Mein nächster Gedanke war, eine Art bignum library zu verwenden, um das Problem zu lösen, aber meiner Meinung nach muss es einen anderen Weg geben, um diese Art von Aufgabe zu lösen.
Aktualisieren Ich habe vergessen zu erwähnen, dass ich diese Aufgabe mit C / Objective-C lösen sollte.
4 Antworten
Wie Bartosz vorgeschlagen hat, würde ich dies lösen, indem ich einfach die Berechnungen in Basis 10 durchführe. Eine Multiplikation mit 11 in der Basis 10 kann mit einer Linksverschiebung und einer Addition erfolgen. Hier ist ein C-Programm, das mit ASCII-Strings arbeitet. Beachten Sie, dass die niedrigstwertige Ziffer in jeder Zeichenfolge an erster Stelle steht.
%Vor%Haben sie Ihnen gesagt, wie effizient der Algorithmus sein sollte?
Ich würde es einfach auf Saiten anwenden; Multiplikation mit 11 ist einfach eine Kopie mit einer nachgestellten 0 hinzugefügt und dann hinzufügen, so alles, was Sie tun müssten, implementieren das Hinzufügen von Zahlen als Strings geschrieben.
nehme an, dass K (i) eine Zeichenkette ist, die aus der k-ten Zeile des Pascal-Dreiecks erzeugt wird.
11 ^ 0 = 1,11 ^ 1 = 11,11 ^ 2 = 121. Aber 11 ^ i = k (i) ist eine falsche Annahme. Weil 11 ^ i = (10 + 1) ^ i & amp;
==== & gt; 
Also ist es für kleine Zahlen wahr, weil 10 ^ i sehr viel größer ist als a [i] für große Zahlen hat es aus dem folgenden Grund vielleicht einen Überlauf.
%Vor%, wenn a[i]*10^(n-i+1) < a[i+1]*10^(n-i) overflow passiert. Indem Sie diese vereinfachen, erhalten Sie (n-i+1)/i >10 , wenn ein Überlauf auftritt.
Sie sollten diese Überläufe in Ihrem Algorithmus berechnen.
Tags und Links algorithm biginteger math