Теория чисел (программа-калькулятор) - формирование заданного подмножества натурального ряда с помощью общего делителя

    Дисциплина: Разное
    Тип работы: Курсовая
    Тема: Теория чисел (программа-калькулятор) - формирование заданного подмножества натурального ряда с помощью общего делителя

    МОСКОВСКИЙ АВИАЦИООНЫЙ ИНСТИТУТ (МАИ)
    МОСКОВСКИЙ АВИАЦИОН
    НЫЙ ИНСТИТУТ (МАИ)
    (ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
    Факультет
    «СИСТЕМЫ УПРАВЛЕНИЯ, ИНФОРМАТИКА И
    ЭЛЕКТРОЭНЕРГЕТИКА»
    Кафедра 308
    «Информационные технологии»
    Группа 03-119
    Пояснительная записка к курсовой работе
    по дисциплине:
    «Теория чисел
    Выполнил: Тузов И.И.
    Руководитель: доцент, к.т.н. Гридин А.Н.
    Москва 2010
    ЗАДАНИЕ
    Разработать программу-калькулятор CalcKurs на языке программирования
    Pascal, реализующую следующие функции:
    1.формирование заданного подмножества натурального ряда с помощью общего
    делителя;
    2.факторизация числа с опциями;
    3.нахождение НОД и НОК для заданной совокупности натурального ряда;
    4.нахождение рациональных решений уравнения с целочисленными
    коэффициентами;
    5.представление рациональной дроби в виде цепной;
    6.представление цепной дроби в виде рациональной.
    Оборудование и ПО:
    Название Windows: Windows Seven (6.1.7600) Ultimate
    Название процессора: Intel(R) Core(TM)2 CPU 6300 @ 1.86GHz
    Установлено памяти: 1022,49 MB
    Среда программирования: Turbo Pascal 7.0
    ОГЛАВЛЕНИЕ
    Задание……………………………………….…………………………………………………2
    Оглавление…………………………………….……………………………………………….3
    1. Введение….………………………………………………………………………………….4
    2. Специальная часть……………...……………………………………………….………..5-17
    2.1. Интерфейс программы…………………………………………………………………5
    2.2. Описание процедур…………………………………………………………………6-17
    2.2.1. DelOstatok..…..….…………………………………………………………………..6-7
    2.2.2. Factor………....….…………………………………………………………………..8-9
    2.2.3. NodNok…..….……………………………………………………………………10-11
    2.2.4. SuperGorner..………..…………………………………….………………………12-13
    2.2.5. Express…………………………………………………………………………….14-15
    2.2.6. AntiExp………….………………………………………………………………...16-17
    3. Заключение……...……….………………………………………………………………….18
    4. Список использованных источников……………….……………………………………..19
    Приложение..…………………………………………….…………………………………20-23
    Листинг программы…..……………………………….………………………………...20-23
    ВВЕДЕНИЕ
    Теория чисел
    — это одно из направлений математики, которое иногда называют «высшей арифметикой». Данная наука изучает натуральные числа и некоторые сходные с ними объекты, рассматривает различные
    свойства (делимость, разложимость, взаимосвязи и так далее), алгоритмы поиска чисел, а также определяет ряд достаточно интересных наборов натуральных чисел.
    Так, к примеру, в рамках теории чисел рассматриваются вопросы делимости
    целых чисел друг на друга,
    алгоритм Евклида
    для поиска наибольшего общего делителя, поиск наименьшего общего кратного,
    малая
    большая
    теоремы Ферма. В качестве самых известных рядов натуральных чисел можно привести
    ряд Фибоначчи
    , простые числа, совершенные и дружественные числа, степени и суперстепени натуральных чисел.
    Вне самой математики теория чисел имеет довольно мало приложений, и
    развивалась она не ради решения прикладных задач, а как искусство ради искусства, обладающее своей внутренней красотой, тонкостью и трудностью. Тем не менее теория чисел оказала большое
    влияние на математическую науку, поскольку некоторые разделы математики (в том числе и такие, которые впоследствии нашли применение в физике) были первоначально созданы для решения
    особенно сложных проблем теории чисел.
    Разработанная программа включает в себя набор из нескольких основных
    операций, которые могут понадобиться при решении более сложных задач.
    Назначение
    программы
    CalcKurs
    Программа CalcKurs выполняет следующие функции:
    1.формирование заданного подмножества натурального ряда с помощью общего
    делителя;
    2.факторизация числа с опциями;
    3.нахождение НОД и НОК для заданной совокупности натурального ряда;
    4.нахождение рациональных решений уравнения с целочисленными
    коэффициентами;
    5.представление рациональной дроби в виде цепной;
    6.представление цепной дроби в виде рациональной.
    СПЕЦИАЛЬНАЯ ЧАСТЬ
    Интерфейс
    программы
    Описание процедур
    procedure DelOstatok;
    Назначение.
    Данная процедура формирует заданное подмножество натурального ряда с
    помощью общего делителя.
    Алгоритм.
    Ищется общий делитель совокупности делителей (общий делитель ищется с
    помощью нахождения наименьшего общего кратного делителей). На заданном множестве (кол-во цифр в числах) ищем первый элемент, который будет удовлетворять заданному условию (делится на НОК
    с остатком), запоминаем элемент и прерываем цикл.
    Формируем подмножество с помощью прибавления к первому элементу делителя,
    суммируем количество элементов, пока элементы не станут больше заданной размерности.
    Пример.
    Делитель=10, остаток=3, размерность=2 (от 10 до 99)
    Количество элементов=9
    Подмножество элементов={13, 23, 33, 43, 53, 63, 73, 83, 93}
    Тесты.
    1.Некорректные данные
    img width=\"683\" height=\"356\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/307973.png\"
    2.Корректные данные
    img width=\"688\" height=\"355\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/307974.png\"
    procedure Factor;
    Назначение
    Данная процедура выполняет факторизацию (разложение на простые множители)
    числа с опциями.
    Алгоритм.
    Ищем для данного числа простой множитель с помощью решета Эратосфена
    (Для нахождения всех простых чисел не больше заданного числа
    n, следуя методу Эратосфена, нужно выполнить следующие шаги:
    Выписать подряд все целые числа от двух до
    n (2, 3, 4, …,
    Пусть переменная
    p изначально равна двум— первому простому числу.
    Вычеркнуть из списка все числа от 2
    p до
    n, делящиеся на
    p (то есть, числа 2
    p, 3
    p, 4
    p, …)
    Найти первое не вычеркнутое число, большее чем
    p, и присвоить значению переменной
    p это число.
    Повторять шаги 3 и 4 до тех пор, пока
    p не станет больше, чем
    Все не вычеркнутые числа в списке— простые числа.)
    и делим заданное число на данный множитель, потом ищем следующий простой
    множитель(если он повторяется, то возводим его в степень), и так до тех пор, пока число не станет равным единице. Записываем все простые множители.
    Далее находим все делители числа и составляем из них множество. Вычисляем
    сумму делителей.
    Пример.
    Число=21
    множество делителей=1 3 7 21
    кол-во простых множителей=2
    21=3 ^ 1 * 7 ^ 1
    кол-во множителей=4
    сумма множителей=32
    Тесты.
    1.Некорректные данные
    img width=\"689\" height=\"356\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/307975.png\"
    2.Корректные данные
    img width=\"689\" height=\"358\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/307976.png\"
    procedure NodNok;
    Назначение.
    Данная процедура находит НОД и НОК для заданной совокупности натурального
    ряда.
    Алгоритм.
    С помощью алгоритма Евклида (есть числа a,b и последовательность R
    N, где каждое R
    K - это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело. Тогда НОД(
    b), наибольший общий делитель a и b, равен R
    N, последнему ненулевому члену этой последовательности) находим НОД
    [4] для первых двух чисел, «цепляем» следующее число для нахождения следующего НОД, и так до тех пор, пока совокупность чисел не закончится.
    Для нахождения НОК первых двух чисел используем следующий алгоритм:
    разлагаем данные числа на простые множители и к одному из таких разложений приписываем множители недостающие у него против разложений остальных данных чисел
    [5], и аналогично нахождению НОД «цепляем» следующее число.
    Пример.
    Числа: 21 и 12
    НОД(12,21)=3
    НОК(12,21)=84
    Тесты.
    1.Некорректные данные img width=\"687\" height=\"358\" alt=\"0x01
    graphic\" src=\"/cache/files/86e0/307977.png\"
    2.Корректные данные
    img width=\"685\" height=\"352\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/307978.png\"
    procedure
    SuperGorner
    Назначение
    Данная процедура находит рациональные решения уравнения с целочисленными
    коэффициентами.
    Алгоритм.
    Рациональные корни уравнения ищутся с помощью расширенной схемы(метода)
    Горнера
    [6] (раскладываем свободный член и коэффициент перед старшей степенью на все возможные множители и делим все множители свободного члена на все множители коэффициента перед
    старшей степенью (добавляем также знак “-”); подставляем полученные значения в уравнение, если уравнение получается равным нулю, то это значение - корень данного уравнения).
    Пример.
    Уравнение: 6x
    3-11x
    2+6x-1=0
    Возможные корни:
    +1/2,
    +1/3,
    +1/6
    Корни уравнения: 1/3, 1/2, 1
    Тесты.
    1.Некорректные данные
    img width=\"687\" height=\"357\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/307979.png\"
    2.Корректные данные
    img width=\"687\" height=\"358\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/3079710.png\"
    procedure Express;
    Назначение.
    Данная процедура переводит рациональную дробь в цепную
    [7].
    Алгоритм.
    Делим числитель на знаменатель, запоминаем его целое значение (a div b,
    где а - числитель, b - знаменатель), находим остаток от деления числителя на знаменатель (a mod b), присваиваем числителю значение остатка, меняем местами числитель и знаменатель, и так
    делаем до тех пор, пока (a mod b) не станет равен нулю.
    Пример.
    Рациональная дробь:123/47
    Цепная дробь: [2,1,1,1,1,1,1,3]
    Тесты.
    1.Некорректные данные
    img width=\"684\" height=\"354\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/3079711.png\"
    2.Корректные данные
    img width=\"685\" height=\"355\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/3079712.png\"
    procedure
    AntiExp
    Назначение
    Данная процедура переводит цепную дробь в рациональную.
    Алгоритм.
    Умножаем последний элемент цепной дроби с предпоследним и прибавляем к
    полученному значению единицу, это будет значением числителя, значением знаменателя будет последний элемент цепной дроби, меняем их местами, теперь последним элементом цепной дроби будет
    полученный знаменатель; так делаем, пока не закончатся элементы цепной дроби.
    Пример.
    Цепная дробь: [2,3,4,5]
    Рациональная дробь: 157/68
    Тесты.
    1.Некорректные данные
    img width=\"683\" height=\"353\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/3079713.png\"
    2.Корректные данные
    img width=\"686\" height=\"352\" alt=\"0x01 graphic\"
    src=\"/cache/files/86e0/3079714.png\"
    ЗАКЛЮЧЕНИЕ
    Разработана программа CalcKurs, выполняющая следующие функции:
    1.формирование заданного подмножества натурального ряда с помощью общего
    делителя;
    2.факторизация числа с опциями;
    3.нахождение НОД и НОК для заданной совоку...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены