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

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

 

/*

Степень числа: простая рекурсия

}

}

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

Правильнее было бы так:

/*

Степень числа: простая рекурсия

}

}

 

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

первой рекурсией вычисляется за 10000 шагов, а второй -- за 19 шагов.

 

/*

Программа 2: степень числа -- оптимизированная рекурсия.

return power(x * x, n / 2);

}

 

/*

Программа 3: cтепень числа -- оптимальный алгоритм без рекурсии.

return a;

}

* Напишите программу, вычисляющую double в степени double.

* Сколько шагов требуется для вычисления <math>a^{30}\,\!</math> вторым методом?

* Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху <math>2\cdot \log_2 n\,\!</math> (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).

* Объясните, как работает программа 3.