Pull to refresh

Однострочники на С++

Programming *C++ *Algorithms *
Sandbox
image
На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке C/С++.
Итак, поехали!

1. Алгоритм Евклида


Рекурсивный алгоритм нахождения наибольшего общего делителя.
int GCD(int a,int b) {
  return b?GCD(b,a%b):a;
}


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 и не требует наличия третей переменой.
void 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?n*fac(n-1):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;
}


11. Числа Мерсенна


Числа Мерсе́нна — числа вида image
int Mersen(int n) {
	return !(n&(n+1));
}


12. Min & Max



int max(int a,int b) {
  return (a>b)?a:b;
}

int min(int a,int b) {
  return (a>b)?b:a;
}


13. Сравнение двух чисел


Функция возвращает значение разницы между двумя числами, поэтому если разница больше 0, то число a больше b, если равна 0, то числа одинаковы, иначе число a меньше b.

template <typename TYPE>
int compare (const TYPE a, const TYPE b){
   return ( a - b );
}


14. Возведение числа 2 в степень n


C помощью сдвига единицы на n битов ми вычислим двойку в степени n.

int pow2(int n) {
  return 1<<n;
}


Однострочники из коментов


Нахождение НОК от Lertmind


int lcm(int a, int b) {
    return (b < 1 ? (b ? lcm(b, a % b) : a) : (a / -lcm(-b, -a % b) * b));
}


Число ненулевых битов в числе от Mrrl


int NBit(unsigned int x){
  return x==0 ? 0 : (x&1)+NBit(x>>1);
}


Максимальная степень двойки, на которую делится n от Mrrl


int MaxDivPow2(int n){
  return n&-n;
}


Сравнение двух чисел от Lertmind


int cmp(int a, int b) {
    return (a < b ? -1 : (a > b ? 1 : 0));
}

или шаблон

template<typename T>
int cmp(const T &a, const T &b) {
    return (a < b ? -1 : a > b);
}


Найти k-й бит в массиве int * (считая, что sizeof(int)==4) от Mrrl


int GetBit(int *a,int k){
  return (a[k>>5]>>(k&31))&1;
}


Жду ещё алгоритмов в коментах…
Tags: однострочникичисла фибоначчистепеньсума цифрфакториалалгорытм Евклидавозведение в степеньнаименьшее общее кратноенаибольший общий делительmaxminбиты
Hubs: Programming C++ Algorithms
Total votes 148: ↑111 and ↓37 +74
Comments 103
Comments Comments 103

Popular right now