Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

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

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
31 
15.
end. 
Из анализа данного алгоритма известно, что его асимптотическая сложность порядка O(log
2
n). 
Задача № 26. Решить квадратное уравнение заданного вида с параметром