Hallo zusammen,
ich stehe gerade absolut auf dem Schlauch:
Ich soll ein Array mit n Elementen in k Teile teilen, die sich maximal um 1 in der Anzahl ihrer Elemente unterscheiden.
Meine Idee: Ich teile das Array in k Teile mit jeweils [n/k] Elementen ([] für untere Gauß-Klammer), dann bleiben r=(n mod k) Elemente, d.h. 0 bis k-1, übrig, die ich auf die ersten r Teile aufteile. Soweit die Theorie.
Code:
// Teile das Array in k Teile und teile den Rest (zwischen 0 und k-1)
// auf die ersten r Teile auf
int sublen=len/k, rest=len%k, r=0;
for (int idx = 0; idx < k; idx++)
{
if (rest > idx) {
rest--;
r++;
}
int s = (idx*sublen);
if (r > 1) start += r-1;
int e = (idx+1)*sublen;
if (r > 1) start += r;
cout << "go sub: k_merge_sort(array, " << s << ", " << e << ", k, alpha)" << endl;
}
Das macht aber so nicht, was es soll. Für n=10 und k=2 kommt dabei
Code:
go sub: k_merge_sort(array, 0, 5, k, alpha)
go sub: k_merge_sort(array, 5, 10, k, alpha)
Und für n=10 und k=3 kommt
Code:
go sub: k_merge_sort(array, 0, 3, k, alpha)
go sub: k_merge_sort(array, 3, 6, k, alpha)
go sub: k_merge_sort(array, 6, 9, k, alpha)
D.h. ein Element ist immer zu viel drin.
Ich komme darauf echt irgendwie nicht klar. Kann mir da jemand weiterhelfen?
Dank und Gruß
Christopher