Google Answers Logo
View Question
 
Q: C++ Programing question ( Answered 5 out of 5 stars,   0 Comments )
Question  
Subject: C++ Programing question
Category: Computers > Programming
Asked by: purplepit-ga
List Price: $50.00
Posted: 10 Apr 2003 15:45 PDT
Expires: 10 May 2003 15:45 PDT
Question ID: 188997
Given the program below:
********************************************************************************

#pragma warning(disable : 4786) // advised for MSVC++


#include <list>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <deque>

using namespace std ;

typedef vector<int> choice;
typedef list<choice> choices;

/*pseudo const*/ int MAX_CHOICES = 6;
/*pseudo const*/ int NUMBERS = 49;

string ordinal(int); // prototype - see code of function after main()

template<class iT> void display(iT start, iT finish)
{
   for (iT it = start; it != finish; it++)
   {
      if (*it < 10)
         cout << ' ';
      cout << *it << ' ';
   }
}

void show(choice c)
{
   display(c.begin(), c.end());
}

void show2(choice c)
{
   show(c);
   cout << endl;
}

void randomize() // standard on some systems
{
	time_t t;
	srand((unsigned) time(&t));
}

void main()
{
   clock_t start,finish;
   randomize(); // comment out to give repeat sequences

   int tickets; // number of tickets sold
   choices allCards; // container to store all tickets
   cerr << "How many balls (usually " << NUMBERS << ")  : "; cin >>
NUMBERS;
   cerr << "How many choices (usually " << MAX_CHOICES << ") : "; cin
>> MAX_CHOICES;
   cerr << "How many tickets sold        : "; cin >> tickets;

   // now sell the tickets
   // duplicate tickets are allowed
   for (int cards = 0; cards<tickets; cards++)
   {
      choice a(MAX_CHOICES,0); // choice::choice(size,initialValue)

      for (int i=0; i<MAX_CHOICES; i++)
      {
         int next, counts=0;
         do
         {
            next = rand()%NUMBERS + 1;
            // check for duplicates
            counts = count(a.begin(),a.end(),next);
         } while (counts > 0);
         a[i]=next;
      }
      sort(a.begin(),a.end());
      allCards.push_back(a);
   }

   // now choose the winning numbers
   choice winner(MAX_CHOICES,0);
   for (int i=0; i<MAX_CHOICES; i++)
   {
      int next,counts=0;
      cerr << "Enter the " << ordinal(i+1) << " ball : ";
      cin >> next;
      // check for duplicates and errors
      counts = count(winner.begin(),winner.end(),next);
      while (next < 1 || next > NUMBERS || counts > 0)
      {
         cerr << "Invalid choice by. Re-enter the "
            << ordinal(i+1) << " ball : ";
         cin >> next; counts = 0;
         counts = count(winner.begin(),winner.end(),next);
      }
      winner[i]=next;
   }
   sort(winner.begin(),winner.end());

   // display a count of the winning tickets
   cout << "\nNumber of balls used: " << NUMBERS
      << "\nNumber of choices per line: " << MAX_CHOICES
      << "\nNumber of tickets sold: " << tickets
      << "\nNumber of matches for ";
   show(winner);
   int counts = 0;
   start = clock();
   counts = count(allCards.begin(), allCards.end(), winner);
   finish = clock();
   cout << " is " << counts << endl;
   cout << "Time taken to search for winners : " <<
            double(finish-start)/CLOCKS_PER_SEC << endl; 

   // option to display all tickets sold
   // why is character input such a pig?
   cerr << "Display all sold cards? (y/n) : ";
   char reply; while ( cin.get() != '\n' ) {}; // what a pig!
   cin.get(reply); while ( cin.get() != '\n' ) {};
   if (reply == 'Y' || reply == 'y')
   {
      allCards.sort(); // when allCards is a list<>
      for_each(allCards.begin(), allCards.end(), show2);
   }
}

string ordinal(int n)
// returns n as ordinal value (e.g. 1st 2nd 3rd etc.)
// couldn't find one in std libraries!
{
   string s = "";
   int ncopy = abs(n);
   if (n<0)
      s += '-';

   string s2="";
   char digit;
   while (ncopy > 0)
   {
      digit = ncopy%10 + '0';
      s2 += digit;
      ncopy /= 10;
   }
   
   reverse(s2.begin(), s2.end());
   s += s2;
   // At this stage we have the number as a string (that's all!)
   // thus if n = 101 then s is "101"
   // if n = -101 then s is "-101"
   
   // I have cut out this bit which adds the suffix letters st, nd, rd
or th
   // So you will have an interesting exercise to do!

   s+= "th"; // let's assume for now they all look like this
   
   return s;
}

********************************************************************************

Can you help with the following questions/ammendments, in order for
this to run/compile without errors????



Part 1
Run the program and test it fairly thoroughly. This is easier said
than done. It is possible to run interactively for small amounts of
data, but if you choose to generate ("sell") hundreds of thousands of
tickets and you want to inspect them it will be necessary to use
redirection to an output file to collect the data. The screen messages
are written to cerr to ensure they appear on the screen even if you
redirect the output.

There are various ways of helping the testing process.

1.    You could restrict the available ball numbers to much fewer than
49 (let's say 6 – so we could only choose numbers 1 to 6. If we then
set the number of choices to 6 as well we have to choose numbers 1 to
6 and so every ticket must be a winner.

2.    You could 'cheat' by turning off the randomize action. The
random number generator will then always generate the same tickets, so
you could run it once, copy down a generated ticket, and then choose
that as the winning ticket for the next run – it should be found.

3.    You could restrict the number of choices (6 in the real game) to
1. This means that single numbers between 1 and 49 are winners. If we
generate a large number of random 'sales' then 1 in 49 of them
(approx) should be winners.

You will be expected to show your tutor that you have thought about
the testing process and tested fairly thoroughly.

Part 2
Measure the time the count() algorithm takes to search for winners (it
is already programmed). I suggest you do this using the 'standard'
data of 49 balls and 6 choices for ticket sales of 10000, 20000,
50000, 100000, 200000, 500000. I think this gives a reasonable range
of timings. If you find that these size data sets are unrealistic for
the computer you are using (e.g. it takes more than a minute for the
largest or unmeasurable for the smallest) then adjust the range up or
down. Tabulate the results and try and predict what would happen if
the data set were to get much larger. You may also be able to test out
your prediction.

Part 3
We have, somewhat arbitrarily, chosen to use a vector<int> to store a
single 'ticket' (or 6 numbers) and a list<choice> to store the whole
data set (of possibly thousands of tickets).

There is no reason why we could not use an alternative container for
either or both of these.

As an experiment (and it's probably not a very good one I'm afraid) I
should like you to change the program so the whole data set uses a
vector<choice> instead of the list<choice>. You will also have to make
slight changes to the part of the program which sorts the tickets into
order prior to printing. Some care is needed here! There are several
places where sorting takes place, but only one which has to be
changed.

When you have made the changes, collect data for the same series of
tests used in part 2 and compare the two sets.

 

Part 4

The function ordinal() is intended to return a string which represents
the number as an ordinal value. The ordinal value of 1 is "1st". The
ordinal value of 6 is "6th".

Try and complete the function ordinal() to behave correctly for any
integer value. As far as I know only the last 2 digits matter however
long the integer.

I suggest you write a separate simple test program (the lottery
program is not a good testing program for ordinal() although it can of
course use it).

 Thank you!!!
Answer  
Subject: Re: C++ Programing question
Answered By: jeanluis-ga on 10 Apr 2003 18:48 PDT
Rated:5 out of 5 stars
 
Ok well here we go... First off I would like to say that the program
compiles in MSVC without error for me as it is posted... Now I will
try and address each of the 4 parts, please feel free to ask me for
more detail if I am unclear on anypart.

Part 1
Not sure what I am really supposed to do here, I tested the program
and it seems to work fairly well... I performed all three suggested
testing procedures, and got the expected results... I don't know what
else to say, other then to point out in testing procedure 2 (the
"cheat") I simply commented out the srand() call in the randomize()
function... That way the same seed will always be used, thus the same
numbers will always be picked... You could also change the call to
rand() so that the argument is a constant integer rather than the
current time, as that would have the same affect.

Part 2
Ok here I just plugged in the numbers that were recommended:
Input      : Output Time
49,6,10000 : 0.02
49,6,20000 : 0.04
49,6,50000 : 0.11
49,6,100000: 0.211
49,6,200000: 0.431
49,6,500000: 1.082
Based on this you can see that the time increases almost linearly with
number of tickets sold. With this in mind you could assume that this
trend will continue as follows:

Input       : Theoretical Output Time
49,6,1000000: 2.164
49,6,2000000: 4.328
... and so on...
Now to put this to the test:

Input       : Actual Output Time
49,6,1000000: 2.183
49,6,2000000: 4.377

As you can see the theroy holds up pretty good... We are only off on
the order of 100ths of a second...

Part 3
For this I simply changed the typedef for choices to the following:
typedef vector<choice> choices; 

Then down in the guts of the code I changed the following line:
allCards.sort(); // when allCards is a list<>
to:
sort(allCards.begin(), allCards.end());/* sort these dudes this way
--jld */

And that appears to produce the same format output (Full source code
will be available at the link below, along with all the output, the
output files will be named n.txt for the files produced in part 2
where n is 10000, 20000, etc..., and the output produced in this step
with the new sort method are in files called nvec.txt, again where n
is 10000, 20000, etc...)

Part 4
For this part I just added a few lines to the ordinal() function, see
the source code for details. I also added a function called
ordinalTest() that performs a simple test of the function and shows
the 1st 100 ordinal numbers with their corresponding cardinals. :)


Here is the link to the files I talked about above (Note: This link
will only be available for 30 days!):
http://chrisd.info/jld/jld.zip
Hope this helps, if you have any questions or problems please let me
know
thanks,
--jld
purplepit-ga rated this answer:5 out of 5 stars
Excellent!!! thanks

Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy