n ділиться на а +1. Обидві суми обчислюються один раз на початку роботи. Ці два умови дозволяють відразу відкинути В«зайвіВ» подільники.
У більш загальному вигляді цей метод дозволяє знаходити розкладання на множники многочлена з раціональними коефіцієнтами.
Нехай f (х)-многочлен з цілими коефіцієнтами. Припустимо, що він є твором многочленів g (х) і Н (х). При будь-якому цілому х з f (x) = g (х) h (х) випливає, що f (х) ділиться на g (x). Нехай т-ступінь многочлена g (x). Візьмемо m + l різних цілих значень х, наприклад 0,1-1,2 ... g (х) цілком задається своїми значеннями в цих точках, які є дільниками значень f (х) в тих же точках. Отже, всі можливі подільники ступеня не вище m з цілими коефіцієнтами многочлена f (х) визначаються різними комбінаціями дільників чисел f (0), f (1), f (-1), ... . p> Чи не розбираючи алгоритм докладно, перелічимо основні етапи роботи.
1. Обчислити f (0), f (1), ... (M +1- значення) (якщо f (х) - многочлен ступеня n, то т достатньо взяти рівним п/2).
2. Розглянути всі можливі комбінації дільників f (0), f (1), ..., взятих з обома знаками.
3. Для кожної комбінації (do, d1, ..., dm) знайти коефіцієнти многочлена g (х), приймає в точках 0,1, -1 ... значення do, d1, ..., dm.
4. Якщо f (х) ділиться без остачі на g (х), то задача вирішена, інакше перейти до аналізу наступної комбінації.
Послідовно застосовуючи цей алгоритм, можна знайти розкладання многочлена на Непріводімие множники. Це завдання демонструє зв'язок уявлення багаточлена як алгебраїчній структури і функціональної залежності, а також практичне додаток цієї зв'язку.
4. Комбінаторика. Одним з найважливіших застосувань комбінаторики є програмування, де, наприклад, перестановки та їх властивості істотно використовуються для аналізу різних алгоритмів сортування інформації. Сортуванням називається розташування раніше невпорядкованою інформації (масиву, файлу) в порядку зростання або спадання. Поняття зростання (порядку) широко застосовується в моделюванні конкретних завдань. Крім звичайного порядку на множині чисел В«число а більше числа &В», можна назвати впорядкування букв в алфавіті, слів у словнику. Іноді інформація впорядковується за якійсь одній частині, або, як зазвичай кажуть, по одному полю. Наприклад, інформація про учнів (журнал) впорядкована за прізвищами. Вважається, що в світі більше чверті всього машинного часу витрачається на сортування. Тому важливо грамотно вибирати метод сортування залежно від конкретного завдання, тобто проводити аналіз ефективності алгоритмів. Неврегульована безліч можна розглядати як деяку перестановку упорядкованого, тому властивості перестановок визначають числові характеристики алгоритмів сортування.
Далі для простоти викладу під перестановкою розуміється перестановка без повторень чисел 1, 2, ..., n, позначувана (a1, a2, ..., an). Наступні основні поняття, часто виходять за межі шкільного курсу математики, призв...
