Изчисляване на степени на числа

Въпреки че в JavaScript има вградена функция pow, която изчислява степента на някакво число, можеш да напишеш рекурентно подобна функция, която да е много ефективна. Единствената уловка е, че степенният показател трябва да бъде цяло число.

Да предположим, че искаш да изчислиш $x^n$x, start superscript, n, end superscript, където $x$x е всяко реално число, а $n$n е всяко цяло число. Лесно е, ако $n$n е 0, тъй като $x^0 = 1$x, start superscript, 0, end superscript, equals, 1 без значение колко е $x$x. Това е добър основен случай.

Да видим какво се случва, когато $n$n е положително. Да започнем, като си припомним, че, когато умножаваш степените на $x$x, събираш степенните показатели: $x^a \cdot x^b = x^{a+b}$x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript за всяка основа $x$x и всеки степенен показател $a$a и $b$b. Следователно, ако $n$n е положително и четно число, тогава $x^n = x^{n/2} \cdot x^{n/2}$x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. Ако искаш да изчислиш $y = x^{n/2}$y, equals, x, start superscript, n, slash, 2, end superscript рекурентно, тогава можеш да изчислиш $x^n$x, start superscript, n, end superscript като $y \cdot y$y, dot, y. Ами ако $n$n е положително и нечетно число? Тогава $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, а $n-1$n, minus, 1 е 0 или положително и четно. Току що видяхме как да изчислим степените на $x$x, когато степенният показател е 0 или положително четно число. Следователно можеш да изчислиш рекурентно $x^{n-1}$x, start superscript, n, minus, 1, end superscript, а след това да използваш резултата, за да изчислиш $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.

Ами ако $n$n е отрицателно? Тогава $x^n = 1 / x^{-n}$x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript и степенният показател $-n$minus, n е положителен, тъй като е отрицание на отрицателно число. Така че можеш да изчислиш $x^{-n}$x, start superscript, minus, n, end superscript рекурентно и да вземеш реципрочното му число.

Като вземем предвид тези неща, получаваме следния рекурсивен алгоритъм за изчисляването на $x^n$x, start superscript, n, end superscript:

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.