O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi buxoro davlat universiteti qo’lyozma huquqida udk

2.6 Ro’yxatning uzunligini hisoblash

Prolog tilida ro’yxatning uzunligi quyidagicha hisoblanadi:

Ro’yxat tipi C tilidagi massiv tipi singari uning elemet tipidan keyin “*” simvolini qoyish orqali ko’rsatiladi. Har xil tipdagi (univetsal) elementlarga ega bo’lgan ro’xatning tipi Element* orqali ko’rsatiladi. Masalan, ro’yxat uzunligini hisoblovchi predicat quyidagicha e’lon qilinadi:

 len:(real*, integer) procedure(i,o).

Predikat “len” deb ataladi, 2 ta parametrga ega, 1- parametr – haqiqiy sonlar ro’yxati, 2- parametr esa butun son. 1- parametr beriladi, 2- parametr esa hisoblanadi. Bu predikat orqali ro’yxatning uzunligi quyidagicha hisoblanadi:

len([],0) :- !.

    len([X|Xs], 1+Len) :- len(Xs, Len).

Bu hisob rekursiv amalga oshiriladi. Berilgan ro’yxat [X|Xs] shabloni asosida qaraladi. Ya’ni uning bosh elementi (1-)elementi) X o’zgaruvchiga va dumi (1- elementsiz ro’yxat) Xs o’zgaruvchiga beriladi. Bu ro’yxatning uzunligi 1+Len ifoda shaklida axtariladi. Bu Xorn gapining ma’nosi quyidagicha: “[X|Xs]shabloni asosida berilgan ro’yxatning uzunligi 1+Len ga teng agar Xs ro’yxatning uzunligi Len ga teng bo’lsa”. Len o’zgaruvchining qiymati - Xs ro’yxatining uzunligini hisoblash uchun yana shu gapdan foydalaniladi, faqat endi dum [X|Xs]shabloni asosida qaralib uning uzunligi 1+Len ifodasi sifatida axtariladi. Shunday qilib ro’yxat uzunligini hisoblash shu ro’yxatdan 1- element olib tashlangan ro’yxat uzunligiga 1 ni qo’shish orqali hisoblanadi. Hisoblash rekursiv davom etib oxiri bosh ro’yxatgacha boradi. Bosh ro’yxatning uzunligini hisoblash uchun esa len([],0) :- !. gapdan foydalaniladi. Bu ro’yxatning uzunligi ga 0 tengligini gap tasdiqlaydi. Bi qiymat oldingi gapdagi Len o’zgaruvchisi o’niga qo’lib 1+Len hisoblanadi, uning qiymati esa undan oldingi gapdagi ifodaga qo’yiladi va h.k.

Ushbu gap len(List, Len) ko’rinishida chaqiriladi, Masalan len([32.4, 2.5, 12.12, 5.0, 24.12], Len). Natija sifatida Len = 5 olinadi. Ushbu natijani olish uchun hisob ro’yxat ustidan 2 marta o’tadi, 1- marta uni qisqartirib va 1+Len ifodani qurib chiqadi, 2- marta esa olingan natijani ifodadagi Len o’zgaruvchining o’rniga qo’yib va 1+Len ifodani hisoblab chiqadi. Bunday hisob-rekursiv hisob deb ataladi. Bunday hisoblash o’rniga iteratsion hisoblash ham mumkin.Predikatni quyidagicha e’lon qilamiz:

len:(real*,integer,integer) procedure(i,i,o).

 Xorn gaplarini esa quyidagicha quramiz:

len([], A, A) :- !.

len([X|Xs], A, T) :- len(Xs, 1+A, T).

Ikkinchi gapning ma’nosi quyidagicha: “Berilgan ro’yxat [X|Xs]shabloni asosida qaraladi va berilgan A o’zgaruvchining qiymatiga T qiymat mos qo’yiladi, agar berilgan ro’yxat dumi- Xs, berilgan A o’zgaruvchi qiymatiga 1 qo’shilganiga T qiymat mos qo’yilsa”. Ushbu gap len(List, 0, Len) ko’rinishida chaqiriladi, Masalan len([32.4, 2.5, 12.12, 5.0, 24.12], 0, Len). Natija sifatida Len = 5 olinadi. Ushbu natijani olish uchun hisob ro’yxat ustidan faqat 1 marta o’tadi, 1- marta uni qisqartirib, va har bir qisqartirganda berilgan A qiymat ustiga 1 qo’shilib borad. Ro’yxat bo’shaganda A, o’zgaruvchi kerakli qiymatni olgan bo’ladi.