MHB Calculate Grains of Wheat: A Program for Chess Inventor's Request

[carl123]

There is a story of the inventor of chess. The king wanted to reward him with riches, but he only asked for the following. One grain of wheat for the first square, two on the second, four on the third, doubling the amount for each square until 64 squares are accounted for.

Questions

1) Design a program for calculating the total number of grains of wheat. You will want to use iteration/looping. Do not forget to keep track of which square you are on and the number of grains of wheat that you currently have.

2) Write the program to determine the number of squares needed to get at least 1000, 1,000,000 and 1,000,000,000 grains of wheat.My code so far, works perfectly for number 1, Not sure how to go about number 2.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
   int calc = 1;
   int sqNum = 1;
   unsigned long long total = 1;
   cout << "Square " << sqNum << " has " << total << " grain of wheat" << endl;
   for (int i = 1; i<64; ++i){
      sqNum++;
      calc = (calc * 2);
      total = total + calc;
      cout << "Square " << sqNum << " has " << total << " grains of wheat " << endl;
       
   }
   
   return 0;
}

 

[MarkFL]

A couple of comments about what you have so far:

You don't need the variable [m]sqNum[/m] since it always has the same value as your looping index. I would try to incorporate all squares (including the first) into the loop so the first square doesn't have to be handled separately before the loop.

In order to do part 2.), it seems you need a conditional to check if [m]total[/m] is at least as large as some given value, and then a means to exit from the loop if it is.

Or, you could instead use a while loop instead of a for loop (as it allows defining a condition for continuing), which is what I think I would do in this case. :)

 

[carl123]

Sorry, I'm not sure i understood what you meant. Can you explain further?

 

[MarkFL]

Sorry, I'm not sure i understood what you meant. Can you explain further?

Which part was unclear?

 

[carl123]

the part where i have to use a conditional to check if "total" is at least as large as some given value

 

[MarkFL]

the part where i have to use a conditional to check if "total" is at least as large as some given value

Well, for example, if I was going to do this in PHP, and I wanted to determine the number of squares to get at least 1,000 grains, I might write:

$total = 0;
$sqr = 0
while ($total < 1000)
{
	$total = pow(2, ++$sqr) - 1;
}
echo "It takes at least $sqr squares to obtain at least 1,000 grains."

Note: I have relied in my code on the fact that:

$$\sum_{k=0}^{n}\left(2^k\right)=2^{n+1}-1$$

 

[johng1]

Here's another way to do your problem. First, the problem said you should find the total number of grains. Your program outputs the number of grains on each square for a total of 64 lines of output. The specifications say that there are only 4 lines of output. Accordingly, I moved your cout outside your for loop. Next, introduce another variable oldTotal, which is the value of total the previous iteration of the for loop. You can add two more if statements in the for loop to answer the questions about 1000000 and 1000000000000 grains.

int main() {
   int calc = 1;
   int sqNum = 1;
   unsigned long long total = 1,oldTotal;
   cout << "Square " << sqNum << " has " << total << " grain of wheat" << endl;
   for (int i = 1; i<64; ++i){
      sqNum++;
      calc = (calc * 2);
      oldTotal = total;
      total = total + calc;
      if (oldTotal < 1000 && total >= 1000) {
         cout<<"It takes " << sqNum << " squares for at least 1000 grains." << endl;
      }
      \\ you add two more if statements
   }
      cout << "Square " << sqNum << " has " << total << " grains of wheat " << endl;   
   return 0;
}