powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
25 сообщений из 450, страница 4 из 18
Как решить задачу по комбинаторике?
    #39764679
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я-бы ввел понятие веса окружностей и диагоналей.

Вес - как инвариант этой задачи.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764707
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
https://jsbin.com/wojuvex/edit?js,output
так ковырять нагляднее.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764708
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а потом окажется, что это задачка для 3го класса...
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764728
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TАлгоритм решения найден, дальше неинтересно. Пусть ТС дорешает.

Я про другое подумал: про тот мозг, который эту задачу придумал. Надо взять 20! комбинаций и найти среди них позиции 3-х чисел чтобы в итоге было однозначное решение.

PS Кто не в теме 20! это 20 лет перебора при проверке одного набора за один такт проца 4 ГГц.

значит, этот мозг перебирал среди решений, которых гораздо меньше )
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764756
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

Спасибо за картинку!

Сразу что-то стало получаться.

А теперь поработаем с уравнениями

Пусть сумма будет К.

Тогда из средней окружности:
х8+х10+х9+х11=К-24
из внутренних окружностей:
х8+х10=К-х13-х4-х7-12
х9-х11=К-х12-х6-х3-12

если подставить в первое уравнение, то получаем:

2хК-х13-х6-х3-х12-х4-х7-24=К-24
Или
К=х12+х6+х3+х12+х4+х7

Из диагоналей – первые три из одной и вторые три из другой. Подставляем:
К=К-х16-х1+К-х14-х1
Или х14+х16=К-2*х1 (умножить)

Если 60 и 20, то х14+х16= 20
Если 57 и 19, то х14+х16= 19

Далее, в таком же виде: окружность, диагональ , окружность, или наоборот...
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764802
Форум программистов разбирает легенькую задачку для олимпиады средних класоов )))

Комбинаторику сюда прикрутили
Зачем вообще считать кол-во итеракций при решении перебором
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764805
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Митя_НиточкинКомбинаторику сюда прикрутили
Зачем вообще считать кол-во итеракций при решении переборомколичество вариантов нужно для оценки возможности расчёта такой задачи, одно дело 1000 вариантов перебрать, 20! - совсем другое
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764809
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
13 уравнений с 18 неизвестными сводится к диафантовому уравнению с 6 неизвестными

а это 17!/(17-6)! вариантов
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764812
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Далее:
Смотрим на внутренние окружности через х15 и х16, а также через х15 и х14.
Складываем, получаем (с учетом х14+х16=20):
2*15+20=2*К-24-х11-х10-х7-х3-х4-х6

Последние 4 слагаемых за счёт внутренней окружности и горизонтального диаметра переводим в:
х11+х10=2*К-36-х1-3*х15-20

Теперь смотрим на внутренние окружности, проходящие через х13 и х14 и через х12 х х16 и складываем:
К-х15-12=2*К-24-х8-х9-х2-х5

Последние 2 слагаемые – К-х1-12-х15

Получаем
Х8+х9=2*х15-12+х1-12

Теперь складываем х8,х9,х10,х11, и с учетом средной окружности получаем:

Х15=К-56

Если 60 и 20, то х15= 4
Если 57 и 19, то х15= 1
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764814
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Митя_Ниточкин, ты ее уже решил?
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764846
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Далее можно определить суммы пар:
х2 и х5, х13 и х14, х9 и х6, х10 и х11.

То есть определены одно число и 5 пар чисел.
Осталась четверка чисел.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764847
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ошибка:
х9 и х8
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764848
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
тороплюсь:
х12 и13
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764849
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот интересный вопрос возникает

Если у нас есть несколько множеств чисел, например x1 =[1..3], x2 =[2...7, 19], x3 =[1..10], x4 =[12..15], ...

Есть ли алгоритм позволяющий эффективно получить всё множество сумм который могут получиться при комбинации (X1 + X2 + X3 + X4 + ...) элементов из этих множеств? При ограничении что число может входить в сумму только 1 раз

эффективно значит "не за NP время" как при наивной реализации
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764858
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я вот думаю о том что если хранить сумму оставшихся чисел из пул доступных.
То можно эффективно прерывать backtracking если мы точно знаем что у данной
окружности или диаметра уже недостаточно массы.

Тоже самое. Докидывать нужные гирьки в те окружности и диаметры где веса не хватает.
По сути балансировать центр масс всей этой конструкции.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764899
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ вот думаю о том что если хранить сумму оставшихся чисел из пул доступных.
То можно эффективно прерывать backtracking если мы точно знаем что у данной
окружности или диаметра уже недостаточно массы.

Тоже самое. Докидывать нужные гирьки в те окружности и диаметры где веса не хватает.
По сути балансировать центр масс всей этой конструкции.
Не, это лишнее. Я новый способ заполнения придумал.

Нам известно:
ПараметрЗначениеЗначениеЦентр1920Сумма5760Пропущено2010

Центр, сумму и пропущенное берем из таблицы. Начинаем заполнять круги от центра, проверяя сумму каждого круга по заполнению. В этом случае к заполнению второго круга не перейдем, если по первому сумма не верна. Третий можно даже не проверять, т.к. если сумма первого и второго верны, то он тоже верен.
В итоге находим потенциальные решения.
Дальше доперебор каждого потенциального решения.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764928
сумма не может быть нечетна
к 4 странице пора бы это понять
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764932
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TНам известно:
ПараметрЗначениеЗначениеЦентр1920Сумма5760Пропущено2010

Мне кажется, на эту дилемму должен найтись однозначный ответ путем исследования четности/нечетности.
В любом случае исключаемое число - четное, т.е. остается всего 9, 3 из них уже выставлены.
Знак суммы такой же как знак центра, поэтому сумма диагональных элементов без середины всегда четная. Т.е. еще как минимум одно четное обязательно должно быть на средней линии (5 осталось). Если в центре четное (4), то сумма тоже четная, значит еще два четных должны быть на эксцентриках левой точки (2 осталось).
Одно четное еще нужно на внешней окружности, но оно может быть совмещено с крайней правой (диагональю).
Дальше пока неясно.



Дальше пока не наметил.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764942
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Митя_Ниточкинсумма не может быть нечетна
к 4 странице пора бы это понять
Почему? Если это доказано, то ответ - пропущено число 10. Или задача не имеет решения.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764947
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Читерные пятнашки переставляй любое число с любым. Стратегия берем число больше всего влияющие на увлечение средней суммы своих множеств и меняем его с ближайшим по значению если это не увеличит разницу средних значений.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764953
Митя_Ниточкин, раз для вас это такая лёгкая задача, на которую не стоит использовать компьютер, попробуйте её решить, но боюсь, что будет слишком сложно. Тогда и можно и использовать ресурсы ЭВМ
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764959
Спасибо всем, очень облегчели работу. Но вот для себя, чтобы потом просто так не обращаться, как эту задачу можно без компьютера решить - без подбора. Ведь такая возможность безусловно есть, на мой взгляд
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764966
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дмитрий СмерксСпасибо всем, очень облегчели работу. Но вот для себя, чтобы потом просто так не обращаться, как эту задачу можно без компьютера решить - без подбора. Ведь такая возможность безусловно есть, на мой взглядскорее всего задача первоначально звуча в виде "какое число лишнее?"

для математики это было бы характерно, задача по информатике?
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39764977
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Малыхин СергейЧитерные пятнашки переставляй любое число с любым. Стратегия берем число больше всего влияющие на увлечение средней суммы своих множеств и меняем его с ближайшим по значению если это не увеличит разницу средних значений.
Эта стратегия начинает работать когда у вас уже есть первое приближение.

Допустим вы бросили 1..20 кроме случайного случайным образом на доску.

Какие два следующих вы поменяете?
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765001
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В самом начале заполняются вакантные места от большего числа к меньшему. Т.е. самое большое число в найденную вакантную точку которая изменит как можно больше множеств с минимальной суммой в сторону увеличения и получаем неплохое начальное распределение. При заполнении всех вакантных точек пробуем переставлять. Алгоритм заведомо не оптимален но работает почти моментально.
...
Рейтинг: 0 / 0
25 сообщений из 450, страница 4 из 18
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]