Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

Пояснительная записка к курсовому проекту

по курсу

«Архитектура вычислительных систем»

на тему

«Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ»

МИНСК, 2001

Постановка задачи

Факторизовать целое число N с помощью ро-метода Полларда.

Исходные данные:

Целое число N.

Краткое описание ро-метода Полларда

Ро-метод Полларда для факторизации заключается в следующем:

Составляется последовательность {x}, x_i+1=f (x_i), f (x)=x²+1

Вычисляются разности y_i= x_2i— x_i

Вычисляется наибольший общий делитель чисел y_i и N. Если он больше 1, полученный НОД (y_i, N) является делителем числа N. Если нет — продолжаем выполнение алгоритма сначала.

Алгоритм работы программы

— Ввод числа N.

— Пока N не равно 1:

1. Вычисление x_i

2. Вычисление x_2i

Нахождение разности y_i= x_2i— x_i

3. Вычисление НОД (y_i, N)

4. Проверка НОД (y_i, 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<<" Делитель: «<<» «;

cout<<" Кол-во шагов: «<

N/=d;

i = 1;

x = 0;

}

}

while (N ≠ 1);

getch ();

}