About Teletype
Join
@senior_py
January 22, 2024

Алгоритмы

1. Решето Эратосфена

Решето Эратосфена — самый простой и известный алгоритм для поиска простых чисел. Его суть состоит в следующем: Выписываем числа 2, 3, ..., N; Берем первое число в списке $p=2$ и вычеркиваем из списка все числа, кратные ему, начиная с $p^2$: 4, 6, 8, ... Берем следующее число в списке $p=3$ и вычеркиваем кратные ему 9, 15, ... Продолжаем процедуру для каждого последующего числа из оставшихся в списке $p=5, 7, 11, ...,$ пока выполняется неравенство p^2 <= sqrt{N}; оставшиеся после этого в списке числа и будут простыми:

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 
 
void sieveOfEratosthenes(int n) { 
    bool* prime = malloc((n + 1) * sizeof(bool)); 
    for (int i = 2; i <= n; i++) { 
        prime[i] = true; 
    } 
 
    for (int p = 2; p * p <= n; p++) { 
        if (prime[p] == true) { 
            for (int i = p * p; i <= n; i += p) { 
                prime[i] = false; 
            } 
        } 
    } 
 
    printf("%d: ", n); 
    for (int p = 2; p <= n; p++) { 
        if (prime[p]) { 
            printf("%d ", p); 
        } 
    } 
    free(prime); 
}

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

Алгоритм Евклида позволяет найти нам наибольший общий делитель чисел. Как это работает: Пусть a = 18, b = 30. Цикл: a!=0 and b!=0 Если a > b, то a = a % b, если меньше, то b = b % a, таким образом мы сначала находим остаток деления, а потом повторяем действия. У нас a < b, значит, ищем остаток деления b % a (30 % 18) = 12, присваиваем b = 12, повторяем цикл но теперь у нас уже a > b(b = 12) значит выполняем a % b (18 % 12) = 6? снова переходим к циклу, теперь снова b > a, значит выполняем b % a (30 % 6), остаток от деления 0, на этом мы прекращаем наш цикл и узнаем, что наибольший общий делитель 18 и 30 = 6. и выводим a + b (b = 0, a = 6).

a = 18 
b = 30 
  
while a!=0 and b!=0: 
    if a > b: 
        a = a % b 
    else: 
        b = b % a 
 
int gcd(int a, int b) { 
   int c; 
   while (b) { 
      c = a % b; 
      a = b; 
      b = c;         
   } 
   return abs(a); 
 }


int euclideanGCD(int a, int b) {    
     if (b == 0) {
        return a; // В случае, если второе число равно 0, то первое число и есть наибольший общий делитель    
     } else {
        return euclideanGCD(b, a % b); // Рекурсивный вызов функции с новыми параметрами    
     }
}

Рекурсивные алгосы

Возведение в степень

2^5 <-> 2 * 2^4 <-> 2 * 2^3 <-> 2 * 2^2 <-> 2*2^1 <-> 2*2^0

double power(double base, int exponent) {
    if (exponent < 0) {
        return 1 / power(base, -exponent);
    }
    if (exponent == 0) {
        return 1;
    }
    else {
        return base * power(base, exponent - 1);
    }
}

Факториал

unsigned long long factorial(int n) {
    if (n == 0) {
        return 1; // Факториал 0 равен 1
    }
    else {
        return n * factorial(n - 1);
    }
}

Фибоначчи

код неэффективен для больших значений n. Рекурсивное вычисление Фибоначчи имеет экспоненциальную сложность времени выполнения из-за повторного вычисления тех же чисел многократно. Для более больших значений n будет необходимо использовать более эффективные алгоритмы, такие как итеративные или алгоритмы с запоминанием промежуточных результатов.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Реализация с использованием цикла

В этом алгоритме используется свойство, что для определения следующего числа Фибоначчи используются только два предыдущих значения.

Алгоритм при этом будет следующий

  • Ввести номер N определяемого элемента.
  • Проинициализировать два первых элемента a и b значениями 1, и если N<=2 вывести 1
  • Выполнять нижеследующие действия N-2 раза
    • Сложить a и b, присвоив результат третьей переменной c.
    • Поменять начальные значения: a = b, b = c
  • Вывести значение b.
#include <stdio.h>
int main()
{
    int N;
    printf("N="); // вводим число N
    scanf("%d", &N);
    int a = 1, b = 1, c;
    if (N <= 2) // Первые два числа (a и b) равны 1
        printf("1 ");
    else
    {
        for (int i = 3; i <= N; i++)
        {
            c = a + b; // вычисляем следующее число как сумму двух предыдущих
            a = b; b = c; // перемещаем два предыдущих числа
        }
        printf("%d ", b); // выводим последнее число
    }
    getchar(); getchar();
    return 0;
}

Сортировка подсчетом

Главная идея алгоритма — посчитать, сколько раз встречается каждый элемент в массиве, а потом заполнить исходный массив результатами этого подсчёта. Для этого нам нужен вспомогательный массив, где мы будем хранить результаты подсчёта. Даже если нам надо отсортировать миллион чисел, мы всё равно знаем диапазон этих чисел заранее, например, от 1 до 100. Это значит, что во вспомогательном массиве будет не миллион элементов, а сто.

В общем виде всё работает так:

  1. Мы создаём вспомогательный массив и на старте заполняем его нулями.
  2. Проходим по всему исходному массиву и смотрим очередное значение в ячейке.
  3. Берём содержимое этой ячейки и увеличиваем на единицу значение вспомогательного массива под этим номером. Например, если мы встретили число 5, то увеличиваем на единицу пятый элемент вспомогательного массива. Если встретили 13 — тринадцатый.
  4. После цикла во вспомогательном массиве у нас хранятся данные, сколько раз встречается каждый элемент.
  5. Теперь мы проходим по вспомогательному массиву, и если в очередной ячейке лежит что-то больше нуля, то мы в исходный массив столько же раз отправляем номер этой ячейки. Например, в первой ячейке вспомогательного массива лежит число 7. Это значит, что в исходный массив мы отправляем единицу 7 раз подряд.
#include <stdio.h>

void countingSort(int array[], int size) {
    int output[size + 1];
    int max = array[0];

    for (int i = 1; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }

    int count[max + 1];
    for (int i = 0; i <= max; ++i) {
        count[i] = 0;
    }

    for (int i = 0; i < size; i++) {
        count[array[i]]++;
    }

    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

int main() {
    int array[] = { 4, 2, 2, 8, 3, 3, 1 };
    int size = sizeof(array) / sizeof(array[0]);
    countingSort(array, size);
    printf("Отсортированный массив: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

1. Находим максимальное значение во входном массиве.

Cint max = array[0];
    
for (int i = 1; i < size; i++) {
    if (array[i] > max) {
        max = array[i];
    }
}

Здесь мы просто находим максимальное значение в массиве, что позволит нам определить размер временного массива count. 2. Создаем временный массив count размером max + 1 и заполняем его нулями.

Cint count[max + 1];
for (int i = 0; i <= max; ++i) {
    count[i] = 0;
}

Здесь мы создаем массив count, который будет использоваться для подсчета количества каждого элемента во входном массиве. 3. Проходим по входному массиву и увеличиваем соответствующий элемент в массиве count.

Cfor (int i = 0; i < size; i++) {
    count[array[i]]++;
}

Здесь мы проходим по входному массиву и увеличиваем соответствующий элемент в массиве count. Таким образом, массив count будет содержать количество каждого элемента. 4. Пройдем по массиву count и преобразуем его так, чтобы он содержал количество элементов, меньших или равных текущему элементу.

Cfor (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
}

В этом шаге мы обновляем значения массива count, чтобы он содержал количество элементов, меньших или равных текущему элементу. 5. Создаем выходной массив output.

Cint output[size + 1];

Мы создаем временный массив output, который будет содержать отсортированные элементы. 6. Проходим по входному массиву в обратном порядке, помещая каждый элемент на правильную позицию в выходном массиве, уменьшая значение в массиве count.

Cfor (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
}

Здесь мы проходим по входному массиву в обратном порядке и помещаем каждый элемент на правильную позицию в массив output, уменьшая соответствующее значение в массиве count. 7. Помещаем отсортированные элементы из массива output обратно в исходный массив.

Cfor (int i = 0; i < size; i++) {
    array[i] = output[i];
}

И, наконец, мы копируем отсортированные элементы из массива output обратно в исходный массив.

Сортировка выбором

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

Проходимся до n-1 по массиву, находим минимальное значение, записываем его индекс. Меняем местами значения текущего элемента (arr[i]) и минимального элемента (arr[min_idx]). Дальше все будет по новой от следующего элемента i

Сдвиг массива

Циклический

void shiftArray(int arr[], int n, int shift) {
    if (shift > 0) {
        // Сдвиг вправо
        for (int i = 0; i < shift; i++) {
            int temp = arr[n - 1];
            for (int j = n - 1; j > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[0] = temp;
        }

Запоминаем последний элемент в временную переменную, сдвигаем все элементы вправо проходом по массиву от конца к началу, и записываем в начало массива значение из временную переменной
так делаем столько раз, на сколько элементов надо сдвинуть массив

Нециклический

void shiftArray(int arr[], int n, int k) {
    for (int i = 0; i < n - k - 1; i++) {
        arr[i] = arr[i + k];
    }
}

Ввод int arr[] = { 1, 2, 3, 4, 5 };
Вывод 3 4 3 4 5

@senior_py
January 22, 2024, 13:39
0 views
0 reactions
0 replies
0 reposts