Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Как разделить массив на N частей

Автор: mur88 12.7.2010, 12:10

Нужно разделить массив на равные части (можно с погрешностью но не с очень большой)
например, массив из 105 эл. делим 10 частей получится 5-ть массивов по 10 эл. и 5-ть по 11 эл.

Автор: Bitter 12.7.2010, 12:32

Цитата(mur88 @ 12.7.2010, 12:10

)

получится 5-ть массивов по 10 эл. и 5-ть по 11 эл.

А как это у вас так получается? Магия? 5*10 = 50, 5*11 = 55!

А дошло! А я подумал вы разделили 105 элементов на 10 и получили 5 массивов по 10 элементов.

Да просто: делите 105 на 10 и округляете, получится 10. Остаток N будет меньше числа на которое делите, значит увеличиваете длину N последних массивов на 1
Остаток я имею в виду не дробное число получаемое при делении, то есть 111/5 = 22,2. Остаток в данном случае = 1.

Автор: triclosan 12.7.2010, 12:34

почему не 6*10 = 60, 5*9 = 45 ?

Автор: ksnk 12.7.2010, 12:57

mur88, находим остаток от деления 105 на X=10, получаем число M=5. (105-5)/10 - получаем число N=10.

цикл  от 1 до X.
{
  откусываем от массива N элементов.
  если M>0, то добавляем к откусаному еще один элемент и делаем M-- ;
}
...
profit

Автор: Silent 14.7.2010, 12:05

Пусть n - количество элементов массива, m - на сколько частей надо поделить. Тогда всего в m-n%m массивах будет по n/m элементов, а в n%m массивах - по n/m+1 элементов. Ровно и без мороки.
пример: n=105, m=10: в 105/10-105%10=5 по 105/10=10 элементов, в 105%10=5 по 105/10+1=11 элементов.

p.s. "жадный алгоритм" решения задачи.

Автор: CramErern 2.9.2022, 23:44