Что нового

Article Проект Эйлера. Решение задачи № 5.

Человек Тьмы 0
19.04.2020
28
68
Любую задачу из проекта Эйлера можно решить несколькими способами.
Пятая задача - не исключение.
Первый вариант решения я назвал: Евклид нервно курит в сторонке.
Такой способ предполагает обыкновенный тупой брутфорс.
Я рассуждал следующим образом:
в условии задачи сказано, что самое маленькое число, которое делится без остатка на все числа от 1 до 10 - число 2520.
Следовательно, самое маленькое число, которое делится без остатка на все числа от 1 до 20 - заведомо больше 2520.
Значит, нужно начать проверку всех чисел, которые больше 2520 (делимого): это числа 2521, 2522, 2523 ... и тк далее ... на деление всех делителей от 1 до 20.
Алгоритм следующий:
  1. Если при делении делимого хоть на одно число от 1 до 20 остаток не равен нулю, то это число на роль НОК не годится.
  2. Прибавляем к делимому единицу и проверяем: делится ли оно на все числа от 1 до 20.
  3. Если остаток от такого деления делимого на все числа от 1 до 20 равен нулю, то это число и есть НОК.
Вот как выглядит код этого алгоритма:
Python:
#! /usr/bin/python3
# -*- coding: utf-8 -*-
print(u"2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10. \
Какое самое маленькое число делится нацело на все числа от 1 до 20? ")
nok = 2510
while True:
    if nok % 2 != 0 or nok % 3 != 0 or nok % 4 != 0 or nok % 5 != 0 or nok % 6 != 0 or nok % 7 != 0 or \
nok % 8 != 0 or nok % 9 != 0 or nok % 10 != 0 or nok % 11 != 0 or nok % 12 != 0 or nok % 13 != 0 or \
nok % 14 != 0 or nok % 15 != 0 or nok % 16 != 0 or nok % 17 != 0 or nok % 18 != 0 or nok % 19 != 0 or nok % 20 != 0:
        nok += 1
    else:
        print("Cамое маленькое число, которое делится без остатка на все числа от 1 до 20:  ", nok)
        break
screen02.png


Этот алгоритм является эталоном того, как не нужно решать задачи по двум причинам:
Условие if nok % 2 != 0 or nok % 3 != 0 or nok % 4 != 0 or nok % 5 != 0 or nok % 6 != 0 or nok % 7 != 0 or nok % 8 != 0 or nok % 9 != 0 or nok % 10 != 0 or nok % 11 != 0 or nok % 12 != 0 or nok % 13 != 0 or nok % 14 != 0 or nok % 15 != 0 or nok % 16 != 0 or nok % 17 != 0 or nok % 18 != 0 or nok % 19 != 0 or nok % 20 != 0:
попросту режет глаза каждому программисту. К своему стыду, я не нашёл способа записать это условие более красивым способом.
С точки зрения математики нахождение НОК при помощи грубой силы (брутфорса) - позор для математика. Евклид никогда не открыл своих законов, если бы у него был компьютер. Интересно, последний факт - это хорошо или плохо ? Можно написать в комментариях :)
Тем не менее, алгоритм справляется с задачей.

screen02.png

Cамое маленькое число, которое делится без остатка на все числа от 1 до 20: 232792560


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

screen03.png


НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД) в алгоритме ниже находится при помощи формул Евклида – древнегреческого математика III века до нашей эры.
Суть алгоритма можно изобразить схемой:

screen03.png


Составим программу по принципу, который по-английскиназывается «KISS». (с поцелуями он ничего об-щего не имеет.)
«KISS» — это всего лишь аббревиатура фразы: «Keepit simple, stupid», что в переводе означает: «Делай это проще, дурачок»
Этот принцип призывает нас решать поставленные задачи более простыми методами, прибегая к изощренным алгоритмам и программным средствам только в крайнем случае.

Python:
print(u"Найти НОД двух чисел \"a\" и \"b\": ")
a = int(input(u"a = "))
b = int(input(u"b = "))
def nod(a, b):
    while b > 0:
        a, b = b, a % b
    return a
n0d = nod(a, b)
print(n0d)

Но вернёмся в НОК ( к поекту Эйлера) :


Python:
def nod (a,b):
    while b > 0:
        a,b = b, a % b  # Формула НОД
    return a
def nok (a,b):
    return a*b // nod(a,b) # Нок по формуле а*b // на нод a,b
d = 1                              # В нем будет хранится значение предыдущего НОК
for i in range (2,21):      # Перебераем делители
    d = nok(d,i)                 # Ищем их НОК
print (d)
screen02.png


К счастью, ответ совпадает с первым вариантом )

screen03.png


На этом - всё )
 
Последнее редактирование:
Верх Низ