ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
25 сообщений из 450, страница 3 из 18
  3  все
Как решить задачу по комбинаторике?
    #39764600
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Надо жирым маркером навести круги. Мне тоже сначала неочевидно было.
...
Рейтинг: 0 / 0
24.01.2019, 18:25
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764602
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Dima TСмотри внимательнее и учти что фото немного под наклоном, поэтому круги немного овальные. Направляющие линии видно, 6 кругов по 6, не считая 3-х вокруг центра. Да уж как только не смотрел.
Вокруг центра - ясно. Если пронумеровать точки слева направо, сверху вниз - какие номера образуют 6 оставшихся кругов (хотя бы один из них чтобы логику понять)?
...
Рейтинг: 0 / 0
24.01.2019, 18:33
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764617
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Все, узрел.
...
Рейтинг: 0 / 0
24.01.2019, 19:01
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764635
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TСоколинский БорисКто мне может пояснить - где авторы задания предполагают наличие 9 окружностей?
Я вижу только три (ну и еще одно без кружков)
Смотри внимательнее и учти что фото немного под наклоном, поэтому круги немного овальные. Направляющие линии видно, 6 кругов по 6, не считая 3-х вокруг центра.А в этих 6 кругах есть центральный кружочек?
...
Рейтинг: 0 / 0
24.01.2019, 19:54
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764636
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Сумма = 69, в центре - 13, нет 3.
...
Рейтинг: 0 / 0
24.01.2019, 19:55
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764637
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Dima TЕму там 17! предложили перебрать Используйте способ, к-рый я предлагал, когда перестановки с ограничениями.
Чтобы не корячить бэктрекинг с нуля, используем стандартный
next_permutation(), а его оборачиваем в ступенчатую послед-сть предварительных циклов FOR(). Назовём это Каскадированным полубэктрекингом.

Направление с наружи - во внутрь:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
2-ной цикл for() {
  CheckPermutation();
  4-ной for() {
    CheckPermutation();
    8-ной for()
       CheckPermutation();
       сколько осталось for() {
           СклеитьВсеЧасти();
           next_permutation();
           CheckPermutation();
           fprintf();
       }
    }
  }
}
end.
...
Рейтинг: 0 / 0
24.01.2019, 20:00
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764638
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Соколинский БорисСумма = 69, в центре - 13, нет 3.
Почему? Выше двумя разными путями пришли к тому что Сумма 57 или 60. В центре 19 или 20. Нет 10 или 20.
...
Рейтинг: 0 / 0
24.01.2019, 20:03
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764642
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Dima TСоколинский БорисСумма = 69, в центре - 13, нет 3.
Почему? Выше двумя разными путями пришли к тому что Сумма 57 или 60. В центре 19 или 20. Нет 10 или 20. Я ошибся, пардон.
Лень латех вставлять, надеюсь и так будет понятно.

1. Суммируем числа по диагоналям и вычитаем внешнюю и внутреннюю окружность.
Получаем 3С=S, где С - число в центре. Замечаем, что сумма должна быть кратна 3.

2. Суммируем все эксцентричные окружности (6S). Добавляем удвоенное центральное и удвоенное отсутствующее - получаем удвоенную сумму всех чисел от 1 до 20
6S+2C+2X=420 или
3S+C+X=210.
Подставляя С=S/3 (1) получаем

X=210-10/3*S=10*(21-S/3).
Т.е отсутствует либо 10, либо 20.
Если отсутствует 10, то S=63 и первое условие не выполняется.
Значит нет 20, в центре 19, сумма=57.
...
Рейтинг: 0 / 0
24.01.2019, 20:30
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764644
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Соколинский БорисЕсли отсутствует 10, то S=63 и первое условие не выполняется.
Откуда 63? S=3С=60. Условие выполняется.
...
Рейтинг: 0 / 0
24.01.2019, 20:35
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764645
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima Tkealon(Ruslan)mayton,
а неизвестных 18Нет, 17.Странно...

У нас известны 5 чисел (2 варианта) и неизвестны 15 чисел.
Следовательно, должно быть 15 неизвестных.
...
Рейтинг: 0 / 0
24.01.2019, 20:38
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764646
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Dima TСоколинский БорисЕсли отсутствует 10, то S=63 и первое условие не выполняется.
Откуда 63? S=3С=60. Условие выполняется. Блин, точно.
...
Рейтинг: 0 / 0
24.01.2019, 20:40
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764648
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy UsovСкорее тут будет метод поиска с возвратом:
ищем, суммируем, подходит или не подходит, если нет, то возвращаемся...Я не про это. Я знаю как решать эту задачу.
Я не знаю как описать входные данные красиво.

Представте что завтра граф будет другой. С большим числом вершин и другими условиями.
Сколько кода вам надо будет сломать?Красиво - это когда на все случаи (либо на несколько случаев).

А у нас могут быть разные круги, разные диагонали (многие красиво разрисовывают новые задачки),
в разных точках известные числа...

А здесь задачу надо решать (если решать) как она есть, в лоб.
...
Рейтинг: 0 / 0
24.01.2019, 20:44
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764649
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovDima Tпропущено...
Нет, 17.Странно...

У нас известны 5 чисел (2 варианта) и неизвестны 15 чисел.
Следовательно, должно быть 15 неизвестных.
Известно 3 из 20. Из оставшихся 17 надо 16 вписать и одно лишнее.
То что 2 из неизвестных ограничены 2-мя вариантами не делает их известными.
...
Рейтинг: 0 / 0
24.01.2019, 20:47
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764651
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima Tkealon(Ruslan)mayton,

а неизвестных 18
Нет, 17.
13 уравнений: 9 кругов, 3 диагонали, 1 уравнение баланса
18 неизвестных: x1..x17 и S

то что мы нашли "частными измышлениями" это тоже неизвестные
...
Рейтинг: 0 / 0
24.01.2019, 20:50
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764652
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А с какой вершины начать backtracking?
...
Рейтинг: 0 / 0
24.01.2019, 20:56
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764653
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

да по сути без разницы, но можно начать с той у которой уже есть варианты
...
Рейтинг: 0 / 0
24.01.2019, 21:00
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764654
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Алгоритм решения найден, дальше неинтересно. Пусть ТС дорешает.

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

PS Кто не в теме 20! это 20 лет перебора при проверке одного набора за один такт проца 4 ГГц.
...
Рейтинг: 0 / 0
24.01.2019, 21:03
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764656
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

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

да по сути без разницы, но можно начать с той у которой уже есть вариантыЗабыли:

там где "Двадцатое лишнее" надо добавить "х17"
...
Рейтинг: 0 / 0
24.01.2019, 21:06
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764659
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy Usov,

пардонс
...
Рейтинг: 0 / 0
24.01.2019, 21:08
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764660
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
...
Рейтинг: 0 / 0
24.01.2019, 21:08
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764661
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TАлгоритм решения найден, дальше неинтересно. Пусть ТС дорешает.

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

PS Кто не в теме 20! это 20 лет перебора при проверке одного набора за один такт проца 4 ГГц.В соообщении 21793555 указывается последовательность действий при решении в лоб.

Не думаю, что здесь будет 20! Будет значительно меньше.
...
Рейтинг: 0 / 0
24.01.2019, 21:09
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764665
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TАлгоритм решения найден, дальше неинтересно. Пусть ТС дорешает.

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

PS Кто не в теме 20! это 20 лет перебора при проверке одного набора за один такт проца 4 ГГц.
Этот мозг знал что перебором эту задачу никто не решит. Но если мы вспомним что бектрекинг
не даёт нам дойти до заведомо фейловой ветки дерева то эта оценка очень резко уменьшается.
...
Рейтинг: 0 / 0
24.01.2019, 21:16
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764668
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Консультанты toster.ru так ничего нового и не выдали.
...
Рейтинг: 0 / 0
24.01.2019, 21:22
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39764678
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Gennadiy UsovНе думаю, что здесь будет 20! Будет значительно меньше.Ну вот расскажите как здесь использовать, что "есть предел насыщения", кроме как помнить об этом? Начальную расстановку из 3-х штук уже имеем.
...
Рейтинг: 0 / 0
24.01.2019, 21:56
| Ответить | Цитировать | Написать  
25 сообщений из 450, страница 3 из 18
  3  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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