Задача

← →
still © (2002-10-10 15:38) [0]

Дано: X
Требуется: минимальным числом операций получить X^78 (в смысле в степени)

← →
AL2002 © (2002-10-10 15:42) [1]

А это смотря какие операции.

← →
qube © (2002-10-10 15:42) [2]

Result := Exp(Ln(78)*X) ?

← →
Внук © (2002-10-10 15:44) [3]

Первое, что подумалось: exp(78*ln x)

← →
qube © (2002-10-10 15:47) [4]

Внук © (10.10.02 15:44)
Тьфу ты, а я все перепутал :).

← →
ZrenBy © (2002-10-10 15:48) [5]

Встречная постановка !

X - целое и > 1000000

Получить точный результат ( в смысле - все знаки).

← →
Внук © (2002-10-10 15:49) [6]

>>qube © (10.10.02 15:47)
Я сначала так же написал, потом посмотрел, что получилось :))

← →
AL2002 © (2002-10-10 15:50) [7]

X^39*X^39?

← →
still © (2002-10-10 15:52) [8]

> Внук © (10.10.02 15:44)

а если с помощью арифметики?

← →
Wonder © (2002-10-10 15:54) [9]

А если с помощью арифметики - то простейшая рекурсия :)

← →
still © (2002-10-10 15:55) [10]

>
> AL2002 © (10.10.02 15:50)
> X^39*X^39?

а X^39 откуда возьмешь?
можно уж тогда сразу так : X^78

← →
qube © (2002-10-10 15:56) [11]

Wonder © (10.10.02 15:54)
Зачем рекурсия? Простейшая итерация :)

← →
still © (2002-10-10 15:57) [12]

> Wonder © (10.10.02 15:54)

ну и количество операций какое?

← →
AL2002 © (2002-10-10 15:58) [13]

>still © (10.10.02 15:55)
но икс же неизвестен. скажи тогда, чему изначально равен икс.

← →
Alx2 © (2002-10-10 16:00) [14]

78 = (2^5+2^2+2+1)*2
result := (x shl 5 + x shl 2 + x shl 1 + 1) shl 1

← →
qube © (2002-10-10 16:01) [15]

Alx2 © (10.10.02 16:00)
Браво!

← →
Внук © (2002-10-10 16:02) [16]

Сначала
X:=X*X 6 раз (это будет 64-ая степень), затем умножить на X^8 - еще четыре умножения (это 72-ая степень), потом еще на X^4 - три умножения и еще на X*X - всего 16 операций, вроде.
X^78= X^64*X^8*x^4*X^2.
А если запоминать промежуточные результаты - и того меньше.

← →
Wonder © (2002-10-10 16:03) [17]

Это вот shl - арифметика ?!?
Ну вы, блин, даете! :)

← →
Alx2 © (2002-10-10 16:05) [18]

>Alx2 © (10.10.02 16:00)
Не то написал :)

Result := ((x^13)^3)^2=sqr(sqr(sqr(sqr(sqr(x)))*sqr(sqr(x))*x)*sqr(sqr(sqr(x)))*sqr(sqr(x))*x)

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

← →
still © (2002-10-10 16:05) [19]

> AL2002 © (10.10.02 15:58)

значение X не играет роли

> Alx2 © (10.10.02 16:00)
> 78 = (2^5+2^2+2+1)*2
> result := (x shl 5 + x shl 2 + x shl 1 + 1) shl 1

для целых чисел красиво, а для произвольных?

Задача вообще-то не программистская, а так - из математики

← →
Внук © (2002-10-10 16:08) [20]

>>Alx2 © (10.10.02 16:05)
Продублировали друг друга :))

← →
Alx2 © (2002-10-10 16:08) [21]

>qube © (10.10.02 16:01)

Мой пост Alx2 © (10.10.02 16:00) прошу считать БРЕДОМ.
Так как там только лишь вычисляется x*78 :)))

← →
Alx2 © (2002-10-10 16:11) [22]

>Внук © (10.10.02 16:08)
:))

← →
Jeer © (2002-10-10 16:11) [23]

Тогда уж
Y = X^64*X^16/X^2

← →
still © (2002-10-10 16:20) [24]

> Alx2 © (10.10.02 16:08)

точно, а я уж повелся:)

← →
Alx2 © (2002-10-10 16:24) [25]

>Jeer © (10.10.02 16:11)
Угу. Еще круче :)

← →
Внук © (2002-10-10 16:26) [26]

>>Alx2 © (10.10.02 16:24)
Если решать как математическую, то да. Если применительно к компьютерам - неоправданное деление = потеря точности.

← →
Jeer © (2002-10-10 16:27) [27]

:))

← →
Jeer © (2002-10-10 16:28) [28]

Y = X^64*X^16*X^(-2)

Зря улыбаетесь, символ ^ и я могу поставить, а реализовывать как будете - все равно через деление?

А вот оптимум, посмею заявить :))
Result := sqr(sqr(sqr(sqr(sqr(sqr(x)))*x)*x)*x);

>Задача вообще-то не программистская, а так - из математики
А что в таком случае считать элементарной операцией? По-моему, без привязки к компьютерам и конкретному языку программирования задача в такой формулировке смысла не имеет.

> qube © (10.10.02 16:35)
> > А что в таком случае считать элементарной операцией?

Умножение, деление, сложение, вычитание
А вот sqr - я бы сказал не операция, а функция, пусть и встроенная

still © (10.10.02 16:43)
Умножение тоже можно с помощью сдвигов и сложений выполнять (другое дело, что это функция процессора, пусть и встроенная :).

>>still © (10.10.02 16:43)
Не важно, можно заменить умножением и введением промежуточных переменных. Ведь про объем памяти не было речи? :)

> Внук © (10.10.02 16:46)
> >>still © (10.10.02 16:43)
> Не важно, можно заменить умножением и введением промежуточных
> переменных. Ведь про объем памяти не было речи? :)

про объем памяти действительно речи не было, как в общем-то и про какой-то язык программирования, особенности процессоров и пр.

Чистая арифметика :)

Задача Найти похожие ветки