Рефераты Главная Начертательная геометрия Оккультизм и уфология Педагогика Полиграфия Политология Программированиекомпьютеры и кибернетика Производство и технологии Социальная работа Начертательная геометрия Не сортированные Таможенная система Теория государства и права Арбитражный процесс Реклама Нотариат Менеджмент Металлургия Минералогия Москвоведение |
Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работПланирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работБЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатикиПояснительная записка к курсовому проектупо курсу«Архитектура вычислительных систем»на тему«Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ» МИНСК, 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. Вычисление xi2. Вычисление x2iНахождение разности yi= x2i- xi3. Вычисление НОД (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();} |
|
