Функциональный подход в поиске решений задач:четность
Понятие четности возникает при рассмотрении самых различных математических задач. Если элементы произвольного множества могут быть условно разделены на две примерно равные группы с диаметрально противоположными свойствами, то речь идет о четности.
Замечание. Четность суммы нескольких чисел зависит от четности числа нечетных слагаемых: если количество нечетных слагаемых не(четно), то и сумма - (не)четна.
Основная теорема арифметики: Всякое натуральное число можно записать в виде произведения чисел (разложить на простые множители), причем это разложение единственно с точностью до перестановки множителей.
Сделаем важные наблюдения. Пусть
– разложение числа n на простые множители, тогда
.
содержит удвоенный набор множителей числа 
. Можно с уверенностью утверждать, что если делится на 3, то делится на 9. Но куда важнее вывод о том, что если делится на 3, то делится на 3. И вообще, если делится на некоторое простое число 
, то и делится на . Кстати, если делится на 9, то с уверенностью можно лишь утверждать, что делится на 3. А вот если длится на 27, то можно утверждать, что делится на 9.
Олимпиадные задачи.Виды олимпиадных задач, методы их решения.
Типы задач
Несмотря на уникальность олимпиадных задач, можно всё-таки выделить несколько типичных идей, составляющих суть задач. Разумеется, по определению, такой список будет неполным.
|
|
|
Задачи на инвариант
Игра
Комбинаторика
Теория графов
Неравенства
Геометрия
Не существует единого метода решения олимпиадных задач. Напротив, количество методов постоянно пополняется. Некоторые задачи можно решить несколькими разными методами или комбинацией методов. Характерная особенность олимпиадных задач в том, что решение с виду несложной проблемы может потребовать применения методов, использующихся в серьёзных математических исследованиях. Ниже приводится (по определению) неполный список методов решения олимпиадных задач:
Доказательство от противного
Принцип Дирихле
Решение методами другой науки (замена алгебраической задачи геометрической или физической и наоборот)
Правило крайнего
Решение с конца
Поиск инварианта
Построение контрпримера
Математическая индукция
Рекурсия
Метод итераций
Подсчёт двумя способами
Метод аналогий
Провокационный метод
Вспомогательное построение
Переход в пространство большего числа измерений
Вспомогательная раскраска
Олимпиадные задачи.Основы теории чисел:простые числа, алгоритм Эвклида
Целые числа включают в себя множество отрицательных чисел,положительных(натуральных) и число ноль
|
|
|
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
Наибольший общий делитель чисел a, b можно найти с помощью алгоритма Евклида, который состоит в следующем.
Пусть b>0. Разделим a на b, тогда по теореме о делении с остатком:
a = bq1 + r1.
Если r1 = 0, то НОД(a, b) = b.
Если r1 ¹ 0, то разделим b с остатком на r1:
b = r1q2 + r2.
Если r2 = 0, то процесс деления закончим, а если r2 ¹ 0, то разделим r1 с остатком на r2:
r1 = r2q3 + r3.
Продолжая далее таким же образом, мы закончим процесс деления как только получится остаток равный 0.
Заметим, что такой остаток обязательно получится. В самом деле, остаток всегда меньше делителя, поэтому b > r1 > r2 > r3 > . . . и число получаемых остатков не превосходит b.
Итак, в результате указанного алгоритма получим, что:
| a = bq1 + r1, | ||
| b = r1 q2 + r2, | ||
| r1 = r2 q3 + r3, | (1) | |
| . . . . . . . . . . . . . | ||
| rn-2 = rn-1qn-1+ rn , | ||
| rn-1 = rnqn . |
Тогда на основании свойств 20 и 10 :
НОД(a, b) = НОД(b, r1) = НОД(r1, r2) = . . . = НОД(rn-1,rn) = rn.
Следовательно, наибольший общий делитель чисел a и b совпадает с последним ненулевым остатком rn в алгоритме Евклида для чисел a и b.
|
|
|
Дата добавления: 2018-05-13; просмотров: 315; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!