ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
25 сообщений из 450, страница 13 из 18
  13  все
Как решить задачу по комбинаторике?
    #39766778
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
Dima TТС пропал, а мне до сих пор интересно задача по какому предмету была?
Это же фото с какого-то стенда - олимпиадная задача или что-то в таком духе. Вне любого предмета. Хотя вообще - явная математика.
...
Рейтинг: 0 / 0
29.01.2019, 21:49
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766779
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
kealon(Ruslan)окинь взглядом магистр, снизойди до нас, найди их
Суть правильная - переменных должно быть столько же, сколько и уравнений, но так же есть дополнительные критерии типа при определителе равном чему-то там возможны только нулевые решения. Но здесь, я надеюсь, нулевых решений и прочих "эдаких" вывертов быть не должно, иначе сам составитель задачи просто идиот (хотя и не исключено, учитывая перепутанность кругов и диаметров).
Dima TМат.либу надо какую-то, по-любому есть что-нибудь, действия не сложные.
У меня установлена система писючной алгебры, какую систему решить? Но переменных нужно столько же, сколько уравнений.
...
Рейтинг: 0 / 0
29.01.2019, 21:54
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766784
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
alex55555 У меня установлена система писючной алгебры, какую систему решить? Но переменных нужно столько же, сколько уравнений.Добавьте ур-ния типа S=S, т.е. тождества, и будет она квадратная. А проглотит ли прога, уж не знаю ...

А кол-во свободных переменных, я выше напоминал. Определяется рангом системы, а та - линейной зависимостью либо независимостью матричных векторов, а не тем, сколько раз встречается. Это и есть выразимость одних ур-ний через другие, что аналогично афинной замене координат (переменных), т.е. умножению на матрицу преобразования координат.

Кол-во свободных переменных даёт линейное пространство размерностью=рангу. Вот в этом пр-ве мы потом и делаем перебор, если его не сузить дополнительным анализом. У кого 4000, у кого 120 ...
...
Рейтинг: 0 / 0
29.01.2019, 22:32
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766787
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Dima T т.е. две переменные никогда не покроют все уравнения и как следствие через две не выразить все остальные, хотя формально 14 переменных и 12 уравнений.Смогут или нет, определяется линейной зависиомстью либо независ-стью (т.е. от вида ур-ний). Хоть 100500 уравнений.
...
Рейтинг: 0 / 0
29.01.2019, 22:39
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766793
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
exp98Добавьте ур-ния типа S=S, т.е. тождества, и будет она квадратная. А проглотит ли прога, уж не знаю ...
Прога проглотит, но не даст решений. Сокращение бесполезных тождеств она умеет делать, так что способ не для неё. И вообще, рассуждая о линейной алгебре вы предлагаете нечто ей противоречащее, так что не совсем понятно какой вывод о вас нужно сделать.

Хотя не знаю, сможет ли программа, например, предложить один из множества вариантов решений. Раньше встречал ситуацию, когда она вывела формулу для результата, вместо конкретных значений. Не знаю, что там внутри алгоритма, но его сочиняли десятки лет, в смысле система довольно древняя, а потому с ней многие работали и что-то иногда дополняли.
...
Рейтинг: 0 / 0
29.01.2019, 23:36
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766794
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
exp98определяется линейной зависиомстью либо независ-стью
Если в уравнениях используются разные переменные (что актуально для диаметров, например), то линейно выразить Х через операции с У вы вряд ли сможете.
...
Рейтинг: 0 / 0
29.01.2019, 23:38
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766795
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
exp98Хоть 100500 уравнений.
Здесь вообще не место просто воспоминаниям из курса линейной алгебры, здесь надо задачу решить. А про критерии любой прочитает при желании, просто освежить память - не так долго. Важнее - как эти критерии применить к конкретной ситуации.
...
Рейтинг: 0 / 0
29.01.2019, 23:40
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766802
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
exp98Dima T, я не нарочно, сам давно уж понял, что макросом было бы быстрее. Но каково?! реклама - двигатель (эксэла)

Теперь остался пустяк. Задать значения и в уравнениях сделать
=СУММПРОИЗВ(... ; ...)

kealon(Ruslan)в экселе есть формула обратной матрицы а ещё есть умножение матриц, ага
Обратную матрицу можно было получить попутно, (но только для квадратной м-цы) методом сбоку присоединённой единичной. Это тоже из начал лин. алг. Только куда потом её засунуть.
По крайней мере умножением сразу переводим в диагональную.
Ну а на что помножить, то конечно подбором, или преобразованием координат))
не нужно её никуда пихать, нужно просто найти наибольшую часть матрицы с ненулевым определителем (МОПРЕД функция в экселе)
переменные которые будут в неё входить можно принять за базис
остальные принять за независимые

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

Я кажется понял почему невозможно выразить через две переменные. Посмотрите на картинку или на таблицу мою исходную 21796078 , там нет ни одной переменной, которая бы участвовала в половине и более уравнений, т.е. две переменные никогда не покроют все уравнения и как следствие через две не выразить все остальные, хотя формально 14 переменных и 12 уравнений.

В общем нормально что через 3 выразилось, но комбинаций для перебора стало 17*16*15 = 4080. Многовато для экселя, но далеко не 17!
просто ранг матрицы 11, отсда и выходит 3 независимые переменные
...
Рейтинг: 0 / 0
30.01.2019, 00:11
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766807
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
x[1] + a[1] + a[2] +a[3] +  x[8] + x[9] + x[10] + x[11] + x[12] + x[13] + x[14] + x[15] + x[16] +  x[17]= 174
x[1] + a[1] + a[2] +a[3] +  x[8] + x[9] + x[10] + 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 + x[8] + x[9] + x[10] + 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] + x[10] + a[3] + x[8]
sum = x[13] + x[14] + 18 + a[1] + x[9]
(*) sum = x[14] + x[15] + 6 +a[2] + x[10]
sum = x[15] + x[16] + x[11] + a[3] + 18
(*) sum = x[16] + x[12] + x[8] + a[1]  + 6


сложим те что со звёздочкой и заменим x[8] + x[10] -> a[4]

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
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
2sum = x[14] + x[15] + 6 +a[2] + a[4] + x[16] + x[12] + a[1]  + 6


где
Код: plaintext
1.
2.
3.
4.
a[1] = x[2] + x[5]
a[2] = x[3] + x[6]
a[3] = x[4] + x[7]
a[4] = x[8] + x[10]
...
Рейтинг: 0 / 0
30.01.2019, 00:27
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766808
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
x[1] + a[1] + a[2] +a[3] +  x[8] + x[9] + x[10] + x[11] + x[12] + x[13] + x[14] + x[15] + x[16] +  x[17]= 174
x[1] + a[1] + a[2] +a[3] +  x[8] + x[9] + x[10] + 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 + x[8] + x[9] + x[10] + 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] + x[10] + a[3] + x[8]
sum = x[13] + x[14] + 18 + a[1] + x[9]
(*) sum = x[14] + x[15] + 6 +a[2] + x[10]
sum = x[15] + x[16] + x[11] + a[3] + 18
(*) sum = x[16] + x[12] + x[8] + a[1]  + 6


сложим те что со звёздочкой и заменим x[8] + x[10] -> a[4]

ну и собственно наша матрица
...
Рейтинг: 0 / 0
30.01.2019, 00:30
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766809
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
вот файлик
...
Рейтинг: 0 / 0
30.01.2019, 00:31
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766815
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Есть беслатный пакет математики. Octave. В нем можно попробовать решать такие уравнения.
Здесь А - это коэффициенты при иксах. B - правая часть системы соотв.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
octave:4> A = [ 2 3 ; 5 -2 ]
A =

   2   3
   5  -2

octave:5> B = [ 12 ; 11 ]
B =

   12
   11

octave:6> X = inv(A) * B
X =

   3
   2


Это чтоб сейчас не парится с расчетом обратной матрицы на обычных языках программирования.
...
Рейтинг: 0 / 0
30.01.2019, 02:37
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766817
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Если подключать к решению задачки метод Гаусса, то получается интересная вещь.

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

В нашем случае в уравнениях очень мало переменных, и получается что при определении переменных методом Гаусса в уравнениях этих переменных появляется много дополнительных переменных – увеличивается время вычислений, уравнения будут сложными при программировании.

В сообщении 21795764 предлагается определять переменные в лоб, сначала с уравнений, где мало неизвестных, и т.д. Получается:
12 уравнений
3 свободные переменные
9 базисных переменных
(определение х1, х17, sum рассматриваем отдельно).

Если в этом сообщении посмотреть на уравнения проверки, то их будет 3.
Следовательно, если применить метод Гаусса, то по этим 3-м уравнениям получаются тождества.

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

Просто в уравнения вводятся новые неизвестные: х18=6, х19=12, х20=18, х21=sum.

Тогда в матрице будут элементы либо 0 либо 1.

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

это как то далеко от олимпиады для школьников
мы уже применяем методы, которые школьникам недоступны

вот все независимые уравнения (11 штук)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
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


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

если бы у меня стояла такая практическая задача, я бы просто наверное в нелинейный солвер её загнал, помучавшись бы только с дискретными условиями, проходов за 20-30 он бы её раскрутил, а тут фиг знает что делать
...
Рейтинг: 0 / 0
30.01.2019, 09:36
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766872
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima TЕще бы я вспомнил что с ней делать :)
если A * x = b
то
x = A -1 * b
Почитал немного. Обратная матрица существует только для квадратной. Неквадратную приводят к квадратной записью свободных членов одним выражением, например "3*x1 - x8 + x16". Как следствие определитель будет выражением с x1, x8, x16. Эксель такое считать не умеет, считать на бумаге придется.

Вот нашел онлайн калькулятор , быстрее всего в него забить исходные данные.
...
Рейтинг: 0 / 0
30.01.2019, 10:02
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766890
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)вот все независимые уравнения (11 штук)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
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

А почему только 11? На основании матрицы?

И где уравнения для определения неизвестных из этих 11-ти? Сколько выборок (свободных переменных)?
...
Рейтинг: 0 / 0
30.01.2019, 10:36
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766899
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima Tkealon(Ruslan)пропущено...

если A * x = b
то
x = A -1 * b
Почитал немного. Обратная матрица существует только для квадратной. Неквадратную приводят к квадратной записью свободных членов одним выражением, например "3*x1 - x8 + x16". Как следствие определитель будет выражением с x1, x8, x16. Эксель такое считать не умеет, считать на бумаге придется.

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


если хочешь с переменными, то просто для каждого коэфициента произведение обратной матрицы на его множитель посчитай

будет у тебя 4 строчки с коэфициентами для x1, x8, x16 и 1
...
Рейтинг: 0 / 0
30.01.2019, 10:49
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766909
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,
...
Рейтинг: 0 / 0
30.01.2019, 11:01
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766911
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy UsovА почему только 11? На основании матрицы?
если найдёшь определитель квадратика 12*12 отличный от нуля для любой комбинации перестановок столбцов и строк матрицы, значит будет 12, я нашёл только для 11 (в эксельке второй блок это определители)
...
Рейтинг: 0 / 0
30.01.2019, 11:04
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39766912
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy Usov,

ну а вообще проверить можно программкой Димы, закоментировав 2 уравнения
если ответ будет другой, значит я плохо искал
...
Рейтинг: 0 / 0
30.01.2019, 11:07
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767026
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
В центре круга стоит число от 12 до 20, контрольная сумма равняется утроенному значению этого числа.... а дальше я хз как решать :)
...
Рейтинг: 0 / 0
30.01.2019, 14:10
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767057
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
alex55555 Прога проглотит, но не даст решений. Телепатов нет. Тем хуже для самой проги и в особенности для её юзера.
alex55555 так что не совсем понятно какой вывод о вас нужно сделать. К сож. помочь не могу. Могу порекомендовать: сделайте вывод о себе.
...
Рейтинг: 0 / 0
30.01.2019, 14:52
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39767063
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
alex55555exp98определяется линейной зависиомстью либо независ-стью
Если в уравнениях используются разные переменные (что актуально для диаметров, например), то линейно выразить Х через операции с У вы вряд ли сможете.Да я вроде и не собирался, против теорем лин.алгебры - как плевать против ветра.
...
Рейтинг: 0 / 0
30.01.2019, 14:56
| Ответить | Цитировать | Написать  
25 сообщений из 450, страница 13 из 18
  13  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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