Название: Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ
Вид работы: курсовая работа
Рубрика: Информатика и программирование
Размер файла: 15.38 Kb
Скачать файл: referat.me-134759.docx
Краткое описание работы: Составление алгоритма и программы для факторизации целого числа N с помощью ро-метода Полларда. Краткое описание данного метода: составление последовательности, вычисление разности и наибольшего общего делителя. Алгоритм работы и листинг программы.
Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
Пояснительная записка к курсовому проекту
по курсу
«Архитектура вычислительных систем»
на тему
«Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ»
МИНСК, 2001
Постановка задачи
Факторизовать целое число N с помощью ро-метода Полларда.
Исходные данные:
Целое число N.
Краткое описание ро-метода Полларда
Ро-метод Полларда для факторизации заключается в следующем:
1. Составляется последовательность {x}, xi +1 =f(xi ), f(x)=x2 +1
2. Вычисляются разности yi = x2i - xi
3. Вычисляется наибольший общий делитель чисел yi и N. Если он больше 1, полученный НОД (yi , N) является делителем числа N. Если нет – продолжаем выполнение алгоритма сначала.
Алгоритм работы программы
- Ввод числа N.
- Пока N не равно 1:
1. Вычисление xi
2. Вычисление x2i
4. Нахождение разности yi = x2i - xi
3. Вычисление НОД (yi , N)
4. Проверка НОД (yi , N) на равенство 1. Если это условие выполняется, то НОД – один из делителей числа N. Делим N на НОД и переходим к началу цикла.
Выход из цикла – равенство числа N единице.
Листинг программы
#include "stdio.h"
#include "conio.h"
#include "iostream.h"
unsigned long NOD(unsigned long a, unsigned long b)
{
while ((a > 0) && (b > 0))
if (a > b) a %= b;
else b %= a;
if (a == 0) return b;
return a;
}
void main()
{
unsigned long N, y, x, x1, i, j, d;
clrscr();
printf("Введите N : ");
scanf("%ld", &N);
i = 1;
x = 0;
do {
x = (x*x + 1) % N;
x1 = x;
for (j = 0; j < i*2-i; j++)
x1 = (x1*x1 + 1) % N;
i++;
y = x1 - x;
d = NOD(y, N);
if (d != 1)
{
cout<<"Делитель : "<<d<<" ";
cout<<"Кол-во шагов : "<<i-1<<endl;
N/=d;
i = 1;
x = 0;
}
}
while (N != 1);
getch();
}
Похожие работы
-
Разработка вычислительного устройства
Структурная схема устройства с ее обоснованием. Блок-схема алгоритма и микропрограммная реализация. Числовые тестовые примеры.
-
Лабораторная работа по информатике ( практика )
Лабораторная работа 4 ИЗУЧЕНИЕ ПРИНЦИПОВ ОРГАНИЗАЦИИ АРИФМЕТИКО-ЛОГИЧЕСКИХ УСТРОЙСТВ. СТРУКТУРА АЛУ ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ С ФИКСИРО- ВАННОЙ ЗАПЯТОЙ Ц е л ь р а б о т ы: Изучение принципов построения и функционирования АЛУ для деления чисел с фиксированной запятой.
-
Деление чисел в нормализованной форме
Оптимальный алгоритм деления чисел в нормализованной форме для получения нормализованного произведения чисел с помощью TP Pascal. Работа со строковыми данными и типами Real и Integer. Описание метода решения. Блок-схема работы программы, ее листинг.
-
Составление и описание программы по заданным параметрам
Характеристика программы на языке VBA, которая вводит исходные данные, выполняет расчеты и выводит результаты на экран. Описание переменных в программе, ее блок-схема и алгоритм работы. Листинг программы. Описание входных данных и результат вычислений.
-
Построение сетевого графика
ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ЧАСТЬ. 6.1. Организационная часть 6.1.1. Построение сетевого графика Большая сложность и комплексность проведения работ по созданию АСОИиУ, одновременное участие многих исполнителей, необходимость параллельного выполнения работ, зависимость начала многих работ от результатов других, значительно осложняют планирование разработки.
-
Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal
НСТИТУТ КАЛИНИНГРАДСКАЯ ВЫСШАЯ ШКОЛА УПРАВЛЕНИЯ РЕФЕРАТ по теме Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal
-
Вычислительная техника и программирование
Построение интерполяционного полинома Ньютона по значениям функции в узлах согласно методу Лагранжа. Составление алгоритмов решения задачи, их реализация на программном уровне на языке Turbo Pascal. Представление результатов работы программы Polinom.
-
Вычисление интеграла
Вычисление определённого интеграла с помощью метода трапеций на компьютере.
-
Примеры решения задач по программированию
Написание программы вычисления сопротивления электрической цепи, состоящей из двух параллельно и двух последовательно соединенных сопротивлений. Схема машинного алгоритма по условию задачи. Применение операций при написании программ на языке C/C++.
-
Алгоритмические языки: использование множеств
Изучение способов описания и использования множеств, разработка алгоритма и составление программы для решения задачи. Нахождение в последовательности целых чисел таких, которые встречаются в ней ровно два раза. Набор программы, ее отладка и тестирование.