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

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

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

По курсу

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

На тему

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

МИНСК, 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();

}


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