472,973 Members | 2,367 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,973 software developers and data experts.

Rice grains on a chessboard

Hey guys I'm a beginner with C++ and am doing a practice problem for my class and am having trouble figuring this problem out.

A man wants 1 grain for the 1st square on a chessboard. 2 grains on the 2nd. 4 grains on the 3rd. 8 grains for the 4th square. etc etc (doubling for each square)

I have to write a program that will tell me how many squares it would take to reach at least 1,000 grains of rice, 1,000,000 grains of rice, and 1,000,000,000 grains of rice.

Every thing has to be in INT's not doubles. If anyone can help me out it would be greatly appreciated. I'm completely lost on how to do this. Thanks!
Oct 2 '09 #1
8 8273
9,065 Expert Mod 8TB
Have you written anything yet.

How about a program that prints out the number of grains of on each square for the first 31 squares? You can work on the limits later.

If you can't do a program like that then try using pen and paper to write down the number of grains of rice on the first 4 or 5 squares. Once you have the method for doing that translate it into a programable algorithm.
Oct 3 '09 #2
2,426 Expert 2GB
You can't count the number of grains of rice with an INT -- the largest number guaranteed to fit in an unsigned INT on all compilers is 65535. You'll have to find a tricky way to solve the problem.
Oct 3 '09 #3
9,065 Expert Mod 8TB
Yes but if you take INT to mean integer arithmetic and take into account what's been asked to be calculated then you will notice that it does fit inside 32 bit integer arithmetic.
Oct 3 '09 #4
542 512MB
On my machine declaring only ints, employing a for loop with the condition set to i<31 the squares hold the following number of rice grains:
boardsq 0 = 1
boardsq 1 = 2
boardsq 2 = 4
boardsq 3 = 8
boardsq 4 = 16
boardsq 5 = 32
boardsq 6 = 64
boardsq 7 = 128
boardsq 8 = 256
boardsq 9 = 512
boardsq 10 = 1024 <------
boardsq 11 = 2048
boardsq 12 = 4096
boardsq 13 = 8192
boardsq 14 = 16384
boardsq 15 = 32768
boardsq 16 = 65536
boardsq 17 = 131072
boardsq 18 = 262144
boardsq 19 = 524288
boardsq 20 = 1048576 <-------
boardsq 21 = 2097152
boardsq 22 = 4194304
boardsq 23 = 8388608
boardsq 24 = 16777216
boardsq 25 = 33554432
boardsq 26 = 67108864
boardsq 27 = 134217728
boardsq 28 = 268435456
boardsq 29 = 536870912
boardsq 30 = 1073741824 <-------
boardsq 31 = -2147483648
At square 31 the result returns a negative which is still valid if multiplied by -1
After square 31 the result returned is zero (0) ..... but in this case the requirements are met. Someone might like to suggest the pseudo code which will get to square no 64.
Oct 5 '09 #5
2,426 Expert 2GB
Do you need to find the first square to hold that many grains of rice; or do you need to find the minimum number of squares such that the sum of all grains of rice is at least that number?
Oct 5 '09 #6
2,426 Expert 2GB
Do these values look strangely familiar? There is an elegant and very rapid algorithm lurking behind the pattern made by these values.
Oct 5 '09 #7
687 512MB
But in the base (namely , 2) where these numbers look familiar, numbers like 1000, 1000000 look unfamiliar and will require effort to implement arithmetic operation with multi-word precision.
Oct 5 '09 #8
9,065 Expert Mod 8TB
No because one of the beauties of C and C++ is the ability to use which ever base, 8, 10, 16(and by extension 2) is convenient at the time so you can use base 16(2) operations for calculation but base 10 operations for comparison.
Oct 5 '09 #9

Sign in to post your reply or Sign up for a free account.

Similar topics

by: Michel | last post by:
I have an html page which, thanks to some javascript, allows to move pieces on a chessboard. I can't find how to reflect the moves in a list displayed by the same page. To understand what I'm...
by: Tony Johansson | last post by:
Hello! Assume you want to store field object that a chess board consist of. A chess board consist of 64 fields where each field is either white or black. Now to my question how should I...
by: Chad Everett | last post by:
Hi all, I am new to the group. Trying to learn Python programming on my own. I am working through Michael Dawson's Book Python Programming for the absolute beginner. I am tring to write a...
by: Jonathan Pritchard | last post by:
I know this is a simple problem, but I've just included this in the title because it explains what my program tries to do. The following does not work, it for someone reason does not want to...
by: tommy34 | last post by:
I'm new to java and any help will be appreciated. Problem is i dont know even where to start. I need to write a program that reads a chessboard configuration and identifies whether a king is...
by: ebrimagillen | last post by:
Hello mates, Just needed a solution on the exercises below. Exercise 2 A classic problem in introductory programming is the grains of rice on a chess board problem. Your program should...
by: punkybrewster | last post by:
I have the idea to create the program but I need help in finishing it. My task is to write a program that prints out a chessboard using only asterisks. I have to use multiple nested loops with...
by: satish100 | last post by:
how can i write a program for making the plain chessboard in PHP
by: DJRhino | last post by:
Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
by: Aliciasmith | last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
by: tracyyun | last post by:
Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
by: giovanniandrean | last post by:
The energy model is structured as follows and uses excel sheets to give input data: 1-Utility.py contains all the functions needed to calculate the variables and other minor things (mentions...
by: NeoPa | last post by:
Hello everyone. I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report). I know it can be done by selecting :...
by: NeoPa | last post by:
Introduction For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all...
by: nia12 | last post by:
Hi there, I am very new to Access so apologies if any of this is obvious/not clear. I am creating a data collection tool for health care employees to complete. It consists of a number of...
by: NeoPa | last post by:
Introduction For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.