Тема: Тесты простоты

Цель: Следует выбрать эффективный алгоритм (по времени) теста простоты числа.

На исследование вам дается два алгоритма:

1. Перебор делителей числа (Проверяем все числа от 2 до n-1 делят ли они заданное число

n),

2. Ограниченный перебор делителей числа (Проверяем числа от 2 до делят ли они

заданное число n).

Необходимо:

1. Реализовать данные алгоритмы,

2. Исследовать их и

3. Составить отчет.

Как исследовать алгоритмы? Конечно, перед тем как исследовать алгоритм нужно его

реализовать. Далее, вы должны запустить свои программы как минимум 5 раз для каждого

набора входных данных (в данной не менее 5 раз для N.1, 5 раз для N.2 и 5 раз для N.3, где N –

номер вашего варианта). При каждом запуске вам необходимо измерять, сколько времени

потребуется алгоритму для решения задачи (т.е. у вас будет 5 измерений для N.1, 5 измерений

для N.2 и 5 измерений для N.3, по каждому алгоритму). Далее находите средние арифметические

значения для каждого входного параметра (для N.1, N.2 и N.3) отдельно для первого и второго

алгоритмов. По этим средним значениям вы строите график зависимости времени работы

алгоритма от величины числа (для первого и второго алгоритма отдельно). Изучая эти графики вы

и должны строить ваши выводы и суждения.

Подсказки:

1. Для больших входных данных, например, для 2-го и 3-го наборов, лучше использовать тип

данных long long или __int64.

2. Для измерения времени работы алгоритма использовать функцию clock() (header file –

сtime).

Пример измерения длительности работы цикла:

#include

#include

#include

void main(){

/*

Определяем переменные, которые будем использовать для измерения времени.

Функция clock() возвращает результат, тип которой clock_t, поэтому

переменные start и end должны иметь такой же тип. Переменные, которые будут

использоваться для вычисления времени работы цикла будут иметь тип double.

*/

clock_t start,end;

double dif_time, time_for_cycle;

//Перед тем как начать вычисления запоминаем во сколько начали мы свои

//вычисления.

start = clock();

for(int i=0;i<1000000000;i++);

//После того как вычисления закончились мы опять запоминаем во сколько они

//закончились

end = clock();

/*

Функция clock() на самом деле возвращает не время, а количество tick

(тиков), которое прошло с начала выполнения программы. Для того чтобы

вычислить сколько секундам или миллисекундам равно измеренное количество

тиков нужно его разделить на константу CLOCKS_PER_SEC, что и делается на

следующих двух строках.

*/

dif_time = end - start;

time_for_cycle = dif_time/CLOCKS_PER_SEC;

//Теперь просто выводим результат измерений на экран

printf("%.10lg sec",time_for_cycle);

getch();

}

Отчет должен включать следующую информацию:

1. Общая информация о работе, т.е. должны быть даны ответы на следующие вопросы: «о

чем эта работа?», «какие алгоритмы были исследованы?».

2. Описание алгоритмов: Здесь вы должны привести словесное описание, блок схемы всех

алгоритмов, которые вы реализовали.

3. Описание тестовых данных, т.е. ответы на следующие вопросы: «Какие тестовые данные

вы использовали?», «Почему именно такие?». И должны привести сами тесты (наборы

данных).

4. Результаты исследований. Здесь вы должны привести результаты ваших измерений.

Обычно сравнивают средние значения показателей нескольких прогонов программ.

Следовательно, нужно запустить программу минимум 5 раз с различными входными

данными одного типа и объема и сравнивать средние арифметические значения.

5. Выводы. Ваши соображения и суждения, основанные на полученных результатах.

6. Исходные коды программ.

И, последнее, помните, что данный вид учебной деятельности называется «Самостоятельной

работой», т.е. вы должны самостоятельно выполнить работу и защитить ее. Работы авторов,

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

начисляться не будут.

Варианты входных данных

1) 5655

2) 800000019937

3) 146948024336453101

0 ответы

Последнее для темы Информатика

Начальные данные для исполнителя Водолей приведены на рисунке: Сколько литров останется в сосуде B

Помогите с информатикой. РЕШИТЕ ЗАДАЧУ ЧЕРЕЗ ДАНО, ПО ВОЗМОЖНОСТИ РЕШИТЕ ЕЕ НА ЛИСТКЕ И ПРИКРЕПИТЕ Ф

Смотрите надо сделать так пример консоль Сколько чисел вывести: 5 Текст:1 Текст:5 Текст:2 Текст

Ребят помогите пожалуйста срочно надо сделать нужно все !!ДАМ 100 БАЛЛОВ!!​

Как исправить ошибку в коде: Traceback (most recent call last): File "script.py", line 1, in name=i

Составить блок схему и написать код программы решающий следующую задачу: Существуют два материала X

Перечислите пункты контекстного меню выделив какой либо из объектов на рабочем столе​

Вариант 2 1. 1. Упорядочи величины от наименьшей к наибольшей 140000 байт; 0,14 Мегабайт; 120 Кил

Решите задачу используя двумерный массив.Выведите два числа :номер строки и номер столбца,в которых

Оля прочитала повесть «Королевство кривых зеркал» и теперь представляет всё наоборот. Она заметила,