На нескольких заданиях отрабатываются навыки нахождения наибольшего общего делителя двух и более натуральных чисел и нахождения взаимно простых чисел по курсу «Виленкин Н. Я. и др. Математика. 6 класс» и «Тарасенкова Н. Я. и др. Математика. 6 класс». Рассматривается исторический материал по нахождению наибольшего общего делителя чисел, на примере объясняется применение алгоритма Евклида.. #6классРешениеЗадач #НОД #НаибольшийОбщийДелитель. Видеоурок по данной теме: https://youtu.be/oUiN9i0dU24
НОД (наибольший общий делитель) натурального числа.. Поддержать Проект: http://donationalerts.ru/r/valeryvolkov. Мои занятия в Скайпе: https://vk.com/id224349278. Новая Группа ВКонтакте: https://vk.com/volkovvalery. Взаимно простые числа. Математика 5-6 классы. Урок 13.
МАТЕМАТИКА 6 класс все темы https://www.youtube.com/playlist?list=PLBnDGoKqP7bZwkO0fuskEmR5fqfyk8peR. РЕШЕНИЕ задач и ПРИМЕРОВ https://vk.com/club49102005. На этом видео уроке по математике для 6 класса объясняется как находить наибольший общий делитель НОД нескольких чисел раскладывая их на простые множители, решаются примеры на нахождение наибольшего общего делителя трех чисел из учебников Виленкин и Мерзляк.. #физикаОГЭматематикаЕГЭ #математика6класс #НОД
В данном уроке мы решим задачу нахождения НОД несколькими методами. Рассмотрим. два метода Евклида: метод вычитания и метод деления;. бинарный алгоритм;. и так же реализуем данную задачу через рекурсию.. Задача №12: Найти наибольший общий делитель двух чисел.. Мой сайт: http://themrden3d.ucoz.ru/. Шаблон INTRO взят с сайта: http://www.varebux.ru
https://stepik.org/course/63085/promo. Записывайся на мой курс на Stepic, где найдешь много практических задач. Стать спонсором канала и получить доступ к дополнительным материалам по Python. https://www.youtube.com/channel/UCMcC_43zGHttf9bY-xJOTwA/join. https://boosty.to/egoroff_channel. https://www.patreon.com/artem_egorov. http://egoroffartem.pythonanywhere.com/course/python/algoritm-evklida. Узнаем как с помощью цикла while найти НОД ( Наибольший общий делитель).. Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.. Для этого нам понадобится реализовать алгоритм Евклида.. . Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.. Задача НОД. http://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=36&id_problem=198. Задача НОК. http://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=36&id_problem=199. http://egoroffartem.pythonanywhere.com/course/python/20. Подробная информация об этом уроке. Все видео этого курса можете найти на сайте. http://egoroffartem.pythonanywhere.com/course/python. или в Вк. https://vk.com/videos-177962775?section=album_1. Если кому нужна помощь, предлагаю индивидуальные занятия. Подробнее пишите в личку в вк. https://vk.com/artem_egoroff. https://vk.com/python.study. В данном группе можете найти информацию о новых видео и задать вопросы
☀Сайт Puzzle English находится здесь: https://bit.ly/34eEfFD. ✏Видеоурок №4 по математике для 6 класса. Онлайн обучение. Математика это просто.. Тема урока: Общий делитель нескольких чисел. Наибольший общий делитель.. Цель урока: Повторение, обобщение и систематизация знаний и умений учащихся 6-х классов. Подготовка к изучению курса математики 7-го класса.. Содержание урока: 1. Общие делители нескольких чисел.. 2. Как найти наибольший общий делитель (НОД).. 3. Взаимно простые числа.. 4. Решение примеров.. Домашнее задание к уроку находится здесь: https://math-helper.net/elementarnaya-matematika/obshhij-delitel-neskolkih-chisel-urok-4. Таблица простых чисел находится здесь: https://math-helper.net/elementarnaya-matematika/razlozhenie-chisel-na-prostye-mnozhiteli-prostye-i-sostavnye-chisla-urok-3. Урок №3 находится здесь: https://youtu.be/i0D7t4o4jTE. ✮✮✮. Хотите отблагодарить? Вот реквизиты: https://www.donationalerts.com/r/videouroki. ✮✮✮. Смотрите все уроки курса «Учимся решать задачи по математике для 6 класса» подряд: https://www.youtube.com/playlist?list=PLk91qesJngSLXu0Hzr9-8OfOZlJJrU7Yu
a, b, n = map ( int, input ().split () ) a1 = a b1 = b n1 = n f = 0 while n!= 0: while a1 > 0 and n!= 0: n1, a1 = a1, n1 % a1 n = n n1 if n = 0 and f!= 1: f = 1 print ( 0 ) a1 = a n1 = n while b1 > 0 and n!= 0: n1, b1 = b1, n1 % b1 n = n n1 if n = 0 and f!= 1: f = 1 print ( 1 ) b1 = b n1 = n
n, m = map ( int, input ().split () ) # n-друзья m-апельсины m = m % n c = n * m d = m * 1 if m = 0: print ( 1 ) else: while m > 0: n, m = m, n % m print ( int ( c / n / d ) )
Есть другой алгоритм на основе остатков: с=ав+q, q>0. НОД(c%в; в), а>в, % находит остаток от деления, т.е. находит q. 2^40-1=(2^30-1)*2^10+q. (2^10+1)*(2^30-1) уже больше чем 2^40-1, поэтому и взяли 2^10. Отсюда q=2^10-1. НОД(2^10-1; 2^30-1); НОД[(2^30-1)%(2^10-1); 2^10-1]; НОД[0; 2^10-1] -> 0 на что угодно делится, т.е. наш ответ 2^10-1.
1) 2^40 1 = 1 + 2 +… + 2^39 = А 2^30 1 = 1 + 2 +… + 2^29 = B А= B + 2^30 +… + 2^39 поэтому A= B + 2^30. (2^10 -1) 2) 2 н е может делить А (1= 1+2(1+ 2^38)), ни 2^2, ни 2^3, и.т.д. 2 н е может делить B, ни 2^2, ни 2^3, и.т.д. 3) общий делитель делит 2^30. (2^10 -1) и он не равно 2, 2^2, и.т.д. 4) НОД делит (2^10 -1) = 1023 = 3.11.31 поэтому НОД = 3, 11, 31, 3.11, 3.31,11.31 или 1023. 5) A = 1023.(1+2^10+2^20+2^30) B = 1023.(1+2^10+2^20) 6) НОД = 1023
Решил немного по-другому. Сначала заметил, что оба числа делятся на 2^10-1 (как разность кубов и разность чисел 4-ой степени), разделил их, и доказал что получившеися числа являются взаимно простыми числами.
Нашел задачу в разделе практика под названием ‘1.А.Эпическая Игра’, накатал индусский код, уверенности в ее правильности нет. Но все же поделюсь решением. Если у кого-нить есть решения, с радостью готов глянуть. Для наглядности изменил вывод ответов для понимания
a1=a=int(input()) #В цикле переменная меняет значения, использовал a=a1(b=b1, n=n1)для возврата исх. значения. b1=b=int(input()) n1=n=int(input()) while n1>=0:
while n>0: a,n=n,a%n if n1-a<0: print(‘Выиграл АНТИСЕМЕН’) break n1=n1-a n=n1 a=a1
while n>0: b,n=n,b%n if n1-b<0: print(‘Выиграл СЕМЕН’) break n1=n1-b n=n1 b=b1
Получается что для степеней простого числа A (в данном случае A=2) НОД(A^n-1, A^m-1) = A^НОД(n, m)-1. Разность степеней приводит к тому что за скобку будет выноситься А^m, а в скобках будет оставаться (A^(n-m) 1), в результате чего имеем тот же алгоритм Евклида для показателей степеней. Для примера: НОД(2^50-1, 2^35-1) = 2^НОД(50, 35)-1, или 2^5-1.
Приносим свои извинения. При решении четвертой задачи была допущена ошибка на 10 мин 46 сек. Вместо слов «45 делится на 5, например, 15 делится на 5» следует понимать «45 делится на 5, будет 9, делится на 3». Как следствие, на 11 мин 21 сек вместо строки «360 = 2 * 2 * 2 *3 *5 *5» следует понимать «»360 = 2 * 2 * 2 *5 *3 *3».
https://codeforces.com/problemset/problem/119/A
Эпическая игра
a, b, n = map ( int, input ().split () )
a1 = a
b1 = b
n1 = n
f = 0
while n!= 0:
while a1 > 0 and n!= 0:
n1, a1 = a1, n1 % a1
n = n n1
if n = 0 and f!= 1:
f = 1
print ( 0 )
a1 = a
n1 = n
while b1 > 0 and n!= 0:
n1, b1 = b1, n1 % b1
n = n n1
if n = 0 and f!= 1:
f = 1
print ( 1 )
b1 = b
n1 = n
https://acmp.ru/index.asp?main=task&id_task=394
Апельсины
n, m = map ( int, input ().split () ) # n-друзья m-апельсины
m = m % n
c = n * m
d = m * 1
if m = 0:
print ( 1 )
else:
while m > 0:
n, m = m, n % m
print ( int ( c / n / d ) )
Есть другой алгоритм на основе остатков: с=ав+q, q>0. НОД(c%в; в), а>в, % находит остаток от деления, т.е. находит q. 2^40-1=(2^30-1)*2^10+q. (2^10+1)*(2^30-1) уже больше чем 2^40-1, поэтому и взяли 2^10. Отсюда q=2^10-1. НОД(2^10-1; 2^30-1); НОД[(2^30-1)%(2^10-1); 2^10-1]; НОД[0; 2^10-1] -> 0 на что угодно делится, т.е. наш ответ 2^10-1.
Эпическая игра.
import math
a,b,n = map(int,input().split())
khodov=0
while n>0:
n=n-math.gcd(a,n)
a,b = b,a
khodov=khodov+1
if khodov%2=0:
print(1)
else:
print(0)
В примечании к задаче нам намекают на использование матовского gcd(x,y). Так получается менее громоздкий код.
Теорема (алгоритм Евклида). ∀a,b >0: a>b → НОД(a, b)=НОД(a-b, b)
□
1) ∀k ∈ ℕ: a ⋮ k, b ⋮ k:⇔ ∃n,m ∈ ℤ: a/k = n, b/k=m ⇒ (a/k – b/k) = (a-b)/k = n-m, (n-m) ∈ ℤ ⇒ [ (a-b)/k = n-m, (n-m) ∈ ℤ:⇔ (a-b) ⋮ k ] и b ⋮ k ⇒ (a-b) ⋮ k, b ⋮ k.
Итого: ∀k ∈ ℕ: a ⋮ k, b ⋮ k ⇒ (a-b) ⋮ k, b ⋮ k (1)
2) ∀k ∈ ℕ: (a-b) ⋮ k, b ⋮ k:⇔ ∃n,m ∈ ℤ: (a-b)/k = n, b/k = m ⇒
a/k – b/k = n, b/k = m ⇒ a/k – m = n ⇒ a/k = n+m, n+m ∈ ℤ ⇒
[ a/k = n+m, (n+m) ∈ ℤ:⇔ a ⋮ k ] и b ⋮ k ⇒ a ⋮ k, b ⋮ k
Итого: ∀k ∈ ℕ: (a-b) ⋮ k, b ⋮ k ⇒ a ⋮ k, b ⋮ k (2)
(1) и (2) ⇒ ( ∀k ∈ ℕ → a ⋮ k, b ⋮ k ⇔ (a-b) ⋮ k, b ⋮ k ) (*)
a > b и b > 0 ⇒ (a-b > 0) и (b > 0) ⇒ ∃k1=НОД(a-b, b)
3) Пусть k = НОД(a, b) ≠ k1 = НОД(a-b, b) ⇒ k > k1 либо k
(*) ⇒ (a-b) ⋮ k, b ⋮ k
(a-b) ⋮ k, b ⋮ k и k1
(*) ⇒ a ⋮ k1, b ⋮ k1
a ⋮ k1, b ⋮ k1 и k
■
Кажется ничего не упустил.
1)
2^40 1 = 1 + 2 +… + 2^39 = А
2^30 1 = 1 + 2 +… + 2^29 = B
А= B + 2^30 +… + 2^39
поэтому A= B + 2^30. (2^10 -1)
2)
2 н е может делить А (1= 1+2(1+ 2^38)), ни 2^2, ни 2^3, и.т.д.
2 н е может делить B, ни 2^2, ни 2^3, и.т.д.
3) общий делитель делит 2^30. (2^10 -1) и он не равно 2, 2^2, и.т.д.
4) НОД делит (2^10 -1) = 1023 = 3.11.31
поэтому НОД = 3, 11, 31, 3.11, 3.31,11.31 или 1023.
5)
A = 1023.(1+2^10+2^20+2^30)
B = 1023.(1+2^10+2^20)
6) НОД = 1023
Решил немного по-другому. Сначала заметил, что оба числа делятся на 2^10-1 (как разность кубов и разность чисел 4-ой степени), разделил их, и доказал что получившеися числа являются взаимно простыми числами.
Нашел задачу в разделе практика под названием ‘1.А.Эпическая Игра’, накатал индусский код, уверенности в ее правильности нет. Но все же поделюсь решением. Если у кого-нить есть решения, с радостью готов глянуть.
Для наглядности изменил вывод ответов для понимания
a1=a=int(input()) #В цикле переменная меняет значения, использовал a=a1(b=b1, n=n1)для возврата исх. значения.
b1=b=int(input())
n1=n=int(input())
while n1>=0:
while n>0:
a,n=n,a%n
if n1-a<0:
print(‘Выиграл АНТИСЕМЕН’)
break
n1=n1-a
n=n1
a=a1
while n>0:
b,n=n,b%n
if n1-b<0:
print(‘Выиграл СЕМЕН’)
break
n1=n1-b
n=n1
b=b1
b=int(input())
a=int(input())
while b!=a:
if b%a=0:
break
if a%b=0:
break
if a>b:
a=a-b
if b>a:
b=b-a
if b%a=0:
print(‘Наибольший общий делитель’,a)
if a%b=0:
print(‘Наибольший общий делитель’,b)
else:
print(‘Наибольший общий делитель’,b)
вот это называется усложнил код
Получается что для степеней простого числа A (в данном случае A=2) НОД(A^n-1, A^m-1) = A^НОД(n, m)-1. Разность степеней приводит к тому что за скобку будет выноситься А^m, а в скобках будет оставаться (A^(n-m) 1), в результате чего имеем тот же алгоритм Евклида для показателей степеней. Для примера: НОД(2^50-1, 2^35-1) = 2^НОД(50, 35)-1, или 2^5-1.
ввел a,b = map(int,input().split())
while a!=b:
if a>b:
a=a-b
else:
b=b-a
print(«По Евклиду»)
print(a)
а получил при вооде это
7
Traceback (most recent call last):
File «C:\python\uroki\evklid_while.py«, line 12, in
a,b = map(int,input().split())
ValueError: not enough values to unpack (expected 2, got 1)
Приносим свои извинения. При решении четвертой задачи была допущена ошибка на 10 мин 46 сек. Вместо слов «45 делится на 5, например, 15 делится на 5» следует понимать «45 делится на 5, будет 9, делится на 3». Как следствие, на 11 мин 21 сек вместо строки «360 = 2 * 2 * 2 *3 *5 *5» следует понимать «»360 = 2 * 2 * 2 *5 *3 *3».