Завдання № 25. Обчислити xn за алгоритмом швидкого зведення в ступінь » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 25. Обчислити xn за алгоритмом швидкого зведення в ступінь

Завдання № 25. Обчислити xn за алгоритмом швидкого зведення в ступінь
Формулювання. Дано натуральні числа x і n. Обчислити xn, використовуючи алгоритм швидко-го зведення в ступінь:

[thumb=]/uploads/posts/2015-05/1432815364_1.png[/thumb]

Рішення. Розберемо цей поки неясний алгоритм, представлений в нашому завданні лише єдиною формулою. Легко зрозуміти, що зазначена рівність має місце: наприклад, 34 = 34 div 2 = (32) 2 = 92 = 81. Інший приклад: 45 = 4 * (42) 5 div 2 = 4 * (42) 2 = 4 * 162 = 4 * 256 = 1024. Причому ес-ли вираз зі ступенем не можна в один крок перетворити таким чином, то необхідно про-повинен перетворення виразу аж до отримання кінцевого відповіді. Однак як тепер реалізувати цю схему?
Розглянемо приклад трохи складніше. Обчислимо 47 = 4 * (42) 3 = 4 * (16) 3 = 4 * 16 * (162) 1 = 4 * 16 * 256 = 16384. Варто звернути увагу на те, що на кожному кроці при обчисленні змінять-ється тільки єдине обробляти число, а решта множники виносяться однократ-а й необхідні тільки для отримання відповіді в останній дії.
    Щоб виключити їх з розгляду, при непарному поточному числі n ми будемо домножать на них деяку проміжну змінну r, спочатку рівну 1 (до речі, непарність числа в Pascal визначає функція odd), потім (вже незалежно від умов) зведемо в квадрат поточний x і розділимо n на 2 з відкиданням залишку. При повторенні цих дій на деякому кроці n обов'язково стане рівним 1. Це відбувається тому, що поділ будь-якого непарного числа a на 2 з відкиданням залишку рівносильно поділу на двійку числа (a - 1), яке є парним, і при розподілі, рухаючись по ланцюжку парних чисел, ми завжди прийдемо до одиниці. Умова n = 1 і буде закінченням циклу з передумовою. По виході з циклу необхідно буде як відповідь вивести останнє значення x, помножене на r.
Тепер алгоритм природною мовою:
1) Введення x і n;
2) Присвоєння змінної r числа 1;
5) Запуск циклу з передумовою n <> 1. У циклі:
  1. Якщо n непарне, домножаем r на x;
  2. Перемінної x присвоюємо значення x * x;
  3. Перемінної n присвоюємо результат від ділення цієї змінної на 2 з відкидаючи-ням залишку;
3) Висновок вираження x * r.

 

Код:


  1. program FastExponentiation;
  2. var
  3. x, n, r: word;
  4. begin
  5. readln(x, n);
  6. r := 1;
  7. while n <> 1 do begin
  8. if odd(n) then r := r * x;
  9. x := x * x;
  10. n := n div 2
  11. end;
  12. writeln(x * r)
  13. end.

0025.-FastExponentiation.rar [650 b] (cкачувань: 3)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 26. Вирішити квадратне рівн... Попередня сторінка » Завдання № 24. Обчислити X^n