Ўзбекистон республикаси ахборот технологиялари ва коммуникацияларини ривожлантириш вазирлиги муҳаммад ал-хоразмий номидаги



Download 7,66 Mb.
Pdf ko'rish
bet189/267
Sana25.02.2022
Hajmi7,66 Mb.
#300373
1   ...   185   186   187   188   189   190   191   192   ...   267
Bog'liq
туплам 21(06.04)

 
Рекурсия.
 
Примитив рекурсив функциялар классик таърифини 
келтирамиз. 
1. Алфавит. 
а) предмет символлар 
𝒂, 𝒃, 𝒙, 𝒚, 𝒂
𝟏
, 𝒃
𝟏
, 𝒙
𝟏
, 𝒚
𝟏
;
б) функционал символлар 
+, −,∙
.
в) техник символлар 
(, ).
2. Термлар 
Предмет символлар; 
Агар 
𝒕
𝟏
, 𝒕
𝟐
, … , 𝒕
𝒑
термлар ва 
𝝋
функционал символ, у холда 
𝝋(𝒕
𝟏
, 𝒕
𝟐
, … , 𝒕
𝒑
)
– терм; 
Бошқа термлар йўқ. 
3. Аксиомалар: 
а1) 
𝑺(𝒙) = 𝒙 + 𝟏;
а2) 
𝑶(𝒙) = 𝟎; 
а3) 
𝑰 
𝒎
𝒏
(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
) = 𝒙
𝒎
.
4. Чиқариш қоидалари
в1) 
𝒇(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
) = 𝝋(𝒇
𝟏
(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
), … , 𝒇
𝒎
(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
));
в2) 
𝒇(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝟎) = 𝒈(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
), 
𝒇(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝒚 + 𝟏) = 𝒉(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝒚, 𝑭(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝒚)). 
Функциялар
𝑺, 𝑶, 𝑰 
𝒎
𝒏
содда функциялар дейилади. Чиқариш қоидаси 
в2 да 
𝒇
функция 
𝒈 
ва 
𝒉
функциялардан примитив рекурсия ёрдамида 
чиқарилади дейилади. Функция 
𝒇
чекли сондаги ўрнига қўйиш ва примитив 
рекурсия амаллари ёрдамида 
𝑺, 𝑶, 𝑰 
𝒎
𝒏
содда функциялардан келтириб 
чиқарилса примитив рекурсив дейилади.” 
Умумлашган рекурсия.Умумлашган рекурсив функцияларни кўрамиз 
Авваламбор терм тушунчасини кенгайтирамиз: 
Агар
 
𝒂, 𝒃
терм бўлса қуйидагилар хам терм 
𝒂 + 𝒃, 𝒂 − 𝒃, 𝒂 ∗ 𝒃, 𝒂/𝒃
 
Агар
 
𝒂, 𝒃
терм бўлса қуйидагилар мантиқий терм 
𝒂 < 𝒃, 𝒂 > 𝒃, 𝒂 ≥ 𝒂, 𝒂 ≤ 𝒃, 𝒂 ≡ 𝒃 
Агар
 
𝒂, 𝒃
мантиқий терм бўлса қуйидагилар мантиқий терм 
𝒂&𝒃, 𝒂 ∨ 𝒃, ~𝒂 
Бундан ташқари шартли терм киритилади 
Агар 
𝑹
мантиқий терм 
𝑓, 𝜑
–терм бўлса қуйидаги хам терм 
𝒊𝑓(𝑅(𝑥)) 𝑡ℎ𝑒𝑛 𝑓(𝑥) 𝑒𝑙𝑠𝑒 𝜑(𝑥); 
Шартли терм қуйидаги терм билан алмаштириш мумкин лекин унга 
эквивалент эмас:
𝑅(𝑥) ∗ 𝑓(𝑥) + (1 − 𝑅(𝑥) ∗ 𝜑(𝑥) 
Чунки шартли терм қуйидагича хисобланади: 
{
𝑓(𝑥) 𝑅(𝑥)
𝜑(𝑥) ~𝑅(𝑥)


400 
Бундан ташқари вергуль билан ажратилган қуйидаги кетма кетликдан 
фойдаланамиз: 
𝑎
1
= 𝑡
1
(𝑎
0
), … , 𝑎
𝑛
= 𝑡
𝑛
(𝑎
0
, … , 𝑎
𝑛−1
)
Бундай кетма кетликни ягона термга келтириш мумкин.
Умумлашган рекурсив қоидаси деб қуйидаги қоидага айтилади 
𝜑(𝑥) = 𝑖𝑓(𝑅(𝑥)) 𝑡ℎ𝑒𝑛 𝑓(𝑥) 𝑒𝑙𝑠𝑒 𝜑(𝑡(𝑥)); 
Ёки 
𝑓(𝑥) = 𝑖𝑓(𝑅(𝑥)) 𝑡ℎ𝑒𝑛 𝑓(𝑡(𝑥)) 𝑒𝑙𝑠𝑒 𝜑(𝑥); 
Бу қоидалар ёрдамида аниқланган функция умумлашган рекурсив 
функция дейилади. 
Дихотомия усули учун функция: 
𝑫𝒕(𝒂, 𝒃) = ( 
𝒄 = (𝒂 + 𝒃)/𝟐, 
𝑰𝒇(𝒂𝒃𝒔(𝒇( 𝒄)) < 𝒆𝒑𝒔) 𝒕𝒉𝒆𝒏 𝒄 𝒆𝒍𝒔𝒆
𝒊𝒇(𝒇(𝒂) ∗ 𝒇(𝒄) < 𝟎) 𝒕𝒉𝒆𝒏 𝑫𝒕(𝒂, 𝒄) 𝒆𝒍𝒔𝒆 𝑫𝒕(𝒄, 𝒂) 
); 
Ньютон усули учун функция:
𝑵𝒕(𝒙) = ( 
𝑰𝒇(𝒂𝒃𝒔(𝒇(𝒙)) < 𝒆𝒑𝒔) 𝒕𝒉𝒆𝒏 𝒙 𝒆𝒍𝒔𝒆
𝑵𝒕(𝒙 − 𝒇(𝒙)/𝒇’(𝒙) 
); 
Итерация усули учун функция: 
𝑰𝒕(𝒙) = ( 
𝒊𝒇(𝒂𝒃𝒔(𝒇(𝒙)) < 𝒆𝒑𝒔) 𝒕𝒉𝒆𝒏 𝒙 𝒆𝒍𝒔𝒆
𝑰𝒕(𝒇(𝒙)) 
); 
Метадастурлаш. Шаблонлар инстанционирлаш механизми компиляция 
жараёнида хисоблашни ташкил этишга имкон беради[2-5]. Бундай 
хисоблашлар шаблонли метадастурлаш деб аталади (iterator traits). Шаблонли 
метадастурлашдан фойдаланиб тузилган дастур шаблонли метадастур 
дейилади (template metaprogram).Шаблонли метадастур икки қисмдан иборат. 
Биринчи шаблонда умумий рекурсив қоида жорий этилади. Иккинчи шаблон 
— рекурсия тугатувчи специализация. Унда ўзгарувчи бошланғич қиймати 
берилади.
Қуйидаги дастурда компиляция жараёнида 3 сони берилган даражага 
кўтариш кўрсатилган. 
Мисол: 
Pow3< N> = 3 * Pow3;
//Рекурсия тугатиш
Pow3<0> = 1 ;
Цикл ёйиш учун метадастурлар.
 
Метадастурлаш кенг қўлланиладиган 
амалий масала сонли хисоблашда циклларни ёйиш масаласидир. 


401 
Векторларни 
скаляр 
кўпайтмасини 
хисоблаш 
масаласини 
кўрамиз.Скаляр кўпайтмани цикл оператори ёрдамида эмас қуйидаги сумма 
шаклида ҳисоблаш самарали: 

Download 7,66 Mb.

Do'stlaringiz bilan baham:
1   ...   185   186   187   188   189   190   191   192   ...   267




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish