Как найти нок программирование

Наименьшее общее кратное

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

На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке 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. Числа Мерсенна

Числа Мерсе́нна — числа вида

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;
}

Жду ещё алгоритмов в коментах…

Задача:

Найти наименьшее общее кратное для всех элементов массива — минимальное число, которое делится на все элементы массива без остатка. Также, найти НОД всех элементов массива.

Решение:

Вот тут приведены алгоритмы расчета НОК и НОД для двух чисел. Ясно, что наиболее эффективный алгоритм расчета НОК двух чисел — это произведение чисел поделить на их НОД. По содержимому статьи ясно что НОК(а1, а2, а3, ... аN) равен НОК(НОК(НОК(А1, А2), А3)..., АN). Таким образом, для расчета НОК массива чисел надо многократно расчитывать НОД двух чисел, реализация этой функции на С++ взята тут.

Реализация на Си (функции чуть-чуть изменены, так как добавлена самописная функция swap):

#include <stdio.h>
#include <stdlib.h>

void read_array(int n, int** values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = ", i);
        scanf("%d", &((*values)[i]));
    }
}

void print_array(int n, int* values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = %dn", i, values[i]);
    }
}

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int gcd(int a, int b) {
    if (a < b) {
        swap(&a, &b);
    }
    while (a % b != 0) {
        a = a % b;
        swap(&a, &b);
    }
    return b;
}

int gcd_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int gcd_value = gcd(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        gcd_value = gcd(gcd_value, values[i]);
    }
    return gcd_value;
}

int lcm(int a, int b) {
    return (a*b)/gcd(a, b);
}

int lcm_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int lcm_value = lcm(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        lcm_value = lcm(lcm_value, values[i]);
    }
    return lcm_value;
}

int main() {
    int n;
    int *values;
    
    printf("n: ");
    scanf("%d", &n);
    
    values = malloc(sizeof(int) * n);
    
    read_array(n, &values);
    
    printf("lcm: %d", lcm_n(n, values));
    
    free(values);
    return 0;
}