n空间中4个对象排列的java递归算法
我已经解决了如下所示的算法
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。 但我认为这对递归解决方案没有帮助
任何指导都将不胜感激
# 1 楼答案
我认为这是可行的:
# 2 楼答案
为了简单起见,我将解释N<;3.使用递归
对于一个空间,有两种情况,E和1,所以当n=1时,它应该是2
当它是2时,它应该返回1+park(1)+park(1),因为2是2,1E,E1,11,当它是2时仍然可以
当它是3时,它应该返回1+公园(2)+公园(1)+公园(1)+公园(2)+公园(1)+公园(1),但你可以看到,在公园(1)+公园(2)和公园(2)+公园(1)中,某些情况会不止一次计算。你必须移除所有这些重复
我认为这不是解决这个问题的好办法
数学会更容易
空槽为N1,1槽车为N2,2槽为N3,3槽为N4。p>
N1+N2+2*N3+3*N4=N
我想你可以自己解决剩下的问题