Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Бодлого №16275
$1,2,\dots,n$ тоонуудыг цагийн зүүний дагуу тойрог дээр байрлуулжээ. 1-ээс эхлэн цагийн зүүний дагуу тоолон явж 2 дахь цэг бүрийг дарж ганц цэг үлдтэл нь дарав. Үлдэх ганц цэгийн дугаар $J(n)$-ын рекурент харьцааг бич.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар:
Бодолт: $J(n-1)$-г мэдэж байг.
Одоо $J(n)=?$. 2-г дарсны дараа $n-1$ цэг үлдэнэ. 3-аас эхлэн
тэднийг шинээр $1,2,\dots,n-1$ гэж дугаарлая. Эдний хувьд шинэ
$J(n-1)$ дугаартай цэг үлдэнэ, түүний хуучин (анхны) дугаар нь
$J(n-1)+2$ байх тул $J(n)=J(n-1)+2$. Гэтэл $1\le J(n)\le n$ байх
ёстой ба 2 дахь тойролтыг хийхэд "1" цэг нь $n+1$ дэх цэг болж
байгаа тул $J(n)=J(n-1)+2(\bmod n)$ болно.
Ийм төрлийн бодлогыг Иосифын бодлого гэдэг.
Ийм төрлийн бодлогыг Иосифын бодлого гэдэг.