Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ
Составление алгоритма и программы для факторизации целого числа N с помощью ро-метода Полларда. Краткое описание данного метода: составление последовательности, вычисление разности и наибольшего общего делителя. Алгоритм работы и листинг программы.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 24.06.2010 |
| Размер файла | 12,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
Пояснительная записка к курсовому проекту
по курсу
«Архитектура вычислительных систем»
на тему
«Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ»
МИНСК, 2001
Постановка задачи
Факторизовать целое число N с помощью ро-метода Полларда.
Исходные данные:
Целое число N.
Краткое описание ро-метода Полларда
Ро-метод Полларда для факторизации заключается в следующем:
Составляется последовательность {x}, xi+1=f(xi), f(x)=x2+1
Вычисляются разности yi= x2i- xi
Вычисляется наибольший общий делитель чисел yi и N. Если он больше 1, полученный НОД (yi , N) является делителем числа N. Если нет - продолжаем выполнение алгоритма сначала.
Алгоритм работы программы
- Ввод числа N.
- Пока N не равно 1:
1. Вычисление xi
2. Вычисление x2i
Нахождение разности 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();
}
Подобные документы
Составление схемы алгоритма и программы для построения графика временной функции, работающей как в машинном, так и в реальном времени. Пример вычисления степенного ряда с помощью схемы Горнера. Описание переменных программы, листинг, процедуры и функции.
курсовая работа [67,6 K], добавлен 20.11.2012Математическое обоснование метода решения задачи: определенный интеграл, квадратурная формула Симпсона (формула парабол). Словесное описание алгоритма и составление его блок-схемы. Выбор языка программирования. Текст программы решения задачи, ее листинг.
курсовая работа [593,6 K], добавлен 09.07.2012Характеристика программы на языке VBA, которая вводит исходные данные, выполняет расчеты и выводит результаты на экран. Описание переменных в программе, ее блок-схема и алгоритм работы. Листинг программы. Описание входных данных и результат вычислений.
курсовая работа [721,4 K], добавлен 10.11.2010Содержание термина "планирование эксперимента". Сущность метода наименьших квадратов. Разработка программы анализа статистической оценки качества проектируемой системы: составление и графическое представление алгоритма решения, листинг программы.
курсовая работа [4,1 M], добавлен 16.09.2011Особенности разработки программы и выбор методов решения задачи. Составление алгоритма, распределение регистров программы и формирование файлов. Описание процедуры очистки памяти, сложения, вычитания, умножения. Тестирование и листинг программы.
лабораторная работа [51,2 K], добавлен 14.05.2011Оценка погрешности и точности в математике. Составление программы и алгоритма для численного дифференцирования с заданной допустимой погрешностью на алгоритмическом языке Turbo Pascal 7.0. Составление алгоритма и программы аппроксимации функции.
курсовая работа [810,6 K], добавлен 24.03.2012Особенности метода численного интегрирования функции одной переменной. Замена на каждом элементарном отрезке подынтегральной функции на многочлен первой степени (линейную функцию). Разработка алгоритма программы, ее листинг. Пример работы программы.
контрольная работа [217,9 K], добавлен 14.07.2012Описание алгоритма решения задачи графическим способом. Вывод элементов массива. Описание блоков укрупненной схемы алгоритма на языке Pascal. Листинг программы, а также ее тестирование. Результат выполнения c помощью ввода различных входных данных.
контрольная работа [150,4 K], добавлен 03.05.2014Описание алгоритма решения задачи графическим способом. Ввод элементов исходного массива в цикле. Нахождение определённых элементов. Сортировка элементов с помощью пузырькового метода. Разработка программы на языке Pascal. Поиск наибольшего элемента.
лабораторная работа [123,5 K], добавлен 15.01.2014Изучение характеристик и режимов работы ВТА 2000-30. Составление блок-схемы алгоритма программы. Рассмотрение особенностей интерфейса вычислительных систем. Описание кодов символьных и функциональных клавиш, полученных при выполнении практической работы.
отчет по практике [26,6 K], добавлен 04.04.2015
