(Вариант № 18)
Выполнил:
Студент группы И-21з
Емельянов К.Ю.
Проверил:
Шишкевич В.Е.
Цель работы: экспериментально исследовать теоретическую оценку трудоемкости алгоритма точного решения задачи о сумме методом полного перебора.
Вариант задания №18
| Вариант
| Размерность вектора случайных чисел
| Максимальное случайное число в векторе
| Значение суммы (V)
|
|
|
|
|
|
Ход выполнения работы
В ходе выполнения работы были разработаны 3 процедуры: TaskSum – функция решения задачи о сумме, create_array – для генерации вектора псевдослучайных чисел и записи его в файл, create_array_manual – для ручного ввода значений вектора. Реализация процедуры create_array представлена на рис. 1, блок-схема – на рис.2.
| void create_array(int Nmax,int *vector)
{
// Cоздание массива из Nmax псевдослучайных целых чисел величиной от 0 до 50
// массив записывается в файл Example_TA3.TXT, на экран выводим максимальное // целое
int i;//переменная цикла
FILE *stream;//файл данных
//Nmax соответствует размерности вектора
stream = fopen("Example_TA2.TXT", "w+");//открываем файл для записи
std::cout << std::endl <<"Maximal integer " << RAND_MAX << std::endl;//вывод максимально возможного числа
printf("\n%d%s\n", Nmax, " random numbers from 0 to 50");//вывод справочного сообщения
for(i=0; i<Nmax; i++)//цикл вывода в файл и на экран элементов массива
{
vector[i]= rand() % 50;//генерация очередного случайного числа в диапазоне от 0 до 550
if ((i+1)%20!=0)//вывод по 20 чисел в ряд
{
printf("%d ", vector[i]);
fprintf(stream,"%d ", vector[i]);
}
else
{
printf("%d\n", vector[i]);
fprintf(stream,"%d\n", vector[i]);
}
}
fclose(stream);
}
|
| Рис.1. Реализация процедуры create_array
|
|
| Рис. 2. Блок-схема процедуры create_array
|
Реализация процедуры TaskSum представлена на рис. 3.
| int TaskSum(int N, int V, int &flag, int *vector, int *counter)
{
int i,j,sum, cnt, MaxN;
int iter = 0;
MaxN = int(pow((double)2,N)-1); iter++;
flag = 0; i=0;
iter++;
while(i<N)
{
counter[i]=0; i++; iter+=3; }//end while(i<N)
cnt = 1;
iter++;
do
{
sum = 0;
i=0;
iter+=3;
while(i<N)
{
sum = sum+counter[i]*vector[i];
i++;
iter+=3;
}//end while (i<N)
iter++;
if (sum== V)
{
flag=1;
return iter;
}//end if
iter++;
j=N-1;
while((counter[j]==1)&&(j!=0))
{
counter[j]=0;
j = j-1;
iter+=4;
}//end while counter[j]==1
iter++;
counter[j]=1; iter++;
cnt = cnt + 1;
}//end do
while(cnt<=MaxN);
return iter;
}//end TaskSum
|
| Рис. 3. Реализация процедуры TaskSum
|
Реализация процедуры create_array_manual представлена на рис. 4, блок-схема – на рис.5.
| void create_array_manual(int N,int *vector)
{
FILE *stream;
int temp;
std::cout << "Input the data!" << std::endl;
stream = fopen("Example_TA3.TXT", "w+");//открываем файл для записи
for(int i=0; i<N; i++)
{
if (fscanf(stdin, "%d", &temp))
printf("The integer read was: %i\n",temp);
fprintf(stream,"%d ", vector[i]);
vector[i]=temp;
}
fclose(stream);
}
|
| Рис. 4. Реализация процедуры create_array_manual
|
|
| Рис. 5. Блок-схема процедуры create_array_manual
|
На рис.6 представлен листинг основной части программы.
| #include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include "Lab3_TA_func.h"
using namespace std;
#define SIZE
int vector[4]; //массив случайных чисел
int counter[4]; //вспомогательный массив для определения элементов, дающих требуемую сумму
int N=11, V=37; //констант N – размерность вектора, V – значение суммы
int flag;
void main()
{
int iter;
//ввод значений элементов вектора с клавиатуры и запись
//вектора в файл
//Lab3_TA::create_array_manual(N,vector);
//Случайное наполнение вектора и запись вектора в файл
Lab3_TA::create_array(N,vector);
flag=0;
iter=Lab3_TA::TaskSum(N,V,flag,vector,counter);
if (flag==1)
{
cout << "OK\n";
cout << "Counter Vector" << endl;
for(int k = 0; k<N; k++) printf("%d%s",counter[k]," ");
printf("%s\n"," ");
cout << "Vector" << endl;
for(int k = 0; k<N; k++) printf("%d%s",vector[k]," ");
printf("%s\n"," ");
cout << "Number of iteration:" << iter << endl;
}//end if
else cout<<"NO elements giving the sum\n";
_getch();
}//end main
|
| Рис. 6. Листинг основной части программы
|
Для нашего варианта заданий были получены следующие результаты рис. 7-9.
|
| Рис.7. Результаты расчета для первого эксперимента (см. табл. 1).
|
|
| Рис.8. Результаты расчета для второго эксперимента
|
|
| Рис.9. Результаты расчета для третьего эксперимента
|
Результаты всех экспериментов представлены в таблице 1.
Таблица 1 – Результаты экспериментов для N = 11 и V = 37
| N эксперимента
| 
| 
|  по данным программного подсчета
|
| 1 (ручной)
|
|
|
|
| 2 (ручной)
|
|
|
|
| 3 (авто)
|
|
|
|
Выводы.
В результате выполнения лабораторной работы:
· была исследована теоретическая оценка трудоемкости алгоритма точного решения задачи о сумме методом полного перебора;
· были получены навыки по расстановке счетчиков;
· были создана программа для исследования трудоемкости алгоритма и блок-схемы основных функций;
· было установлено, что практическая оценка трудоемкости алгоритма при существовании решения значительно меньше теоретической для худшего варианта.
