n個空間中4個對象排列的遞歸算法

我已經解決了下面顯示的算法。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

我在這花了很多時間。我知道有多少種排列沒有上述算法的空白空間。所以我一直在試圖弄清楚有多少空置空間。這兩套的結合應該給我答案。對於n，具有一個或多個空白空間的單個空間排列的數目是2^n-1。但我不認爲這將幫助我在遞歸解決方案。

任何指導，將不勝感激。

來源

2011-09-16 Alex_B

看起來像Java或C＃給我。 –

當然你想要一個遞歸解決方案？有一個**更快的DP解決方案。 – quasiverse

Java，我添加了標籤。我對動態編程不熟悉，但由於這個任務中的其他問題是遞歸的，所以我也假設這也是。 –

我想這樣的作品：

public static long park(int n) 
{ 
    if(n==1) 
     { return 2; } 
    else if(n==2) 
     { return 5; } 
    else if(n==3) 
     { return 13; } 
    else 
     { 
     return (park(n-1) + park(n-1) + park(n-2) + park(n-3)); 
     } 
}

來源

2011-09-16 09:43:21 Steve

謝謝。這似乎工作，並遞歸。 –

隨時接受答案:) – Steve

爲簡單起見，我將解釋其中使用遞歸腳麻的N < 3。

對於一個空間，在兩個情況中，E和1，因此，當n = 1時，它應該是2.

當它爲2，則它應該返回1個+公園（1）+公園（1 ），因爲2是2，1E，E1,11，當它是2時仍然沒問題。

當它是3時，它應該返回1 +公園（2）+公園（1）+公園（1）+公園（2）+公園（1）+公園（1）+公園（1）可以看到，在公園（1）+公園（2）和公園（2）+公園（1）不止一次會計算一些情況。你必須刪除所有這些重複。

我不認爲這是處理這個問題的好方法。

數學會更容易。

考慮空槽爲N1,1槽車爲N2,2槽車爲N3,3槽車爲N4。

N1 + N2 + 2 * N3 + 3 * N4 = N

我認爲你可以自己弄清楚它休息了。

來源

2011-09-16 10:16:42 iamsleepy

n個空間中4個對象排列的遞歸算法

回答

相關問題