IPB

Добро пожаловать, гость ( Вход | Регистрация )

> Новые задачи, не так то просто
pegoopik
20.5.2017, 14:55
Сообщение #1


Новичок
*

Группа: Пользователи Braingames
Сообщений: 42
Регистрация: 10.8.2012
Из: Новосибирск
Пользователь №: 38 696



Предисловие. Я пытаюсь не шлака добавить, а только действительно интересные задачи.

Несколько зим назад я предложил на сайт две задачи на разные темы:

1. Физика, чуть углубляясь в оптику, но с расчетом на эрудицию
2. Теория игр. Три полосы, фишки, выигрышная стратегия и прочее.

По первому вопросу так и не получил ни одного правильного ответа. А по второму так и вовсе получил резолюцию вида:

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

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

Обе задачи имеют красивые решения. И я с огромным удовольствием видел бы их на сайте.

Вот обнаружил ещё одну интересную задачку. Думаю ничего страшного опубликовать её здесь. Задача чисто на оптимизацию алгоритмов. Решения тут писать не надо, можете в личку.

==============================

Формулировка:

Есть множество 2х мерных векторов, найти такое его подмножество, которое даст в сумме вектор максимальной длины.

Задача чисто алгоритмическая и немного геометрическая. Но там такое красивое решение, что я не мог не написать тут.

В лоб решение - это О(2^N), чуть подумав получаем O(N^2), оптимизировав можем получить O(N*Ln(N)), но если перед расчетами отсортировать вектора некоторым образом, получаем O(N).
Всё портит сортировка, т.к. она уже O(N*Ln(N)), но формулировку можно составить по-разному.

==============================


Администраторам ресурса:
Если вы и это забреете, я уж и не знаю, как к вам попадают новые задачи.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Сообщения в этой теме


Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 29.3.2024, 1:51
Яндекс.Метрика