Тойрогт k дахь хүн бүр гардаг тоглоомд хэн үлдэхийг recursion ашиглан олно.

Pre-IntermediateХугацаа: O(n)Санах ой: O(n) (рекурс)

Эхлээд жижиг бодлого

7 хүн тойрог болж зогсоно. 1-ээс эхлэн тоолж, 3 дахь хүн бүр гарна. Гарах дараалал: 3, 6, 2, 7, 5, 1.

Сүүлд 4-р хүн үлдэнэ. Хариу: 4.

Энгийн аргаас санаа руу

Энгийн арга: тойргийг list-ээр хадгалж, k алхам тоолоод нэг хүн хасна. n хүн хасах тул O(n · k), устгах нь удаан бол O(n²).

Гол санаа: нэг хүн гарсны дараа үлдсэн n − 1 хүн яг ижил тоглоом тоглоно. Зөвхөн дугаарлалт нь k-гаар шилжсэн. Тиймээс n − 1 хүний ялагчийн дугаар дээр k нэмээд n-д хуваасан үлдэгдлийг авбал n хүний ялагч гарна: jos(n) = (jos(n - 1) + k) % n.

Нэр томьёо ба тэмдэглэгээ

jos(n)
n хүнтэй тойргийн ялагчийн дугаар, 0-ээс эхэлсэн.
base case
jos(1) = 0: ганц хүн бол тэр ялагч.
% n
Тойрог учраас дугаар n-д хүрвэл 0-ээс дахин эхэлнэ.
call stack
Хүлээж буй recursion дуудалтууд. Энд n дуудалт зэрэг хүлээнэ.
1234567
n = 7k = 3
Call stack
хоосон

7 хүн тойрог болж зогсоно. Эхний хүнээс эхлэн тоолж, 3 дахь хүн бүр тойргоос гарна. Хамгийн сүүлд хэн үлдэх вэ? Тоглоомыг тоглолгүйгээр recursion ашиглан олъё.

Алхам 1 / 15
Хурд
  • Энэ удаа гарах хүн
  • Ялагч
  • Ганц үлдсэн
  • Гарсан
Слайд 1 / 6

Тойргийн тоглоом

7 хүн тойрог болж зогсоно. 3 дахь хүн бүр гарна: 3, 6, 2, 7, 5, 1. Сүүлд 4 үлдэнэ. Тоглоомыг тоглолгүйгээр үүнийг олох арга бий.

josephus.cpp
#include <bits/stdc++.h>
using namespace std;
int k;
int jos(int n) {
if (n == 1) return 0;
int r = (jos(n - 1) + k) % n;
return r;
}
int main() {
int n;
cin >> n >> k;
cout << jos(n) + 1 << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Тоглоомыг нэг нэгээр нь тоглолгүйгээр ялагчийг n алхамд олно. Жижиг бодлогын хариунаас том бодлогын хариуг гаргадаг сайхан жишээ.

Яаж ажилладаг вэ?

1. jos(n) бол n хүнтэй тойргийн ялагчийн дугаар. Дугаар 0-ээс эхэлнэ. 2. jos(1) = 0: ганц хүн байвал тэр л ялагч. Энэ бол base case. 3. Нэг хүн гарсны дараа n − 1 хүнтэй ижил тоглоом үлдэнэ. Зөвхөн дугаарлалт нь k-гаар шилжсэн. Тиймээс jos(n) = (jos(n − 1) + k) % n. 4. Хариу нь jos(n) + 1. Оролт: n ба k.

Яагаад зөв, хэр хурдан бэ?

n хүнтэй тойрогт эхлээд #(k − 1) гарна, тойрог учраас n-д хуваасан үлдэгдлээр. Дараа нь түүний дараагийн хүнээс эхлэн шинээр дугаарлавал n − 1 хүнтэй ижил тоглоом болно. Тэнд #r ялсан хүн хуучин дугаараар (r + k) % n байна. Base case зөв, алхам бүр зөв тул бүх n-д зөв.

n дуудалт, тус бүр O(1): хугацаа O(n). Recursion n гүнтэй тул n = 10⁶ бол stack хүрэлцэхгүй байж болно. Тэр үед loop ашиглан бич.

Түгээмэл алдаа

  • Хариуд 1 нэмэхээ мартах. jos 0-ээс эхэлсэн дугаар буцаана.
  • % n-ийг мартах. Дугаар n-ээс хэтэрнэ.
  • Том n дээр recursion stack overflow өгнө. int r = 0; for (int i = 2; i <= n; i++) r = (r + k) % i; гэж loop ашиглан бич.
  • k > n үед k-г өөрчлөх гэж оролдох. Томьёо k > n үед ч зөв ажилладаг.

Хязгаарын тохиолдол

  • n = 1: шууд 1 хэвлэнэ.
  • k = 1: хүмүүс дарааллаараа гарна, сүүлд n-р хүн үлдэнэ.
  • n = 5, k = 2: гарах дараалал 2, 4, 1, 5, хариу 3.
  • k > n, жишээ нь n = 5, k = 8: тойргийг хэд хэдэн удаа эргэж тоолно, томьёо өөрчлөгдөхгүй. Хариу 1.

Өөрийгөө шалга

  1. k = 3 бол jos(2) хэд вэ?

    Хариу харах

    (0 + 3) % 2 = 1. Хоёр дахь хүн ялна.

  2. n = 4, k = 2 бол хариу хэд вэ?

    Хариу харах

    1. Гарах дараалал: 2, 4, 3.

  3. Яагаад % n хийдэг вэ?

    Хариу харах

    Дугаарууд тойрог болж эргэдэг. n-д хүрвэл 0 рүү буцна.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 6, k = 2 дээр jos(1)-ээс jos(6) хүртэлх утгуудыг бод.

    Hint харах

    jos(1) = 0-ээс эхэлж томьёог дахин дахин хэрэглэ.

    Хариу ба тайлбар

    0, 0, 2, 0, 2, 4. Хариу: 4 + 1 = 5.

  2. 2.Энэ функцийг recursion биш, loop ашиглан бич.

    Hint харах

    jos(1)-ээс эхлээд дээш нь бод.

    Хариу ба тайлбар

    int r = 0; for (int i = 2; i <= n; i++) r = (r + k) % i; cout << r + 1; Stack хэрэглэхгүй тул n = 10⁷ ч асуудалгүй.

  3. 3.k = 2 үед ялагчийн томьёог гаргаж, n = 1 … 16 дээр шалга.

    Hint харах

    n = 1, 2, …, 16-гийн хариуг бичээд 2-ын зэрэг дээр юу болдгийг ажигла.

    Хариу ба тайлбар

    Хариунууд: 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1. n = 2ᵐ + L (0 ≤ L < 2ᵐ) бол хариу 2L + 1. Жишээ нь n = 6 = 4 + 2 бол 5.

Жишээ

Оролт

7 3

Гаралт

4