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

5-лаборатория иши.

Қисм сатрларни қидириш.

Мақсад: Талабаларда ассивларни қайта ишлашга мўлжалланган алгоритмларни корректлиги кўрсатиш кўникмасини ҳосил қилиш.

Лаборатория ишини бажариш учун зарур жиҳозлар. 2- лаборатория иши давомида ишлаб чиқилган дастур матни, лаборатория ишини бажариш бўйича (ушбу) услубий кўрсатма

Зарур назарий маълумотлар.

Ушбу лаборатория иши оддий итератив алгоритмларнинг корректлигини цикл инвариантдан фойдаланиш орқали асослашга бағишланган. Инвариант сифатида биз циклнинг биринчи итерациясидан олдин ва хар бир итерациясидан сўнг ўринли бўлган (рост қиймат қабул қиладиган) мантиқий ифодани тушунамиз. Инвариантнинг бажарилиши бизга циклнинг тўғри бажарилишини исботлаш имконини беради. Инвариант қуйидаги хусусиятларга эга:

Инициализация. Инвариант цикл бошланишидан (биринчи итерация бажарилишидан олдин) ўринли

Сақланиш. Агар инвариант циклнинг навбатдаги итерациясидан олдин ўринли бўлса, итерация тугаганидан сўнг ҳам ўринли бўлади.

Якунлаш. Цикл якунланганда инвариант циклнинг тўғри ишлаганлигини кўрсатади ва бу ҳол, хусусан тартиблаш алгоритмлари учун, бутун алгоритмнинг тўғри ишлаши исботлайди.

Лаборатория топшириқлари ва
иш давомида ишлаб чиқиладиган дастурнинг тўлиқ намунаси.

Лаборатория топшириғи. 1- лаборатория иши давомида ўзингиз ишлаб чиққан дастур алгоритмининг корректлиги кўрсатинг.

Лаборатория ишини бажариш намунаси. 1-лаборатория ишида ишлаб чиқилган дастур матни қайта келтирамиз (қулайлик унинг баъзи сатрларини номерлаган ҳолда) ва корректлиги исботлаймиз. Келтирилган дастур учун инвариантни қуйидагича ифодалаш мумкин:

Инвариaнт: i ўзгарувчининг қиймати кетма-кетликнинг кўриб чиқилган қисмидаги номусбат ҳадларнинг сонидан биттага ортиқ.

Инициализация: while цикли (4 сатр) бажарилишидан олдин инвариант бажарилади, i нинг қиймати 1 га тенг, кетма-кетликнинг ҳали бирорта элементи кўриб чиқилгани йўқ ва демак номусбат ҳадлар сони ҳам 0 га тенг.

Сақланиш: Биз i ўзгарувчининг қиймати k бўлганда ( да) цикл танаси бажарилиши олдидан инвариант ўринли бўлса, унинг кейинги қийматида ҳам инвариант ўринли бўлишини исботлашимиз керак. Ўзгарувчиларнинг итерация бошланишидан олдинги қийматларини билан, итерациядан кейинги қийматини билан белгилайлик. У ҳолда , эса , эса чи итерация давомида Х ўзгарувчи киришдан қабул қилган қийматни англатади.



Фараз қилайлик, i ўзгарувчининг қиймати бўлганда инвариант бажарилсин, яъни кетма-кетликнинг номусбат элементлари сони га тенг бўлсин. Циклнинг даги итерациясининг бажарилиши цикл сарлавҳасидаги шартнинг ростлигини англатади: ва , яъни аввалги итерацияда киритилган X нинг номусбат (Биринчи итерация олдидан бу шартнинг бажарилишини қийматлаш орқали таъминлаймиз, 1-сатрга қаранг). Цикл танаси бажарилганда биринчидан i нинг қиймати биттага ортади (7-сатр), яъни . Шу билан бирга олдинги итерацияда қабул қилинган номусбат хисобига кўриб чиқиладиган қисм узунлиги ҳам, ундаги номусбат ҳадлар ҳам биттага ортади, яъни кетма-кетликнинг номусбат ҳадлари сони та бўлади. Шундай қилиб, янги итерация бошланишидан олдин i ўзгарувчининг қиймати , яъни номусбат ҳадлар сони дан биттага ортиқ.

Якунлаш: Цикл оператори ўз ишини шарт бузилганда якунлайди, яъни ёки. яъни шартлардан бирортаси ўринли бўлганда.

Лаботория топшириғи шарти. S satr va C belgi berilgan. S satrdagi har bir uchragan C belgi ikkilantirilsin.

жуда содда бўлгани учун, унинг C++ даги дастури матнини келтирамиз:

#include

int main(int argc, char **argv)

{

static char s[64],s1[64],*ss[64],c;

static short int k,i,j;

ifstream f1("string28.in");

ofstream f2("string28.out");

f1.getline(s,sizeof(s));

*ss=s;

k=strlen(*ss);

f1>>c;

j=0;

for (i=0;i{

if (s[i]==c) {s1[j]=s[i];j++;};

s1[j]=s[i];j++;

}

for (i=0;i

f2<

f1.close();

f2.close();

return 0;

}