C++

Forum

 
simulation problem

the storm (13)
hi guys, I have a problem with my program ... first my program is
"
The Problem:
There are a number of problems known collectively as "Random Walk" problems that have been of longstanding interest to the science community. All but the most simple of these are extremely difficult to solve and for the most part they remain largely unsolved. One such problem may be stated as follows:
A (drunken) bug is placed on a given square in the middle of a tile floor in a rectangular room of size (N x M) tiles. The bug wanders (possibly in search of an aspirin) randomly from tile to tile throughout the room. Assuming that it may move from its present tile to any of the eight surrounding tiles (unless it is against a wall) with equal probability, how many moves will it take to touch every tile on the floor at least once?
Hard as this problem may be to solve by probability theory techniques, it is easy to solve using the computer. The technique for doing so is called "Simulation”.
This technique is widely used in industry to predict traffic flow, inventory control, and so forth. The problem may be simulated using the following method:
Methodology:
An (N x M) array is used to represent the number of times Cij our bug has reached a tile at position (i , j) on the floor. All the cells of this array are initialized to Zero before simulation starts. At the start, the position of the bug is set to (istart, jstart). The eight possible moves of the bug are represented by the tiles located at
(i + imove[k] , j + jmove[k]), where 1<= k <= 8 and
imove[l ] = -1 jmove[l ] = 1
imove[2] = 0 jmove[2] = 1
7 8 1
6 i,j 2
5 4 3
imove[3] = 1 jmove[3] = 1

imove[4] = 1 jmove[4] = 0
imove[5] = 1 jmove[5] = -1
imove[6] = 0 jmove[6] = -1
imove[7] = -1 jmove[7] = -1
imove[8] = -1 jmove[8] = 0

Generating a random value for k lying between 1 and 8 simulates a random walk to one of the eight given squares. Of course, the bug cannot move outside the room, so coordinates that leap up a wall must be ignored and a new random combination formed. Each time a square is entered the count Cij for that square is incremented so that a nonzero entry shows the number of times the bug has landed on that square so far. When every square has been entered at least once, the experiment is complete.

Program Specification:
Write a program to perform the specified simulation experiment. The program should provide the following:
• Arbitrary values of N and M , 2 < N <= 20 , 2 < M <= 40 with dynamic (Run-time) allocation.
• Arbitrary starting positions (istart, jstart).
• An iteration limit, that is, a maximum number of squares the bug may enter during the experiment (this avoids getting in an infinite loop); a maximum of 50,000 is appropriate for this exercise.
• For each experiment, a display of:
1. The total number of legal moves that the bug made
2. The final Cij array (this will show the density of the walk, i.e., the number of times each tile on the floor was touched during the experiment). You should show the array of counts in character symbols on the screen using the following scheme:
Let the average count in a tile be , then use:
Symbol 1 for 1 ≤ Cij < 0.5 x
2 for 0.5 x ≤ Cij < x
3 for x ≤ Cij< 1.5 x
4 for 1.5 x ≤ Cij < 2x
5 for Cij ≥ 2x
0 for zero counts

Some Design Guidelines:
• You will need to create the space for Cij dynamically. That space will be a run-time 2-D array of size N*M tiles.
• Build a function to initialize the counts Cij to zeros.
• Build a function to display the array on the screen. It computes the average count (x) and uses the scheme given above.
• Build a function to generate one random move out of 8 possible moves. It receives the old position and returns the new position of the bug.
• Build a Boolean function to return true only if the move is inside the room



I managed to write the code of the program with no syntax error and I traced the program and for me it seems has no problem, but when I build and execute the problem I get an error. the program crashes and the windows starts to close the program...
here is my code.. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
int RandInt(int i, int j);
bool Completed_move(int **p);
void bug_move(int x, int& imove, int& jmove);
void zeros_2d_array(int **p);
bool Inside_room(int imove, int jmove);
void display(int **p, int counter);
void header();
int n,m;
void main()
{
	srand ( (unsigned) time (NULL) );
	//DECLARATION
	int **p;
	int x, l, imove, jmove, counter = 0;
	
	//Getting the values of the arrays :) :) 
	cout << "Please, enter the width of the room \nnote the width should be between 2 and 20" << endl;
	cin >> n;
	while ( (n < 2)|| (n > 20) )
	{
		cout << "Error, out of the range. \nplease enter the correct width" << endl;
		cin >> n;
	}
	cout << "Please, enter the length of the room \nnote the length should be between 2 and 40" << endl;
	cin >> m;
	while ( (m < 2) || (m > 40) )
	{
		cout << "Error, out of the range. \nplease enter the correct the length" << endl;
		cin >> m;
	}
	//------------------------------------------------------------------------------------
	imove = n/2; //initiaing the arbiratry first move vertically
	jmove = m/2; //initiating the arbiratrt first move horizontally

	p = new int*[n]; //Creating 2D array by pointers :) 
	for(l = 0; l < n; l++)
		p[l] = new int[m]; 
	
	zeros_2d_array(p); //initiaing all cells with zeros
	

	while( (!Completed_move(p)) && (counter < 500) )
	{
		do
		{
			x = RandInt(0, 7);
			bug_move(x, imove, jmove);
		} while(!Inside_room(imove, jmove) );
		p[imove][jmove]++;
		counter++;
	}
	
	display(p, counter);
	system("pause");

}


int RandInt(int i, int j) 					
{
	return rand( ) % (j-i+1) + i ;
}

bool Completed_move(int **p) //to check that the bug has touched every tile at least 1 time .....
{
	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (p[i][j] == 0)
				return false;
	return true;
}
void bug_move(int x, int& imove, int& jmove) // moving the bug from older place to the new one ..... 
{
	int imovex[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
	int jmovex[8] = {1, 1, 1, 0, -1, -1, -1, 0};
	imove = imove + imovex[x];
	jmove = jmove + jmovex[x];
}

void zeros_2d_array(int **p)
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			p[i][j] = 0;
}
bool Inside_room(int imove, int jmove)
{
	if ( (imove >= n) || (jmove >= m) )
		return false;
	else
		return true;
}
void display(int **p, int counter)
{
	header();
	for(int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << setw(3) << p[i][j] << "|";
		cout << endl;
		header();
	}

	cout << "\nThe legal number of moves till now is: " << counter << " move" << endl;

}
void header()
{
	for(int i = 0; i < n*4; i++)
		cout << "-";
	cout << endl;
}




Any help ??
Last edited on
horance89 (23)
I copied your code and make a buil/run in Eclipse
It worked just fine for me after I:
1. changed
void main() with int main()

2. added 
1
2
3
 
#include <cstdio>
#include <ctime>
#include <cstdlib>


And as seen in first topic here -> http://www.cplusplus.com/forum/beginner/1988/

you should change system("pause"); .

Have a lot of fun!
the storm (13)
I changed from void main() to int main() and return 0 ...
and I added
#include <cstdio>
#include <ctime>
#include <cstdlib>

but still the same problem....so what do you think ?
Mathhead200 (1016)
Comments on lines: 7, 49 - 50, 80, 103
Line 103 was your big error!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
int RandInt(int i, int j);
bool Completed_move(int **p);
//change the return type of bug_move to bool, to make sure bug move is in the room
bool bug_move(int x, int& imove, int& jmove);
void zeros_2d_array(int **p);
bool Inside_room(int imove, int jmove);
void display(int **p, int counter);
void header();
int n,m;
void main()
{
	srand ( (unsigned) time (NULL) );
	//DECLARATION
	int **p;
	int x, l, imove, jmove, counter = 0;
	
	//Getting the values of the arrays :) :) 
	cout << "Please, enter the width of the room \nnote the width should be between 2 and 20" << endl;
	cin >> n;
	while ( (n < 2)|| (n > 20) )
	{
		cout << "Error, out of the range. \nplease enter the correct width" << endl;
		cin >> n;
	}
	cout << "Please, enter the length of the room \nnote the length should be between 2 and 40" << endl;
	cin >> m;
	while ( (m < 2) || (m > 40) )
	{
		cout << "Error, out of the range. \nplease enter the correct the length" << endl;
		cin >> m;
	}
	//------------------------------------------------------------------------------------
	imove = n/2; //initiaing the arbiratry first move vertically
	jmove = m/2; //initiating the arbiratrt first move horizontally

	p = new int*[n]; //Creating 2D array by pointers :) 
	for(l = 0; l < n; l++)
		p[l] = new int[m]; 
	
	zeros_2d_array(p); //initiaing all cells with zeros
	

	while( (!Completed_move(p)) && (counter < 500) )
	{
		//This loop can run forever! Use walls, dont make the bug find it's way back...
		// Run the check inside the bug_move function.
		do
		{
			x = RandInt(0, 7);
		} while( !bug_move(x, imove, jmove) );
		p[imove][jmove]++;
		counter++;
	}
	
	display(p, counter);
	system("pause");

}


int RandInt(int i, int j) 					
{
	return rand( ) % (j-i+1) + i ;
}

bool Completed_move(int **p) //to check that the bug has touched every tile at least 1 time .....
{
	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (p[i][j] == 0)
				return false;
	return true;
}
bool bug_move(int x, int& imove, int& jmove) // moving the bug from older place to the new one ..... 
{
	//modified, see lines 7 and 49
	int imovex[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
	int jmovex[8] = {1, 1, 1, 0, -1, -1, -1, 0};
	// imove = imove + imovex[x];
	// jmove = jmove + jmovex[x];
	int _imove = imove + imovex[x],
		_jmove = jmove + jmovex[x];
	if( Inside_room(_imove, _jmove) ) {
		imove = _imove;
		jmove = _jmove;
		return true;
	}
	return false;
}

void zeros_2d_array(int **p)
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			p[i][j] = 0;
}
bool Inside_room(int imove, int jmove)
{
	//forgot to check lower bounds
	// if ( (imove >= n) || (jmove >= m) )
	if( imove >= n || imove < 0 || jmove >= m || jmove < 0 )
		return false;
	else
		return true;
}
void display(int **p, int counter)
{

	header();
	for(int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << setw(3) << p[i][j] << "|";
		cout << endl;
		header();
	}

	cout << "\nThe legal number of moves till now is: " << counter << " move" << endl;

}
void header()
{
	for(int i = 0; i < n*4; i++)
		cout << "-";
	cout << endl;
}
Last edited on
the storm (13)
Done :) .... Thank you dude :)
Mathhead200 (1016)
Your welcome. Let me know if you have any more questions.
Topic archived. No new replies allowed.