задача на сообразительность

[Rocks]

задача на сообразительность

Люди, хээээээээээээээлп!


Ввести вещественное число A и натуральное k, Вычислить и напечатать
A(в степени k) с выполнением следующих условий:
операцией возведения в степень пользоваться нельзя; k может оказаться
настолько большим, что недопустимо выполнять k умножений.

 

[Astral Man]

bcpow

 

[kvf77]

Rocks

создание тем с ничего незначащим названием запрещено

 

[SiMM]

Astral Man, не удовлетворяет правилам
Rocks, а экспоненту и логарифмы пользовать - можно? Если да - ищи ответ в справочнике по математике. Если нет - k - целое?

 

[Rocks]

Автор оригинала: SiMM
Astral Man, не удовлетворяет правилам
Rocks, а экспоненту и логарифмы пользовать - можно? Если да - ищи ответ в справочнике по математике. Если нет - k - целое?

SiMM, честно говоря, не знаю. По идее, это испытательное задание. НО! Прямо так и было написано в задании: "простая задачка на сообразительность:", т.е. думаю, что наворотов здесь нет....

И теряюсь...

Вакантное место просто до невозможности нужно!

-~{}~ 24.10.05 15:25:

Автор оригинала: kvf77
Rocks

создание тем с ничего незначащим названием запрещено

прошу громадное прощение....

 

[diztex]

возведения в k степень можно заменить операцией побитового сдвига влево на k позиций
PS если k - целое, а
Исходя из условия k - натуральное число, т.е. целое и больше 0

 

[Rocks]

а разве натуральное - это не целое?

Автор оригинала: diztex
возведения в k степень можно заменить операцией побитового сдвига влево на k позиций
PS если k - целое

каким образом это сделать?

 

[SiMM]

> а разве натуральное - это не целое?
А я помню?

Даю наводку - дальше думай сам (поскольку к форуму про PHP это никакого отношения не имеет):
x^(2n) = x^n * x^n
x^(2n+1) = x * x^n * x^n
где x^n - x в степени n

> Вакантное место просто до невозможности нужно!
Вобще-то если ты не в состоянии решить конкурсную задачу - значит, скорее всего ты этого места не заслуживаешь.

> возведения в k степень можно заменить операцией побитового сдвига влево на k позиций
В общем случае - это бред. В частном - работает при x = 2, и то с поправками. Чуть не забыл - без поправок работает при x = 0

 

[diztex]

http://php.rinet.ru/manual/ru/language.operators.bitwise.php

 

[kruglov]

Rocks
0 - не натуральное число. Но целое.

В принципе, путем дихотомии можно умножать не k раз, а примерно двоичный логарифм из k.

 

[Rocks]

Автор оригинала: SiMM
Даю наводку - дальше думай сам (поскольку к форуму про PHP это никакого отношения не имеет):
x^(2n) = x^n * x^n
x^(2n+1) = x * x^n * x^n
где x^n - x в степени n

))))

Ага. И проверку на большое число тогда делать по типу

if (step == 0)
y = x*x^n
else {
y1 = y*x^n
if (count(res) < 9)
y = y1
else
print "Error"
}

-~{}~ 24.10.05 15:53:

Автор оригинала: kruglov
0 - не натуральное число. Но целое.

В принципе, путем дихотомии можно умножать не k раз, а примерно двоичный логарифм из k.

Натуральные числа - это целые положительные числа 1, 2, 3... Да, 0 в них не входит.

Каким образом сделать использовать логарифмические функции?

-~{}~ 24.10.05 15:57:

здесь.


to SiMM.
2е задание было совсем другим, и связано непосредственно с php. Естественно, его я буду делать самостоятельно. В этом же задании я просто теряюсь. Честно говоря, с вышкой никогда не дружил.

 

[kruglov]

Не логарифмические функции, а количество умножений не линейное, а логарифмическое.

1024 = 2*2*2*2*2*2*2*2*2*2 - 9 умножений
или
1024=((2^2)^2)^2)*(2^2) - 5 умножений.

-~{}~ 24.10.05 16:04:

(а если еще и предыдущие вычисления кэшировать...)

 

[SiMM]

> 2е задание было совсем другим, и связано непосредственно с php. Естественно, его я буду делать самостоятельно. В этом же задании я просто теряюсь. Честно говоря, с вышкой никогда не дружил.
Вышка тут не при чём совершенно. Если работодатель считает, что нанимаемый должен это знать - значит, должен знать. Это всего лишь один из критериев отбора, отделения зёрен от плевел. Вообще эта задачка из курса школьной информатики (по крайней мере - у нас она была). И ведь потом - это не единственное задание, да и вес у него может быть малым.

 

[kruglov]

Рекурсия.

2^10 = 2^5 * 2^5

2^2 = 2^2 * 2^3

2^3 = 2^1 * 2^2

Итого нам нужно вычислить 2^2 - 1 умножение, 2^3 - + еще одно умножение, 2^5 - + еще одно, 2^10 - + еще одно.

Итого с кэшированием-рекурсией (использованием наработок) - 4 умножения.

 

[Rocks]

Автор оригинала: kruglov
Не логарифмические функции, а количество умножений не линейное, а логарифмическое.

1024 = 2*2*2*2*2*2*2*2*2*2 - 9 умножений
или
1024=((2^2)^2)^2)*(2^2) - 5 умножений.

-~{}~ 24.10.05 16:04:

(а если еще и предыдущие вычисления кэшировать...)

не совсем понял алгоритм.

т.е. если A = 0.3, a k = 4, то переменная result будет считаться как result = ??

 

[kruglov]

0.3 ^ 4 = 0.3 ^ 2 * 0.3 ^ 2
0.3 ^ 2 = 0.3 * 0.3
2 умножения. (Рекурсия она как делается? Вычисления снизу вверх проделываются)

 

[SiMM]

А вообще мне честно говоря не понятно, почему тредстартер до сих пор не воспользовался тем же гуглом.
kruglov, рекурсия там кстати ни к чему. Итераций достаточно.

 

[Rocks]

Автор оригинала: kruglov
0.3 ^ 4 = 0.3 ^ 2 * 0.3 ^ 2
0.3 ^ 2 = 0.3 * 0.3
2 умножения. (Рекурсия она как делается? Вычисления снизу вверх проделываются)

догнал. Но пересмотрел ещё раз условия задачи: операцией возведения в степень пользоваться нельзя.

-~{}~ 24.10.05 16:28:

Автор оригинала: SiMM
А вообще мне честно говоря не понятно, почему тредстартер до сих пор не воспользовался тем же гуглом.

а что искать-то?


И по поводу работы. Во-первых, плата за работу - по рез-там собеседования (т.е. от х до х*2), а, во-вторых, есть возможность ежедневной как удалённой, так и офисной работы в течение рабочего дня.

-~{}~ 24.10.05 17:20:

хм... А если использовать это:

http://ru.php.net/pow ?

 

[kruglov]

операцией возведения в степень пользоваться нельзя

Неее, нельзя вам на эту вакансию...

 

[Rocks]

а, это я уже торможу...

да, колхоз прибыл... Просто счас работаю asp-истом, и день выматывающий был..

строго прошу не судить. Лучше подскажите что-нибудь реальное, т.к. всерьёз буду этим заниматься по приезду домой, т.е. в 10 вечера. А сделать нужно к завтрашнему дню.

-~{}~ 24.10.05 17:44:

А если так, как считаете?

$result=exp(log(A)*k);