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

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

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

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

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

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

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