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

Понимание алгоритма:
Ключ к пониманию алгоритма заключается в распознавании существования циклов в процессе преобразования числа в соответствии с заданными правилами. Давайте пройдемся по шагам, чтобы получить ясность:

  1. Начиная с числа А, мы вычисляем сумму квадратов его цифр.
  2. С помощью этого преобразования мы получаем еще одно число B.
  3. Из B мы продолжаем применять то же преобразование, и в конце концов мы снова встретимся с B, образуя цикл.

Например, рассмотрим число 4: 4² = 16: 1² + 6² = 37: 3² + 7² = 58: 5² + 8² = 89: 8² + 9² = 145: 1² + 4² + 5² = 42: 4² + 2² = 20. : 2² + 0² = 4

Обратите внимание, что мы снова достигли числа 4, завершив цикл.

Применение алгоритма обнаружения цикла Флойда:
Для обнаружения наличия цикла мы можем использовать алгоритм Обнаружение цикла Флойда. . Концепция проста, но мощна:

  1. Инициализируйте два указателя, медленный указатель и быстрый указатель.
  2. Медленный указатель перемещает числа по одному шагу за раз, а быстрый указатель перемещается по два шага за раз.
  3. Если есть цикл, быстрый указатель в конечном итоге догонит медленный указатель.

В контексте алгоритма счастливых чисел мы можем использовать эту технику для определения повторяющегося цикла в преобразованиях. Вот как мы можем реализовать это на C++:

#include <iostream>

class Solution {
public:
    bool isHappy(int n) {
        int slow = n, fast = n;

        do {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        } while (slow != fast);

        return slow == 1;
    }

private:
    int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
};

Для тех, кто ищет дополнительные сведения о реализации алгоритма, рекомендуется изучить следующую ссылку на GitHub.

Пояснение к коду:

  1. Функция isHappy принимает целое число n в качестве входных данных и возвращает логическое значение, указывающее, является ли n счастливым числом или нет.
  2. Мы инициализируем медленные и быстрые указатели на заданное число n.
  3. Используя цикл do-while, мы вычисляем сумму квадратов цифр медленных и быстрых указателей. Медленный указатель перемещается на один шаг за раз, а быстрый указатель перемещается на два шага за раз.
  4. Если есть цикл, быстрый указатель в конечном итоге догонит медленный указатель. Мы проверяем это условие в цикле do-while.
  5. Наконец, мы возвращаем, достиг ли медленный указатель числа 1, указывая, что n является счастливым числом.

Заключение.
Применяя алгоритм обнаружения циклов Флойда к проблеме счастливых чисел, мы можем эффективно идентифицировать циклы и определять, является ли данное число счастливым числом или нет. Этот алгоритм обеспечивает элегантное и эффективное решение проблемы, используя свойства циклов в процессе преобразования. Используя пример кода на C++, вы можете легко реализовать и изучить этот алгоритм.