Язык Си в примерах/Степень числа: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Поставил теги <source> |
||
Строка 7: | Строка 7: | ||
Вот программа, которая основана на этой формуле: |
Вот программа, которая основана на этой формуле: |
||
<source lang="c"> |
|||
/* |
/* |
||
Степень числа: простая рекурсия |
Степень числа: простая рекурсия |
||
Строка 26: | Строка 27: | ||
} |
} |
||
} |
} |
||
</source> |
|||
Но есть более «умная» рекурсивная функция: |
Но есть более «умная» рекурсивная функция: |
||
Строка 42: | Строка 43: | ||
первой рекурсией вычисляется за 10000 шагов, а второй -- за 19 шагов. |
первой рекурсией вычисляется за 10000 шагов, а второй -- за 19 шагов. |
||
<source lang="c"> |
|||
/* |
/* |
||
Программа 2: степень числа -- оптимизированная рекурсия. |
Программа 2: степень числа -- оптимизированная рекурсия. |
||
Строка 54: | Строка 55: | ||
return power(x * x, n / 2); |
return power(x * x, n / 2); |
||
} |
} |
||
</source> |
|||
<source lang="c"> |
|||
/* |
/* |
||
Программа 3: cтепень числа -- оптимальный алгоритм без рекурсии. |
Программа 3: cтепень числа -- оптимальный алгоритм без рекурсии. |
||
Строка 75: | Строка 76: | ||
return a; |
return a; |
||
} |
} |
||
</source> |
|||
* Сколько шагов требуется для вычисления <math>a^{30}\,\!</math> вторым |
* Сколько шагов требуется для вычисления <math>a^{30}\,\!</math> вторым |
Версия от 16:12, 5 июня 2007
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате 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));
}
}
Но есть более «умная» рекурсивная функция:
Например, если обозначть стрелочкой слово «сводится к », то при вычислении для первой рекурсии получим цепочку длины 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;
}
- Сколько шагов требуется для вычисления вторым
- Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).
- Объясните, как работает программа 3.