По време на скорошно интервю за работа ме помолиха да напиша на бяла дъска необходимите процедури, за да получа факториела на число. Първият ми въпрос беше „Какво е факториел?“
Какво е факториел?
Според Уикипедия:
В математиката факториелът на неотрицателно цяло число n, обозначено с n!, е продуктът на всички положителни цели числа по-малки или равни на n.
А!?
Точно! Да, няма смисъл, когато се опитвате да го обясните с думи. Необходим е пример:
Да кажем, че предоставяме числото 4. Ето какво ще се случи:
4 * (4 - 1) = 12 12 * (3 - 1) = 24 24 * (2 - 1) = 24
Така че, както виждате, вие просто вземате числото и го умножавате само по себе си минус едно, след което умножавате резултата по следващото най-малко число, докато първоначалното число накрая стане едно. Последното умножение всъщност не е необходимо, защото знаем, че всичко, умножено по едно, винаги е едно. Включих го само за да стане по-ясно какво се случва.
Както можете да видите, с увеличаването на входното число резултатът нараства експоненциално:
5 * (5 - 1) = 20 20 * (4 - 1) = 60 60 * (3 - 1) = 120 120 * (2 - 1) = 120
След като стигнете до двуцифрените числа, резултатът нараства до над три милиона!
10 * (10 - 1) = 90 90 * (9 - 1) = 720 720 * (8 - 1) = 5,040 5,040 * (7 - 1) = 30,240 30,240 * (6 - 1) = 151,200 151,200 * (5 - 1) = 604,800 604,800 * (4 - 1) = 1,814,400 1,814,400 * (3 - 1) = 3,628,800 3,628,800 * (2 - 1) = 3,628,800
Сглобяване на всичко
Ето какво трябва да се случи, за да разрешите това:
- Уверете се, че въведеното е число.
- Ако е нула, върнете 1 (тъй като очевидно факториелът на 0 винаги е 1).
- Дефинирайте работеща променлива и я заредете с входния номер.
- Повторете, докато намалявате числото, докато стигнем до 1 (можем да излезем по-рано, когато стигнем до 1, защото 1, умножено по нещо, винаги е 1)
Решение
За съжаление, в JavaScript не можете надеждно да получите факториела на нищо, по-голямо от 18, тъй като спецификацията на номера на JavaScript работи само между -9,007,199,254,740,991 и 9,007,199,254,740,991.
Допълнителен кредит! Направете го с рекурсия!
В моята публикация за пермутации говорих много за рекурсия, защото рекурсията е може би най-добрият начин за създаване на списък с всички възможни подреждания на списък. Често рекурсията може да се използва вместо цикъл, защото вместо цикъл вие просто трябва самата функция да се извика отново, като използва резултата.
И така, ето как да направите факториел рекурсивно!
const factorial = (num) => {
if (num === 0) return 1;
return num * factorial(num - 1);
}
да! Това е всичко. Но как е възможно това, питате вие? Е, това е много добър въпрос. Рекурсията е трудна за интуиция, така че ще трябва да я разбием малко.
Да кажем, че се опитваме да получим факториел от 10. Ето какво се случва на практика:
const factorialTEN = () => {
const ten = 10;
const nineFunc = (nine) => {
const eightFunc = (eight) => {
const sevenFunc = (seven) => {
const sixFunc = (six) => {
const fiveFunc = (five) => {
const fourFunc = (four) => {
const threeFunc = (three) => {
const twoFunc = (two) => {
const oneFunc = (one) => {
return one;
}
return two * oneFunc(two - 1);
}
return three * twoFunc(three - 1);
}
return four * threeFunc(four - 1);
}
return five * fourFunc(five - 1);
}
return six * fiveFunc(six - 1);
}
return seven * sixFunc(seven - 1);
}
return eight * sevenFunc(eight - 1);
}
return nine * eightFunc(nine - 1);
}
return ten * nineFunc(ten - 1);
}
factorialTEN се обажда nineFunc който се обажда eightFunc който се обажда sevenFunc който се обажда sixFunc който се обажда fiveFunc който се обажда fourFunc който се обажда threeFunc който се обажда twoFunc който се обажда oneFunc. И вместо да извиква друга функция, oneFunc връща 1, което задейства всичко да се умножава така:
10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
Защо умножението не се случва преди всички извиквания на каскадни функции? Е, причината е свързана с реда на операциите. Начинът, по който работи кодът, е това, което е в скобите, да се изпълнява първо. Така че в случая на factorialTEN имаме десет комплекта вложени скоби, през които да преминем, преди да може да се случи умножение.
Ето го. Направих факториел рекурсивно и ви показах какво се случва.
