Делители числа

Задачи 2 – 3. Расщепление числа. Обращение числа

Эти задачи принципиально не отличаются от задачи 1. Никаких новых алгоритмических решений здесь нет. Задача расщепления предполагает создание массива цифр. Такая задача возникает, например, при реализации алгоритма игры "Быки и коровы". Но разделять число на цифры необходимо было и при переводе чисел из одной системы счисления в другую.

Построим функцию Split, которая создает массив цифр для заданного целого числа N. Вот ее возможный код:

        /// <summary>
        /// Расщепление целого числа
        /// и создание массива цифр
        /// </summary>
        /// <param name="N">целое число</param>
        /// <returns>массив цифр числа N</returns>
        public static int[] Split(int N)
        {
            int k = N.ToString().Length;    //число цифр
            int[] res = new int[k];         //результат
            int digit;                      //текущая цифра
            for(int i = k-1; i >= 0; i--)
            {
                digit = N % 10;     //младшая цифра
                res[i] = digit;     //в конец массива
                N = N / 10;         //отрезаем цифру
            }
            return res;
        }

Алгоритм почти совпадает с переводом десятичного числа в систему с основанием p. Следует обратить внимание на два момента. Первый предварительно нужно создать массив, в котором будут храниться цифры числа N, а число цифр нужно как-то определить. Здесь применяется прием перевода числа в строку, для которого есть функция length, возвращающая длину строки.

Второй момент, который неоднозначно решается, куда помещать старшую цифру, - в начало или в конец массива. У нас старшая цифра помещается в первый элемент массива с индексом ноль.

Упражнение. Напишите функцию intlength, возвращающую число цифр целого числа.

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

        /// <summary>
        /// Реверс числа: 123 => 321
        /// </summary>
        /// <param name="N">исходное число</param>
        /// <returns>обращенное число</returns>
        public static int Reverse(int N)
        {
            int res = 0;        //результат
            int digit;          //текущая цифра
            while(N != 0)       //пока есть цифры
            {
                digit = N % 10;         //младшая цифра
                res = res * 10 + digit; //становится старшей
                N = N / 10;             //отрезаем цифру
            }
            return res;             //возвращаем результат
        }

Палиндромом называется число, которое одинаково читается слева направо и справа налево. Имея функцию Reverse, решение этой задачи дается в одну строчку:

        /// <summary>
        /// Является ли число палиндромом
        /// </summary>
        /// <param name="N">исходное число</param>
        /// <returns>true, если палиндром</returns>
        public static bool IsPalindrom (int N)
        {
            return Reverse(N) == N;
        }

Задачи 4-5-6. Делители числа

Числа могут обладать некоторыми свойствами. Одним из простых свойств числа –это свойство четности. Число четное, если оно делится на два без остатка. Нетрудно написать функцию в одну строчку:

Работа у доски

        /// <summary>
        /// Является ли число четным
        /// </summary>
        /// <param name="N">исходное число</param>
        /// <returns>true, если четно</returns>
        public static bool IsEven(int N)
        {
            return N % 2 == 0;
        }

Если N без остатка делится на 2, то число четное. Это утверждение справедливо как для положительных, так и для отрицательных целых чисел. А как определить, что число является нечетным?

Работа у доски

        /// <summary>
        /// Является ли число нечетным
        /// </summary>
        /// <param name="N">исходное число</param>
        /// <returns>true, если нечетно</returns>
        public static bool IsOdd(int N)
        {
            //return N % 2 == 1; //Ошибка, если N < 0
            return N % 2 != 0;
        }

Заметьте, правильное определение дается второй строчкой. Определение, данной в первой закомментированной строчке, корректно только для положительных целых.

Определение четности – это частный случай задачи определения того, является ли число d делителем числа N. Понятно, что и определение этого более общего свойства дается функцией в одну строчку:

Работа у доски

        /// <summary>
        /// Является ли число d делителем числа N
        /// </summary>
        /// <param name = "d">кандидат в делители</param>
        /// <param name="N">исходное число</param>
        /// <returns>true, если d делитель N</returns>
        public static bool IsDivisor(int d, int N)
        {
            return N % d == 0;
        }

Двойственным (дополняющим) понятием по отношению к понятию делитель числа является определение кратного числа. Число N кратно числу d, если d – делитель N. В учебнике Виленкина большой раздел посвящен делителям и кратным числам.

Рассмотрим более сложную задачу – нахождение всех делителей числа N. Имея компьютер, эту задачу решить несложно, перебирая все возможные варианты. Сколько делителей может быть у целого числа N? Минимум 2. Делителями любого числа N являются числа 1 и N.

А каково максимальное число делителей? Число делителей всегда четно. Если d – делитель N, то у d есть напарник – b, такой что N = d * b. Пусть в паре (d, b) – d минимальный сомножитель ($$$d\leq b$$$). Тогда максимально возможное значение d не превосходит $$$\sqrt{N}$$$. Отсюда следует, что максимальное число делителей не больше $$$2\sqrt{N}$$$.

Поскольку число делителей может варьироваться в широких пределах, то для хранения делителей удобно использовать не массив, а динамическую структуру данных, называемую списком, в которой число элементов не фиксируется в момент создания, как это принято у массивов, а динамически меняется при добавлении элементов в список или при их удалении. Со списками мы частично знакомы, поскольку в Windows формах использовали аналогичный элемент управления – список (ListBox).

Рассмотрим код функции, которая находит все пары делителей числа N:

        /// <summary>
        /// Найти все делители числа N
        /// </summary>
        /// <param name="N">исходное число</param>
        /// <returns>список всех пар - делителей N N</returns>
public static List<int> AllDivisors(int N)
        {
            // список - новая структура данных
            List<int> list = new List<int>();
            int n = (int)Math.Sqrt(N); //n - граница перебора кандидатов в делители
            list.Add(1);
            list.Add(N);    //обязательная пара делителей
            int b;
            for(int d = 2; d <= n; d++) //цикл перебора кандидатов
                if (IsDivisor(d, N))    //фильтр кандидатов
                {
                    list.Add(d);    //добавление пары, прошедшей фильтр 
                    b = N / d;
                    list.Add(b);
                }
            return list;
        }

Код снабжен подробными комментариями.

Число N, у которого только одна пара делителей (1, N), которое делится только на единицу и само на себя, называется простым. Число, у которого есть хотя бы одна пара делителей (d, b), отличных от единицы и N, называется составным.

Если число простое, то у него есть один простой делитель – само число N. Если число составное, то его можно представить в виде произведения всех его простых делителей:

Докажем это утверждение. Наше доказательство будет конструктивным, позволяя сформулировать алгоритм поиска всех простых делителей числа N. Также, как и в предыдущем алгоритме, начнем поиск с нахождения пары делителей числа N (d, b), где d – минимальный делитель числа N. Справедливо утверждение:

d - минимальный делитель числа N, больший 1, является простым числом.

Доказательство от противного.

Предположим, что d составное число, тогда существует пара (p, q), такая, что d = p * q , p<d и p – делитель d. Но, если p – делитель d, а d - делитель N, то p – делитель N, меньший чем d. Пришли к противоречию с утверждением, что d – минимальный делитель. Значит наше предположение, что d – составное число неверно и d является простым числом.

Применим этот же алгоритм нахождения минимального делителя к делителю b из пары (d, b). Найденный простой делитель b будет являться следующим по возрастанию простым делителем N. Продолжая этот процесс, пока очередной элемент пары не станет равным 1, получим все простые делители числа N. По построению произведение всех найденных делителей дает число N.

Рассмотрим функцию, определяющую минимальный делитель d числа N, больший единицы:

        /// <summary>
        /// Нахождение минимального простого делителя - d
        /// числа N = d * b
        /// </summary>
        /// <param name="N">исходное число</param>
        /// <returns>d - минимальный делитель или -1 для простого числа</returns>
        public static int MinDivisor(int N)
        {
            if (IsDivisor(2, N))    //если есть четный делитель 2
                return 2;
            int n = (int)Math.Sqrt(N); //поиск нечетного делителя
            for (int d = 3; d <= n; d += 2)
                if (IsDivisor(d, N))
                    return d;
            return -1;
        }

Теперь напишем функцию, которая находит все простые делители числа N:

        /// <summary>
        /// все простые делители N
        /// </summary>
        /// <param name="N">данное число</param>
        /// <returns>список простых делителей N</returns>        
       public static List<int> PrimeDivisors(int N)
        {
            List<int> list = new List<int>();
            bool exist_divisor = true;
            int d = 0;
            while (exist_divisor)
            {
                d = MinDivisor(N); //минимальный делитель
                if (d != -1)         //N - составное число
                {
                    list.Add(d); N /= d;
                }
                else
                {                       // N - простое число
                    if(N != 1) list.Add(N);
                    exist_divisor = false;
                }
            }
            return list;
        }

Работа в классе

Построить проект Divisors, используя приведенные выше методы:

Домашняя работа

Написать функцию:

bool IsPerfect(int N)

возвращающую true, если N – совершенное число – число, равное сумме всех его делителей за исключением самого числа. Первым совершенным числом является число 6 (6 = 1 +2 +3), следующим – число 28.

Указания: Вызвав функцию AllDivisors, можно получить список всех делителей. Свойство Count позволяет определить число элементов списка. В цикле по числу элементов можно найти сумму всех делителей кроме самого числа, что дает решение задачи. К элементам списка можно получать доступ по индексу также, как и для массивов.