Сколько потребуется умножений для возведения числа х в степень n=147, если построить для этого эффективный алгоритм? ответ:

(см. объяснение)

Объяснение:

Решая задачу "в лоб", нам потребовалось бы умножить число само на себя ровно 147 раз. Это много, потому попробуем оптимизировать алгоритм. Заметим, что , а . Изначально имеем число . Пусть - степень. Пусть - наш будущий ответ. На каждой итерации цикла будем умножать сам на себя, а целочисленно делить на 2. При этом заметим, что когда , то нам надо умножить текущий результат на . Таким образом, всего за 8 итераций (вместо 147!) мы можем возвести некоторое число в степень 147.

Покажем, как написать это на C++:

#define ll long long

ll bpow(ll x, ll y) {

   ll r = 1;

   while (y > 0) {

       if (y % 2 > 0) {

           r *= x;

       }

       x *= x;

       y /= 2;

   }

   return r;

}

Задание выполнено!

program pryam;

var y1, y2, y3, x1, x2 : real;

begin

  writeln ('введите координату (у) верхней точки прямой');

  readln (y1);

  writeln ('введите координату (у) нижней точки прямой');

  readln (y2);

  writeln ('введите координату (х) точек-концов прямой');

  readln (x1);

  writeln ('введите координату (у) точки, принадлежность к прямой которой нужно определить');

  readln (y3);

  writeln ('введите координату (х) точки, принадлежность к прямой которой нужно определить');

  readln (x2);

if (y3< =y1) and (y3> =y2) and (x2=x1) then writeln (' принадлежит ')

else writeln (' не принадлежит ');

readln;

end.

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