Разбить последовательность чисел на три набора с равной суммой

@LexaNoob · Регистрация: 09.08.2019

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

Написать программу, которая получает на вход последовательность из N чисел и выводит 3 подмножества, в которых сумма равна. Вывести их, если это возможно. Должны быть использованы все числа.
Пример: { 20, 23, 25, 49, 45, 27, 40, 22, 19 } может быть разделен на три набора { 20, 25, 45 }, { 23, 27, 40 }, { 49, 22, 19 }

@XLAT · 09.05.2020, 16:08

LexaNoob,

Code
1
2
3
4
5
6
7
алгоритм:
1. Сумма всех элементов последовательности:         S
2. Сумма каждого набора:             S1 = S2 = S3 = S / 3
3. Брутфорсом находим ВСЕ наборы в которых s = S3
4. Брутфорсом сравниваем эти найденные наборы на предмет неравенства(см.5)
5. ПРИЗНАК НЕРАВЕНСТВА: Два набора не равны друг другу если индексы(*) из входной последовательности все УНИКЛЬНЫ.
6. Если по окончанию цикла проверки на неравенство у нас осталось два набора, то ГУД! , иначе ФЕЙЛ...

*)
контроль по индексам на случай присутствия во входной последовательности ОДИНАКОВЫХ чисел.

@LexaNoob · 09.05.2020, 16:46 **[ТС]**

XLAT, а сложность алгоритма брутфорса какая?

Добавлено через 12 минут
XLAT, и мне нужно строго на 3 подмножества

Добавлено через 58 секунд
XLAT, и в каждом одинаковое кол-во элементов

@XLAT · 09.05.2020, 17:04

Сообщение от LexaNoob

и в каждом одинаковое кол-во элементов

это всё упрощает.

Code
1
2
3
3. Если есть 3 числа равные S3 гоуту 4, иначе ФЕЙЛ.
4. В оставшихся 6 числах если есть 3 числа равные S3 гоуту 5, иначе ФЕЙЛ.
5. Гуд!

Вся задача сводится к нахождению 3 чисел равных сумме S3.

@LexaNoob · 09.05.2020, 17:29 **[ТС]**

XLAT, а если реализовывать брутфорс, то какая сложность будет у брутфорса N^2 или n!. Скажи, пожалуйста.

@XLAT · 09.05.2020, 20:00

Сообщение от LexaNoob

N^2 или n!

ну, если округлить в тяжелый случай, то чет мне видится, что N^3
поэтому я и назвал сей цикло-файндер брутфорсом, (это излюбленный мой приём, чтобы не забивать голову

)
но в реальности проходы будут урезаться:
если первое слагаемое из первого индекса, то второе уже надо будет брать откуда угодно, но только не из нулевого.

Добавлено через 8 минут

сумма вычисляется 54 раз

C++
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
#include <iostream>
#include <conio.h>
 
int main()
{
    const int N = 9;
    int m[N] = { 20, 23, 25, 49, 45, 27, 40, 22, 19 };
    
    int S = 0;
    for(int i = 0; i < N; S += m[i++]) ;
    
    S /= 3;
    
    int o = 0; /// Количество вычислений.
    
    for(int i = 0; i < N-2; i++)
    {   int s = m[i];
        
        for(int j = i+1; j < N-1; j++)
        {   s += m[j];
            if(s  > S)
            {    s -= m[j];
                continue;
            }
            
            for(int k = j+1; k < N; k++)
            {   o++;
                if(s + m[k] == S)
                {   std::cout << m[i] << ", " << m[j] << ", " << m[k] << "\n";
                    goto m;
                }
                
            }
            s -= m[j];
        }
m:
        ;
    }
    
    std::cout << "o = " << o << "\n";
}

А в самом тяжёлом случае(когда ничего не находит) здесь 84 раза.

без гоуту

C++
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
#include <iostream>
 
int main()
{
    const int N = 9;
    int m[N] = { 20, 23, 25, 49, 45, 27, 40, 22, 19 };
    
    int S = 0;
    for(int i = N; i--; S += m[i]) ;
    
    S /= 3;
    
    for(int i = 0; i < N-2; i++)
    {   int s = m[i];
        
        for(int j = i+1; j < N-1; j++)
        {   s += m[j];
            for(int k = j+1; k < N; k++)
            {   if(s + m[k] == S)
                {   std::cout << m[i] << ", " << m[j] << ", " << m[k] << "\n";
                    j = k = N;
                }
            }
            s -= m[j];
        }
    }
}

в общем случае можно использовать эвристики:
если с первым слагаемым искомая сумма не найдена, то FAIL.
можно придумать и кучу других.

но ваш случай, конеш, простенький.

@HWAA · 25.08.2022, 18:09

а если количество чисел в подмножествах может быть разным и последовательность 1,2,3,...,n можно обойтись без перебора?

Новые блоги и статьи Все статьи Все блоги /
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. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@LexaNoob 0 / 0 / 0 Регистрация: 09.08.2019 Сообщений: 88

	Разбить последовательность чисел на три набора с равной суммой 09.05.2020, 14:28. Показов 4478. Ответов 6 Метки нет (Все метки) Написать программу, которая получает на вход последовательность из N чисел и выводит 3 подмножества, в которых сумма равна. Вывести их, если это возможно. Должны быть использованы все числа. Пример: { 20, 23, 25, 49, 45, 27, 40, 22, 19 } может быть разделен на три набора { 20, 25, 45 }, { 23, 27, 40 }, { 49, 22, 19 } 0

@LexaNoob 0 / 0 / 0 Регистрация: 09.08.2019 Сообщений: 88
	09.05.2020, 16:46 [ТС]
	XLAT, а сложность алгоритма брутфорса какая? Добавлено через 12 минут XLAT, и мне нужно строго на 3 подмножества Добавлено через 58 секунд XLAT, и в каждом одинаковое кол-во элементов 0

@LexaNoob 0 / 0 / 0 Регистрация: 09.08.2019 Сообщений: 88
	09.05.2020, 17:29 [ТС]
	XLAT, а если реализовывать брутфорс, то какая сложность будет у брутфорса N^2 или n!. Скажи, пожалуйста. 0

@HWAA 8 / 7 / 1 Регистрация: 08.04.2021 Сообщений: 151
	25.08.2022, 18:09
	а если количество чисел в подмножествах может быть разным и последовательность 1,2,3,...,n можно обойтись без перебора? 0

Разбить последовательность чисел на три набора с равной суммой

Решение