|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[238] Теорема 33.8 (Существование и единственность разложения) Всякое составное число а единственным образом представляется в виде ei еоег а = Plp22 -р/, где pi < р2 < < рг - простые числа, а ег- - положительные целые числа. Доказательство оставляется читателю (упр. 33.1-10). Упражнения. 33.1-1 Докажите, что существует бесконечно много простых чисел. (Указание: ни одно из простых чисел pi,P2, ,Pk не делит число (PiP2 • • -Рк) + 1-) 33.1-2 Докажите, что если а \ Ь и Ь с, то а \ с. 33.1-3 Пусть число р - простое, а 0 < к < р. Докажите, что НОД(к,р) = 1. 33.1-4 Докажите следствие 33.5. 33.1-5 Пусть число р - простое, а 0 < к < р. Докажите, что р Ср. Выведите отсюда, что для любых целых а, Ь и простого р выполняется сравнение (а + Ь)р = ар + Ьр (modp). 33.1-6 Пусть а и Ь - целые числа, причём а \ Ь и Ь > 0. Докажите, что (ж mod Ъ) mod а = ж mod а при любом целом ж. Докажите, что (при тех же допущениях) из ж = у (mod Ъ) следует, что ж = у (mod а) при любых целых хну. 33.1-7 Фиксируем целое положительное к. Будем называть целое число п (точной) к-й степенью (Arth power), если п равно ак при некотором целом а. Целое число п > 1 назовём нетривиальной степенью (nontrivial power), если оно является к-ъ степенью при некотором целом к > 1. Предложите полиномиальный алгоритм, определяющий, является ли данное число п нетривиальной степенью. 33.1-8 Докажите свойства (33.8)-(33.12). 33.1-9 Докажите, что функция gcd ассоциативна, то есть для gcd(a, gcd(6, с)) = gcd (gcd (a, b), с) для любых целых a,b,c. 33.1-10* Докажите теорему 33.8. 33.1-11 Предложите алгоритмы, вычисляющие за время 0(/32) частное и остаток от деления /3-битового целого числа на более короткое (временем считаем число битовых операций). 33.1-12 Постройте эффективный алгоритм, переводящий /3-битовое целое число из двоичной системы в десятичную. Покажите, что если умножение и деление двух целых чисел длины не более /3 (имеется в виду длина двоичной записи) требует времени М(/3), то перевод /3-битового целого числа из двоичной системы в десятичную может быть выполнен за время 0(М(/3) lg/3). (Указание. Используйте метод «разделяй и властвуй», получая отдельно левую и правую части результата.) 33.2. Наибольший общий делитель В этом разделе мы предполагаем, что все рассматриваемые целые числа положительны (для наибольшего общего делителя знак роли не играет). Можно вычислять НОД(а,Ь), разлагая а и Ь на множители и отбирая общие множители: если a = fyf-(33.13) и Ъ = р{1р{2 ... -р1/,(33.14) то gcd(a, b) = pm-(eb/0pmin(e2J2) pmin(er,/r)(33 Но разложение на множители, как мы увидим в разделе 33.9, является трудной задачей, так что его лучше избегать. Алгоритм Евклида для нахождения наибольшего общего делителя основан на следующей теореме. Теорема 33.9 (Рекуррентная формула для gcd) Пусть а - целое неотрицательное, а Ь - целое положительное число. Тогда gcd (a, Ъ) = gcd (b, a mod b). Доказательство. Пара (a, b) имеет те же делители, что и пара (b, a mod b) (a mod b является целочисленной линейной комбинацией а и b и наоборот). Поэтому и наибольший общий делитель у этих пар одинаковый. Алгоритм Евклида. Приводимый ниже алгоритм вычисления наибольшего общего делителя описан в книге Евклида «Начала» (около 300 г. до Р.Х.), хотя, возможно, был известен и ранее. Мы запишем его в виде рекурсивной процедуры; её входом являются неотрицательные целые числа а и Ь. Euclid (a,b) 1if b=0 2then return a 3else return Euclid (b, a mod b) Например, при вычислении Euclid(30, 21) = Euclid(21.9) = Euclid(9, 3) = Euclid(3, 0) = 3 процедура вызывает себя трижды. Правильность процедуры Euclid вытекает из соотношения (33.11) и из теоремы 33.9. Процедура не может работать бесконечно, поскольку рекурсивный вызов происходит с меньшим значением второго аргумента. Время работы алгоритма Евклида. Оценим время работы алгоритма Евклида, считая, что размера входа случай а > ft 0 (при ft > а 0 процедура Euclid (а, ft) первым делом вызывает себя, переставив аргументы местами, а при а = Ь > 0 работа процедуры завершается после единственного рекурсивного вызова, поскольку a mod а = 0). Заметим, что во всех рекурсивных вызовах первый аргумент будет строго больше второго (остаток меньше делителя). Время работы процедуры Euclid пропорционально глубине рекурсии. Для её оценки нам пригодятся числа Фибоначчи Fk, определённые рекуррентным соотношением (2.13). Лемма 33.10 Пусть а > Ь 0. Если процедура EucLm(a,ft) во время работы вызывает себя к раз (к 1), то a Fk+2 и ft ) Fk+\. Доказательство проведём индукцией по к. Базисом индукции служит значение к = 1. Если происходит хоть один рекурсивный вызов, то Ь 1 = F2; по условию теоремы а > Ь, так что а 2 = F3. Пусть лемма выполнена для случая к - 1 вызовов; докажем её для к вызовов. На первом шаге процедура Euclid (а, ft) выполняет вызов Euclid (b, a mod Ъ), внутри которого происходит к - 1 рекурсивных вызовов, так что по предположению индукции Ь -Ffc+i и (a mod Ъ) Fk- Из неравенства а > Ь > 0 следует, что [a/b\ 1 и Ь + (a mod Ъ) = Ь + (а - [a/b\b) а, так что а Ь + (a mod Ъ) Fk+1+Fk = Fk+2. Из леммы 33.10 вытекает следующая теорема. Теорема 33.11 (Теорема Ламе) Пусть к - целое положительное число. Если й > ft 0 и ft < Fk+i, то процедура Euclid (a, ft) выполняет менее к рекурсивных вызовов. Покажем, что оценка теоремы 33.11 неулучшаема, рассмотрев вычисление наибольшего общего делителя соседних чисел Фибоначчи. Процедура Euclid(F3, F2) выполняет один рекурсивный вызов. Поскольку Fk+i mod Fk = Fk-i, вычисление будет идти так: gcd(Ffc+i,Ffc) = gcd(Ffc, (Ffc+i mod Fk)) = ЯОД(,-1), поэтому |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||