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

[crocodile2u]

Rocks
Не, не прокатит.

Брось затею со всякими функциями. используй циклы и операторы.

 

[Rocks]

я слышал что-то про уравнение Стирлинга. Может кто-нибудь сказать, здесь оно пройдёт? И как его использовать, если пройдёт?

 

[Andreika]

а почему $result=exp(log(A)*k); не прокатит?

 

[crocodile2u]

Rocks
Да тебе же уже написал алгоритм kruglov...

Andreika
Да потому, что это тупо - во-первых. А во-вторых - возведение в степень использовать нельзя.

 

[Rocks]

потому что оно с использованием возведения в степень

 

[Andreika]

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

 

[Rocks]

Автор оригинала: crocodile2u
Rocks
Да тебе же уже написал алгоритм kruglov...

аа......
0.3 ^ 4 = 0.3 ^ 2 * 0.3 ^ 2
0.3 ^ 2 = 0.3 * 0.3

если принять A = 0.3, k = 9, to
x = 0.3
x1 = x*x
x2 = x1*x1
x3 = x2*x2
x4 = x3*x

точно! Надо в эту сторону покопать!


kruglov и все кто отвечал: громадное вам спасибо!!!

Осталось только подумать как разделить k на равные части!..

Хотя... Если взять k=7.. Какая тут будет рекурсия?

 

[Andreika]

Rocks
http://algolist.manual.ru/maths/count_fast/fast_exp.php

 

[baev]

http://algolist.manual.ru/maths/count_fast/fast_exp.php

Rocks, кстати, если в Яндексе набрать "возведение в степень" -- это будет третьей ссылкой в результатах...

 

[ksnk]

crocodile2u
а это отчего-ж? С фукцией довольно изяшшно получается Циклами , вроде помассивнее выглядит...

function step ($a,$k) {
  if (!$k) return 1 ;
  else { $x = step ($a,$k>>1) ;
    return (($k&1)?$a:1)*$x*$x;
  }
}
$a=1.3 ;
$k = 25 ;
echo 'step: '.step($a,$k)."<br>pow: ".pow($a,$k)

Кстати - у меня чегото ссылка на algolist... не работает

 

[SiMM]

> кстати, если в Яндексе набрать "возведение в степень" -- это будет третьей ссылкой в результатах...
В гугле - первый

> Кстати - у меня чегото ссылка на algolist... не работает
Из кэша гугла читай

 

[Andreika]

С фукцией довольно изяшшно получается Циклами , вроде помассивнее выглядит...

function powmod($a, $k)
{
  $b=1;
  while ($k) {
    if ($k%2==0) {
      $k /= 2;
      $a *= $a; // [ a = (a*a)%n; ]
    } else {
      $k--;
      $b *= $a; // [ b = (b*a)%n; ]
    }
  }
  return $b;
}

вольный перевод с http://algolist.manual.ru

 

[Rocks]

Громадное всем спасибо!!

Сегодня ночью тоже подумал и хотел предложить такой метод:

$A = 1.5; $k = 25;
$i = 0; $d = 0;
$not_more = 9999999999;
while ($d<1) do {
  $A = $A * $A;
  $i++;
  if (($A > $not_more) || ($i == $k)) {
    $d = 1;
  }
}
//$A = res

Как данный код, на ваш взгляд?

Автор оригинала: Andreika
С фукцией довольно изяшшно получается Циклами , вроде помассивнее выглядит...

function powmod($a, $k)
{
  $b=1;
  while ($k) {
    if ($k%2==0) {
      $k /= 2;
      $a *= $a; // [ a = (a*a)%n; ]
    } else {
      $k--;
      $b *= $a; // [ b = (b*a)%n; ]
    }
  }
  return $b;
}

Это тоже хороший. Очень хороший код. Спасибо! Если специалистам (всем присутствующим в этой теме) не понравится предложенный мною вариант, остановлюсь на вашем.

 

[baev]

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

недопустимо выполнять k умножений

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

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

"А во второй степени" -- это одно умножение.
"А в k-той степени" -- это k-1 умножений.

Все!

P.S. По-моему, этому топику место в "Юморе"...

 

[SiMM]

>> недопустимо выполнять k умножений
> "А в k-той степени" -- это k-1 умножений.
Да, слона не заметили Однако вариант с числом умножений порядка O(ln k) выглядит куда заманчивее

 

[baev]

выглядит куда заманчивее

Тут-то -- дело не в заманчивости, а в сообразительности.

Тот, кто такое тестовое задание для приёма на работу использует -- видимо, своё дело знает...

 

[SiMM]

> Тут-то -- дело не в заманчивости, а в сообразительности.
Однако проблема выбора между сообразительностью и знаниями (в данном случае - это в общем-то тоже сообразительность ) - остаётся Ибо оба этих понятия не являются взаимоисключающими Идеальный вариант - представить оба варианта, или же только O(ln k), указав при этом на "огрех" задания и возможность решить его более примитивным способом

 

[baev]

знаниями (в данном случае - это в общем-то тоже сообразительность

Не-а.
Если топик перечитать -- сразу видно, что «знания встают на пути сообразительности». (Заметьте -- я тоже в топике участвовал. И был уверен, что решение с algolist.manual.ru -- верное.)

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

Вот и осенило...

 

[Andreika]

baev
там расписана причина почему нельзя использовать K ( имхо, читать величины, близкие к K) умножений.. если K умножений это очень много, то К-1 особо ситуацию не изменит

 

[baev]

Andreika, «там» написано, что «задача на сообразительность».

Перечитайте первый пост: «k может оказаться
настолько большим, что недопустимо выполнять k умножений».

Про то, что «k может оказаться
настолько большим, что недопустимо выполнять k-1 умножений» -- в условиях задачи нет ни слова. И про «почему именно нельзя использовать K» -- тоже ничего не сказано. Так что -- это только Ваши домыслы.