Загадки и головоломки(и шуточные:))

[topol-m]

Ага, всё же хищный кит :lol:

 

:no_sad: "A common reason for the use of "orca" in favor of "killer whale" is the fact that orcas are not whales, but rather are related to dolphins." Википедия

[depilot]

Касатка?

 

Подлодка что-ли?

[Starwalker]

Я теперь попробую :)

Что за рыба? Тополь-м - в курсе, нет?

[Storm]

Групер

[Starwalker]

Нет

[Dutch]

:no_sad: "A common reason for the use of "orca" in favor of "killer whale" is the fact that orcas are not whales, but rather are related to dolphins." Википедия

Вообще то мой пост про кита был шуточным :smilewink:

[Geen]

Карась обыкновенный :)

[Storm]

Нет

Уверены?:)

[Alone]

Латимерия?

[hawk1]

окунь морской

[JGr124_MUTbKA]

Я теперь попробую :)

Что за рыба? Тополь-м - в курсе, нет?

Это глубоководная хищная хрень, забыл, как ее зовут. :)

[Namenlos Ein]

Не она ли, часом? Пардон за самоцитату.

Вот, украинцы в Африке тоже неплохо порыбачили.

 

 

И, так, для разнообразия. Для чего этому лётчику голуби?

 

Edited December 11, 2009 by Namenlos Ein

[FVMAD]

И, так, для разнообразия. Для чего этому лётчику голуби?

 

 

Это птички для "опускания" красных :D которые теперь будут летать в ГС2 :)

[topol-m]

 

И, так, для разнообразия. Для чего этому лётчику голуби?

 

Для указания декомпрессии в кабине?

[Dutch]

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

[hawk1]

И, так, для разнообразия. Для чего этому лётчику голуби?

 

 

Чтоб определять направление до суши в море, если упадешь. Куда птиц полетел - там суша. Если начал кругами летать - лучше сразу утопиться. :)

[Starwalker]

Карась обыкновенный :)

Нет.

[Starwalker]

Уверены?:)

Уверен.

[Starwalker]

Латимерия?

окунь морской

Нет

[Starwalker]

Это глубоководная хищная хрень, забыл, как ее зовут. :)

Глубоководная. Хищная. Не современная.

[Starwalker]

Namenlos Ein Нет

[Namenlos Ein]

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

Правильно.

http://forum.pigeonbasics.com/m-1254163972/

All RAF bombers and reconnaissance aircraft carried pigeons and, if the aircraft had to ditch, the plane’s co-ordinates were sent back with the pigeon to its RAF base and a search and rescue operation was effected. Thousands of servicemen’s lives were saved by these heroic birds that flew often in extreme circumstances.

 

During World War II homing pigeons were seconded into the National Pigeon Service from Britain’s fanciers including one from the Royal Lofts. In fact one pigeon, Royal Blue, was the first pigeon to bring a message from a force-landed aircraft on the continent. On the 10th October 1940 this young bird was released in Holland. He flew 120 miles in 4 hours 10 minutes reporting the information regarding the situation of the crew. After the war, the Dickin Medal was instituted. Commonly known as the Animal VC, it was awarded to 53 animals including 32 homing pigeons including Royal Blue.

32 почтовых голубя входят в число 53 животных (32 голубя, 18 собак, 3 лошади и один кот по кличке Саймон), которые были награждены специальной медалью Марии Дикин — высшей воинской наградой Великобритании для животных.

[Geen]

Даны два отсортированных массива a(n) и b(m) длин n и m соответственно (считаем, что n<=m).

Назовём выравниванием строго монотонный массив j длины n индексов массива b (т.е. чисел от 1 до m) - этот массив задаёт соответствие каждому элементу из a какого-то элемента из b (причём, любой элемент из b не может соответствовать более чем одному элементу из a).

Назовём погрешностью выравнивания min( sum( (a(i)-b(j(i))+d)^2, i=1..n ) ) (минимум берётся по d; для d очевидна формула 1/n*sum(b(j(i))-a(i),i=1..n)).

Нужен эффективный алгоритм нахождения оптимального (с минимальной погрешностью) выравнивания.

 

P.S. Решения у меня нет (а надо), а я что-то туплю, толи после праздников, толи по жизни :)

[DarkWanderer]

Целевая функция второго порядка, так что больше одного локального минимума быть не должно. Соответственно, ЕМНИП, задача решается "алгоритмом амебы" за полиномиальное время.

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

Принцип:

Цикл по индексу 1<=k<=m

Цикл по индексу 1<=i<=n

- Если для b(k) уже задано соответствие:

-- проверить, что [b(k)-a(соотв.k)]^2+[b(j(i))-a(i)]^2<[b(k)-a(i)]^2+[b(j(i))-a(соотв.k)]^2. Если нет - поменять местами индексы прямого и обратного соответствия для k и j(i). Обращаем внимание, что при такой замене d не меняется, т.е. его опускание закономерно.

- Если для b(k) не задано соответствие

-- проверить, что [b(j(i))-a(i)]^2<[b(k)-a(i)]^2. Если нет - заменить j(i) на k. Здесь нужно будет доказать, что такая замена уменьшит целевую функцию - относительно просто.

Соответственно, если замена произведена - сделать еще один цикл. Если нет - закончить, улучшить больше ничего не получится.

Анализ такого алгоритма, правда, будет непростым, но что-то мне подсказывает, что максимальная сложность будет O(n*m^2).

Хватит для решения?..

Edited January 9, 2010 by DarkWanderer

[Geen]

Целевая функция второго порядка, так что больше одного локального минимума быть не должно. Соответственно, ЕМНИП, задача решается "алгоритмом амебы" за полиномиальное время.

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

Принцип:

Цикл по индексу 1<=k<=m

Цикл по индексу 1<=i<=n

- Если для b(k) уже задано соответствие:

-- проверить, что [b(k)-a(соотв.k)]^2+[b(j(i))-a(i)]^2<[b(k)-a(i)]^2+[b(j(i))-a(соотв.k)]^2. Если нет - поменять местами индексы прямого и обратного соответствия для k и j(i). Обращаем внимание, что при такой замене d не меняется, т.е. его опускание закономерно.

- Если для b(k) не задано соответствие

-- проверить, что [b(j(i))-a(i)]^2<[b(k)-a(i)]^2. Если нет - заменить j(i) на k. Здесь нужно будет доказать, что такая замена уменьшит целевую функцию - относительно просто.

Соответственно, если замена произведена - сделать еще один цикл. Если нет - закончить, улучшить больше ничего не получится.

Анализ такого алгоритма, правда, будет непростым, но что-то мне подсказывает, что максимальная сложность будет O(n*m^2).

Хватит для решения?..

Вероятно, я продолжаю тупить :)

 

В смысле "второго порядка"? Второго порядка относительно какой переменной? А если на мн-ве всех выборок из m по n, то с какой структурой?

 

Какой смысл может быть в первой операции, если у нас массивы изначально отсортированы (или могут быть отсортированы на входе)?

 

Вторая операция не учитывает сдвиг массивов (d) - разве это нормально?

 

В целом. Либо я всё-таки не понял алгоритм, либо он не работает, например, на массивах [1,2,3] и [1,2,6,7,8].

 

На всякий случай табличка погрешностей выравниваний:

1 2 6 6

1 2 7 10.667

1 2 8 16.667

1 6 7 10.667

1 6 8 14

1 7 8 16.667

2 6 7 6

2 6 8 8.6667

2 7 8 10.667

6 7 8 0