Алгоритмы. Задачки для программистов

Сообщение №24368 от 13 апреля 2008 г. 09:53
Тема: Алгоритмы. Задачки для программистов

Тема по оптимизации алгоритмов.
Тема по оптимизации конструкций на алгоритмических языках.


Отклики на это сообщение:

Хорошо известна задачка, которую в разных видах предлагают начинающим программистам - придумать алгоритм, возводящий в натуральную степень (y=x^n). При этом "качество" алгоритма оценивается как число умножений, и ответ засчитывается, если учащемуся удаётся уложиться в удвоенную длину двоичной записи степени.
Иными словами, если доказана верхняя оценка числа необходимых умножений s(n) как 2*lb(n), где lb(n) - "почти" двоичный логарифм... С другой стороны, из рассмотрения n=степень_двойки имеем просто 1*lb(n) в качестве нижней оценки.

Таким образом, возникает "зазор" между верхней и нижней оценками, и я нигде не видел попыток "закрыть" его.
Так что предлагаю это в качестве новой(?) задачки - я умею её решать ;)


ну, раз умеете, то напишите.


> ну, раз умеете, то напишите.
Не, хочу помучить :)
Известные мне математики такого решения не знают.


> > ну, раз умеете, то напишите.
> Не, хочу помучить :)
> Известные мне математики такого решения не знают.

http://server.179.ru/tasks/cpp/for2.html
ищите "быстрое возведение в степень".
Не вы первый. :)


> http://server.179.ru/tasks/cpp/for2.html
> ищите "быстрое возведение в степень". Не вы первый. :)

==Быстрое возведение в степень По данному действительному a и натуральному n вычислите an за время порядка log(n).
Указание воспользуйтесь представлением числа n в двоичном виде, или свойством: an=(a2)n/2. ==
Это и есть обычное решение с верхней оценкой 2*lb(n).
Я говорю о решении с верхней оценкой (1+o(n))*lb(n)


> Я говорю о решении с верхней оценкой (1+o(n))*lb(n)

Замечу, что "умножение" в задаче непринципиально. Фактически речь идёт о произвольной бинарной ассоциативной операции и расстановке скобок.
Так что задачу можно ставить так -
имеем выражение х * х * х * х * х * х * х * х * х * х * х * х * ... * х.
Требуется расставить скобки так, чтобы минимизировать количество неэквивалентных подформул. Достаточно вообще оперировать выражением 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + .. + 1...
Можно переформулировать и как задачу построения бинарного дерева с заданным количеством висячих вершин и минимальным количеством различных поддеревьев в нём.


> Это и есть обычное решение с верхней оценкой 2*lb(n).
> Я говорю о решении с верхней оценкой (1+o(n))*lb(n)

Не понял:
(1+o(n))*lb(n) может быть и 2*lb(n) и 3*lb(n) ... может уточните?


> > Это и есть обычное решение с верхней оценкой 2*lb(n).
> > Я говорю о решении с верхней оценкой (1+o(n))*lb(n)

> Не понял:
> (1+o(n))*lb(n) может быть и 2*lb(n) и 3*lb(n) ... может уточните?

(1 + An)*lb(n), An-->0.
Эту An нужно писать как о(n)? ;)


Короче (1+o(n))*lb(n) >> (много хуже чем) >> 2*lb(n).
и вообще не стоит смешивать знак o() с обычными числами
Нужно определиться либо:
(o(1)+o(n))*o(lb(n)) что эквивалентно o(n)o(lb(n))
либо
(1+An)*lg(Bn)

PS есть классный сайт http://rsdn.ru/ ---> Этюды для программистов
Если любите помучать там этот номер не пройдет ... вас помучают ;)


> PS есть классный сайт http://rsdn.ru/ ---> Этюды для программистов
> Если любите помучать там этот номер не пройдет ... вас помучают ;)
"Этюды для программистов" - скорее мёртв, чем жив: пусто после 2003 года.

Вот эквивалентная задачка -
Список натуральных чисел назовём честным, если он начинается с 1 и каждый член есть сумма каких-либо предыдущих членов. Он чемпион, если нет более короткого с данным последним элементом n.
Естественна задача о поведении ф-ии S(n) - длине чемпионов...
Утверждается, что S(n)=(1 + o(1))*lb(n).

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


> > PS есть классный сайт http://rsdn.ru/ ---> Этюды для программистов
> > Если любите помучать там этот номер не пройдет ... вас помучают ;)
> "Этюды для программистов" - скорее мёртв, чем жив: пусто после 2003 года.
Нет что вы. Форум цветет как весна перед шашлыками!!! На всяк случай повторю сайт - rsdn.ru - далее слева в окошке выбираете "прикладные направления", а после "этюды для программистов" и там задаете свой этюдик!!!

> Естественна задача о поведении ф-ии S(n) - длине чемпионов...
> Утверждается, что S(n)=(1 + o(1))*lb(n).
Ну нельзя так говорить.
Если S(n) - конкретная функция, то она не может определяться через символ o(...)


> Нет что вы. Форум цветет как весна перед шашлыками!!!
Ок, наконец нашёл вход ;)


> > > PS есть классный сайт http://rsdn.ru/ ---> Этюды для программистов
> > > Если любите помучать там этот номер не пройдет ... вас помучают ;)
Ответ я получил довольно быстро - вроде бы такую же оценку, что и у меня.
Поэтому раскрою карты :).

Пусть битовая запись числа n разбита на h групп длины d (с поправками, если нельзя точно). Таких групп не более 2^d, и все соответствующие числа q можно получить менее чем за 2^d умножений. Само n можно представить в q-ичной системе и действовать также, как в случае двоичного разложения, употребляя на каждую "цифру" h+1 умножения.
Остаётся подобрать d, чтобы общее число умножений было поменьше...
Вроде получается log(n) + log(n)/log(log(n)) + o(log(n)/log(log(n))).


> > Естественна задача о поведении ф-ии S(n) - длине чемпионов...
> > Утверждается, что S(n)=(1 + o(1))*lb(n).
> Ну нельзя так говорить.
> Если S(n) - конкретная функция, то она не может определяться через символ o(...)

Интересная задачка! И, кстати, почему так нельзя говорить? Это же не определение, а утверждение о том, что сущестует такая Аn, что Аn есть о(1) и верно, что S(n)=(1 + Аn)*lb(n). Это стандартное применение о-символики.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100