Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Севастополь – 2012




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Цель работы: экспериментально исследовать теоретическую оценку трудоемкости алгоритма точного решения задачи о сумме методом полного перебора.

Вариант задания №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 (авто)

 

Выводы.

В результате выполнения лабораторной работы:

· была исследована теоретическая оценка трудоемкости алгоритма точного решения задачи о сумме методом полного перебора;

· были получены навыки по расстановке счетчиков;

· были создана программа для исследования трудоемкости алгоритма и блок-схемы основных функций;

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







Дата добавления: 2015-10-12; просмотров: 385. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.02 сек.) русская версия | украинская версия