python recursive function

[Tom_chicollegeboy]

here is what I have to do:

This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):

If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)

If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.

For example, suppose that you start with 250 bears. Then you could
make these moves:

Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.


Usage:

>>bears(42)

True

>>bears(250)

True

>>bears(50)

False

>>bears(84)

True

>>bears(41)

False


As you see my program must use recursion.

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False

If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

[Gary Herron]

Re: python recursive function

Tom_chicollegeb oy wrote:

here is what I have to do:
>
This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):
>

This sounds very much like a homework assignment, and so should probably
not be answered here. (Neither should it have been asked here.) If,
in your attempt to write this program, you have some questions about
Python, then I encourage to ask those questions here.

Gary Herron

If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)
>
If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.
>
For example, suppose that you start with 250 bears. Then you could
make these moves:
>
Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.
>
>
Usage:
>
>

>>>bears(42)
>>>>

True
>

>>>bears(250)
>>>>

True
>

>>>bears(50)
>>>>

False
>

>>>bears(84)
>>>>

True
>

>>>bears(41)
>>>>

False
>
>
As you see my program must use recursion.
>
I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:
>
def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False
>
If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!
>

[Bruno Desthuilliers]

Re: python recursive function

Tom_chicollegeb oy a écrit :
(snip)

As you see my program must use recursion.

It's conceptually easier to express using recursions - but every
recursion-based algorithm can be rewritten to use iteration (and
vice-versa).

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:
>
def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)

You want:
return bears(n - 42)

if n%2==0:
bears(n/2)

idem

if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))

idem

return False
>

[Bruno Desthuilliers]

Re: python recursive function

Gary Herron a écrit :

Tom_chicollegeb oy wrote:

>here is what I have to do:
>>
>This question involves a game with teddy bears. The game starts when I
>give you some bears. You then start giving me back some bears, but you
>must follow these rules (where n is the number of bears that you
>have):
>>

This sounds very much like a homework assignment,

Indeed.

and so should probably
not be answered here. (Neither should it have been asked here.) If,
in your attempt to write this program, you have some questions about
Python, then I encourage to ask those questions here.

Garry, you should have read the whole post before answering. The OP's
attempt at solving the problem was below, along with the question.

(snip)

[cokofreedom@gmail.com]

Re: python recursive function

On Jan 11, 9:46 am, Gary Herron <gher...@island training.comwro te:

Tom_chicollegeb oy wrote:

here is what I have to do:

>

This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):

>
This sounds very much like a homework assignment, and so should probably
not be answered here. (Neither should it have been asked here.) If,
in your attempt to write this program, you have some questions about
Python, then I encourage to ask those questions here.
>
Gary Herron
>

If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)

>

If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.

>

For example, suppose that you start with 250 bears. Then you could
make these moves:

>

Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.

>

Usage:

>

>>bears(42)

>

True

>

>>bears(250)

>

True

>

>>bears(50)

>

False

>

>>bears(84)

>

True

>

>>bears(41)

>

False

>

As you see my program must use recursion.

>

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:

>

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False

>

If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

Note that for ;
if one!=0 and two!=0:

you can use
if one and two:

which is my pythonic.

Also in your example with 52, shouldn't it divide by even first?
Obviously this must not happen, thus maybe you should run a check that
when you are returning a new value it does not go below 42? Frankly
this looks like a terrible way to use recursion.

[Duncan Booth]

Re: python recursive function

Bruno Desthuilliers <bruno.42.desth uilliers@wtf.we bsiteburo.oops. com>
wrote:

You want:
return bears(n - 42)

Actually, no he doesn't. He needs to explore all options when the first
attempt fails. But I'm not going to write his homework for him.

[Chris]

Re: python recursive function

On Jan 11, 10:30 am, Tom_chicollegeb oy <tbab...@gmail. comwrote:

here is what I have to do:
>
This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):
>
If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)
>
If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.
>
For example, suppose that you start with 250 bears. Then you could
make these moves:
>
Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.
>
Usage:
>

>bears(42)

True

>bears(250)

True

>bears(50)

False

>bears(84)

True

>bears(41)

>
False
>
As you see my program must use recursion.
>
I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:
>
def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False
>
If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

Stylistically I prefer 'if not n % 5', looks neater.
As for your assignment, the hardest task will be creating an effective
method of ensuring you recurse through all possibilities.

ie. do you brute force on every step, or when getting to step do you
fork your possibilities.
That is more a design question rather than a python one though.

[cokofreedom@gmail.com]

Re: python recursive function

Stylistically I prefer 'if not n % 5', looks neater.

As for your assignment, the hardest task will be creating an effective
method of ensuring you recurse through all possibilities.

I was chatting to a friend about the 'if not n % 5' and while I am
happy to use it saying that when 5 % 5 is False because it returns
0...for this case just feels wrong to me.

I understand the reason to keep it this way...but still...having to
use not all the time is just annoying.

[HYRY]

Re: python recursive function

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False
>
If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

try this:

def bears (n):
if n==42:
return True
if n%5==0:
if bears(n-42):
return True
if n%2==0:
if bears(n/2):
return True
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
if bears(n-(one*two)):
return True
return False

print bears(42)
print bears(250)
print bears(50)
print bears(84)
print bears(41)

[Bruno Desthuilliers]

Re: python recursive function

Duncan Booth a écrit :

Bruno Desthuilliers <bruno.42.desth uilliers@wtf.we bsiteburo.oops. com>
wrote:
>

>You want:
> return bears(n - 42)

>
Actually, no he doesn't. He needs to explore all options when the first
attempt fails.

Possibly - I didn't bother checking the algorithm correctness, just
pointed out an obvious newbie programming error.

But I'm not going to write his homework for him.

Nor do I.

[Nick Craig-Wood]

Re: python recursive function

HYRY <ruoyu0088@gmai l.comwrote:

def bears (n):
if n==42:
return True
if n%5==0:
if bears(n-42):
return True
if n%2==0:
if bears(n/2):
return True
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
if bears(n-(one*two)):
return True
return False

Almost but you missed a case...

>>for i in range(100):

.... try:
.... print i, bears(i)
.... except RuntimeError, e:
.... print i, e
....
0 0 maximum recursion depth exceeded
1 False
2 False
3 False
4 False
5 False
6 False
7 False
8 False
9 False
10 10 maximum recursion depth exceeded
11 False
12 12 maximum recursion depth exceeded
113 False
14 False
15 15 maximum recursion depth exceeded
16 16 maximum recursion depth exceeded
17 False
[snip]
89 False
90 90 maximum recursion depth exceeded
91 False
92 False
93 93 maximum recursion depth exceeded
94 False
95 False
96 96 maximum recursion depth exceeded
97 False
98 False
99 99 maximum recursion depth exceeded

--
Nick Craig-Wood <nick@craig-wood.com-- http://www.craig-wood.com/nick

[Fidtz]

Re: python recursive function

On 11 Jan, 08:30, Tom_chicollegeb oy <tbab...@gmail. comwrote:

here is what I have to do:
>
This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):
>
If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)
>
If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.
>
For example, suppose that you start with 250 bears. Then you could
make these moves:
>
Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.
>
Usage:
>

>bears(42)

True

>bears(250)

True

>bears(50)

False

>bears(84)

True

>bears(41)

>
False
>
As you see my program must use recursion.
>
I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:
>
def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False
>
If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

May != Must and Could != Should

[Steven D'Aprano]

Re: python recursive function

On Fri, 11 Jan 2008 06:30:04 -0600, Nick Craig-Wood wrote:

HYRY <ruoyu0088@gmai l.comwrote:

> def bears (n):
> if n==42:
> return True

....

> return False

>
Almost but you missed a case...

Why are you people doing the OP's homework for him? And then DEBUGGING it
as well? Haven't you got something better to do than to help create a new
generation of incompetent, under-educated programmers?




--
Steven