Поделитесь красивыми/неожиданными решениями с виду сложных задач?

← →
Vlad Oshin © (2008-08-27 09:53) [0]

Имеющих решение (смысл их решать таким способом) только при наличии скоростного "вычислителя" (PC подойдет :))

Мне понравилась такая:
Не знаете ли Вы алгоритма определения площади объекта,
определяющего площадь рисунка
растрового или векторного(без разницы), т.е. рисунок не
прямоуголник, а некая безформенная область. И просто надо
задаваясь масштабом и этим рисунком определить на выходе
площадь объекта.
У меня и у самого встают `волосы дыбом` при одной только
мысли вручную интегрировать данное художество :(.
Надо вычислить площадь пруда произвольно сложной формы. Обводим этот пруд прямоугольником с известными длиной L и шириной W - такими, чтобы весь пруд заведомо оказался внутри прямоугольника.
Случайным образом кидаем в прямоугольник N камней и считаем количество всплесков. Пусть их было M. Тогда с определенным приближением площадь пруда будет равна M * L * W / N. При достаточно большом N получаем практически точное значение (с погрешностью, во всяком случае, не хуже, чем дают детерминированные методы численного интегрирования).
Метод, как видите, очень прост. "Кидание камней" моделируется через
Randomize и Random, а "всплеск" можно проверить, скажем, через цвет
пикселя (конечно, сначала надо чем-то залить обрамляющий прямоугольник).
Юрий Зотов

← →
иной пример (2008-08-27 10:39) [1]

Организация внедряет новое клиентское ПО для своих клиентов.
Ранее клиенты использовали разное ПО от разных производителей.

В новом и старом ПО есть справочники контрагентов.
Хранение справочников было реализовано на различных субд различных версий и типов.

Требуется дешево и быстро обеспечить миграцию стправочников в новое ПО.

Решение:
Не заморачиваться вообще с импортом данных из разнородных субд на у клиентов.
Наполнить новые справочники по имеющимся в организации клиентским документам (платежкам)

← →
tesseract © (2008-08-27 10:44) [2]

> Наполнить новые справочники по имеющимся в организации клиентским
> документам (платежкам)

Платёжки из баз проще вырезать ? Жесть. Есть специальный софт - завёться скипт на perl-е которым всё и делаеться. Например у моей конторы ~ 1500 юрлиц. В прошлой ~ 4000-4500 Представляюеш сколько их с бумаги переносить ?

Решение нестандартное :
Импортировать в свой софт платёжки через выгрузку с клиент-банков, они в 95 % случаях имеют выгрузку истории платежей.

← →
shlst (2008-08-27 10:44) [3]

Площадь легко искать, я по дискавери в программе "Грязная работёнка" видел - там Майк работал на фабрике по обработке шкур, и показали механический станок для определения их площади. станок прошлого века, но точный -
суть работы над столом много колёс подряд - |||||||| между колёс и столом просовывают шкуру, колёса катятся по шкуре, где нет шкуры там не катятся. и в зависимости от угла поворота колёс вычисляется площадь и показывается стрелкой))
это как вручную интеграл искать - разбивать на области вертикальные и суммировать, изящное решение этот станок :)

← →
Jeer © (2008-08-27 10:45) [4]

> Мне понравилась такая:

Это даже не смешно, "патаму-чо" метод "Монте-Карлы" известен с незапамятных времен и достаточно широко применяется

← →
иной пример (2008-08-27 10:50) [5]

Платёжки из баз проще вырезать

Они и вырезаются из платежек. Но не у клиентов.
В старом ПО зоопарк субд включая всякую экзотику.
В чем вся и соль.

← →
boriskb © (2008-08-27 10:51) [6]

> метод "Монте-Карлы" известен с незапамятных времен

И что из того?
Если я не знаю про таблицу умножения и пытаюсь вычислить
2+2+2+2+....+2
и мне кто то подскажет, что существует операция "*" , я ему только спасибо скажу.
Другое дело что "неожиданным решением" назвать не возьмусь :)

← →
Vlad Oshin © (2008-08-27 10:55) [7]

хотел агит.работу провести, показать новичку как можно комп применить

спасибо за примеры ...

← →
Mystic © (2008-08-27 11:23) [8]

Кнута что-ли почитай. У него таких красивых примеров...

← →
Vlad Oshin © (2008-08-27 11:53) [9]

интересует неожиданное, казалось бы, не связанное с программированием

← →
Дуб © (2008-08-27 12:15) [10]

>Vlad Oshin ©

:)

1. Измерить высоту останкинской башни: Берем бутылку и двигаем ее перд взглядом до тех пор пока не закроем башню, меряем высоту бутылки и расстояние до нее. Отходим на 100 метров и проделываем то же самое. Составляем пропорции и считаем высоту.

2. Измеряем скорость света: Оказываемся на одном радиусе с ..Юпитером, замечаем время затмения спутника. Ждем около полугода - оказываемся на противопложнлом радиусе с ним, замечаем время затмения того же спутника. Считаем скорость света.

:)

← →
Vlad Oshin © (2008-08-27 12:27) [11]

А где программирование?
тогда так:

> Измерить высоту останкинской башни

берем twebbrowser, кидаем на форму, navigate на www.ya.ru и:
Останкинская телебашня — телевизионная и радиовещательная башня, расположенная в Москве. Высота — 540 м

> Измеряем скорость света

берем twebbrowser, кидаем на форму, navigate на www.ya.ru и:
Скорость света в вакууме — фундаментальная физическая постоянная, по определению, точно равная 299 792 458 м/с
:)

Надо показать интерес к программированию группе из последних классов
Пруд из [0] интересен тем, что можно брать заранее обсчитываемую фигуру. Чтоб они сами могли посчитать и проверить рассчет этого метода.

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

← →
boriskb © (2008-08-27 12:37) [12]

> Надо показать интерес к программированию группе из последних
> классов

Нууу... если так...
Тогда надо игрушки показывать...

IMHO, надо интерес не к программированию пробуждать, а интерес к работе головой.

← →
Skyle © (2008-08-27 12:42) [13]

> boriskb © (27.08.08 12:37) [12]

Ага, пусть пишут крестики-нолики самообучающие или программу, выводящую алгоритм перекладывания в Ханойских башнях.

← →
Mystic © (2008-08-27 12:56) [14]

Меня впечатлило в свое время следующее решение на C такой задачи: получить номер первого установленного бита для 64-битного числа и сбросить его.
Применялась для шахмат, поэтому номер бита заменен на константу поля (A1 = 0, B1 = 1, ..., H8 = 63).

static const FLD LSB_Magic[64] = { A8, B4, E1, H5, E8, B2, E2, G5, D8, H4, F7, G2, A7, E3, C3, F5, C8, C4, F1, C7, E7, A3, G6, F3, H8, D4, G1, E6, B6, E4, H1, E5, B8, A4, F8, D1, C1, G7, B7, B1, A2, D7, D2, H6, A1, F6, C6, H3, G4, G8, H7, C2, F2, A5, H2, D6, D3, A6, B5, B3, G3, C5, D5, F4 }; static inline FLD pop_lsb_inner(U64* pb) { if (*pb == 0) return NF; U64 lsb = *pb ^ (*pb - 1); unsigned int foldedLSB = ((int) lsb) ^ ((int)(lsb>>32)); int ind = (foldedLSB * 0x78291ACF) >> (32-6); // range is 0..63 *pb &= ~lsb; return LSB_Magic[ind]; }

← →
TUser © (2008-08-27 22:20) [15]

← →
TUser © (2008-08-27 22:34) [16]

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

Решение. Нумеруем башни 1, 2, 3, и представим, что они образуют кольцо. На нечетных ходах перекладываем самую мелкую из верхних по часовой стрелке. На четных - самую большую перекладываем против часовой стрелки. На всех ходах пропускаем колышек, если нельзя на него перекладывать, и фишку, если ее вообще нельзя переложить. Например

[321] [] [] (на первом колышке три фишки размеров 3, 2 и 1, фишку 1 передвигаем вперед) -> [32] [1] [] (2 назад, она наибольшая из верхних) -> [3] [1] [2] (1 вперед) -> [3] [] [21] (3 назад, колышек [21] пропускаем, на него нельзя положить 3) -> [] [3] [21] (1 вперед) -> [1] [3] [2] (2 назад) -> [1] [32] [] (1 вперед) -> [] [321] []

Этот метод работает для любого числа N фишек и требует 2^N-1 ходов. Доказывается по индукции.

← →
Тыщ © (2008-08-27 23:10) [17]

Mystic © (27.08.08 12:56) [14]

Сбросить первый установленный бит? Есть получше решение:

; EAX:EDX - 64-bit integer resetfirstbit: bsf ecx,edx jz nolowbits btr edx,ecx jmp exit nolowbits: bsf ecx,eax jz exit btr eax,ecx exit: ret

← →
Юрий Зотов © (2008-08-27 23:15) [18]

Есть решение и еще проще: i := 0;

← →
ketmar © (2008-08-27 23:28) [19]

собрать новый Qt. запустить disigner. увидеть segmentation fault. сидеть, офигевать и удивляться.

решение: откатиться на старый Qt.

---
All Your Base Are Belong to Us

← →
Renegat © (2008-08-27 23:37) [20]

> получить номер первого установленного бита для 64-битного числа и сбросить его

А BSF/BSR + BTC уже запретили?

← →
MsGuns © (2008-08-28 00:33) [21]

Блин, вот вам задачка из "простых":

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

Решение есть очень даже простое и, главное, НЕОЖИДАННОЕ ;)

← →
ketmar © (2008-08-28 00:56) [22]

>[21] MsGuns © (2008-08-28 00:33:00)
в евклидовом пространстве или нет?

---
All Your Base Are Belong to Us

← →
McSimm © (2008-08-28 00:58) [23]

нанять молдаван ?

← →
TUser © (2008-08-28 01:02) [24]

грани обязаны быть плоскими?

← →
TUser © (2008-08-28 01:03) [25]

грани обязаны быть плоскими?

← →
McSimm © (2008-08-28 01:20) [26]

положить в основание неправильный четырехугольник

|><|

такой

← →
McSimm © (2008-08-28 01:23) [27]

только не уверен насколько они противоположные :)

класс

кстати, еще - нарисовать карандашом (фломастером, ручкой, мелом, ...) на бумажке, не отрывая одного от другого, фигуру, нарисованную в [26]

>[27] McSimm © (2008-08-28 01:23:00)
Максим, это галстук-бабочка, а не чертёж. %-)

---
Understanding is not required. Only obedience.

> положить в основание неправильный четырехугольник
>
> |><|

Решение красивое, но немного спорное, т.к. это настолько неправильный четырехугольник, что он стал шестиугольником :)

> У меня и у самого встают `волосы дыбом` при одной только
> мысли вручную интегрировать данное художество :(.

Фотографируем объект, желательно 5 Мпиксельньной камерой, по синезубому сливаем в комп, определяем коэффициент пиксель = площадь, считаем кол-во пикселей в интерьере. Программно. Интегрирование в полный рост. Любых объектов. Дёшево. Самовывозом из Москвы.

> А BSF/BSR + BTC уже запретили?

Это решение привязано к платформе.

В свое время меня впечатлила задача о кошках и мышах в амбаре (к теме имитационного моделирования) из книги Гудман, Хидетниеми "Введение в разработку и анализ алгоритмов".

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

Vlad Oshin © (28.08.08 12:33) [35]

> не нашел.

Увы, я тоже в электронном виде не нашел, только в бумажном. У меня в бумажном.

> Это ведь все условие?
> Как там, примерно?

Нет, конечно не все. Там предлагается написать программу (и приводится ее пример), и дается масса начальных условий, как то: средняя продолжительность жизни мыши, средняя прожорливость мыши, средняя продолжительность жизни кошки, средняя прожорливость кошки, как в зависимости от количества поедаемой пищи появляется потомство у обоих видов и т.п.

Кстати еще о занятных задачах - есть, опять же, неплохая книжка Чарльза Уэзерелла "Этюды для программистов". В электронном виде не видел.

спасибо
Будем искать (с)

ps
завтра уже идти

Книга американского специалиста по системному программированию - уникальный сборник задач по программированию из разных областей: моделирования, точности вычислений, обработки текстов, искусственного интеллекта, конструирования компиляторов. Большинство задач базируется на реальных и игровых ситуациях.
Перевод с английского Ю. М. Баяковского.
Автор(ы): Уэзерелл Ч. Страниц: 288 Год: 1982

http://ru.dleex.com/details/?8701

> http://ru.dleex.com/details/?8701

благодарю, заодно и себе сохраню

Поделитесь красивыми/неожиданными решениями с виду сложных задач? Найти похожие ветки