Тема: Тесты простоты Цель: Следует выбрать эффективный алгоритм (по времени) теста простоты числа.
На исследование вам дается два алгоритма:
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