Misol. 5 ta predmet bor. O’yinda kishi qatnashadi: boshlovchi va uning raqibi. Har bir o’yinchi navbat bilan bir, ikki yoki uchta predmetni oladi. Kim oxirgi predmetni olsa

Misol. 15 ta predmet bor. O’yinda 2 kishi qatnashadi: boshlovchi va uning raqibi. Har bir o’yinchi navbat bilan bir, ikki yoki uchta predmetni oladi. Kim oxirgi predmetni olsa, o’sha yutgan hisoblanadi. Boshlovchi yutish uchun o’yinda qanday strategiyani ishlatishi kerak?

• Misol. 15 ta predmet bor. O’yinda 2 kishi qatnashadi: boshlovchi va uning raqibi. Har bir o’yinchi navbat bilan bir, ikki yoki uchta predmetni oladi. Kim oxirgi predmetni olsa, o’sha yutgan hisoblanadi. Boshlovchi yutish uchun o’yinda qanday strategiyani ishlatishi kerak?

Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Shuni ham ta’kidlab o’tamizki, har qanday qismiy rekursiv funksiyaning qiymati mexanik xarakterga ega bo’lgan ma’lum bir protsedura yordamida hisoblanadi va bu protsedura bizning algoritm haqidagi intuitiv tasavvurimizga to’g’ri keladi.

• Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Shuni ham ta’kidlab o’tamizki, har qanday qismiy rekursiv funksiyaning qiymati mexanik xarakterga ega bo’lgan ma’lum bir protsedura yordamida hisoblanadi va bu protsedura bizning algoritm haqidagi intuitiv tasavvurimizga to’g’ri keladi.
• Ikkinchidan, hozirgacha qanday muayyan algoritmlar yaratilgan bo’lmasin, ular yordamida qiymatlari hisoblanuvchi sonli (arifmetik) funksiyalar albatta qismiy rekursiv funksiyalar bo’lib chiqdilar.
• Shuning uchun ham hozirgi paytda qismiy rekursiv funksiya tushunchasi algoritm tushunchasining ilmiy ekvivalenti sifatida qabul qilingan.

Buni birinchi bo’lib, yuqorida ta’kidlab o’tganimizdek, ilmiy tezis sifatida A.Chyorch va S.Klinilar o’rtaga tashladilar.

• Buni birinchi bo’lib, yuqorida ta’kidlab o’tganimizdek, ilmiy tezis sifatida A.Chyorch va S.Klinilar o’rtaga tashladilar.
• Xuddi shunday har qanday algoritmni mos Tyuring mashinasi yordamida realizatsiya qilish mumkin. Algoritmning ilmiy ekvivalenti qismiy rekursiv funksiya bo’lganligi uchun hamma qismiy rekursiv funksiyalar sinfi А bilan Tyuring mashinalari yordamida hisoblanuvchi funksiyalar (Tyuring bo’yicha hisoblanuvchi funksiyalar) sinfi В bilan bir xildir, ya’ni А=В.