如何將n長度的數組劃分爲k個子數組（大小相同）（C）？

Question

我有一個大小爲n的數組，並且想要分成k個子數組，並且每個數組必須具有大致相同的大小。我一直在想，並且知道你必須使用兩個for循環，但是我很難實現這些for循環。

我試了一下：

//Lets call the original integer array with size n: arr 
// n is the size of arr 
// k is the number of subarrays wanted 

int size_of_subArray = n/k; 
int left_over = n%k; // When n is not divisible by k 
int list_of_subArrays[k][size_of_subArray + 1]; 

//Lets call the original integer array with size n: arr 

for(int i = 0; i < k; i++){ 
    for(int j = 0; j < size_of_subArray; j++){ 
     list_of_subArrays[i][j] = arr[j]; 
    } 
} 

我與得到正確的索引在forloops掙扎。

任何想法？

Answer 1

我重構了您的代碼並對其進行了註釋。

的要點是：

1. 當計算子陣列的大小，它必須向上
2. 指數爲arr需要繼續從0遞增（即它是不復位0）

以下應該工作，但我沒有測試[請原諒無償風格清理]：

// Lets call the original integer array with size n: arr 
// n is the size of arr 
// k is the number of subarrays wanted 

// round up the size of the subarray 
int subsize = (n + (k - 1))/k; 

int list_of_subArrays[k][subsize]; 

int arridx = 0; 
int subno = 0; 

// process all elements in original array 
while (1) { 
    // get number of remaining elements to process in arr 
    int remain = n - arridx; 

    // stop when done 
    if (remain <= 0) 
     break; 

    // clip remaining count to amount per sub-array 
    if (remain > subsize) 
     remain = subsize; 

    // fill next sub-array 
    for (int subidx = 0; subidx < remain; ++subidx, ++arridx) 
     list_of_subArrays[subno][subidx] = arr[arridx]; 

    // advance to next sub-array 
    ++subno; 
} 

---

UPDATE：

是這個劃分陣列分成n個子陣列，但它不平均分配的。假設有10個大小的數組，並且想把它分成9個子數組。然後8個子數組將有1個原始數組元素，但是一個子數組需要2個元素。

你原來的代碼有一些bug [修正在上面的例子中]。即使我爲自己做了這些，上面的工作也將是第一步做好工作的第一步。

在你原來的問題，你做說：「和每個陣列必須有大約相同大小」。但是，在這裏，列表子數組的物理大小[仍然是一個四捨五入的值]。

但是，我可能會說一些像「均勻分佈」或一些這樣的事情來進一步澄清你的意圖。也就是說，你希望最後一個子陣列/桶到而不是是「短」[大幅度]。

鑑於此，代碼開始有點相同，但需要更復雜一點。這仍然有點粗糙，可能會進一步優化：

#include <stdio.h> 

#ifdef DEBUG 
#define dbgprt(_fmt...)  printf(_fmt) 
#else 
#define dbgprt(_fmt...)  /**/ 
#endif 

int arr[5000]; 

// Lets call the original integer array with size n: arr 
// n is the size of arr 
// k is the number of subarrays wanted 

void 
fnc2(int n,int k) 
{ 
    // round up the size of the subarray 
    int subsize = (n + (k - 1))/k; 

    int list_of_subArrays[k][subsize]; 

    dbgprt("n=%d k=%d subsize=%d\n",n,k,subsize); 

    int arridx = 0; 

    for (int subno = 0; subno < k; ++subno) { 
     // get remaining number of sub-arrays 
     int remsub = k - subno; 

     // get remaining number of elements 
     int remain = n - arridx; 

     // get maximum bucket size 
     int curcnt = subsize; 

     // get projected remaining size for using this bucket size 
     int curtot = remsub * curcnt; 

     // if we're too low, up it 
     if (curtot < remain) 
      ++curcnt; 

     // if we're too high, lower it 
     if (curtot > remain) 
      --curcnt; 

     // each bucket must have at least one 
     if (curcnt < 1) 
      curcnt = 1; 

     // each bucket can have no more than the maximum 
     if (curcnt > subsize) 
      curcnt = subsize; 

     // last bucket is the remainder 
     if (curcnt > remain) 
      curcnt = remain; 

     dbgprt(" list[%d][%d] --> arr[%d] remain=%d\n", 
      subno,curcnt,arridx,remain); 

     // fill next sub-array 
     for (int subidx = 0; subidx < curcnt; ++subidx, ++arridx) 
      list_of_subArrays[subno][subidx] = arr[arridx]; 
    } 

    dbgprt("\n"); 
}