Effizientere „Zuerst K Zahlen, dass ihre stelligen Summe S ist“ Algorithmus

Question

Das ganze Problem klingt wie:

„Wir haben zwei Zahlen auf Eingabe, K und S Wir sind auf Ausgabe drucken möchten erste (niedrigste) K-Nummern, während ihre Zahl ist genau S "

Es gibt einen einfachen naiven Algorithmus, um ein solches Problem zu lösen (die ich konstruieren und finden konnte). Es ist Prinzip, eine Funktion zu haben bigint digitSum (i), (Ich schreibe bigint, weil S ist sowieso nicht begrenzt, wie ich will nur effektiver Algorithmus ...), die Ziffer Summe der Argumentnummer zurückgeben wird. Wir werden von Nummer 0 ausgehen und immer um 1 erhöhen, während wir diese Zahlen in die Funktion einfügen. Wenn die Funktion die gleiche Summe wie S zurückgibt, drucken Sie diese Nummer und fahren Sie fort, bis Sie K Zahlen drucken.

Code Funktion ist hier:

bigint digitSum(number){ 
bigint total = 0; 
while(number > 0) 
    { 
    total += number % 10; 
    number /= 10; 
    } 
return total; 
} 

Algorithmus asymptotische Komplexität in Big-O ist als ist die Komplexität der Zahlen 0,1,2,3 Suche Trog ... n, bis wir finden genau K benötigten Zahlen und ist Komplexität unserer Funktion stelligen Summe zu finden, da es dividieren Zahl immer um 10.

gibt es einen Algorithmus oder so, wie es effizienter zu machen ?? Vielen Dank!

Answer 1

Um solche Probleme zu lösen, müssen Sie einige Regelmäßigkeiten abfangen. Um zum Beispiel eine Sequenz der ersten Build-Nummern, für die Ziffer Summe S ist

S 0 1 .. 9 10 11 12 .. 18 19 20 .. 31 ... 
F(S) 0 1 .. 9 19 29 39 .. 99 199 299 .. 4999... 

Wir können sehen, dass die erste Zahl

M = S div 9 
R = S mod 9 

als

F(S) = R(9xM) ////concatenation of digit R and M 9s 
for S=31 M=3,R=4, and 
F(31) = 4(9x3) = 4999 //concatenation of 4 and three nines 

unter Verwendung von Werten gefunden werden konnte

So können wir die erste benötigte Zahl in O (1) bestimmen. Dann aufwendigen Regeln für die nächste Nummer mit der gleichen Ziffer Summe (beachten Sie, dass oft N(i+1) = N(i) + 9)

Answer 2

Dies ist eine rekursive Algorithmus ist, dass Sie die K kleinsten Zahlen, deren Ziffern summieren sich zu S geben wird. Die Komplexität ist definitiv besser als Ihr Brute-Force-Algorithmus, obwohl ich mir nicht sicher bin, wie es in der großen O-Notation aussehen würde.

Der Algorithmus geht wie folgt:

• alle finden die Kombinationen von nDigits = 1, die S
• zusammenzufassen Dann nDigits = 2, nDigits = 3, ...bis Zählung == K
• alle Kombinationen von nDigit → alle Kombinationen von 1 + alle Kombinationen von nDigit-1

Hier ist der Code in Java:

public static void main(String[] args) { 
    int[] currentCount = {0}; 
    int k = 10, s = 10; 

    for(int n = s/9 ; currentCount[0] != 10 ; n++) { 
     digitSum(new StringBuilder(), n, 0, s, k, currentCount); 
    } 
} 

public static void digitSum(StringBuilder subNumber, int nDigit, int currentSum, int s, int k, int[] currentCount) { 
    if(nDigit == 0) { 
     if(currentSum == s) { 
      System.out.println(subNumber); 
      currentCount[0]++; 
     } 
     return; 
    } 

    if(currentCount[0] == k) return; //if already have k numbers, terminate 

    int remaining = s-currentSum; 

    if(remaining > nDigit*9) return; //if not enough digits to reach S, terminate 

    final int bound = Integer.min(9, remaining); //what's the largest valid digit 

    //zero digit is only valid if subNumber != 0 
    if(subNumber.length()!=0) digitSum(new StringBuilder(subNumber).append('0'), nDigit-1, currentSum, s, k, currentCount); 

    for(int i = 1 ; i <= bound ; i++) digitSum(new StringBuilder(subNumber).append((char)(i+'0')), nDigit-1, currentSum+i, s, k, currentCount); 
} 

EDIT
ich grob gemessen wurde die Zeitkomplexität, und es ist deutlich O (N) wie unten zu sehen: