n 空间中 4 个对象排列的递归算法
我已经解决了如下所示的算法。
public static long park(int n)
{
// precondition: n >= 1
// postcondition: Return the number of ways to park 3 vehicles,
// designated 1, 2 and 3 in n parking spaces, without leaving
// any spaces empty. 1 takes one parking space, 2 takes two spaces,
// 3 takes three spaces. Each vehicle type cannot be distinguished
// from others of the same type, ie for n=2, 11 counts only once.
// Arrangements are different if their sequences of vehicle types,
// listed left to right, are different.
// For n=1: 1 is the only valid arrangement, and returns 1
// For n=2: 11, 2 are arrangements and returns 2
// For n=3: 111, 12, 21, 3 are arrangements and returns 4
// For n=4: 1111,112,121,211,22,13,31 are arrangements and returns 7
if(n==1)
{ return 1; }
else if(n==2)
{ return 2; }
else if(n==3)
{ return 4; }
else
{
return (park(n-1) + park(n-2) + park(n-3));
}
}
我需要帮助的是解决一个后续问题,即在排列中包含空停车位。这应该递归地解决。
Let's designate a single empty space as E.
For n=1: 1,E and returns 2
For n=2: 11,2,EE,1E,E1 and returns 5
For n=3: 111,12,21,3,EEE,EE1,E1E,1EE,11E,1E1,E11,2E,E2 and returns 13
For n=4: there are 7 arrangements with no E, and 26 with an E, returns 33
我在这上面花了很多时间。从上面的算法我知道有多少种没有空格的排列。所以我一直试图找出有多少种排列有 1 个或多个空位。这两组的并集应该给我答案。 对于 n,具有一个或多个空格的单空间排列的数量为 2^n-1。 但我不认为这对我的递归解决方案有帮助。
任何指导将不胜感激。
I have solved the following algorithm shown below.
public static long park(int n)
{
// precondition: n >= 1
// postcondition: Return the number of ways to park 3 vehicles,
// designated 1, 2 and 3 in n parking spaces, without leaving
// any spaces empty. 1 takes one parking space, 2 takes two spaces,
// 3 takes three spaces. Each vehicle type cannot be distinguished
// from others of the same type, ie for n=2, 11 counts only once.
// Arrangements are different if their sequences of vehicle types,
// listed left to right, are different.
// For n=1: 1 is the only valid arrangement, and returns 1
// For n=2: 11, 2 are arrangements and returns 2
// For n=3: 111, 12, 21, 3 are arrangements and returns 4
// For n=4: 1111,112,121,211,22,13,31 are arrangements and returns 7
if(n==1)
{ return 1; }
else if(n==2)
{ return 2; }
else if(n==3)
{ return 4; }
else
{
return (park(n-1) + park(n-2) + park(n-3));
}
}
What I need help on is figuring out a followup problem which is to include empty parking spaces in the permutation. This should be solved recursively.
Let's designate a single empty space as E.
For n=1: 1,E and returns 2
For n=2: 11,2,EE,1E,E1 and returns 5
For n=3: 111,12,21,3,EEE,EE1,E1E,1EE,11E,1E1,E11,2E,E2 and returns 13
For n=4: there are 7 arrangements with no E, and 26 with an E, returns 33
I've spent many hours on this. I know how many arrangements there are without an empty space from the above algorithm. So I've been trying to figure out how many arrangements there are with 1 or more empty spaces. The union of these two sets should give me the answer.
For n, the number of single space permutations with one or more empty spaces is 2^n-1.
But I don't think this will help me in a recursive solution.
Any guidance would be appreciated.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
我认为这有效:
I think this works:
为了简单起见,我将解释 N < 哪里出了问题。 3.使用递归。
对于一个空间来说,有两种情况,E和1,所以当n=1时,应该是2。
当是2时,应该返回1+park(1)+park(1),因为2就是2,1E ,E1,11,两个的时候还可以。
当它是 3 时,它应该返回 1 + park(2) + park(1) + park(1) + park(2) + park(1) + park(1) + park(1) 但你可以看到, Park(1) + Park(2) 和 Park(2) + Park(1) 会多次计算某些情况。你必须删除所有这些重复的内容。
我认为这不是解决这个问题的好方法。
数学会更容易。
考虑空车位为N1,1车位车为N2,2车位车为N3,3车位车为N4。
N1 + N2 + 2 * N3 + 3 * N4 = N
我想你可以自己算出剩下的部分。
To make it simple, i will explain where is going wrong in N < 3 using recursive.
For one space, there is two situation, E and 1, so when n = 1, it should be 2.
When it is 2, it should return 1 + park(1) + park(1), because 2 is 2, 1E, E1,11, It is still ok when it is two.
When it is 3, it should return 1 + park(2) + park(1) + park(1) + park(2) + park(1) + park(1) + park(1) but you can see, in Park(1) + Park(2) and Park(2) + Park(1) will count some situation more than once. You have to remove all these repeat.
I don't think this is a good way to deal with this problem.
Math will be easier.
Consider empty slots is N1, 1 slot car is N2, 2 slots car is N3, 3 slots car is N4.
N1 + N2 + 2 * N3 + 3 * N4 = N
I think you can figure rest of it out by yourself.