7-лаборатория иши. Қисм сатрларни қидириш

7-лаборатория иши. Қисм сатрларни қидириш.

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

Лаборатория ишини бажариш учун зарур жиҳозлар. 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;

}

Лаборатория ишини бажариш тартиби. Лаборатория ишини бажаришда қуйидаги тартибга амал қилинг:

1. 
   Гуруҳ журналидаги номерга кўра ўз вариантингизни аниқланг
   
2. 
   Масалани ечиш учун алгоритм ва дастур қуринг.
   
3. 
   Кичик ҳажмдаги маълумотлар учун дастурнинг тўғри ишлаётганлигига ишонч ҳосил қилинг.
   
4. 
   Бажарилган ишлар хақида ҳисобот тайёрланг
   

Лаборатория топшириқлари вариантлари

№	Топшириқ матни
1	N(N>0) butun soni va S satr berilgan. N uzunlikka teng bo`lgan S satr quyidagi ko`rinishda aniqlanadi: agar S satr uzunligi N dan katta bo`lsa, uning bosh qismidan ortiqcha belgilar olib tashlanadi, agar S satr uzunligi N dan kichik bo`lsa, uning bosh qismiga nuqtalar qo`shilsin.
2	Butun musbat N1, N2 sonlar va S1, S2 satrlar berilgan. Bu satrlardan foydalanib yangi S satr hosil qilinsin: S satrning dastlabki N1 ta belgisi S1 satrning bosh qismidan, oxirgi N2 ta belgisi S2 satrning oxiridan iborat bo`lsin.
3	C belgi va S, S0 satrlar berilgan. S satrda uchragan har bir C belgining oldiga S0 satr joylashtirilsin.
4	C belgi va S, S0 satrlar berilgan. S satrda uchragan har bir C belgidan keyinga S0 satr joylashtirilsin.
5	S va S0 satrlar berilgan. Agar S0 satr S satrda mavjud bo`lsa true aks holda false qiymat chiqarilsin.
6	S va S0 satrlar berilgan. S satrda S0 satrning necha marta uchrashi aniqlansin.
7	S va S0 satrlar berilgan. S satrdan S0 satr bilan ustma-ust tushuvchi 1-qism satr o`chirilsin. Agar S satrda S0 satr topilmasa S satr o`zgarishsiz chop etilsin.
8	S va S0 satrlar berilgan. S satrdan S0 satr bilan ustma-ust tushuvchi oxirgi qism satr o`chirilsin. Agar S satrda S0 satr topilmasa S satr o`zgarishsiz chop etilsin.
9	S va S0 satrlar berilgan. S satrdan S0 satr bilan ustma-ust tushuvchi barcha qism satrlar o`chirilsin. Agar S satrda S0 satr topilmasa S satr o`zgarishsiz chop etilsin.
10	S, S1 va S2 satrlar berilgan. S satrdagi 1-uchragan S1 qism satr S2 qism satr bilan almashtirilsin.
11	S, S1 va S2 satrlar berilgan. S satrdagi oxirgi uchragan S1 qism satr S2 qism satr bilan almashtirilsin.
12	Hech bo`lmaganda 1 ta bo`sh joyga ega satr berilgan. Berilgan satrdagi 1- va 2- bo`sh joylar orasida joylashgan qism satr chiqarilsin. Agar satrda 1 ta bo`sh joy topilsa, bo`sh satr chop etilsin.
13	Hech bo`lmaganda 1 ta bo`sh joyga ega satr berilgan. Berilgan satrdagi 1- va oxirgi bo`sh joylar orasida joylashgan qism satr chiqarilsin. Agar satrda 1 ta bo`sh joy topilsa, bo`sh satr chop etilsin.
14	Bo`sh joylar bilan ajratilgan o`zbekcha so`zlaridan tuzilgan satr berilgan. Satrdagi so`zlar soni topilsin.
15	Bosh harflar bilan terilgan va bo`sh joylar(1 yoki bir nechta) bilan ajratilgan o`zbekcha so`zlardan iborat satr berilgan. 1- va oxirgi harflari bir xil bo`lgan so`zlar soni topilsin.
16	Bosh harflar bilan terilgan va bo`sh joylar(1 yoki bir nechta) bilan ajratilgan o`zbekcha so`zlardan iborat satr berilgan. Hech bo`lmaganda bitta “A” harfi bor bo`lgan so`zlar soni ekranga chiqarilsin.
17	Bosh harflar bilan terilgan va bo`sh joylar(1 yoki bir nechta) bilan ajratilgan o`zbekcha so`zlardan iborat satr berilgan. 3 ta harfi “A” bo`lgan so`zlar soni ekranga chiqarilsin.
18	Bo`sh joylar bilan ajratilgan o`zbekcha so`zlaridan tuzilgan satr berilgan. Satrdagi eng qisqa so`zning uzunligi topilsin.
19	Bo`sh joylar bilan ajratilgan o`zbekcha so`zlaridan tuzilgan satr berilgan. Satrdagi eng uzun so`zning uzunligi topilsin.
20	Bo`sh joylar bilan ajratilgan o`zbekcha so`zlaridan tuzilgan satr berilgan. Satr oxiri nuqta bilan tugallanmagan. “.” bilan ajratilgan so`zlar ekranga chiqarilsin.