4. Примеры оптимизированных алгоритмов. Алгоритм Евклида. Решето Эратосфена.

Примеры оптимизированных алгоритмов.

Алгоритмизация – это не только генерация уникальных и гениальных идей. Очень часто для того, чтобы решить конкретную задачу, не надо изобретать велосипед. Старайтесь познакомиться с огромным количеством придуманных ранее алгоритмов и просто пробуйте «приложить» каждый из них к данной задаче. Во многих случаях это поможет сэкономить очень много времени и сил. Но это не значит, что взяли готовое решение и все! На самом деле сначала надо увидеть, какой алгоритм вам подойдет, в чем его преимущества и недостатки именно для решения данной задачи, выбрать, а потом еще и оптимизировать под конкретный случай.

Но давайте рассмотрим несколько примеров алгоритмов, которые, несмотря на их «математичность», очень часто помогают при решении реальных задач.

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

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Был описан примерно за 300 лет до нашей эры.

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

Самый простой пример из школьной математики: на какое максимальное число можно сократить дробь a/b.

Алгоритм нахождения НОД вычитанием

Из большего числа вычитаем меньшее.

Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).

Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18.

30 - 18 = 12

18 - 12 = 6

12 - 6 = 6

6 - 6 = 0

Конец: НОД – это уменьшаемое или вычитаемое.

НОД (30, 18) = 6

Код программы:

Console.WriteLine("Введите числитель дроби:");
int a = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите знаменатель дроби:");
int b = Convert.ToInt32(Console.ReadLine());
while (a != b)
{
    if (a > b)
    {
        a -= b;
    }
    else
    {
        b -= a;
    }
}

Console.WriteLine("НОД=" + a);

Алгоритм нахождения НОД делением (более быстрый)

Большее число делим на меньшее.

Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).

Если есть остаток, то большее число заменяем на остаток от деления.

Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18.

30 / 18 = 1 (остаток 12)

18 / 12 = 1 (остаток 6)

12 / 6 = 2 (остаток 0)

Конец: НОД – это делитель 6.

НОД (30, 18) = 6

Код программы:

Console.WriteLine("Введите числитель дроби:");
int a = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите знаменатель дроби:");
int b = Convert.ToInt32(Console.ReadLine());
while (a != 0 && b != 0)
{
    if (a > b)
    {
        a = a % b;
    }
    else
    {
        b =b % a;
    }
}

Console.WriteLine("НОД=" + (a + b));

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

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

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

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 2, второе простое число - это 3. Теперь начнем рассуждать:

Все четные числа, кроме двойки, - составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.

Все числа кратные трем, кроме самой тройки, - составные, так как делятся не только на самих себя и единицу, а также еще на 3.

Число 4 уже выбыло из игры, так как делится на 2.

Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.

Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Последний пункт вытекает из того, что сложные числа всегда можно записать как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

Код программы:

Console.WriteLine("Введите число n:");
int n = Convert.ToInt32(Console.ReadLine());

bool[] numbers = new bool[n + 1];
numbers[0] = true;

for (int i = 2; i < numbers.Length; i++)
{
    if (!numbers[i])
    {
        int j = 2 * i;
        while (j < numbers.Length)
        {
            numbers[j] = true;
            j += i;
        }
    }
}

for (int i = 0; i < numbers.Length; i++)
{
    if (!numbers[i])
    {
        Console.Write(i + " ");
    }
}
Console.WriteLine();

Вопросы к размышлению:

А можно ли хоть немного ускорить этот алгоритм? Если да, то как?

Итоги занятия