Современные информационные технологии/2. Вычислительная техника и программирование

Балгабаева Р.Н., Мурадилова Г.С., Отарова А.С.

Кокшетауский государственный университет им.Ш.Уалиханова, Казахстан

БЕЙСТАНДАРТТЫ ӨҢДЕУ АЛГОРИТМДЕРІНДЕ БҮТІН ҰЗЫН САНДАРДЫ САЛЫСТЫРУ

Программалау тілдерінде мәліметтердің базалық сандық типтері мәндерінің диапазондары әдетте шектеулі, және көптеген есептерді шығару барысында олардың жетіспеушілігі байқалады. Есептеулердің дәлдігін көтеру, диапазонды үлкейту немесе кейбір сипаттаманы жақсарту үшін, программаларды өңдеушілер - сандарды сақтауға арналған және олармен арифметикалық амалдар орындайтын ішкі программалары үшін мәліметтер типтерін өздері құрастырады.

Үлкен көлемді теріс емес бүтін сандардың дәл мәндерін өңдеуге мүмкіншілік беретін кейбір алгоритмдерді қарастырайық. Белгілердің саны шығарылатын есептен, программаның жұмыс істеу уақыты мен жады шектеулерінен тәуелді. Бұл, мысалы, жүз немесе мың және одан да көп ондық белгілер болуы мүмкін. Осындай сандарды өңдеу нақты есептің қойылуынан да тәуелді. Бір есептерде сандарға тек аддитивті арифметикалық амалдарды, ал басқа есептерде тек мультипликативті амалдарды және т.с.с. қолдану қажет болады.

Көпразрядты сандармен жұмыс істеу үшін көбінесе 0-ден 99-ға дейін (100 негізіндегі цифрлар) санды ұсынатын byte типті немесе word типті (10000 негізіндегі цифрлар) элементтер массивін қолданған дұрыс. Byte-та бір ондық цифрды сақтаумен салыстырғанда, енгізу-шығаруды қиындатпай-ақ жадыны екі еседей жуықтап үнемдеуге болады. Сонымен бірге, 10000-дық жүйедегі санда ондық санға қарағанда цифрлар төрт есе аз болғандықтан, кейбір арифметикалық амалдар үдетіледі.

Массивпен жұмыс істегенде оның элементтерінің санын анықтау керек. Көбінесе ұзын бүтінді массивпен емес, екі өрісі бар жазу арқылы ұсыну ыңғайлы: бүтін санды айнымалы – массивтің нақты орын алған элементтердің саны және массив.

Таңбасыз ұзын бүтін сандарды ұсыну үшін келесі құрылымды пайдаланайық:

const n = 1000; const m = 100; const m1=1;

type t1 = 0..n; t2 = 0..m-1;

…

…

type BzLong = record

us: t1;

mas: array [1..n] of t2;

end;

Нақты орын алатын цифрлар санын жазудың жеке өрісі ретінде бермей-ақ, сол массивтің нөлінші элементінде орналастыруға болады (Turbo Pascal тіліндегі string типіндегі жол ұзындығы сияқты). Бірақта бұл онша жақсы шешім емес, себебі бір массивте түрлі текті шамалар араласып кетеді. Осыған орай, бірнеше өрісті жазулар бір текті шамалардың типтерін (сонымен бірге диапозонды), басқа шамаларға тиіспей, оңай алмастыруға мүмкіншілік береді.

BzLong типінде ұсынылған ұзын сандарды салыстырайық. Ішкі программаға екі ұзын сан беріледі (оларды l1 және l2 деп белгілеп алайық). Нәтиже ретінде теріс санды (< белгісі), оң санды (> белгісі) немесе нольді (= белгісі) келесі жағдайларға сәйкес қайтарамыз: бірінші аргумент екінші аргументтен кем, артық немесе тең. Бұндай шешім қарапайым "иә/жоқ" жауабына қарағанда, ақпаратты артығырақ қайтарады. Егер кейбір алгоритмде әрбір үш ll<l2, l1=l2, l1>l2 жағдайға сәйкес өз амалдарын орындау қажет болса, онда салыстыру көмекші программасын бір рет шақырып және нәтижесін осы үш жағдайды ажырататын бүтін айнымалыда сақтау жеткілікті.

Сонымен, егер l1.us<>l2.us болса онда цифрлары көп сан артық болады. Егер екі санның да цифрлар саны тең болса, онда цифрлар мәндерін үлкен индекстерден бастап салыстырамыз, осы үрдіс мына екі жағдайдың біреуі орындалғанға дейін жалғасады- цифрлар әртүрлі [цифры үлкен сан артық] немесе цифрлар тізбегі аяқталды [сандар тең].

Бүтін ұзын сандарды салыстыру программаның фрагменті төмендегі листингте ұсынылады:

function fun(const l1,l2:Bzlong): integer;

var i:t2;

begin

if l1.us>l2.us then

begin

fun:=m1; writeln('>') end

else if l1.us < l2.us then

begin fun:=-m1 ; writeln('<');end

else begin

i:=l1.us;

while (i>=1) and (l1.mas[i]=l2.mas[i]) do

dec(i);

if i=0 then

begin fun:=0;writeln('=') ;end

else fun:=integer(l1.mas[i])-integer(l2.mas[i]) ;

end;

end;

Литература:

1. Иванова Г.С. Технология программирования: Учебное пособие. М.: МГТУ им. Н.Э.Баумана, 2002.

2. Павловская Т.А. С/С++. Программирование на языке высокого уровня: Учебное пособие. СПб.: Питер, 2002.

3. Кнут Д. Искусство программирования для ЭВМ.Т.З: Сортировка и поиск. М.: Мир, 1978.