На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке С++.
Итак, поехали!
1. Алгорытм Евклида
Рекурсивний алгоритм нахождения наибольшего общего делителя.
int GCD(int a,int b) {return (!b)?a:GCD(b,a%b);}
2. Нахождение НОК
Рекурсивний алгоритм нахождения наименьшего общего кратного.
int LCM(int a,int b) {return a/GCD(a,b) * b;}
3. Проверка числа 2^n
Рекурсивний алгоритм проверки числа на степень 2.
int isPow2(int a) {return !(a&(a-1));}
4. Функция обмена двоих переменных
Этот алгоритм работает при помощи свойства симметричного различия, которым обладает XOR и не требует наличия третей переменой.
int swap(int &a,int &b) {a^=(b^=(a^=b));}
5. Алгоритм возведения в степень
Степень числа за линейное время.
Условие окончания рекурсии: если степень числа равно 0, то a^0=1.
int pow(int a,int n) {return (!n)?1:a*pow(a,n-1);}
6. Индийский алгоритм возведения в степень
Степень числа за логарифмическое время.
int powInd(int a,int n) {return (!n)?1:((n&1)?a:1)*powInd(a*a,n/2);}
7. Факториал числа
Факториал целого неотрицательного числа n.
Условие продолжения рекурсии: факториал ето произведение всех натуральных чисел до n включительно.
Условие окончания рекурсии: если число равно 0, то 0!=1.
int fac(int n) {return (!n)?1:n*fac(n-1);}
8. Сумма цифр числа
Условие продолжения рекурсии: сума цифр числа равна последней цифре плюс сума цифр числа бес последней цифры.
Условие окончания рекурсии: если число равно 0, то и сума цифр равна 0.
int count(int a) {return (!a)?0:(a%10+count(a/10));}
9. Числа Фибоначчи
Числа Фибоначчи — элементы числовой последовательности в которой каждое последующее число равно сумме двух предыдущих чисел.
int fib(int n) {return (n<=2)?1:(fib(n-1)+fib(n-2));}
10. Следующее число Фибоначчи
Функция нахождения чисел Фибоначчи.
int fibNext(int &f1,int &f2) {return f1=(f2+=f1)-f1;}
Жду ещё алгоритмов в коментах…
Автор: Oleksandr17
