Ich war verwirrt mit einer der Fragen in Microsoft-Interview, das wie folgt angegeben ist:
Eine Funktion sollte einen Bereich (3 - 21) akzeptieren und es sollten alle fortlaufenden Zahlenkombinationen gedruckt werden, um jede Zahl wie unten angegeben zu bilden:
%Vor%Könnten Sie mir bitte helfen, diese Sequenz in C # zu erstellen?
Danke, Mahesh
Also hier ist eine einfache / naive Antwort (in C ++, und nicht getestet; aber Sie sollten in der Lage sein zu übersetzen). Es nutzt die Tatsache, dass
1 + 2 + ... + n = n (n + 1) / 2,
was Sie wahrscheinlich schon einmal gesehen haben. Hier gibt es viele einfache Optimierungen, die ich zur besseren Übersicht weggelassen habe.
%Vor%Dies ist ein Pseudocode, um alle Kombinationen zu finden, falls welche existieren:
%Vor%Ein Aufruf von all_consecutive_numbers (21) würde Folgendes ausgeben:
%Vor%Ich habe es in Ruby (Code hier ) getestet und es scheint zu funktionieren. Ich bin mir sicher, dass die Grundidee auch in C # problemlos implementiert werden könnte.
Hier ist etwas in Groovy, du solltest verstehen können, was vor sich geht. Es ist nicht der effizienteste Code und erstellt nicht die Antworten in der Reihenfolge, die Sie in Ihrer Frage angeben (Sie scheinen jedoch einige zu verpassen), aber es könnte Ihnen einen Anfang geben.
%Vor% Ausgabe für f(3,21) ist:
Hoffe, das hilft. Es entspricht dem Grundsatz, die einfachste Sache zu tun, die möglicherweise funktionieren könnte.
wenn wir a in zwei Ziffern schneiden, dann a = b + (b + 1) = 2 * b + (0 + 1)
wenn wir a in 3 Ziffern zerlegen, dann ist a = b + (b + 1) + (b + 2) = 3 * b + (0 + 1 + 2) |
...
wenn wir a in die Zahl n schneiden, dann ist a = b + (b + 1) + ... + (b + n) = n b + (0 + 1 + n-1)
das letzte Ergebnis ist a = n b + n * (n-1) / 2, a, b, n sind alle Inte
so ist O (N) Algorithmus: