Logic/C++ question? - DFWstangs Forums
 
LinkBack Thread Tools Display Modes
post #1 of 8 (permalink) Old 01-25-2004, 02:53 AM Thread Starter
R.E.N.G.
 
Turd's Avatar
 
Join Date: Jul 2001
Location: E = MC Vagina
Posts: 2,919
Logic/C++ question?

I finally started back to school and it's been a few years since my last programming class. It's pissing me off because I can't get done with the logic to even begin fighting with the code. I'm not looking for a free ride, I just want an educated nudge in the right direction to help get the ball rolling:

Five robbers have stolen one hundred bearer bond certificates and they have to divide the certificates between themselves. The most senior robber proposes a distribution of the certificates. (Robber 5 is most senior, Robber 1 is least senior) He suggets that the robbers all vote and if at least fifty percent accept the proposal, the certificates are divided as proposed. Otherwise, the most senior robber will be executed, and the remaining robbers will start over again with the next senior robber. What solution does the most senior robber propose?

Assume that the robbers are all very intelligent and they are all as greedy as possible and that they would prefer not to die. Also "at least fifty percent" means that three robbers must vote for the proposal when there are five for the proposal to pass; two must vote for the proposal if there are four robbers, etc.

Turn in the proposal by the first robber as “Robber 5 (me) gets ____ certificates. Robber 4 gets ____ certificates, etc” and an explanation of how you arrived at your solution.

This relates to recursion in that it is sometimes easier to evaluate a potential solution from the bottom up.
Turd is offline  
Sponsored Links
Advertisement
 
post #2 of 8 (permalink) Old 01-25-2004, 01:48 PM
¯\(º_o)/¯
 
AbecX's Avatar
 
Join Date: Nov 2001
Location: Las Colinas
Posts: 25,373
thats a math problem, why would anyone want to make a c program that answers that?
AbecX is offline  
post #3 of 8 (permalink) Old 01-25-2004, 02:28 PM Thread Starter
R.E.N.G.
 
Turd's Avatar
 
Join Date: Jul 2001
Location: E = MC Vagina
Posts: 2,919
I know, just stupid busy work to "get us thinking about problem solving"!
Turd is offline  
 
post #4 of 8 (permalink) Old 01-25-2004, 03:27 PM
HERE WE GO STEELERS
 
Geor!'s Avatar
 
Join Date: Dec 2003
Location: HERE WE GO!!!
Posts: 18,685
Just a guess, but i am fairly logical.. so here's the only solution the way I see it.

If all of the robbers are equally as greedy you have two options:

Divvy the certs. up evenly... 20 to each robber, but that would just be too easy... so here's what I propose: Robbers 5-2 get none of the certificates. Robber 1 gets all of them. If all of the robbers are extremely greedy, chances are, that they wouldn't agree on something unless it benefits them 100%. Now.. since they would go in descending order in seniority, this would leave robber number 1 with all of the money in the first place after the other 4 were killed... So makes sense to me to give it all to him and let him decide how to divvy it up... I'm probably way off, but that is the only way that makes sense to me...

Geor! is offline  
post #5 of 8 (permalink) Old 01-25-2004, 03:43 PM
No Cerveza... No Trabajo
 
01WhiteCobra's Avatar
 
Join Date: Jun 2002
Location: Where's my beer?
Posts: 21,924
Ah.... I'm so glad I'm over algorithm classes.

I'm not going to help you solve the problem, but I'll give you the logic behind the answer. You should be able to solve it readily with recursion (which, btw, is typically avoided in real-life business problems)

Your Problem
Any robber that gets 0 will always vote no (of course).

Work your problem from 2 robbers on up, instead of from 5 robbers on down.

If there are two robbers, the senior robber will vote he gets all of the bonds.
Robber 2 - 100
Robber 1 - 0

If there are three robbers, the senior robber will get 99 bonds and the LEAST senior robber will get 1. Why? Because, if he doesn't accept only 1 bond he will end up with none and be killed.
Robber 3 - 99
Robber 2 - 0
Robber 1 - 1

If there are four robbers, the senior robber will give himself 99 bonds and the number 2 robber gets 1.
Robber 4 - 99
Robber 3 - 0
Robber 2 - 1
Robber 1 - 0

Robber two will go for this, because, if he doesn't he wont get any and be killed.

If there are five robbers, the senior robber must give up 2 bonds to secure majority.

Robber 5 - 98
Robber 4 - 0
Robber 3 - 1
Robber 2 - 0
Robber 1 - 1

Robber 3 and 1 will go for this, because if there are only 4 robbers, they get squat.


In your recursion function, you need a terminal case, the smallest number before popping the stack. In this case it would be 2 (for two robbers). You must ensure the terminal case is always met, or you will eventually blow the stack and crash the program. Possibly you could still blow the stack, even if the terminal case is not met. Which is why recursion is typically avoided at all cost in real production code.
01WhiteCobra is offline  
post #6 of 8 (permalink) Old 01-25-2004, 03:45 PM
No Cerveza... No Trabajo
 
01WhiteCobra's Avatar
 
Join Date: Jun 2002
Location: Where's my beer?
Posts: 21,924
Quote:
Originally posted by Kayasuma
Just a guess, but i am fairly logical.. so here's the only solution the way I see it.

If all of the robbers are equally as greedy you have two options:

Divvy the certs. up evenly... 20 to each robber, but that would just be too easy... so here's what I propose: Robbers 5-2 get none of the certificates. Robber 1 gets all of them. If all of the robbers are extremely greedy, chances are, that they wouldn't agree on something unless it benefits them 100%. Now.. since they would go in descending order in seniority, this would leave robber number 1 with all of the money in the first place after the other 4 were killed... So makes sense to me to give it all to him and let him decide how to divvy it up... I'm probably way off, but that is the only way that makes sense to me...
You are using logic intersped with emotion. You'll always lose doing that.
01WhiteCobra is offline  
post #7 of 8 (permalink) Old 01-25-2004, 03:58 PM Thread Starter
R.E.N.G.
 
Turd's Avatar
 
Join Date: Jul 2001
Location: E = MC Vagina
Posts: 2,919
Quote:
Originally posted by 01WhiteCobra
Ah.... I'm so glad I'm over algorithm classes.

I'm not going to help you solve the problem, but I'll give you the logic behind the answer. You should be able to solve it readily with recursion (which, btw, is typically avoided in real-life business problems)

Your Problem
Any robber that gets 0 will always vote no (of course).

Work your problem from 2 robbers on up, instead of from 5 robbers on down.

If there are two robbers, the senior robber will vote he gets all of the bonds.
Robber 2 - 100
Robber 1 - 0

If there are three robbers, the senior robber will get 99 bonds and the LEAST senior robber will get 1. Why? Because, if he doesn't accept only 1 bond he will end up with none and be killed.
Robber 3 - 99
Robber 2 - 0
Robber 1 - 1

If there are four robbers, the senior robber will give himself 99 bonds and the number 2 robber gets 1.
Robber 4 - 99
Robber 3 - 0
Robber 2 - 1
Robber 1 - 0

Robber two will go for this, because, if he doesn't he wont get any and be killed.

If there are five robbers, the senior robber must give up 2 bonds to secure majority.

Robber 5 - 98
Robber 4 - 0
Robber 3 - 1
Robber 2 - 0
Robber 1 - 1

Robber 3 and 1 will go for this, because if there are only 4 robbers, they get squat.


In your recursion function, you need a terminal case, the smallest number before popping the stack. In this case it would be 2 (for two robbers). You must ensure the terminal case is always met, or you will eventually blow the stack and crash the program. Possibly you could still blow the stack, even if the terminal case is not met. Which is why recursion is typically avoided at all cost in real production code.
thanks, that was already my current favortie route, just wanted another opinion before I looked like a dumbass. when just writing out tables I am able to convince myself that there every new pattern I write down would provide a better solution, but now I'll just stick with this scenario.
Turd is offline  
post #8 of 8 (permalink) Old 01-25-2004, 04:02 PM Thread Starter
R.E.N.G.
 
Turd's Avatar
 
Join Date: Jul 2001
Location: E = MC Vagina
Posts: 2,919
I was getting too caught up in the logic, and thinking that was too simple. It's funny how often I make simple things complex by not trusting my gut. Thanks again.
Turd is offline  
Sponsored Links
Advertisement
 
Reply

Bookmarks

Quick Reply
Message:
Options

Register Now



In order to be able to post messages on the DFWstangs Forums forums, you must first register.
Please enter your desired user name, your email address and other required details in the form below.

User Name:
Password
Please enter a password for your user account. Note that passwords are case-sensitive.

Password:


Confirm Password:
Email Address
Please enter a valid email address for yourself.

Email Address:
OR

Log-in










Thread Tools
Show Printable Version Show Printable Version
Email this Page Email this Page
Display Modes
Linear Mode Linear Mode



Posting Rules  
You may post new threads
You may post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On
Trackbacks are On
Pingbacks are On
Refbacks are On

 
For the best viewing experience please update your browser to Google Chrome