help needed with recursion algorithm..
I can't seems to figure out which recursion method to use, if anyone can give me some advice, pls do..
Input: There is a row ofn elecments with the initial value of 1.
Output: Change all the 1s to 0s using the following conditions.
-The first element can change from 1 to 0, and 0 to 1 at any time (without conditions).
-While the rest of the elements can only be changed to 0 when the preceeding element is 1 and all other elements are 0.
For example, whenn = 3
1 1 1 - initial state of all elements
0 1 1 - change first element to 0 w/o condition
0 1 0 - change third element to 0 as only second element is 1 and rest are 0
1 1 0 - change first element to 1 w/0 condition
1 0 0 - change second element to 0 as only first element is 1 and rest are 0
0 0 0 - change first element to 0 w/o condition
I really can't think of a recursive method to work this out, and am desperate to know the answer. Can anyone please help?
[1018 byte] By [
rukiaa] at [2007-10-2 5:22:23]
It's insoluble for n > 3. Are you sure you've understood the problem correctly?
I have also noticed that as I was trying to finger it out for the past few days. But that is the way the question is being asked. What about the possibility of coming out with an recursive algorithm based on n = 3? Is there any recursion method that can solve the problem?
Thanks for the reply
Your working seems to reduce it to the case n=2 in the fourth line. However, the solution of the case n=2 is quite different to the solution of the case n=3. Maybe. I suppose they can be unified as clear(int n)
{
if (n == 0)
{
return;
}
if (n == 1)
{
flip(0);
return;
}
clear(n - 2);
attemptFlip(n - 1);
reset(n - 2);
clear(n - 1);
}
If this is a homework exercise (as I presume, since it has no practical application as is) I think you're probably better off asking the person who set it whether they've set the problem they intended to set.
The system you have described is the recursion relationship for solving the chinese ring puzzle. The thing that you left out that led YAT to believe that it is insolvable is simple that anytime you have a string like
00...0001x
you can set x to either zero or one
The system is practically in recursive form already. Here are the components that you need
write routine setBit(int bitNumber, boolean bit)
and write routine setAllBits(int bitNumber, boolean bit)
How do you setAllBits(n, b)? Clearly you setBit(n,b) and then setAllBits(n-1,b)
How do you setBit(n, b) well if n is the first bit you just set it but if n is not the firs bit then you must first setBit(n-1, true) then setAllBits(n-2, false) before you can finally make the nth bit = b.
Yeah, you could have 0000001x and change x to anything, but when it starts out 111111111 how do you get to that point? You can flip the first bit all you want, but no other bits because the requirement is all bits but the preceding bit be 0. If I had to guess, I think the person who set the question meant that either all bits to the right must be 0 or all bits to the left must be 0, not that both must be true. If it was all to the right:
11111
11110
11100
11000
10000
00000
But that seems to easy. If you made it so all bits to the left of the preceding bit must be 0 it gets more interesting:
11111
01111
01011
11011
10011
00011
00010
00110
00100
01100
01000
11000
10000
00000
But even that doesn't make sense because the question implies that you can't change any bit but the first back to a 1.
I really don't understand the question.
Sorry about it, you can change the rest of the bit back to 1 but provided that the preceeding bit is also 1.
and that makes the question:
Input: There is a row of n elecments with the initial value of 1.
Output: Change all the 1s to 0s using the following conditions.
-The first element can change from 1 to 0, and 0 to 1 at any time (without conditions).
-While the rest of the elements can only be changed to 0 or 1 when the preceeding element is 1 and all other elements are 0.
For example, when n = 3
1 1 1 - initial state of all elements
0 1 1 - change first element to 0 w/o condition
0 1 0 - change third element to 0 as only second element is 1 and rest are 0
1 1 0 - change first element to 1 w/0 condition
1 0 0 - change second element to 0 as only first element is 1 and rest are 0
0 0 0 - change first element to 0 w/o condition
I'll check my the person who sets the question and get back to you guys as soon as possible. Thanks a lot for helping me out.
As I said, the reccurance relation is that of the chinese rings, it was just misstated. The code is what I described, a handful of lines. http://staff.ccss.edu.hk/jckleung/ninering/solu_eng.html
> As I said, the reccurance relation is that of the
> chinese rings, it was just misstated. The code is
> what I described, a handful of lines.
>
> http://staff.ccss.edu.hk/jckleung/ninering/solu_eng.ht
> ml
Sorry to ask, but how should the algorithm or the code be like if its of the Chinese Rings Puzzle?
