Множество, подмножества, суммы

@Ahiles · Регистрация: 03.10.2008

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

Всем привет!

Дано множество {1, 2, ... ,n} n=<200 и число k, делитель n. Написать программу которая выведет одну из возможностей разбиения этого множества на k подмножеств по n/k элементов, так что сумма элементов во всех подмножествах равна.

Я написал для n чётного, но не могу найти решения для нечётного.. Существует ли для нечётного вообще алгоритм???

Вот что у меня получилось

Pascal
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
program premii;
type t=array[1..200] of integer;
var n,k,j,s,i:integer; f,g:text;  A:t;
  begin
    assign(f, 'in.txt');
    reset(f);
    assign(g, 'out.txt');
    rewrite(g);
    read(f, n); read(f,k);
    if n mod 2 =0 then
        begin
           if k mod 2=1 then writeln(g, '0') else
 
           begin
              for i:=1 to k do begin
 
                for j:=1+s to trunc(n/(2*k))+s do
                  write(g, j, ' ',n-j+1, ' ');
 
                s:=s+trunc(n/(2*k));
 
                writeln(g);
 
                end;
 
           end;
 
        end;
    close(f); close(g);
  end.

Если ВОЗМОНЖНО то сначала подать идей, а уж потом решение.. Хочется самому допереть...

@Puporev · 12.11.2008, 12:31

Дело не в четности или нечетности. Нужно чтобы n не было прстым числом, т.е должно иметь делители кроме 1 и n. Поэтому при вводе n нужно делать соответствующую проверу.
Для этого я бы написал логическую функцию проверки простых чисел и проверял ввод n так:

Pascal
1
2
3
4
repeat
write('n=');
readln(n);
until not Prost(n);

Кроме того число k должно быть таким делителем числа n. Опять нужна проверка типа:

Pascal
1
2
3
4
repeat
write('k=');
readln(k);
until (k>1)and (k<n) and (n mod k=0);

Добавлено через 1 час 3 минуты 49 секунд
Да и решение какое-то странное. Нужно ведь из множества, например [1,2,3,4,5,6,7,8,9] получить его разбиения из 3 по три с равной суммой и чтоб в разбиениях элементы не поаторялись, т.е. например
[1,5,9] [2,6,7] [3,4,8]. А это для больших n не такая простая задача, рекурсией попахивает.

@Ahiles · 12.11.2008, 23:16 **[ТС]**

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

Дело не в четности или нечетности. Нужно чтобы n не было прстым числом, т.е должно иметь делители кроме 1 и n. Поэтому при вводе n нужно делать соответствующую проверу.
Для этого я бы написал логическую функцию проверки простых чисел и проверял ввод n так:
repeat
write('n=');
readln(n);
until not Prost(n);
Кроме того число k должно быть таким делителем числа n. Опять нужна проверка типа:
repeat
write('k=');
readln(k);
until (k>1)and (k<n) and (n mod k=0);

В условии сказано что k делитель n, следовательно n не простое!

А МОЖЕТ КТО-ТО РЕШИТЬ ЭТУ ЗАДАЧУ???

@Puporev · 13.11.2008, 09:30

следовательно n не простое!

А если пользователь введет число 17? Если ты таких вещей не знаешь, зачем за серьезные задачи берешься? Ищи в инете, в книгах про генерацию разбиений множеств.

@Ahiles · 13.11.2008, 16:55 **[ТС]**

Пользователь не вводит... А число уже дано... Не понял... каких вещей я не знаю??? И всё-таки можно хоть какую нибудь идею.. Или вы просто сами не знаете как решить??

@Puporev · 13.11.2008, 17:06

А число уже дано.

Кем дано? Богом? Я Вам написал, что и где искать. А решать эту задачу мне как то ни к чему, мне ее не задавали.

@Puporev · 13.11.2008, 18:40

Вот работа на тему разбиения множеств, но там генерируются все подмножества, а тебе надо выбрать из них только те, в которых количество элементов равно n div k, а их сумма ((1+n)*n div 2) div k.

Новые блоги и статьи Все статьи Все блоги /
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .

@Ahiles 0 / 0 / 0 Регистрация: 03.10.2008 Сообщений: 9
	13.11.2008, 16:55 [ТС]
	Пользователь не вводит... А число уже дано... Не понял... каких вещей я не знаю??? И всё-таки можно хоть какую нибудь идею.. Или вы просто сами не знаете как решить?? 0