For loop excercise?
Ok, I recently took a c++ exam and the final portion of the exam was to code a valid c++ program that would do the following:
Peter the Postman is assigned to night duty at the Post Office. Peter gets easily bored, so he decides to amuse himself as follows:
1.The are 100 post office boxes at his assigned substation.
2.First Peter goes through and opens all 100 mailboxes.
3.He then returns to the first box and closes every other one.
4.Then he returns to the first box and checks every third one:
If its open, he closes it
If its closed he opens it
5.He repeats this process for every fourth box, then every fifth box, etc.
until he gets through them all.
6.At the end, which boxes are open and which are closed?
I was completely at a loss as to how to do this, with the exception of the fact that I believe it involves a series of nested for loops for the various steps. I'd post the code I wrote on the test, but it is an empty shell and, I'm sure, is horribly wrong. IF anyone could help me out with this, i'd appreciate it.
[1101 byte] By [
ledjon] at [2007-11-11 9:57:10]
# 1 Re: For loop excercise?
This is a quick thought I had that may work..
Please dont flame me!! lol
bool box[100];
int num = 0;
for(int x = 0; x < 100; x++)
box[x] = true;
num++;
while(num < 100)
{
for(int x = 0; x < 100; x + num;)
{
if((num % 2) == 0)
box[x] = true;
else box[x] = false;
}
num++;
}
True is an open box, False is closed...
Anyway, just a quick thought, I havent tried this code or anything...
# 2 Re: For loop excercise?
After sitting down for a while, and using some ideas from the above poster, i've come up with the following code. It returns results that I believe are right, but I can't be sure. What do you guys think of this:
#include<iostream>
#include<iomanip>
using namespace std;
int box[100];
int main()
{
for(int x=0; x<=99; x++)
box[x]=0;
for(int counter=2; counter<=100; counter++)
{ for(int x=0; x<=99; x+=counter)
{ if(box[x]==0)
box[x]=1;
else if(box[x]==1)
box[x]=0; }}
cout<<"The numbers of the open boxes are: \n\n";
for(int x=1; x<=100; x++)
{ if(box[x-1]==0)
cout<<setw(5)<<(x); }
cout<<"\n\nThe numbers of the closed boxes are: \n\n";
for(int x=1; x<=100; x++)
{ if(box[x-1]==1)
cout<<setw(5)<<(x); }
cout<<endl;
return 0;
}
ledjon at 2007-11-11 21:00:48 >
# 3 Re: For loop excercise?
Out of this thread concept .. I just wanna tell u to reduce comparison number ..
I know it's trivial but usually it's better to get the processor work less :) :
x<=100 are two operation : x<100 or x=100 --> x<101 only one operation !
Really it's not only one operation in plus as it appears it may be up to 3 or 4 more operation if you look in assembled instructions .
This make me remember a time when I'm was worink for unprotect [crack work] such a software , it needed a serial number to be activated .. normaly coded operation for checking this serial is some thing like that :
If(txtField1 != check(case_1))
Invalid_Serial;
else
//start next check operation ...
But this software was coded by a very complicated method (a good protector programmer) like that :
a = check(case1);
If(!((textField1 <= a) && (textField1 >= a)))
Invalid_Serial;
else
//start next check operation ...
Yes it's very complicated if u see it's instruction I can say it's larger than the first one with more than 10 bytes ..
the first method is commonly knowen by patching the JNEQ to JEQ [Jumb if Not EQual to Jumb if EQual] and the new if condition will be :
If(txtField1 == check(case_1)) ; hence any entred data in serial field will be accepted exept the true serial number !!!
the second one and after many hours of trying to change many [bytes] of the programme , I found a small mistake in this method that's the using of "AND" which is the contrary of "OR" ..
(!((textField1 <= a) && (textField1 >= a)))
equivalent to
(textField1 <= a) || (textField1 >= a)
and to disable it a small negation :
(!((textField1 <= a) || (textField1 >= a)))
So only what I needed is to change each "AND" by "OR" only !!
Amahdy at 2007-11-11 21:01:46 >
# 4 Re: For loop excercise?
Hi,
... or Peter could sit back use some of his brain and think before he starts opening and closing boxes (which should be good practise in programming too).
Every box b[n] (n between 1 and 100) will be visited exactly n times. If n is even, the box will be closed at the end, because the opening and closing cancel each other out. If n is odd the box will be open. so you can reduce the complexity of your program O(n^2) to O(n)
#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
int main()
{
int numberOfBoxes = 100
vector<bool> box;
box.resize(numberOfBoxes); // all boxes are initialised with false
for(int i=0; i<numberOfBoxes/2;i++)
box[2*i] = true;
return 0;
}
I know it's a bit cheeky, but I guess your examiner would have loved that... ;-)
Cheers,
D
# 5 Re: For loop excercise?
Hi again,
seems I could need a bit of sitting back myself, because the above solution solves an entirely (but not quite) different problem and is *NOT* a sloution to the original problem. It was quick shot from the hip - and I missed.
But the real solution is even better - performance-wise. We're talking about O(sqrt(n))
and all you need to do is to change
for(int i=0; i<numberOfBoxes/2;i++)
box[2*i] = true;
to
for(int i=0; i<sqrt(numberOfBoxes);i++)
box[i*i+1] = true;
In both solutions true means closed and true means open, mind you.
Sorry for the inconvenience.
D
# 6 Re: For loop excercise?
Nice one. Only one slight tweak left to do: Dont take the sqrt every iteration. I dont think most compilers catch that redundancy when they optimize (?)
const int max = sqrt(numberOfBoxes);
for(int i=0; i<max;i++)
jonnin at 2007-11-11 21:04:52 >
