Азтай хулгана

Тавил:
Тойрог дээр N ширхэг хулгана сууж байв. Хулганууд 1..N гэсэн дугааруудтай. Муур 1-р хулганаас эхлэн тоолоод k-р хулганыг идэж, цаашид (k+1)-р хулганаас эхлэн тоолж мөн k дахь хулганыг гэх мэтээр идсээр хамгийн сүүлд нэг хулганыг үлдээжээ. Хамгийн сүүлд үлдсэн азтай хулганы дугаарыг ол.
Эх өгүүлбэр

Бодолт:
Энгийн динамик програмчлалын арга ашиглая.
Хамгийн эхний хулганыг сонгочихлоо гэж бодъё. Өөрөөр хэлбэл K дахь хулгана түрүүлээд идэгдчихлээ гэсэн үг. Одоо тойрог дээр N-1 ширхэг хулгана үлдсэн ба K+1 дахь хулганаас эхлэн тоолох боловч энэ нь яг л N-1 ширхэг хулганы хувьд бодлого маань хэвээрээ тавигдана гэсэн үг. Тэгэхлээр N-1 ширхэг хулганы хувьд ямар нэг X дахь хулгана нь азтай хулгана болж таарна гэвэл тэр нь анхны N хулганы хувьд K+1 дахь хулганаас эхлэн тоолсон байх тул K+X дахь хулгана N хулганы хувьд азтай хулгана болж таарна. Мөн хулганууд тойргоор байрласан учир K+X тоо N-ээс хэтэрсэн тохиолдолд 1-ээс эхлэн тоологдох болно. Үүнийг харгалзан үзвэл дараах рэкуррэнт томьёо гарах ба үүгээр бодлогыг бодож бүрэн болно.

F(N) = (F(N-1) + K - 1) % N + 1