Язык Си в примерах/Степень числа

Язык Си в примерах

---

1. Компиляция программ
2. Простейшая программа «Hello World»
3. Учимся складывать
4. Максимум
5. Таблица умножения
6. ASCII-коды символов
7. Верхний регистр
8. Скобочки
9. Факториал
10. Степень числа
11. Треугольник Паскаля
12. Корень уравнения
13. Система счисления
14. Сортировка
15. Библиотека complex
16. Сортировка на основе qsort
17. RPN-калькулятор
18. RPN-калькулятор на Bison
19. Простая грамматика
20. Задача «Расчёт сопротивления схемы»
21. Простая реализация конечного автомата
22. Использование аргументов командной строки
23. Чтение и печать без использования stdio
24. Декодирование звукозаписи в формате ADX
25. Другие примеры

Для вычисления функции $f(n)=a^{n}\,\!$ есть рекуррентная формула:

$a^{n}=a\cdot a^{n-1},\quad a^{0}=1.\,\!$

Вот программа, которая основана на этой формуле:

 /* 
   Степень числа: простая рекурсия
 */
 
 #include<stdio.h>
 
 double power(double x, long n) {
    if(n == 0) return 1;
    if(n < 0) return power ( 1.0 / x, --n);
    return x * power(x, n - 1);
 }
 
 void main() {
     double x;
     long n;
     while (scanf ("%lf %ld", &x, &n) == 2) {
        printf("%lf\n", power (x, n));
     }
 }

Но есть более «умная» рекурсивная функция: $a^{n}=\left\{{\begin{matrix}a\cdots a^{n-1},&{\mbox{if }}n{\mbox{ is odd}}\\(a^{n/2})^{2},&{\mbox{if }}n{\mbox{ is even}}\end{matrix}}\right.\,\!$

Например, если обозначть стрелочкой $\to \,\!$ слово «сводится к », то при вычислении $a^{12}\,\!$ для первой рекурсии получим цепочку длины 12:

$a^{12}\to a^{11}\to a^{10}\to a^{9}\to a^{8}\to a^{7}\to a^{6}\to a^{5}\to a^{4}\to a^{3}\to a^{2}\to a^{1}\to a^{0}.\,\!$

А для второй рекурсии цепочку из 5 шагов: $a^{12}\to a^{6}\to a^{3}\to a^{2}\to a^{1}\to a^{0}.\,\!$

Для больших n разница в длине цепочки более разительная. В частности $a^{10000}\,\!$ первой рекурсией вычисляется за 10000 шагов, а второй -- за 19 шагов.

 /*
  Программа 2: степень числа -- оптимизированная рекурсия.
 */
 double power(double x, long n)
 {
     double tmp; 
    if(n == 0) return 1;
    if(n < 0) return power ( 1 / x, --n);
    if(n % 2) return x * power (x, n - 1);
    return power(x * x, n / 2);
 }

 /* 
    Программа 3: cтепень числа -- оптимальный алгоритм без рекурсии.
 */
 double power(double x, long n)
 {
     double a = 1;
     while(n) {
         if(n % 2) {
             a *= x;
             n--;
         }
         else{  
             x *= x;
             n /= 2;    
         }
     }
     return a;
 }

• Сколько шагов требуется для вычисления $a^{30}\,\!$ вторым методом.
• Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху $2\cdot \log _{2}n\,\!$ (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).
• Объясните, как работает программа 3.