SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
Walter Savitch ,kenrick Mock
Chapter:
Standard Template Library
Exercise:
Programming Projects
Question:6 | ISBN:9780132846813 | Edition: 5

Question

a. Here is pseudocode for a program that inputs a value n from the user and then inserts n random numbers, ensuring that there are no duplicates:

Input n from user Create vector v of type int

Loop i = 1 to n

r = random integer between 0 and n-1

Linearly search through v for value r

if r is not in vector v then add r to the end of v

End Loop

Print out number of elements added to v

Implement this program with your own linear search routine and add wrapper code that will time how long it takes to run. Test the program for different values of n . Depending on the speed of your system, you may need to input large values for n so that the program takes at least one second to run. Here is a sample that indicates how to calculate the difference in time: (time.h is a library that should be available on your version of C++).

#include <time.h>

time_t start,end;

double dif;

time (&start); // Record start time

// Rest of program goes here.

time (&end); // Record end time

dif = difftime(end,start);

cout << "It took " << dif << " seconds to execute. " << endl;


b. Next, create a second program that has the same behavior except that it uses an STL set to store the numbers instead of a vector:

Input n from user

Create set s of type int

Loop i = 1 to n

r = random integer between 0 to n-1

Use s.find(r) to search if r is already in the set

if r is not in set s then add r to s

End Loop

Print out number of elements added to s

Time your new program with the same values of n that you used in the vector version. What do the results tell you about the Big- O run time of the find( ) function for the set compared with linear search through the vector? Note that the find( ) function is really redundant because insert has no effect if the element is already in the set. However, use the find( ) function anyway to create a program comparable to the vector algorithm.


TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

part a.

#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>

int n, r;
time_t start, end;
double dif;

int main() 
{

	std::cin >> n;
	time(&start);
	std::vector<int> v;
	srand(time(NULL));

	for (int i = 1; i <= n; i++)
	{

		r = rand() % (n - 1) + 0;

		std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), r);

		if (std::find(v.begin(), v.end(), r) != v.end())
		{
			it == v.end();
		}
		else
		{
			v.push_back(r);
		}

	}

	std::cout << std::endl << "There are " << int(v.size()) << " numbers stored in this vector." << std::endl;

	time(&end);
	dif = difftime(end, start);
	std::cout << "It took about " << dif << " second(s) to finish the program. " << std::endl << std::endl;

	system("pause");
	return 0;
}

 

0 0

Discussions

Post the discussion to improve the above solution.