ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
25 сообщений из 450, страница 14 из 18
  14  все
Как решить задачу по комбинаторике?
    #39767086
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Gennadiy UsovВ нашем случае в уравнениях очень мало переменных, и получается что при определении переменных методом Гаусса в уравнениях этих переменных появляется много дополнительных переменных А почему в НАШЕМ случае у меня НЕ получилось много, скорее наоборот? Те же 5, а потом 3.

kealon(Ruslan),
тоже метод, но для детерминанта перестановки мутить, матрица ведь не квадратная.
Мы сначала хотели уйти от перестановок.
...
Рейтинг: 0 / 0
30.01.2019, 15:12
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767091
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
exp98,

какая разница как вы будете делать перестановки в уме или двигая столбцы строки
так хоть ошибиться сложнее и сразу видно где "не получится"
...
Рейтинг: 0 / 0
30.01.2019, 15:15
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767113
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
kealon(Ruslan),
да я и не против, я свой способ дожал до самого ответа.

Народ,
непонятно другое, продолжается обсуждение решений ад хок или народ ориентируется на обобщённый случай, где 18 переменных вместе с суммой и 13 начальных уравнений?
...
Рейтинг: 0 / 0
30.01.2019, 15:29
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767119
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Gennadiy Usov,
а-а-а, кажется догадываюсь, Вы наверное имеете ввиду верхнетреугольную матрицу. А обратным ходом она приводится к строго диагональной. И уж тут переменных - сколько получится.
...
Рейтинг: 0 / 0
30.01.2019, 15:33
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767181
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
kealon(Ruslan)это как то далеко от олимпиады для школьников мы уже применяем методы, которые школьникам недоступны
Вообще здесь пока не исследовались как следует эвристики. Понятно, что программисты хотят быстрее написать программу и не копать вглубь, поскольку это долго и не всегда полезно, но вот как раз школьнику из-за его незнания линейной алгебры пришлось бы упорно ковырять эти эвристики, ну и может быть он бы нашёл.

Хотя ещё момент - если всё же поменять местами диаметры с кругами, то может уже и школьник бы справился?

По решению уравнений:

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
solve([
	        x1 + x2 + x5 + x3 + x6 +x4 + x7 +  x8 + x10 + x9 + x11 + x12 + x13 + x14 + x15 + x16 +  x17= 174,
	        sum = 12 + x12 + x13 + x14 + x15 + x16,
	        sum = 18 + 6 +  x8 + x10 + x9 + x11,
	        sum =x2 + x5  + x3 + x6+x4 + x7,
	        sum =12 + x2 + x5 + x1 + x15,
	        
	        sum = x14 +  x4 + x7+ x1 + x12,
	        sum = x13 + x3 + x6+ x1 + x16,
	        sum = 12 + x9 + x3 + x6+ x11 + x12,
	        sum = 12 + x13 +  x4 + x7 + x8 + x10,
	        sum = x13 + x14 + 18 +x2 + x5 + x9,
	        sum = x15 + x16 + x11 +  x4 + x7 + 18,
	        2*sum = x14 + x15 + 6 +x3 + x6+ x8 + x10 + x16 + x12 +x2 + x5  + 6
	
	      ],
	    [x1, x2, x5, x3, x6, x4, x7, x8, x10, x9, x11, x12, x13, x14, x15, x16, x17]);


dependent equations eliminated: (10)

x1=sum/3,
x2=%r5,
x3=%r6,
x4=%r2,
x5=(2*sum-3*%r5-3*%r3-36)/3,
x6=(sum-12*%r6+6*%r4+6*%r3+108)/12,
x7=(sum-2*%r4+2*%r3-4*%r2+12)/4,
x8=(sum-2*%r1-12)/2,
x9=(sum-18*%r4+18*%r3+36)/12,
x10=%r1,
x11=(5*sum+18*%r4-18*%r3-252)/12,
x12=(5*sum-6*%r4-6*%r3-36)/12,
x13=(sum+2*%r4-2*%r3-36)/4,
x14=%r4,
x15=%r3,
x16=(sum-3*%r4)/3,
x17=-(10*sum-630)/3

Если искать ещё и сумму, то получим:

dependent equations eliminated: (11)

x1=%r7/3,
x2=(2*%r7-3*%r12-3*%r10-36)/3,
x3=(-2*%r9+%r7-4*%r11+2*%r10+36)/4,
x4=%r8,
x5=%r12,
x6=%r11,
x7=(6*%r9-12*%r8+%r7+6*%r10+36)/12,
x8=(%r7-2*%r13-12)/2,
x9=-(-18*%r9+5*%r7-18*%r10-36)/12,
x10=%r13,
x11=(-18*%r9+11*%r7-18*%r10-252)/12,
x12=(2*%r9+%r7-2*%r10-12)/4,
x13=(-6*%r9+5*%r7-6*%r10-108)/12,
x14=(%r7-3*%r9)/3,
x15=%r10,x16=%r9,
x17=-(10*%r7-630)/3,
sum=%r7

Здесь %r есть любое реальное число, но в нашем случае интересны лишь целые, значит это любое целое.
...
Рейтинг: 0 / 0
30.01.2019, 16:17
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767199
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я возьму на себя смелость и процитирую википедию.

Эвристика (от др.-греч. εὑρίσκω — «отыскиваю», «открываю») — отрасль знания, научная область, изучающая специфику творческой деятельности[1].

Под эвристикой понимают совокупность приёмов и методов, облегчающих и упрощающих решение познавательных, конструктивных, практических задач[2].

Эвристика связана с психологией, физиологией высшей нервной деятельности, кибернетикой.

Как наука эвристика развивается на стыке философии, психологии, теории искусственного интеллекта, структурной лингвистики, теории информации, математики и физики[3].
...
Рейтинг: 0 / 0
30.01.2019, 16:45
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767245
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
maytonЯ возьму на себя смелость и процитирую википедию.
В данном обсуждении под эвристикой понимается конкретная находка пути упрощения решения. Само слово эвристика происходит от известного случая с Архимедом, когда внезапно в голову пришла умная мысль. Вот так же точно и нашим участникам внезапно в голову может прийти некая полезная мысль, она и будет той эвристикой, которая упростит решение.

Вообще же в википедии определение не полное, оно не учитывает одну мысль, ту самую, которая к Архимеду пришла. Хотя может уже даже сочинили целую науку "эвристику", но я никогда не встречал использования этого слова в контексте указания на какую-либо науку, а вот в контексте указания на на отдельную полезную мысль - многократно.
...
Рейтинг: 0 / 0
30.01.2019, 17:42
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767275
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Товарищи ученые, доценты с кандидатами!

А решение на поверхности!
Просто лень расписывать большую кипу бумаги формулами.
kealon(Ruslan)Gennadiy Usov,
это как то далеко от олимпиады для школьников
мы уже применяем методы, которые школьникам недоступны
пользуясь основами линейной алгебры (определитель матрицы) мы это определили, как это должен сделать школьник - непонятно
Подумаем, что делает школьник- математик, увидев эту задачку.
Давайте засечем время. Сколько нужно этого времени на задачку?

Школьник делает следующие:
1)Построил 12 уравнений, например 21795456

2)Увидел, что есть общности и заменил часть неизвестных на а1,а2,а3 и добавил уравнение баланса. Например, 21796006

3)Из 4,5,6 уравнений определил а1,а2,а3, подставил в 3-е уравнение, получил
sum = 3*х1

4)Из 7 – 10 уравнений нашел х8,х9,х10,х11 и подставляет во 2-е уравнение. Получил:
х16=х1-х14

5)Подставил х8,х9,х10,х11 в 11-е уравнение. Получил:
х16+х13-х12=4

6)Те же переменные подставил в 12-е уравнение. Получил:
х14+х12-х13=(х1+12)/2

7)Подставил (х12-х13) из уравнения 5) в уравнение 6) получил:
х1=20.
Тогда sum=60

8)Из суммы уравнений 2 и 4-6 получил:
х17=10

Самое главное: нет второго варианта для х1 и х17

9)Из 1-го уравнения и из 5) и 6) получил:

х13=(sum-28-х15-х16)/2
Далее определил х12 из 5)

Получается, что количество свободных переменных сократилось до 2х – х15 и х16.
Ведь у нас 13 уравнений (с балансом) и 15 переменных (вместе с sum).

Остальные переменные из 12-ти уравнений определяются, если есть выборка по х15 и х16.

И, конечно, далее выборка для определения х2,х3,х4,х5,х6,х7, если известны а1,а2,а3

Сколько получилось времени?
Бумаги ушло с черновиками 10 листов А4.

Можно, наверное, ещё поработать, чтобы найти х15 и х16.
...
Рейтинг: 0 / 0
30.01.2019, 18:57
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767281
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нифига. Взял Турбо-Паскаль и закодил.

Кстати надо спросить у Димы. Сколько времени заняла реализация. Без перекуров и фейсбука.
...
Рейтинг: 0 / 0
30.01.2019, 19:07
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767282
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

задача то с подвохом, если впрямую закодить перебор то на расчёт скорее всего никакого времени не хватит

скорее всего требуется найти, то что мы нашли по суммам и дальше как сделал Дима
это как бы идеальный и выполнимый вариант для школьника

о расчёте вручную, даже с помощью экселя, речь конечно не идёт - у школьника просто нет матаппарата
...
Рейтинг: 0 / 0
30.01.2019, 19:21
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767283
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)mayton,
задача то с подвохом, если впрямую закодить перебор то на расчёт скорее всего никакого времени не хватит

скорее всего требуется найти, то что мы нашли по суммам и дальше как сделал Дима
это как бы идеальный и выполнимый вариант для школьника

о расчёте вручную, даже с помощью экселя, речь конечно не идёт - у школьника просто нет матаппарата
У школьника только бумага и шариковая ручка
...
Рейтинг: 0 / 0
30.01.2019, 19:23
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767284
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy UsovУ школьника только бумага и шариковая ручкатогда бы задача звучала как "найти лишнее - x17" , и всё

а не все варианты
...
Рейтинг: 0 / 0
30.01.2019, 19:25
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767287
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)Gennadiy UsovУ школьника только бумага и шариковая ручкатогда бы задача звучала как "найти лишнее - x17" , и всё

а не все вариантыВ результате 21798189 Я не говорю, что расчеты закончены.

Но уже прогресс:
- нет второго варианта для х1
- количество свободных неизвестных для 12 уравнения сокращено до 2-х.

Я не уверен, что на олимпиаде прокатит появление свободных неизвестных. Скорее всего, надо найти всё.
Может быть есть ещё комбинации уравнений.
...
Рейтинг: 0 / 0
30.01.2019, 19:32
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767289
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy Usov,

смотря какая олимпиада, если по математике то вполне достаточно того что я написал, с бумагой и ручкой больше очень сложно сделать (мы это сделали довольно легко, там только осталось найти способ отклонить неправильный вариант с суммой равной 57)

если по информатике то 21798205

ИМХО, большего за адекватное время требовать от школьника наверное бессмысленно
...
Рейтинг: 0 / 0
30.01.2019, 19:40
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767292
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)Gennadiy Usov,

смотря какая олимпиада, если по математике то вполне достаточно того что я написал, с бумагой и ручкой больше очень сложно сделать (мы это сделали довольно легко, там только осталось найти способ отклонить неправильный вариант с суммой равной 57)

если по информатике то 21798205

ИМХО, большего за адекватное время требовать от школьника наверное бессмысленноТак в сообщении 21798189 неправильный вариант с суммой равной 57 отклонен: нет второго варианта для х1 и х17
Есть только вариант х1=20, х17=10, sum=60
...
Рейтинг: 0 / 0
30.01.2019, 19:46
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767293
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Bingo Quest это вобщем - то приложение для Андроида. Наверное там - семейство таких
головоломок. Но я не ставил пока. В телефоне совсем памяти нехватает для важных
приложений.
...
Рейтинг: 0 / 0
30.01.2019, 19:47
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767294
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy Usov,

ну тогда матвариант как бы всё
...
Рейтинг: 0 / 0
30.01.2019, 19:50
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767296
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)Gennadiy Usov,

ну тогда матвариант как бы всёА кто-нибудь на топике говорил о кругах Эйлера?

Что-то похожее у нас...
Сейчас смотрю в интернете
...
Рейтинг: 0 / 0
30.01.2019, 19:59
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767298
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНифига. Взял Турбо-Паскаль и закодил.

Кстати надо спросить у Димы. Сколько времени заняла реализация. Без перекуров и фейсбука.
Во-первых надо уметь кодить.

Версия 1.0 пара часов, она тут не показана, но результаты ее работы упоминались.

Проработка алгоритма в уме несколько дней в свободное время.

Версия 2.0: час на отладку next_combination() и полчаса на все остальное.
...
Рейтинг: 0 / 0
30.01.2019, 20:02
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767300
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну... вот. Проработка в уме несколько дней. Не укладывается в разумное время для олимпиады.

Моя версия приложения с deep search - где-то так-же. И работает только в теории.
...
Рейтинг: 0 / 0
30.01.2019, 20:04
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767301
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonНу... вот. Проработка в уме несколько дней. Не укладывается в разумное время для олимпиады.

Моя версия приложения с deep search - где-то так-же. И работает только в теории.Кстати, круги Эйлера есть и для 5-го класса
...
Рейтинг: 0 / 0
30.01.2019, 20:10
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767312
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНу... вот. Проработка в уме несколько дней. Не укладывается в разумное время для олимпиады.

Моя версия приложения с deep search - где-то так-же. И работает только в теории.
Тут важно даже не сколько дней, т.к. это можно и за час переосмыслить.
Важно что параллельно подкинули альтернативные идеи 21793586 .
...
Рейтинг: 0 / 0
30.01.2019, 20:56
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767313
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Что до той эврики,так я и начал глядеть на круги: из этих получаем то, из этих - следующее... Потом не хватило пальцев, что бы тыкать и ещё заподозрил неоднозначность, а это уже как-то не очень для школьников. Квадраты думал рисовать, вычеты, но не пошло))
Так что всё у нас пучком.
kealon(Ruslan)ну тогда матвариант как бы всё Не рассматривали собственные числа, но это экзотика.
А кто со знанием лин. алгебры, могут добавить, дойдя до независимых штучек, что теперь, мол, достаточно угадать или найти 1 решение, выписать общее решение однородной системы, и,перебирая его, складывать с первым решением. Вместо подстановки в уравнения.
...
Рейтинг: 0 / 0
30.01.2019, 20:57
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767317
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ребята. Все эти детерминанты. Крамеры. Гауссы Жорданы и Зейдели. Это все не про олимпиаду.

Олимпиада по математике - это другое. Это должно быть как озарение. Как вспышка. Посидел
подумал. И решил.

По информатике - примерно то что написал Дима. Хардкодно. Одной простыней. Но решаемо.
...
Рейтинг: 0 / 0
30.01.2019, 21:11
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767350
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

Хардкодно если это сделано тупым перебором чисто за счёт техники это плохо (эта задача таких обломает и этим она хороша). Но последнии тенденции говорят, что классическая олимпиада уже мало где нужна
...
Рейтинг: 0 / 0
30.01.2019, 23:59
| Ответить | Цитировать | Написать  
25 сообщений из 450, страница 14 из 18
  14  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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