Deutliche n Zahlen, so dass die Summe gleich N ist N

Question

Angenommen, ich möchte n verschiedene Zahlen im Bereich von 1 bis N finden, so dass ihre Summe gleich N ist, z.

n = 3, N = 10: the numbers will be (2, 3, 5); 
n = 4, N = 10: the numbers will be (1, 2, 3, 4). 

Während alle möglichen Kombinationen für dieses Problem herauszufinden, wird exponentielle Zeit in Anspruch nehmen, ich bin für die „kleinste“ Kombination, das heißt die größte Zahl der kleinste ist. Zum Beispiel

in dem Fall, wo n = 4, and N = 12, beide (6, 3, 2, 1) and (5, 4, 2, 1) kann die Lösung sein, aber ich interessiere mich nur für (5, 4, 2, 1).

Gibt es für dieses Problem einen Algorithmus mit einer besseren Zeitkomplexität? Ich habe von der logarithmischen Verschmelzung gehört, bin mir aber nicht sicher, wie das hier angewendet werden kann.

Wenn Details zu dem Problem angegeben werden müssen, lassen Sie es mich wissen. Und immer wird jede Hilfe sehr geschätzt.

Answer 1

Es gibt einen einfachen Greedy-Algorithmus für dieses Problem.

Zuerst gibt es n Elemente in aufsteigender Reihenfolge, damit sie unterschiedlich sein können, jedes Element sollte um mindestens eins größer als sein Vorgänger sein.

so haben wir

1, 2, 3 ... , n

nun die Summe aller n Zahl ist n*(n + 1)/2

Was bleibt, ist left = N - n*(n + 1)/2

Um das letzte Element so klein zu halten, wie möglich, müssen wir die left Differenz zu allen Zahlen

streuen

so haben wir

1 + left/n, 2 + left/n, ..., n + left/n

Wenn left % n != 0, wir müssen nur Extra1 zu den letzten left % n Elemente hinzuzufügen.

Hinweis: wenn N < n*(n + 1)/2, gibt es keine Lösung

Beispiel:

Also, für n = 4 und N = 12

First, we start with 

1, 2, 3, 4 

left = 12 - (4*5/2) = 2 

So, now we have 

1 + (2/4), 2 + (2/4), 3 + (2/4), 4 + (2/4) = 1, 2, 3, 4 

As left % n = 2 
Finally, we have 

1, 2, 3 + 1, 4 + 1 = 1, 2, 4, 5 

ähnliche Weise für n = 3, N = 10

First, we start with 

1, 2, 3 

left = 10 - (3*4/2) = 4 

So, now we have 

1 + (4/3), 2 + (4/3), 3 + (4/3) = 2, 3, 4 

As left % n = 1 
Finally, we have 

2, 3, 4 + 1 = 2, 3, 5 

Pseudo-Code, t ie Komplexität O (n)

int[]result = new int[n]; 
int left = N - n*(n + 1)/2; 

for(int i = 0; i < n; i++){ 
    result[i] = i + 1 + left/n; 
    if(i >= n - (left % n)){//Add extra one for last left % n elements 
     result[i]++; 
    } 
} 
return result; 

Answer 2

Angenommen, Sie haben eine Funktion f(n, N, sum) - es Ergebnis zurück, dass Sie die Möglichkeit haben, aus n Elemente aus dem Bereich 1-N zusammenfassend zu sum zeigen.

Zumindest jetzt können Sie bestimmen, ob die Lösung existiert einfach f(n, N, N) aufrufen.

sagen lassen, dass für ein gegebenes n, N und sum das Problem p(n,N,sum) eine Lösung hat und x ist die kleinste größte Zahl in Folge. Dann sollte das Problem p(n',N',sum') mit n'=n-1, N'=x-1, sum'=sum-x auch eine Lösung haben. Das Problem p(0,N,0) hat immer eine Lösung und es ist eine Basis der Induktion.

Funktion f(n, N, sum) wird die kleinste Zahl tatsächlich zurückkehren x aus dem Bereich 1-N, die Teil der Lösung sein kann (sonst sollte es -1 oder etwas zurückgeben angibt Lösung Abwesenheit). Wir können jede Nummer von 1 bis N als x versuchen und prüfen, ob f(n - 1, x - 1, sum - x) eine Lösung hat.

Der Schlüssel hier ist, Memoisierung zu verwenden, um nicht die gleiche Funktion viele Male zu berechnen. Erinnere dich einfach gefunden x. Das Speichern jeder möglichen Eingabekombination dauert höchstens O(n * N * N) Speicherplatz und dieselbe O(n * N * N) Zeit, die berechnet werden soll. Es würde auch keine Lösung geben, wenn wir solche Anrufe sofort löschen könnten. Dies ist eine Polynom-Zeit/Raum-Komplexität, die besser als exponentiell ist.

Answer 3

Lassen Sie uns versuchen, das Problem zu brechen, angenommen, wir haben n eindeutige Zahlen zwischen [1, N]. was die minimal mögliche Summe ist, wäre es die Summe der ersten n natürlichen Zahlen sein, dh

1 + 2 + 3 + 4 + ... + n 

die maximale Anzahl möglich

(N-n+1) + (N-n+2) + (N-n+3) + ... + (N-n+n) 

Hinweis alle Summe zwischen minimalen und maximalen Wert kann sein würde, gemacht werden mit n Zahlen

Jetzt wie es überprüft wird, ob der Wert möglich ist oder nicht, können wir tun. Nehmen wir an, wir nehmen die Zahlen von 1 bis n. Stromsumme S gleich

S = 1 + 2 + ... + n 

wenn ich x zu jedem Element hinzufügen würde es werden

S = 1 + 2 + ... + n + x*n <= N 

Wenn wir die maximal mögliche solche x dann die Summe wäre erreichbar durch Zugabe von 1 Element auswählen zu allen Zahlen beginnend vom Größten bis zum Erreichen der gewünschten Summe (dh höchstens n-1 Zahlen). Dies würde mir dann eine gültige Antwort geben.

Also, wenn die Antwort möglich ist, wäre es

1. nehmen Elemente von 1 bis n
2. Add x zu jedem Element
3. von der größten Zahl halten Zugabe von 1, bis die Summe erreicht ist

Answer 4

Dies kann fast sofort berechnet werden. Die Antwort wird immer entweder wie eine Reihe von Zahlen um N/n aussehen, oder aber eine Reihe von Zahlen mit im Wesentlichen der gleichen Mitte, mit einer Lücke von 1 irgendwo in der Mitte.

Berechnen Sie also diese Mitte, dann berechnen Sie, ob und wo Sie diese Lücke brauchen. Dann bist du fertig.

Wenn n ungerade ist, dann ist die Mitte N/n (vorausgesetzt, ganzzahlige Division) mit genug verschoben 1 nach rechts, um den Rest zu berücksichtigen. Wenn also zum Beispiel N 10000 ist und n 17 ist, dann ist die Mitte 588, und Ihr Startbereich ist 588 ± (17-1)/2, was 580-596 ist. Aber der Rest ist 4, also verschiebe 4 und deine Antwort lautet 580-592, 594-597.

Wenn n ist, beginnt die Mitte auf einer halben Zahl. Also ist die Mitte (N-n/2)/n + 0.5. Wenn also zum Beispiel N 10000 ist und n 18 ist, dann ist die Mitte 555,5 und Ihr Startbereich ist 555,5 ± (18-1)/2, was 547-564 ist. Aber diese Division hatte einen Rest von 1, also erhalten wir eine Antwort von 547-563, 565.