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

Материал из Викиучебника

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

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

 /* 
   Степень числа: простая рекурсия
 */
 
 #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));
     }
 }

Приведёный выше пример не будет работать для отрицательных показателей степени (см. третью строку функции "power"). Правильнее было бы так:

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

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

Материал из Викиучебника

Просмотры

Личные инструменты

Навигация

участие

Поиск

Инструменты

Печать/Экспорт