Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 15 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Al Zimmermann's Programming Contests
СообщениеДобавлено: 14 окт 2017, 21:54 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
24 ноя 2016, 21:32
Сообщений: 1066
Откуда: Махачкала
Cпасибо сказано: 68
Спасибо получено:
190 раз в 177 сообщениях
Очков репутации: 34

Добавить очки репутацииУменьшить очки репутации
Оказывается стартовал http://azspcs.com/Contest/PrimorialSoup.
Интересная задача на расставление простых чисел по ребрам полного графа.
Думаю никто меня не обвинит, если приведу оптимальный вариант для [math]n=4[/math]
[math]\{11,3,7\},\{11,5,2\},\{3,5,13\},\{7,2,13\}.[/math]
Энергия графа при этом [math]718.[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 14 окт 2017, 22:12 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
А что делать-то надо? И как взаимосвязаны энергия графа и расставленные простые числа, в чем оптимальность?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 14 окт 2017, 22:20 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
24 ноя 2016, 21:32
Сообщений: 1066
Откуда: Махачкала
Cпасибо сказано: 68
Спасибо получено:
190 раз в 177 сообщениях
Очков репутации: 34

Добавить очки репутацииУменьшить очки репутации
ivashenko
По ссылке вроде все ясно.
Расставить простые числа в качестве весов для ребер полного графа (т.е. все ребра соединены с друг другом).
При этом надо добиться минимума "энергии графа".
Энергия графа вычисляется как сумма энергий узлов, а энергия узлов это произведение весов всех смежных с узлом ребер.
Если у нас [math]n[/math] узлов, очевидно, что ребер [math]\frac{n(n-1)}{2}[/math] и надо расставить столько же первых простых чисел.
В наборе указанном выше выписаны веса ребер смежных к четырем узлам [math]n=4[/math].
Изображение
Вес в этом не оптимальном примере [math]2 \cdot 3\cdot 7+2\cdot 5\cdot 11+3\cdot 5\cdot 13+7\cdot 11\cdot 13=1348.[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Student Studentovich "Спасибо" сказали:
ivashenko
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 14 окт 2017, 22:59 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Student Studentovich писал(а):
По ссылке вроде все ясно.

Я с english не особо лажу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 14 окт 2017, 23:01 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Ну так это задача на оптимизацию, которая похоже решается перебором или здесь есть закономерности?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 14 окт 2017, 23:33 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
24 ноя 2016, 21:32
Сообщений: 1066
Откуда: Махачкала
Cпасибо сказано: 68
Спасибо получено:
190 раз в 177 сообщениях
Очков репутации: 34

Добавить очки репутацииУменьшить очки репутации
Перебором вы максимум решите только для [math]n=4;5;6[/math] ну черт с ним [math]7[/math]. А в задаче [math]n=4..25.[/math]
Если граф представить в виде матрицы смежности то перестановок будет [math]\frac12 n(n-1)![/math].
Это много.
А закономерности искать надо. Хотя они не всегда будут приводить к оптимальному варианту.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 15 окт 2017, 01:45 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Student Studentovich писал(а):
А закономерности искать надо.


А если их нет?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 15 окт 2017, 07:04 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Student Studentovich писал(а):
Если граф представить в виде матрицы смежности то перестановок будет [math]\frac12 n(n-1)![/math].

Вот-вот, надо работать с матрицами и забыть вообще про графы :)
Был уже подобный конкурс с графами у Al. Но быстро все поняли, что ни к чёрту графы не нужны в задаче, а всё сводится к линейкам. Я в том конкурсе участвовала. Там было интересно - вновинку была задача. Я там искала симметричные графы (по линейкам). Ко мне присоединился один конкурсант из США - по поиску симметричных решений. Мы с ним классно поработали.

А в данной задаче всё сводится к матрицам.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 15 окт 2017, 07:32 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Вот он - тот конкурс с графами, о котором я сказала выше
http://azspcs.com/Contest/GracefulGraphs

Посмотрите таблицу результатов в этом конкурсе
http://azspcs.com/Contest/GracefulGraphs/Standings

Больше половины таблицы - 25 баллов :)
Быстренько нашли в Сети эти самые линейки - готовый алгоритм! Применили его и... задача полностью решена.
Я там на 80-й позиции. После того, как задачу решила, начала заниматься поиском симметричных решений. Это было интересно!

Может быть, и в теперешнем конкурсе есть нечто подобное.
Во всяком случае, Ярослав Врублевский уже в первые дни конкурса набрал много баллов, первым был.
Значит, алгоритм хороший есть!

Тема на форуме dxdy.ru о текущем конкурсе
http://dxdy.ru/topic121133.html

В этой теме читаем:

Цитата:
На самом деле алгоритм решения данного конкурса чрезвычайно прост: я думаю, что к концу конкурса верх будет заполнен одними 25-ками. Если же этого не случится, то сразу по окончании конкурса я опубликую этот алгоритм, а точнее, мгновенно и в любом случае, чтобы мое утверждение не считали голословным (ответ заготовлю заранее).

Правда, потом форумчанин написал, что погорячился.
Но хороший алгоритм, как я уже написала выше, есть. И не исключено, что его раскопают и 25 баллов посыпятся :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Nataly-Mak "Спасибо" сказали:
Student Studentovich
 Заголовок сообщения: Re: Al Zimmermann's Programming Contests
СообщениеДобавлено: 15 окт 2017, 19:44 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
24 ноя 2016, 21:32
Сообщений: 1066
Откуда: Махачкала
Cпасибо сказано: 68
Спасибо получено:
190 раз в 177 сообщениях
Очков репутации: 34

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Спасибо за ссылочки.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 15 ]

Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved