Iosif masalasi Reja: Tarixi a o(n) yechim Ro‘yxat yordamida boshqa yondashuv Tarixi

Iosif masalasi

Reja:

• Tarixi
• A O(n) yechim
• Ro‘yxat yordamida boshqa yondashuv

Tarixi

Iosif Flaviy muammosi - bu Baxer de Meziriakning qiziqarli matematika (1612) bo'yicha dastlabki asarlaridan biriga kiritilgan muammo. Vazifa quyidagicha: 41 jangchi birinchi jangchidan boshlab aylanada turishadi, ular har uchdan birini o'ldiradilar. Savol shundaki, oxirgi omon qolish uchun siz qayerda turishingiz kerak. Umumiyroq formulada n ta jangchi qatnashadi, ular aylanada sanaladi va har m-ni o'ldiradi. Muammoning nomi yahudiylar urushi paytida Flaviy Iosif bilan sodir bo'lgan voqeadan olingan.

A O(n) yechim

Informatika va matematikada Jozef muammosi (yoki Jozefning o'rnini almashtirish) nazariy muammodir. Quyida vazifa bayonoti keltirilgan:

Aylanada qatl etilishini kutayotgan n kishi bor. Ortga hisoblash aylananing qaysidir nuqtasida boshlanadi va belgilangan yo‘nalishda aylana bo‘ylab davom etadi. Har bir qadamda ma'lum miqdordagi odamlar o'tkazib yuboriladi va keyingi odam qatl qilinadi. Tugatish aylana bo'ylab davom etadi (o'ldirilgan odamlar olib tashlangan sayin kichrayib boradi) faqat oxirgi erkinlik berilgan odam qolmaguncha. Odamlarning umumiy soni n va k soni berilgan bo'lib, bu aylanada k-1 kishi o'tkazib yuborilganligini va k-chi odam o'ldirilganligini ko'rsatadi. Vazifa - boshlang'ich doiradagi joyni tanlash, shunda siz oxirgi bo'lib qolasiz va shuning uchun omon qolasiz.

Misol uchun, agar n = 5 va k = 2 bo'lsa, u holda xavfsiz holat 3. Birinchidan, 2-pozitsiyadagi odam o'ldiriladi, keyin 4-pozitsiyadagi odam o'ldiriladi, keyin 1-pozitsiyadagi odam o'ldiriladi. Nihoyat, 5-pozitsiyadagi odam o'ldiriladi. Shunday qilib, 3-pozitsiyadagi odam omon qoladi.

Misol uchun, agar n = 5 va k = 2 bo'lsa, u holda xavfsiz holat 3. Birinchidan, 2-pozitsiyadagi odam o'ldiriladi, keyin 4-pozitsiyadagi odam o'ldiriladi, keyin 1-pozitsiyadagi odam o'ldiriladi. Nihoyat, 5-pozitsiyadagi odam o'ldiriladi. Shunday qilib, 3-pozitsiyadagi odam omon qoladi.

Ro‘yxat yordamida boshqa yondashuv:

Oddiy yondashuv - ro'yxat yaratish va unga 1 dan n gacha bo'lgan barcha qiymatlarni qo'shish. Argument sifatida roʻyxat, start (sanoq boshlanadigan joy) va k(oʻtkazib yuboriladigan odamlar soni) ni oladigan rekursiv funksiya yaratiladi. Agar ro'yxat o'lchami bitta bo'lsa, ya'ni faqat bitta odam qolsa, o'sha pozitsiya qaytariladi. Aks holda, boshlang'ich pozitsiyadan kishini soat yo'nalishi bo'yicha hisoblash boshlanadi va k-o'rindagi odam olib tashlanadi. Endi k-o'rindagi odam o'chiriladi va endi hisoblash shu pozitsiyadan boshlanadi. Bu jarayon faqat bir kishi qolguncha davom etadi.

Tushuntirish

Ro'yxatga 1 dan n gacha bo'lgan barcha qiymatlarni qo'shing. Biz start = 0 va k = 1 (0-indekslash) bilan rekursiv funktsiyani chaqiramiz.

Endi bizda 4 kishi bor, 1-indeksdan boshlab (shaxs raqami 3) va k. (2-indeks) pozitsiyasidagi odam o'ldiriladi.

Tushuntirish

Endi 1-indeksdagi element (2-raqamdagi odam) o'ldiriladi. Va u ro'yxatdan o'chirildi. Yangi hisoblash 1-indeksdan boshlanadi, 1-indeksdagi odam halok bo'ladi, shuning uchun endi 2-indeksdagi shaxs (3-shaxs) 1-indeksga keladi va hisoblash shu erdan boshlanadi.

Endi bizda 4 kishi bor, 1-indeksdan boshlab (shaxs raqami 3) va k. (2-indeks) pozitsiyasidagi odam o'ldiriladi.

Endi bizda 4 kishi bor, 1-indeksdan boshlab (shaxs raqami 3) va k. (2-indeks) pozitsiyasidagi odam o'ldiriladi.

Tushuntirish

0 indeksli odam o'ldirildi, endi bizda aylanada ikki kishi qoldi. Va 1-indeksga ega bo'lgan shaxs 0-indeksga o'tdi, ya'ni. shaxs raqami 3.

Yakuniy hisoblash amalga oshiriladi va 1-indeksdagi odam o'ldiriladi va qolgan yagona odam 3-pozitsiyada.

Foydalanilgan adabiyotlar

• М. А. Алексеев Задача Иосифа Флавия // Империя Математики. — 2001. — № 2. — С. 22—28
• www.hmong.press/wiki/Josephus_problem
• www.fayllar.org