Жадный алгоритм разбиения массива на n частей

@Freeman666 · Регистрация: 04.03.2013

Студворк — интернет-сервис помощи студентам

Всем привет.
Понадобилось разбить массив на n приблизительно равных частей. Нашёл где-то на просторах инета якобы жадный алгоритм разбивки.
Пусть у нас дан массив длиной length и разбить его надо на n частей.

первый массив = length / n - length % n;
кол-во элементов в нём = length / n;

второй массив = length % n;
кол-во эл-тов в нём = length / n + 1;

1)тест (Верно)

length = 5 n=2

5/2 - 5%2 = 1
5/2 = 2

5%2=1
5/2+1 = 3

2) тест (Неверно)

length = 4 n=3

4/3 - 4%3 = 0
4/3 = 1

4%3=1
4/3+1 = 2

3) тест (Верно)

length = 9 n=3

9/3 - 4%3 = 3
9/3 = 3

9%3=0
9/3+1 = 4

4) тест (Неверно)

length = 3 n=3

3/3 - 3%3 = 1
3/3 = 1

3%3=0
3/3+1 = 2

Кто-нибудь знает нормальный алгоритм, а то этот неюзабельный...

@blackhard27 · 30.04.2013, 05:24

Что Вы подразумеваете под "разбить"? Найти последовательность индексов, которые обозначают номера границ разделенного массива на n частей или составить из одного массива n -приблизительно равных массивов?

Добавлено через 46 минут
Я вот быстро накидал. Смысл в том, что равные части - это значит, что длина не отличается больше, чем на единицу. Вводим длину массива и количество частей. Выводит последовательность последних индексов каждой части(нумерация с нуля):

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static void main(String []args){
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int n = scanner.nextInt();
        int arr[] = new int[n];
        int mod = length%n;
        int step = (length - mod)/n;
        int i0;
        if(mod == 0){
            i0 = step-1;
        } else {
            i0 = step;
            mod--;
        }
        for (int i=0; i < arr.length; i++){
            arr[i] = i0;
            if(mod > 0){
                i0 += step + 1;
                mod--;
            }
            else
                i0 += step;
        }
        System.out.println();
        System.out.print("{");
        for (int d: arr){
            System.out.print(d+" ");
        }
        System.out.println("}");
    }

@Freeman666 · 30.04.2013, 17:07 **[ТС]**

Хотел что-то вроде этого. Но эту фигню я с утра написал, поэтому наполовину нерабочая =)

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void main(String[]args){
       Scanner scanner = new Scanner(System.in);
       int[] mass = new int[4];
        int length = scanner.nextInt();
        int n = scanner.nextInt();
        int div = length/n;
        int mod = length%n;
        mass[0] = n;
        mass[1] = div;
        if(mod==0){ 
            mass[2] = 0;
            mass[3] = 0;
            for (int i : mass) {
                System.out.println(i);
            }
            return;
        }else{
            mass[0] = n/2;
            mass[1] = div;
            mass[2] = n/2+n%2;
            mass[3] = div+1;
            for (int i : mass) {
                System.out.println(i);
            }
        }
}

Добавлено через 4 часа 4 минуты
В общем если заюзать код, приведённый выше, то получим нечто такое вот кривое, но работающее

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 public int[] divide(int n, int length) {
        final int numOfElem;
        int temp;
        int res[] = new int[4];
        int arr[] = new int[n];
        int mod = length % n;
        int step = (length - mod) / n;
        int i0;
        if (mod == 0) {
            i0 = step - 1;
        } else {
            i0 = step;
            mod--;
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i0 + 1;
            if (mod > 0) {
                i0 += step + 1;
                mod--;
            } else {
                i0 += step;
            }
        }
        res[0]++;
        res[1] = arr[0];
        numOfElem = arr[0];
        for (int i = 1; i < arr.length; i++) {
 
            temp = arr[i] - arr[i - 1];
 
            if (numOfElem == temp) {
 
                res[0]++;
            } else {
                res[2]++;
                res[3] = temp;
            }
 
        }
        return res;
    }

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@Freeman666 10 / 36 / 7 Регистрация: 04.03.2013 Сообщений: 184

	Жадный алгоритм разбиения массива на n частей 30.04.2013, 03:52. Показов 9183. Ответов 2 Метки нет (Все метки) Всем привет. Понадобилось разбить массив на n приблизительно равных частей. Нашёл где-то на просторах инета якобы жадный алгоритм разбивки. Пусть у нас дан массив длиной length и разбить его надо на n частей. первый массив = length / n - length % n; кол-во элементов в нём = length / n; второй массив = length % n; кол-во эл-тов в нём = length / n + 1; 1)тест (Верно) length = 5 n=2 5/2 - 5%2 = 1 5/2 = 2 5%2=1 5/2+1 = 3 2) тест (Неверно) length = 4 n=3 4/3 - 4%3 = 0 4/3 = 1 4%3=1 4/3+1 = 2 3) тест (Верно) length = 9 n=3 9/3 - 4%3 = 3 9/3 = 3 9%3=0 9/3+1 = 4 4) тест (Неверно) length = 3 n=3 3/3 - 3%3 = 1 3/3 = 1 3%3=0 3/3+1 = 2 Кто-нибудь знает нормальный алгоритм, а то этот неюзабельный... 0

Жадный алгоритм разбиения массива на n частей

Решение