Referat.me

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

Вид работы: курсовая работа

Рубрика: Информатика и программирование

Размер файла: 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++.

  • Алгоритмические языки: использование множеств

    Изучение способов описания и использования множеств, разработка алгоритма и составление программы для решения задачи. Нахождение в последовательности целых чисел таких, которые встречаются в ней ровно два раза. Набор программы, ее отладка и тестирование.