Adottak az {1, 1, 2, 2, …, n, n} számok. Van-e olyan sorrendjük, ahol a k szám két előfordulása között pontosan k darab elem van, minden k ∈ {1,2,…,n} esetén?
Ha igen, adjunk meg egy ilyen permutációt! Adott 1 <= n <= 16 esetén adjuk meg, hány különböző Langford permutáció létezik. PéldaHa n = 3, akkor egyetlen ilyen permutáció létezik: 231213 . Megjegyzés: a szimmetrikus párokat azonosnak tekintjük, tehát a 312132 ugyanannak számít, mint a fenti megoldás. TesztadatokL[n] a Langford-permutációk számát jelöli.
n | L[n] | 1 | 0 | 2 | 0 | 3 | 1 | 4 | 1 | 5 | 0 | 6 | 0 | 7 | 26 | 8 | 150 | 9 | 0 | 10 | 0 | 11 | 17792 | 12 | 108144 | 13 | 0 | 14 | 0 | 15 | 39809640 | 16 | 326721800 |
Címkék
A feladat forrása: saját feladat
Algoritmusok: összes eset generálása, visszalépéses keresés, backtrack
megoldás |