ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
25 сообщений из 450, страница 8 из 18
  8  все
Как решить задачу по комбинаторике?
    #39765514
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВ актуальной ревизии

https://github.com/Dmitriy-GH/remove20th/blob/master/remove20th.cpp

Я-бы ввел некую сущность под названием Graph
Код: plaintext
1.
struct Graph {...}


и передавал бы ее в функции-предикаты.
Например. Вместо.

Код: plaintext
1.
if (sum == 12 + *x2 + *x1 + *x5 + *x15 // Горизонтальный


Ввел-бы
Код: plaintext
1.
2.
3.
if (isHorizontalGraphBalanced(graph)) {
...
}


Предикаты соотв. проверяют подграфы на сбалансированность по весу.

Но я не настаиваю. А то со стороны выглядит будто я заставляю тебя подгонять код под Callgrind.

Я в принципе всегда стараюсь писать код максимально разбитым на элементарные фунции.
Единственный кейс когда я этого не делал - в карточном трассировщике - просто для сохранения
оригинального подобия к исходнику Гекберта.
на обощенный Graph это не тянет, т.к. речь о вполне конкретной фигуре и даже твой isHorizontalGraphBalanced() это тоже о конкретной фигуре.

Твоя идея посчитать количество вызов каждого sum == ... в корне неверная. Вызов std::next_permutation() или next_combination() намного тяжелее чем это.
...
Рейтинг: 0 / 0
27.01.2019, 16:41
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765515
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonНапример. Вместо.

Код: plaintext
1.
if (sum == 12 + *x2 + *x1 + *x5 + *x15 // Горизонтальный


....
А почему сразу не посчитать
Код: plaintext
1.
*x15 = sum12 - 12 -*x2 - *x1 - *x5

и сравнить с массивом?
...
Рейтинг: 0 / 0
27.01.2019, 16:41
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765517
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вы не поймете. Выж математик.
...
Рейтинг: 0 / 0
27.01.2019, 16:44
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765518
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovА как же красота алгоритма?
 
Самый красивый алгоритм - не оптимизированный
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
void start() {
	int x[18] = { 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20 };
	do {
		int sum = 12 + x[12] + x[13] + x[14] + x[15] + x[16]; // Внешний круг
		if (sum == 18 + 6 + x[8] + x[9] + x[10] + x[11] // Средний круг
			&& sum == x[2] + x[3] + x[4] + x[5] + x[6] + x[7] // Внутренний круг
			&& sum == 12 + x[2] + x[1] + x[5] + x[15] // Диаметр горизонтальный
			&& sum == x[14] + x[4] + x[1] + x[7] + x[12] // Диаметр cлева направо
			&& sum == x[13] + x[3] + x[1] + x[6] + x[16] // Диаметр cправа налево
			// Шесть кругов
			&& sum == 12 + x[9] + x[3] + x[6] + x[11] + x[12]
			&& sum == 12 + x[13] + x[10] + x[4] + x[7] + x[8]
			&& sum == x[13] + x[14] + 18 + x[5] + x[2] + x[9]
			&& sum == x[14] + x[15] + 6 + x[6] + x[3] + x[10]
			&& sum == x[15] + x[16] + x[11] + x[7] + x[4] + 18
			&& sum == x[16] + x[12] + x[8] + x[2] + x[5] + 6
			) {
			count++;
			printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n", x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17]);
		}
	} while (std::next_permutation(x+1, x + 18));
}



Под спойлером рабочий код, все предельно понятно, но считать будет несколько недель.
...
Рейтинг: 0 / 0
27.01.2019, 16:57
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765520
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TТвоя идея посчитать количество вызов каждого sum == ... в корне неверная. Вызов std::next_permutation() или next_combination() намного тяжелее чем это.
Давай избавимся от permutation.
...
Рейтинг: 0 / 0
27.01.2019, 17:29
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765521
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И у нас в воздухе провис вопрос о количестве решений. Или их 16. Или их больше.
...
Рейтинг: 0 / 0
27.01.2019, 17:32
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765523
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima TТвоя идея посчитать количество вызов каждого sum == ... в корне неверная. Вызов std::next_permutation() или next_combination() намного тяжелее чем это.
Давай избавимся от permutation.
Как? Это оптимальная реализация, моя переделка в циклы заметно тормознее получилась.

Загугли " размещения алгоритм ", везде аналогичный подход.
...
Рейтинг: 0 / 0
27.01.2019, 17:49
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765524
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonИ у нас в воздухе провис вопрос о количестве решений. Или их 16. Или их больше.
Ровно 16, иначе можно утверждать что задача не решена, т.к. исключить можно только одно число.
...
Рейтинг: 0 / 0
27.01.2019, 17:50
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765527
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonИ у нас в воздухе провис вопрос о количестве решений. Или их 16. Или их больше.В сообщении 21795098 показано, что количество решений задачки кратно 8.
...
Рейтинг: 0 / 0
27.01.2019, 18:11
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765529
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonИ у нас в воздухе провис вопрос о количестве решений. Или их 16. Или их больше.В сообщении 21795098 показано, что количество решений задачки кратно 8.
Может быть 24 ?
...
Рейтинг: 0 / 0
27.01.2019, 18:16
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765531
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy UsovВ сообщении 21795098 показано, что количество решений задачки кратно 8.
Может быть 24 ?Всё возможно.

Хотя Dima T уже всё посчитал.
...
Рейтинг: 0 / 0
27.01.2019, 18:26
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765535
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Проверим.
...
Рейтинг: 0 / 0
27.01.2019, 18:46
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765576
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
maytonГлупый codeblocks. Где в нём рефакторинг? Где extract procedure...
Установил Clion. Рефакторит получше. Хотя я сделал авто-форматирование последней версии сорца.
Получилась такая некислая лесенка....
...
Рейтинг: 0 / 0
27.01.2019, 20:19
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765592
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Дима а прокомментируй плиз зачем тут так много сорцов. Какой из них - актуален?

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
$ ls -lF
total 92
-rwxr-xr-x 1 mayton mayton    67  27 19:26 make.sh*
-rw-r--r-- 1 mayton mayton  5442  27 20:03 remove20th.cpp
-rw-r--r-- 1 mayton mayton  2701  27 20:03 remove20th_nooptimize.cpp
-rw-r--r-- 1 mayton mayton  1433  27 19:26 remove20th.sln
-rw-r--r-- 1 mayton mayton  6599  27 20:03 remove20th_trash.cpp
-rw-r--r-- 1 mayton mayton  7863  27 19:26 remove20th.vcxproj
-rw-r--r-- 1 mayton mayton 55370  27 19:26 задание.jpg
...
Рейтинг: 0 / 0
27.01.2019, 21:09
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765641
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Здесь говорили, но не стали реализовывать 2-й вариант, через систему ур-й. Кратко озвучиваю это. Ибо вопрос темы звучит "как решить задачу".
Я поздно присоединился, но в итоге результат не получился, хотя и перепроверял несколько раз. По этому случаю только краткую схему на тему насколько легко это можно сделать в экселе (систему саму получить, а потом по свободным переменным получать решения).

В общем, нарисовал на листке неоднородную систему наших 12 линейных ур-ний с 15-ю переменными. Поскольку из предварительного анализа X1= одно из 2-х значений, то их вынес в параметры алгоритма, ну т.е. приравнял тоже к константе. Если надо, запускаем два раза и все дела. Эти шаги нетрудно запрограммировать.

Значит, таблицу к-тов заносим в матрицу 12х15,
приводим к "диагональному" виду.
Получилось как на вложенном рисунке (справа там ещё есть преобразованный константный вектор (S-Y-X1-18-12-6)).
Почему-то свободных переменных осталось 5.
Далее 2 варианта действий.
1) полный перебор A(5,15)=360360, вопрос фигнядля программы.
2) воспользоваться эвристиками и сузить перебор. Я воспользовался, остались 54 варианта, но увы ...

Прогу диагонализации писать неохота, ибо в прошлом такое на бумаге делал мильоны раз. Но сделать это легче всего в VBA. Просто привожу свой полуручной неправильный, видимо, вариант.
...
Рейтинг: 0 / 0
28.01.2019, 01:54
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765642
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Уточню. Исходный константный вектор без Y-лишнее: (S-X1-18-12-6), X1 - центр, S - сумма каждого пути. Вектор тоже преобразуется по мере диагонализации. Просто для радиальныхх ур-й X1 изначально присутствует, а для остальных вместо него 0. Аналогично и с остальными константами.
...
Рейтинг: 0 / 0
28.01.2019, 02:03
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765644
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я рисовал граф. Но граф не особо нужен так как топология слабо учитывается.
Тут скорее важно учесть реляционное отображение вершин на подграфы и контролировать
частичные суммы. Тоесть помаркировал вершину (Vertex) числом - и синхронно добавил
это число к суммам всех связных подграфов.


Видя что граф - игрушка а не необходимость я - охладел. Чуть позже возможно я выкачу
своё решение. Но я не люблю репризы. И никогда не копирую чужие сорцы просто так.
Нужна оригинальная идея. Иначе выходить на сцену бесполезно.
...
Рейтинг: 0 / 0
28.01.2019, 02:11
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765656
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима а прокомментируй плиз зачем тут так много сорцов. Какой из них - актуален?

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
$ ls -lF
total 92
-rwxr-xr-x 1 mayton mayton    67  27 19:26 make.sh*
-rw-r--r-- 1 mayton mayton  5442  27 20:03 remove20th.cpp
-rw-r--r-- 1 mayton mayton  2701  27 20:03 remove20th_nooptimize.cpp
-rw-r--r-- 1 mayton mayton  1433  27 19:26 remove20th.sln
-rw-r--r-- 1 mayton mayton  6599  27 20:03 remove20th_trash.cpp
-rw-r--r-- 1 mayton mayton  7863  27 19:26 remove20th.vcxproj
-rw-r--r-- 1 mayton mayton 55370  27 19:26 задание.jpg


remove20th.cpp основной
remove20th_nooptimize.cpp перебор 2*15! комбинаций
remove20th_trash.cpp без вызовов std::next_permutation() и next_combination() тебе для профилирования
удалил последние два
...
Рейтинг: 0 / 0
28.01.2019, 07:25
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765658
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Если кому система уравнений нужна, то вот она
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
sum = 12 + x[12] + x[13] + x[14] + x[15] + x[16]; // Внешний круг
sum = 18 + 6 + x[8] + x[9] + x[10] + x[11] // Средний круг
sum = x[2] + x[3] + x[4] + x[5] + x[6] + x[7] // Внутренний круг
sum = 12 + x[2] + x[1] + x[5] + x[15] // Диаметр горизонтальный
sum = x[14] + x[4] + x[1] + x[7] + x[12] // Диаметр cлева направо
sum = x[13] + x[3] + x[1] + x[6] + x[16] // Диаметр cправа налево
// Шесть кругов
sum = 12 + x[9] + x[3] + x[6] + x[11] + x[12]
sum = 12 + x[13] + x[10] + x[4] + x[7] + x[8]
sum = x[13] + x[14] + 18 + x[5] + x[2] + x[9]
sum = x[14] + x[15] + 6 + x[6] + x[3] + x[10]
sum = x[15] + x[16] + x[11] + x[7] + x[4] + 18
sum = x[16] + x[12] + x[8] + x[2] + x[5] + 6


Также доказано что
Код: plaintext
1.
2.
3.
sum = x[1] * 3
x[1] = 19 или 20
x[17] = 20 или 10
...
Рейтинг: 0 / 0
28.01.2019, 07:33
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765659
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Если поможет:

Код: plaintext
1.
x[16] =  20 - x[14]
...
Рейтинг: 0 / 0
28.01.2019, 07:56
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765670
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima T,

можно упростить систему уравнений. если ввести переменные а1,а2,а3:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
sum = 12 + x[12] + x[13] + x[14] + x[15] + x[16]; // Внешний круг
sum = 18 + 6 + x[8] + x[9] + x[10] + x[11] // Средний круг
sum = а[1] + а[2] + а[3]  // Внутренний круг
sum = 12 + x[2] + x[1] + x[5] + x[15] // Диаметр горизонтальный
sum = x[14] + x[4] + x[1] + x[7] + x[12] // Диаметр cлева направо
sum = x[13] + x[3] + x[1] + x[6] + x[16] // Диаметр cправа налево
// Шесть кругов
sum = 12 + x[9] + а[2] + x[11] + x[12]
sum = 12 + x[13] + x[10] + а[3] + x[8]
sum = x[13] + x[14] + 18 + а[1] + x[9]
sum = x[14] + x[15] + 6 + а[2]  + x[10]
sum = x[15] + x[16] + x[11] + а[3]  + 18
sum = x[16] + x[12] + x[8] + а[1]  + 6


То есть, получается 12 уравнений и 12 неизвестных
[/quot]
...
Рейтинг: 0 / 0
28.01.2019, 09:03
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765671
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima T,
вот теперь верно:

можно упростить систему уравнений. если ввести переменные а1,а2,а3:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
sum = 12 + x[12] + x[13] + x[14] + x[15] + x[16]; // Внешний круг
sum = 18 + 6 + x[8] + x[9] + x[10] + x[11] // Средний круг
sum = а[1] + а[2] + а[3]  // Внутренний круг
sum = 12 +  x[1] + а[1] + x[15] // Диаметр горизонтальный
sum = x[14] + x[1] + а[3] + x[12] // Диаметр cлева направо
sum = x[13] + x[1] + а[2] + x[16] // Диаметр cправа налево
// Шесть кругов
sum = 12 + x[9] + а[2] + x[11] + x[12]
sum = 12 + x[13] + x[10] + а[3] + x[8]
sum = x[13] + x[14] + 18 + а[1] + x[9]
sum = x[14] + x[15] + 6 + а[2]  + x[10]
sum = x[15] + x[16] + x[11] + а[3]  + 18
sum = x[16] + x[12] + x[8] + а[1]  + 6


То есть, получается 12 уравнений и 12 неизвестных
[/quot]
...
Рейтинг: 0 / 0
28.01.2019, 09:07
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765676
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще не помешает указать что
Код: plaintext
1.
2.
3.
a[1] = x[2] + x[5]
a[2] = x[3] + x[6]
a[3] = x[4] + x[7]


Еще вместо sum написать 3*x[1] и можно решать.
...
Рейтинг: 0 / 0
28.01.2019, 09:30
| Ответить | Цитировать | Написать  
Как решить задачу по комбинаторике?
    #39765740
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
На самом деле, 12 уравнений и 12 неизвестных – это не совсем точная информация.

Часть из этих уравнений использовалась для определения sum и x[1] 21793339 . Так что, если строго, была использована ещё одна выборка по sum и часть уравнений для определения x[1].

Следовательно, этих 12 уравнений не достаточно для определения 12 неизвестных.

Поэтому, необходимо эти 12 уравнений преобразовать в определения n неизвестных при наличии выборки m чисел.
n + m + 3 = 15.

Часть уравнений из 12 не дадут новой информации, а будут использоваться для проверки найденных чисел.

Тогда можно будет точно сказать, сколько необходимо выборок.Dima TЕще не помешает указать что
Код: plaintext
1.
2.
3.
a[1] = x[2] + x[5]
a[2] = x[3] + x[6]
a[3] = x[4] + x[7]


Еще вместо sum написать 3*x[1] и можно решать.Данные уравнения можно дописать к 12 уравнениям. но они пока не нужны.

Их можно будет использовать после определения а1, а2, а3.

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

уравнение баланса забыл
x1 + x2 + ...x7 = ...
...
Рейтинг: 0 / 0
28.01.2019, 12:09
| Ответить | Цитировать | Написать  
25 сообщений из 450, страница 8 из 18
  8  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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