|
Primitiv rekursiya operatori
|
| bet | 5/6 | | Sana | 14.05.2024 | | Hajmi | 36,86 Kb. | | #230945 |
Bog'liq eRGASHEV SHOXPrimitiv rekursiya operatori
summa(x,y)=R⟨f,g⟩(x,y) , Qayerda f(x)=x
g(x,y,z)=N(z) R⟨f,g⟩(x,y)={f(x)g(x,y−1,R⟨f,g⟩(x,y−1))y=0y>0
={xN(R⟨f,g⟩(x,y−1))y=0y>0 ={xN(sum(x,y−1))y=0y>0
Oddiyroq shaklga aylantirilishi mumkin. yig'indisi(x,0)=x summa(x,y)=N(sum(x,y−1))
Ko'paytirish mahsulot(x,0)=Z(x)
mahsulot(x,y)=sum(x,mahsulot(x,y−1))
Ayirishlar
Agar x⩽y, keyin sub(x,y)=0 , aks holda sub(x,y)=x−y .
Avval bitta sub1(x)=x−1 ayirishni ko‘rib chiqamiz sub1(0)=Z(0) sub1(x+1)=x
Endi sub(x, y) ni ko'rib chiqing sub(x,0)=x
sub(x,y)=sub1(sub(x,y−1))Taqqoslash operatsiyalari ekv(x,y)=1 agar x=y , aks holda eq(x,y)=0 le(x,y)=1 agar x⩽y , aks holda lq(x,y)=0 pastki(x,y)=1 agar xEndi barcha boshqa funktsiyalar le(x,y)=eq0(sub(x,y))
eq(x,y)=mul(le(x,y),le(y,x))
pastki(x,y)=mul(le(x,y),le(N(x),y))
Shartli operator
agar(0,x,y)=y
agar(c,x,y)=x
Bo'lim bo'lish(x,y)=⌊xy⌋
, agar y>0 bo'lsa . Agar y=0 bo'lsa
, u holda funktsiyaning qiymati bizni qiziqtirmaydi va biz uni xohlagan tarzda belgilashimiz mumkin.
Avval biz divmax (x, y) ni aniqlaymiz.
— funksiya x dan kichik yoki teng maksimal songa teng , bu y ga to'liq bo'linadi .
divmax(0,y)=Z(y) divmax(x,y)=if(eq(sub(N(x−1),divmax(x−1,y)),y), N(x−1),divmax(x−1,y)) Endi bo'linmaning o'zi
bo'lish(0,y)=Z(y) bo'lish(x,y)=h(x,y,bo'lish(x,y))
, bu h(x,y,z)=sum(z,eq(N(x),divmax(N(x),y)))
Bo'limning qolgan qismi quyidagicha ifodalanadi:
mod(x,y)=sub(x,mul(y,bo'lish(x,y))))
Ruxsat etilgan uzunlikdagi ro'yxatlar bilan ishlash
Yuqorida tavsiflangan arifmetik amallardan foydalanib, siz sonning tubligi va n ni qidirish testini ifodalashingiz mumkin.
- tub son. Natural sonlar roʻyxatini koʻrib chiqing [x1,…,xn]
, keyin siz uni px1+11⋅px2+12⋅…⋅pxn+1n raqami bilan moslashingiz mumkin.
, qaerda pi
- men
- bu tub son. Ko'rinishdan ko'rinib turibdiki, ro'yxat yaratish, i
- bu element va qolgan amallar oddiy arifmetik amallar, shuning uchun primitiv rekursivdir. Shunday qilib, biz ibtidoiy rekursiv funktsiyaning argumentlari va natijasi natural sonlar ro'yxati bo'lishi mumkin deb taxmin qilamiz.
|
| |
