Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 9 10 11 12 13 14 15 16 17 [18]
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Gennadiy Usov
kealon(Ruslan)
Gennadiy Usov,
внимательно читайте, табличку в эксельке посмотрите (участвует там то уравнение или нет)
Тогда просто укажите те уравнения, которые остались, если не трудно.

Без таблицы они будут смотреться интереснее.
21797455
4 фев 19, 10:35    [21801076]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
kealon(Ruslan)
G
x[1] + a[1] + a[2] +a[3] +  a[4] + x[9] + x[11] + x[12] + x[13] + x[14] + x[15] + x[16] +  x[17]= 174
sum = 12 + x[12] + x[13] + x[14] + x[15] + x[16]; // Внешний круг
sum = 18 + 6 +  a[4] + x[9] + x[11] // Средний круг
sum = a[1]  + a[2] + a[3] // Внутренний круг
sum = 12 + a[1] + x[1] + x[15] // Диаметр горизонтальный
sum = x[14] + a[3] + x[1] + x[12] // Диаметр cлева направо
sum = x[13] + a[2] + x[1] + x[16] // Диаметр cправа налево
// ~Шесть кругов
sum = 12 + x[9] + a[2]+ x[11] + x[12]
sum = 12 + x[13] + a[3] + a[4]
sum = x[13] + x[14] + 18 + a[1] + x[9]
sum = x[15] + x[16] + x[11] + a[3] + 18



начинаем перечислять неизвестные: a[4] x[9] x[11] x[12] x[13] x[14] x[15] x[16] a[1] a[2] a[3] x[1] x[17] sum

Получаем 11 уравнений и 15 неизвестных
4 фев 19, 11:44    [21801135]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Gennadiy Usov,

слушай, раз 5 пересчитал, 14 неизвестных
4 фев 19, 12:10    [21801154]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
kealon(Ruslan)
Gennadiy Usov,

слушай, раз 5 пересчитал, 14 неизвестных
Я ошибся, 14 неизвестных.
4 фев 19, 12:15    [21801165]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Gennadiy Usov
Gennadiy Usov
Если идти дальше, то есть ещё неравенства, и работа в конечном множестве.
Например, х16 не может иметь значения 6,10,12,18,20.
А, из уравнения х16=20-х14, получается, что для х16 не могут быть значения 2, 8, 14 (из четных, остаются только 4 и 16). Такие же значения не может иметь х14.
Далее
х12+х13 >=9
а1>=9
х13<=14 – только 1,2,3,5,7,8,9,11,13,14 (нет 4, иначе х12=х16)
х15>=3
Если выбирать х16 и х13, то получается 10 х 12 = 120 вариантов.
Далее:
из уравнения
х12=х16+х13-4
видно, что х16 и х13 либо оба четные, либо нечетные.
Следовательно: для четных х16 будет 16 (4 нельзя) и для х13 – 2 (8 и 14 нельзя).
То есть один вариант.
Для нечетных: 10 х 7 = 70 вариантов.
х16+х13<=23.
Тогда уже 54 варианта.
Убираем:
одинаковые варианты.
х12 не может быть 6,10,12,18, 20 и более
То есть, убираем 30 вариантов.
Остаётся 24 +1 = 25 вариантов.
Подставил оставшиеся х16 и х13 в уравнения для х14 и х15, получилось, что осталось 13 вариантов.
4 фев 19, 12:45    [21801191]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Далее,

подставил в уравнение определения х9 - осталось 7 вариантов

подставил в уравнение определения х8 - осталось 2 варианта

подставил в уравнение х11 - остался один вариант.

Нашел а1, а2, а3 - 19, 22, 19
4 фев 19, 13:05    [21801209]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Забыл указать значения переменных, полученных ранее:
х16=13, х13=5, х12=14, х15=9, х14=7, х8=8, х9=11, х10=16, х11=1

Далее имеем:

Остались числа 2,3,4 и 15,17,19
и получены значания:
а1 (х2,х5) = 19
а2 (х3,х6) = 22
а3 (х4,х7) = 19

22 - это только 19 и 3
19 – это 15 и 4, или 17 и 2

Получаем два варианта
15, 19, 17, 4, 3, 2
и
17, 19, 15, 2, 3, 4
У каждого варианта есть 8 подвариантов (сочетаний), когда меняются значения х2 и х5, х3 и х6, х4 и х7.

В результате определены 16 вариантов решения задачки, опубликованной в начале топика.
4 фев 19, 13:21    [21801227]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Замечена интересная вещь: 2 числа, расположенные на линии, проходящей через центр, и которые находятся на одном расстоянии от центра,
имеют примерно одну и ту же сумму.

Что-то напоминает центр тяжести системы чисел.
4 фев 19, 13:27    [21801235]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
alex55555
Member

Откуда:
Сообщений: 2095
kealon(Ruslan)
я эти два уравнения вообще удалил (количество по детерминанту определил), не нужны они, там всего 11 независимых уравнений
удалил их потому, что тогда можно было X8 + X10 одной переменной заменить

Это неправильно, в результате ослабилось ограничение на решение и получились 16 лишних вариантов.
kealon(Ruslan)
вы же сами скидывали автоматическое решение

Да, выкладывал, но это решение как раз на основе вашего предложения по сложению уравнений. То есть без сложения было бы другое решение. Я пробовал на этом решении выводить результат, но то ли я где-то ошибся, то ли ещё что, у меня не получилось найти решения таким способом. Потом я переключился на другие варианты, тогда и понял, что сложение уравнений создаёт лишнюю пару переменных, в которой возможны перестановки, что даёт лишние решения.
kealon(Ruslan)
кстати, у вас там прямо и написано что всего 11 независимых уравнений
автор
dependent equations eliminated: (11)

Я не уверен в смысле этой фразы. Что там имели в виду разработчики системы я не знаю, но здесь (если читать буквально) говорится об устранении 11-ти уравнений.
4 фев 19, 13:38    [21801246]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Gennadiy Usov
В результате определены 16 вариантов решения задачки, опубликованной в начале топика.

Ну вот, я же говорил, что можно всё свести к перебору перестановок в трёх парах, плюс одно "перетекание", в итоге - 8*2 вариантов, где 8 для перестановок (2^3) и ещё умножаем на 2 из-за "перетекания".

В итоге школьнику нужно просто заметить перестановочные пары и за счёт ограничений вывести 11 фиксированных значений, а далее взять любой из 16 вариантов перестановок.
4 фев 19, 13:42    [21801248]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Gennadiy Usov
В результате определены 16 вариантов решения задачки, опубликованной в начале топика.

Ну вот, я же говорил, что можно всё свести к перебору перестановок в трёх парах, плюс одно "перетекание", в итоге - 8*2 вариантов, где 8 для перестановок (2^3) и ещё умножаем на 2 из-за "перетекания".

В итоге школьнику нужно просто заметить перестановочные пары и за счёт ограничений вывести 11 фиксированных значений, а далее взять любой из 16 вариантов перестановок.
Но надо было сначала все ограничения расписать, а потом потратить примерно час, чтобы отбросить ненужные пары из х16 и х13
4 фев 19, 13:51    [21801260]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Gennadiy Usov
Но надо было сначала все ограничения расписать, а потом потратить примерно час, чтобы отбросить ненужные пары из х16 и х13

Да, суммарно на это нужно приличное время. Если задача не олимпиадная, то тогда наверное нашлись бы "успевшие вовремя" (ибо время не ограничено), а вот в 3 часа - не знаю, разве что если аналогичный подход был отработан на другой задаче. А с нуля всё расписать, да учитывая разные направления, перебирая которые уходит время, сильно не уверен в возможности в 3 часа уложиться.
4 фев 19, 16:58    [21801450]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Gennadiy Usov
Но надо было сначала все ограничения расписать, а потом потратить примерно час, чтобы отбросить ненужные пары из х16 и х13
Да, суммарно на это нужно приличное время. Если задача не олимпиадная, то тогда наверное нашлись бы "успевшие вовремя" (ибо время не ограничено), а вот в 3 часа - не знаю, разве что если аналогичный подход был отработан на другой задаче. А с нуля всё расписать, да учитывая разные направления, перебирая которые уходит время, сильно не уверен в возможности в 3 часа уложиться.
На самом деле, уложиться можно.

В своё время я был на подготовительных курсах мехмата, где обсуждались типовые задачи (почти "натаскивание") и пути их решения. Это позволило мне решить все задачи на приёмных экзаменах за время, меньшее часа.

Мы же старались обсуждать задачку со стороны, без строгого подхода к её решению.

В нашем случае, получена задача, и необходима следующая последовательность типовых действий:
- выявить все неизвестные и написать все уравнения. При этом окажется, то неизвестных много больше, чем уравнений.
- найти пути упрощения уравнений (определить а1, а2, а3). При этом окажется, что неизвестных всё равно больше.
- попытаться работать с уравнениями, находить более простые уравнения. Можно попробовать метод Гаусса.(смотря кто в чем преуспел)
- определить свободные переменные, и за счет того, что множество чисел конечное, попытаться выработать неравенства.
- далее, продолжительное, отсекание лишних сочетаний свободных неизвестных (у меня на EXCELе ушло минут 20). Определение а1, а2, а3.
- а разложить а1, а2, а3 - это совсем просто.

Конечно, сейчас это просто говорить, после нескольких дней работы, но "натасканный" школьник будет работать примерно так.
4 фев 19, 18:54    [21801526]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Gennadiy Usov
Конечно, сейчас это просто говорить, после нескольких дней работы, но "натасканный" школьник будет работать примерно так.

То есть он должен решить аналогичную задачу до встречи с данной задачей. По сути олимпиада отбирает тех, кто решал аналогичные олимпиадным задания раньше. Но это означает отсев безумных заучек. В смысле школьнику нет необходимости думать, ему нужно лишь усердно запоминать кучу различных способов решений стандартных задач. Потом он даже где-то может применить свои знания, но вот столкнувшись с проблемой, для которой в его голове нет типового решения, он побежит к мамочке другим математикам и станет выяснять, а нет ли у них в голове чего-то подходящего. А если и у них нет? Кто математику-то двигать будет? Готовые решения никому не интересны, а они все натасканы именно на такое. Поколение ЕГЭ отличается именно таким подходом, но поколение олимпиадников на них в чём-то похоже.
5 фев 19, 14:42    [21801962]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
alex55555,

ну приблизительно так, только объём гораздо больше, часов по 6 каждый день несколько месяцев мало кто осилит

всё как в спорте, разве что не с 3-х лет
5 фев 19, 15:01    [21801980]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Gennadiy Usov
Конечно, сейчас это просто говорить, после нескольких дней работы, но "натасканный" школьник будет работать примерно так.

То есть он должен решить аналогичную задачу до встречи с данной задачей. По сути олимпиада отбирает тех, кто решал аналогичные олимпиадным задания раньше. Но это означает отсев безумных заучек. В смысле школьнику нет необходимости думать, ему нужно лишь усердно запоминать кучу различных способов решений стандартных задач. Потом он даже где-то может применить свои знания, но вот столкнувшись с проблемой, для которой в его голове нет типового решения, он побежит к мамочке другим математикам и станет выяснять, а нет ли у них в голове чего-то подходящего. А если и у них нет? Кто математику-то двигать будет? Готовые решения никому не интересны, а они все натасканы именно на такое. Поколение ЕГЭ отличается именно таким подходом, но поколение олимпиадников на них в чём-то похоже.
Если Вы заметили по репортажам, в которых рассказывали о победителях международных олимпиад, то в разговоре наши победители говорили о том, как они готовились. В том числе, был тренинг, который проводили преподаватели.

И вот в тренинг входит решение основных типовых задач, которые могут встретиться, естественно, по мнению преподавателей.
Такая же практика наверное существует и на местных олимпиадах.

А насчет проблем? Все сталкиваются, и Вы тоже. Всё объять невозможно. И Вы просите помощь у сподвижников, когда непонятно, и что-то новое.

А имея некоторый математический аппарат и имея искусство логически мыслить можно прийти к решению неизвестной задачи.
Даже при этом двигая науку вперед.

А то, что мало, по Вашему мнению, у нас математиков, то это виновато программирование. Школьнику дали инструмент всё решать, не вдаваясь в формулы. Зачем ему упрощать систему уравнений? Пусть машина думает. А он пока покурит.

В насчет ЕГЭ? Наши победители международных олимпиад сдавали ЕГЭ.
5 фев 19, 17:11    [21802081]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
kealon(Ruslan)
alex55555,
ну приблизительно так, только объём гораздо больше, часов по 6 каждый день несколько месяцев мало кто осилит
всё как в спорте, разве что не с 3-х лет
Кто-то занимается борьбой, кто-то шахматами, кто-то фигуркой, кто-то гимнастикой (разной), ..., а кто-то математикой.

Либо сам выбирает, либо родители подсказывают.
И с раннего возраста. Иначе можно опоздать, или придут другие мысли.
5 фев 19, 17:15    [21802090]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
alex55555
Member

Откуда:
Сообщений: 2095
В общем нашёл стандартную задачу для ЕГЭ. Вот здесь. У нас типичное решение с помощью динамического программирования. Ну а сочинять такие задачи как раз удобно используя ссылки из википедии.

Интересно, 3 фиксированных авторами переменных принадлежат к множеству обязательно фиксированных или всё же могут иметь другие значения? Перестановки и перетекания для них исключены, но, возможно, отказ от фиксации этих переменных даст другие наборы для 11 фиксированных в нашем случае.
5 фев 19, 18:14    [21802138]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
В общем нашёл стандартную задачу для ЕГЭ. Вот здесь. У нас типичное решение с помощью динамического программирования. Ну а сочинять такие задачи как раз удобно используя ссылки из википедии.
В статье "Задача о сумме подмножеств" рассматривается задача разделения некоторого множества чисел на несколько подмножеств, имеющих определенную сумму входящих в это подмножество чисел. В этом случае необходимо динамическое программирование.

У нас в задачке имеется множество из 20 чисел от 1 до 20 и 5 не пересекающихся подмножеств этого множества: 3 окружности по 6 чисел, центр и некоторый центр (число, "вычеркнутое" из множества). Для каждого подмножества неизвестна сумма чисел, однако у 3-х окружностей сумма одинаковая. В данной постановке задачка подпадает под динамическое программирование.

Но у задачки есть ещё дополнительные условия: дополнительно имеются 3 диагонали и 6 внутренних окружностей, то есть 9 подмножеств из того же множества, которые пересекаются с основными окружностями и между собой: 5 подмножества по 5 чисел и 6 подмножеств по 6 чисел. И у всех этих новых подмножеств сумма чисел совпадает с суммами чисел в основных окружностях.

Поскольку появляются дополнительные условия, то задача динамического программирования упрощается до перебора 2-х чисел, а если в уравнениях использовать замкнутость множества, то задачка решается без динамического программирования.
6 фев 19, 16:13    [21802839]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Основная задача - решена?
6 фев 19, 16:19    [21802842]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Интересно, 3 фиксированных авторами переменных принадлежат к множеству обязательно фиксированных или всё же могут иметь другие значения? Перестановки и перетекания для них исключены, но, возможно, отказ от фиксации этих переменных даст другие наборы для 11 фиксированных в нашем случае.
Если бы авторы не поставили числа 6, 12, 18 в кружочки задачки, то расширенная задачка решалась бы с помощью динамического программирования, когда переменных - 5. Замкнутость множества тут бы не помогла для уменьшения переменных.

А получение х2,х3,х4,х5,х6,х7 из а1, а2, а3 останется таким же.

Поскольку в расширенной задачке увеличивается количество степеней свободы на 3, то, возможно, в данном варианте расширенной задачки может быть больше решений. чем в исходной задачке.
6 фев 19, 16:20    [21802844]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Основная задача - решена?
Решена.

Решена двумя способами:
динамическим программированием полученных уравнений (назовем так с учетом новых сообщений) 21794557
и решением полученных уравнений с учетом уравнений неравенств и замкнутости множества чисел 21801191, 21801209 и 21801227
6 фев 19, 16:54    [21802895]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Дмитрий Смеркс
Спасибо всем, очень облегчели работу. Но вот для себя, чтобы потом просто так не обращаться, как эту задачу можно без компьютера решить - без подбора. Ведь такая возможность безусловно есть, на мой взгляд
Как оказалась, такая возможность (без применения компьютера) есть.

А в чем заключалась Ваша работа?
6 фев 19, 16:58    [21802901]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Я предлагаю тему закрыть. Дима задачу решил.

Исключительно из соображений модерации и чистоты контента.
6 фев 19, 17:02    [21802905]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
Я предлагаю тему закрыть.

Поддерживаю
6 фев 19, 17:32    [21802926]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 9 10 11 12 13 14 15 16 17 [18]
Все форумы / Программирование Ответить