What are search tries? Why are they more efficient than usualsearching algorithms?
1 answer:
You might be interested in
Answer:
Here is the C++ program.
#include <iostream> //to use input output functions
using namespace std; // to access objects like cin cout
void chessboard(int N){ // function that takes a number N as parameter generates corresponding board
int i, j;
string black = "B"; // B for black squares
string white = "W"; // W for white squares
for(i=1;i<=N;i++){ //iterates through each column of the board
for(j=1;j<=N;j++){ //iterates through each row of the board
if((i+j)%2==0) // if sum of i and j is completely divisible by 2
cout<<black<<" "; //displays B when above if condition is true
else //if (i+j)%2 is not equal to 0
cout<<white<<" "; } // displays W when above if condition is false
cout<<endl; } } //prints the new line
int main(){ //start of the main function
int num; //declares an integer num
cout << "Enter an integer representing the size of the chessboard: "; //prompts user to enter size of chess board
cin >> num; //reads value of num from user
chessboard(num); } //calls chessboard function to display N lines consist of N space-separated characters representing the chessboard pattern
Explanation:
The function works as follows:
Lets say that N = 2
two string variables black and white are declared. The value of black is set to "B" and value of white is set to "W" to return a chessboard pattern in B and W squares.
The outer loop for(i=1;i<=N;i++) iterates through each column of the chess board. The inner loop for(j=1;j<=N;j++) iterates through each row of chess board.
At first iteration of outer loop:
N = 2
outer loop:
i=1
i<=N is true because i=1 and 1<=2
So the program enters the body of the outer for loop. It has an inner for loop:
for(j=1;j<=N;j++)
At first iteration of inner loop:
j = 1
j<=N is true because j=1 and 1<=2
So the program enters the body of the inner for loop. It has an if statement:
if((i+j)%2==0) this statement works as:
if(1+1) % 2 == 0
(1+1 )% 2 takes the mod of 1+1 with 2 which gives the remainder of the division.
2%2 As 2 is completely divisible by 2 so 2%2 == 0
Hence the if condition evaluates to true. So the statement in if part executes:
cout<<black<<" ";
This prints B on the output screen with a space.
B
The value of j is incremented to 1.
j = 2
At second iteration of inner loop:
j = 2
j<=N is true because j=2 and 2=2
So the program enters the body of the inner for loop. It has an if statement:
if((i+j)%2==0) this statement works as:
if(1+2) % 2 == 0
(1+2 )% 2 takes the mod of 1+2 with 2 which gives the remainder of the division.
3%2 As 3 is not completely divisible by 2
Hence the if condition evaluates to false. So the statement in else part executes:
cout<<white<<" ";
This prints W on the output screen with a space.
B W
The value of j is incremented to 1.
j = 3
Now
j<=N is false because j=3 and 3>2
So the loop breaks and program moves to the outer loop to iterate through the next row.
At second iteration of outer loop:
N = 2
outer loop:
i=2
i<=N is true because i=2 and 2 = 2
So the program enters the body of the outer for loop. It has an inner for loop:
for(j=1;j<=N;j++)
At first iteration of inner loop:
j = 1
j<=N is true because j=1 and 1<=2
So the program enters the body of the inner for loop. It has an if statement:
if((i+j)%2==0) this statement works as:
if(2+1) % 2 == 0
(2+1 )% 2 takes the mod of 2+1 with 2 which gives the remainder of the division.
3%2 As 3 is not completely divisible by 2
Hence the if condition evaluates to false. So the statement in else part executes:
cout<<white<<" ";
This prints W on the output screen with a space.
B W
W
The value of j is incremented to 1.
j = 2
At second iteration of inner loop:
j = 2
j<=N is true because j=2 and 2=2
So the program enters the body of the inner for loop. It has an if statement:
if((i+j)%2==0) this statement works as:
if(2+2) % 2 == 0
(2+2 )% 2 takes the mod of 2+2 with 2 which gives the remainder of the division.
4%2 As 4 is completely divisible by 2 so 4%2 == 0
Hence the if condition evaluates to false. So the statement in if part executes:
cout<<black<<" ";
This prints B on the output screen with a space.
B W
W B
The value of j is incremented to 1.
j = 3
Now
j<=N is false because j=3 and 3>2
So the loop breaks and program moves to the outer loop. The value of outer loop variable i is incremented to 1 so i = 3
N = 2
outer loop:
i=3
i<=N is false because i=3 and 3>2
So this outer loop ends.
Now the output of this program is:
B W
W B
Screenshot of this program along with its output is attached.
