Агуулгыг алгасах

Иосефын бодлого

Нөхцөл

Бидэнд $n$ ба $k$ натурал тоо өгөгдсөн. $1$-ээс $n$ хүртэлх бүх натурал тоог тойрог хэлбэрээр бичнэ. Эхлээд эхнийхээс эхлэн $k$-р тоог тоолж, түүнийг устгана. Дараа нь дараагийнхаас эхлэн $k$ тоо тоолж, $k$-р тоог дахин хасах ба ингэсээр үргэлжилнэ. Процесс нэг тоо үлдэхэд зогсоно. Сүүлийн тоог олох шаардлагатай.

Энэ бодлогыг 1-р зуунд Флавиус Иосеф тавьсан (гэхдээ арай нарийн томьёололд: $k = 2$-ийн хувьд).

Энэ бодлогыг процедурыг загварчлах замаар бодож болно. Шууд хүчний загварчлал $O(n^{2})$-д ажиллана. Хэрчмийн мод ашиглан бид үүнийг $O(n \log n)$ хүртэл сайжруулж болно. Гэвч бид үүнээс илүү сайн зүйл хүсэж байна.

$O(n)$ шийдлийг загварчлах

Бид өмнөх бодлогуудын шийдлээр дамжуулан $J_{n, k}$ бодлогын хариуг илэрхийлэх хэв маягийг олохыг оролдоно.

Шууд хүчний загварчлал ашиглан бид утгуудын хүснэгт байгуулж болно, жишээ нь дараах:

$$\begin{array}{ccccccccccc} n\setminus k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ 3 & 3 & 3 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 \\ 4 & 4 & 1 & 1 & 2 & 2 & 3 & 2 & 3 & 3 & 4 \\ 5 & 5 & 3 & 4 & 1 & 2 & 4 & 4 & 1 & 2 & 4 \\ 6 & 6 & 5 & 1 & 5 & 1 & 4 & 5 & 3 & 5 & 2 \\ 7 & 7 & 7 & 4 & 2 & 6 & 3 & 5 & 4 & 7 & 5 \\ 8 & 8 & 1 & 7 & 6 & 3 & 1 & 4 & 4 & 8 & 7 \\ 9 & 9 & 3 & 1 & 1 & 8 & 7 & 2 & 3 & 8 & 8 \\ 10 & 10 & 5 & 4 & 5 & 3 & 3 & 9 & 1 & 7 & 8 \\ \end{array}$$

Эндээс бид дараах хэв маяг-ийг тод харж болно:

$$J_{n,k} = \left( (J_{n-1,k} + k - 1) \bmod n \right) + 1$$
$$J_{1,k} = 1$$

Энд 1-индекслэл нь томьёог арай эмх замбараагүй болгодог; хэрэв та байрлалыг 0-ээс дугаарлавал маш дэгжин томьёо гарна:

$$J_{n,k} = (J_{n-1,k} + k) \bmod n$$

Ингэснээр бид Иосефын бодлогод $O(n)$ үйлдэлд ажилладаг шийдэл оллоо.

Implementation

Simple recursive implementation (in 1-indexing)

int josephus(int n, int k) {
    return n > 1 ? (josephus(n-1, k) + k - 1) % n + 1 : 1;
}

Non-recursive form :

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
      res = (res + k) % i;
    return res + 1;
}

This formula can also be found analytically. Again here we assume 0-indexing. After we delete the first number, we have $n-1$ numbers left. When we repeat the procedure, we will start with the number that had originally the index $k \bmod n$. $J_{n-1, k}$ would be the answer for the remaining circle, if we start counting at $0$, but because we actually start with $k$ we have $J_{n, k} = (J_{n-1,k} + k) \ \bmod n$.

$O(k \log n)$ шийдлийг загварчлах

Харьцангуй бага $k$-ийн хувьд бид дээрх $O(n)$ рекурсив шийдлээс илүү сайн шийдэл гаргаж болно. Хэрэв $k$ нь $n$-ээс хамаагүй бага бол бид нэг гүйлтэд давталгүйгээр олон тоо ($\lfloor \frac{n}{k} \rfloor$) устгаж болно. Үүний дараа бидэнд $n - \lfloor \frac{n}{k} \rfloor$ тоо үлдэх ба бид $(\lfloor \frac{n}{k} \rfloor \cdot k)$-р тооноос эхэлнэ. Тиймээс бид тэр хэмжээгээр шилжих ёстой. $\lfloor \frac{n}{k} \rfloor \cdot k$ нь зүгээр л $-n \bmod k$ болохыг анзаарч болно. Бид $k$-р тоо бүрийг устгасан тул үр дүнгийн индексээс өмнө устгасан тоонуудынхаа тоог нэмэх ёстой. Үүнийг үр дүнгийн индексийг $k - 1$-д хуваах замаар тооцоолж болно.

Мөн $n$ нь $k$-ээс бага болох тохиолдлыг зохицуулах хэрэгтэй. Энэ тохиолдолд дээрх оптимизаци төгсгөлгүй давталтад хүргэнэ.

Implementation (for convenience in 0-indexing):

int josephus(int n, int k) {
    if (n == 1)
        return 0;
    if (k == 1)
        return n-1;
    if (k > n)
        return (josephus(n-1, k) + k) % n;
    int cnt = n / k;
    int res = josephus(n - cnt, k);
    res -= n % k;
    if (res < 0)
        res += n;
    else
        res += res / (k - 1);
    return res;
}

Энэ алгоритмын complexity-г үнэлье. Эхлээд $n < k$ тохиолдлыг хуучин шийдлээр шинжилдэг бөгөөд энэ тохиолдолд $O(k)$-д ажиллана гэдгийг тэмдэглэе. Одоо алгоритмыг өөрийг нь авч үзье. Үнэн хэрэгтээ итерац бүрийн дараа $n$ тооны оронд бидэнд $n \left( 1 - \frac{1}{k} \right)$ тоо үлдэх тул алгоритмын нийт итерацийн тоо $x$-г дараах тэгшитгэлээс ойролцоогоор олж болно:

$$ n \left(1 - \frac{1}{k} \right) ^ x = 1, $$

хоёр талд логарифм авбал бид:

$$\ln n + x \ln \left(1 - \frac{1}{k} \right) = 0,$$ $$x = - \frac{\ln n}{\ln \left(1 - \frac{1}{k} \right)},$$

логарифмыг Тейлорын цуваанд задалснаар бид ойролцоо үнэлгээ олж авна:

$$x \approx k \ln n$$

Тиймээс алгоритмын complexity нь үнэндээ $O (k \log n)$ болно.

$k = 2$-ийн аналитик шийдэл

Энэ тодорхой тохиолдолд (Иосеф Флавиус энэ бодлогыг тавьсан) бодлого хамаагүй амархан бодогдоно.

Тэгш $n$-ийн хувьд бүх тэгш тоо хасагдах ба дараа нь $\frac{n}{2}$-ийн хувьд бодлого үлдэнэ, тэгвэл $n$-ийн хариу нь $\frac{n}{2}$-ийн хариунаас хоёроор үржүүлж, нэгийг хасаж (байрлалыг шилжүүлэх замаар) гарна:

$$ J_{2n, 2} = 2 J_{n, 2} - 1 $$

Үүнтэй адил, сондгой $n$-ийн хувьд бүх тэгш тоо, дараа нь эхний тоо хасагдаж, $\frac{n-1}{2}$-ийн бодлого үлдэх ба байрлалын шилжилтийг харгалзан бид хоёр дахь томьёог олж авна:

$$J_{2n+1,2} = 2 J_{n, 2} + 1 $$

Бид энэ рекуррент хамаарлыг хэрэгжүүлэлтдээ шууд ашиглаж болно. Энэ хэв маягийг өөр хэлбэрт хувиргаж болно: $J_{n, 2}$ нь $n$ хоёрын зэрэг болох бүрд нэгээс "дахин эхэлдэг" бүх сондгой тоонуудын дарааллыг илэрхийлнэ. Үүнийг нэг томьёогоор бичиж болно:

$$J_{n, 2} = 1 + 2 \left(n-2^{\lfloor \log_2 n \rfloor} \right)$$

$k > 2$-ийн аналитик шийдэл

Бодлогын энгийн хэлбэр ба энэ болон холбогдох бодлогуудын талаарх олон тооны өгүүллийг үл харгалзан Иосефын бодлогын шийдлийн энгийн аналитик илэрхийллийг хараахан олоогүй байна. Бага $k$-ийн хувьд зарим томьёо гаргасан боловч тэдгээр нь бүгд практикт хэрэглэхэд хэцүү бололтой (жишээ нь Halbeisen, Hungerbuhler "The Josephus Problem" ба Odlyzko, Wilf "Functional iteration and the Josephus problem"-ыг үзнэ үү).