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

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

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


  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

Для вычисления функции есть рекуррентная формула:


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

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

Но есть более «умная» рекурсивная функция:

Например, если обозначить стрелочкой слово «сводится к », то при вычислении для первой рекурсии получим цепочку длины 12:

А для второй рекурсии цепочку из 5 шагов:

Для больших n разница в длине цепочки более разительная. В частности первой рекурсией вычисляется за 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;
 }
  • Напишите программу, вычисляющую double в степени double.
  • Сколько шагов требуется для вычисления вторым методом?
  • Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).
  • Объясните, как работает программа 3.