Algoritmlash

TOKI musbat BAJAR TOKI juft BAJAR _TAM2 ga bo‘l

OM

_TAM1 ni ayir

OM

a) Bu algoritmga mos blok-sxemani chizing.

Ikkb) Ikkala algoritmni 13; 1024; i 1023 sonlari uchun qoMlang.

ala holda ham qadamlar sonin hisoblang.

d) Nima uchun bu algoritmlar cheksiz vaqt bajarilmaydi?

5.5- masala

Quyida ikkita algoritm keltirilgan. Birinchisi:

88

TOKI musbat BAJAR 1 ni ayir

TOKI juft BAJAR _TAM2 ga bo‘l

TAMOM ^OM

Ikkinchisi:

TOKI juft BAJAR 1 ni ayir

Bu algoritml TAMOM day kamchiligi bor?

arning qan

TOKI —BAJAR tuzilmasiga ba'zi sharhlar

2- sharh

0 ‘z oldimizga hunday maqsad qo ‘ymagan bo ‘Isak-da, faqat 1000 dan kichik sonlar uchun emas, balki barcha natural sonlar uchun qo ‘llash mumkin bo igan algoritm tuzdik. Algoritmning o ‘zi nechta qadam kerak bo ‘Isa, shuncha hajaradi.

Masalan, 1000000soni uchun Kamaytiruvchi 29 ta ko'rsatma bajaradi. Agarson kattaroq boisa, uning algoritmining bajaritishi ko'proq qadam talab qilishi mumkin. Bu tuzilmada biz endi TAKRORLANSIN - MARTA tuzilmasidagi kabi takrorlanishlar soni haqida o ‘ylashimiz shart emas. Endi takrorlanishlar uchun algoritmning o ''zijavob beradi!

3- sharh

TOKI — BAJAR tuzilmasining bajarilishi shart tekshirishdan boshlanadi. Birinchi savolga javob YOLG‘ONbo ‘Isa-chi? Bu holda algoritm bajarilishi darrov to ‘xtatiladi hamda BAJAR va TAMOM orasidagi ko ‘rsatmalar bir marta ham bajarilmaydi.

Masalan, 5.4-rasmdagi blok-sxemada boshlang‘ich quymat Oga teng bo ‘Isa, u holda musbat sharti YOLG‘ONho ‘ladi, shunga ko ‘ra algoritm bajarilishi to ‘xtatiladi.

4- sharh

Agar shartga javob doimo RO ST bo‘isa-yu, bir marta ham YOLG‘ON ho ‘Imasa-chi? U holda algoritm ishi hech qachon to ‘xtamaydi. U cheksiz uzoq vaqt davom etadi.

Masalan, quyidagi algoritmga.

89

TOKI juft BAJAR _TAM2 ga bo‘l

OM

boshlang ‘ich qiymat sifatida Osonini kiritamiz■ 0 —juft son, shuning uchun juftsharti ROST, Oni 2 ga bo ‘Isak, yana Osonini hosil qilamiz■ Ko ‘rsatmalaming bajarilishi yana boshidan boshlanadi va cheksiz marta davom etadi. Dasturchilar bunday holatni siklga tushib qoldi deyishadi (yoki ccheksiz siklga tushib qo/di»).

Albatta, siklga tushib qolishi yoqimli emas. Dasturchilar doimo bu holatga tushib qolmaslik choralarini ko ‘rishlari shart. Shunda ham bu holat yuz bergan bojsa, u holda klaviaturadan bir yoki bir nechta klavishalarjuftligiyordamida algoritm ishini to ‘xtatish mumkin.

5-sharh

_doi Tajribasiz dasturchilar, ichki ko ‘rsatmalami bajarayotgan kompyuter

_{o y‘} mo TOKI shartini nazarda tutib turadi va tekshirib boradi, deb

lashadi.

Lekin bunday emas, kompyuter shartni barcha ichki ko ‘rsatmalami bajarib bojgachgina tekshiradi. Buni quyidagi algoritm misolida ^{ko ‘rsatamiz:} TOKI juft BAJAR

2 ga bo‘l

_TAM2 ga bo‘l

OM

Bu algoritmni 24 soniga qo ‘Uashnijadval orqali ko ‘ramiz:

Ko‘rsatma Son ^{Shart Natija}

juft

²⁴ ROST

^{2 ga bo‘l} 12 ROST

^{2 ga bo‘1} 6 ROST

2 ga bo'l 3 YOLGON

^{2 ga bo'l} INKOR
Algoritmda INKOR vaziyatiyuzpga ke/ishi ikkinchi marta bo ‘lishdan avval biz ju ft shartini tekshirmayapmiz. Bu vaziyat blok-sxemada quyidagicha aks etadi:

90

5.5-rasm.

6-sharh

TAKRORLANSIN - MARTA takrnrlash ko ‘rsatmasini TOKI

— BAJAR takmrlash ko ‘rsatmasi bilan osongina almashtirish mumkin.

tax Keling, i 5.4-rasmdagi iblok-sxemadagi bqadamlar sonini

tepminiy h soblabt ko'ram z. Har gal r biz hi lok-sxema orqali

adan pastga o‘ ganimizda Kamayti uvc bitta yoki ikkita

ko'rsatmani bajaradi. Bir marta o‘tishda son, hech bo'lmaganda ikki marta kamayadi (ixtiyoriy yo‘lda son ikkiga bo'linadi). Shuning uchun, biz agar blok-sxema orqali, masalan, IQ marta o'tsak, Ijrochi 10 tadan 20 tagacha qadam o‘tadi, son esa hech bo‘lmaganda 210 = 1024 marta kichrayadi.

tek Biri million taxminan 230 ga teng- (220 dan kichikroq ham;

mishir b ko‘ring: 220 = 210-2in= 1024 1024 = ?). Demak, bizga

llionni 0 ga ayiantirish uchun kamida 20-1 = 20 va ko‘pi

bilan 20-2 = 40 qadam kerak bo‘ladi.

Bu baholash millionga yaqin har qanday son uchun o'rinli, aytaylik, 600000 dan 1000000 gacha sonlar uchun.

Nazorat savollari va topshiriqlar

1. Algoritmikada qandayshartlarbilan ish koYdadi?

2. Mantiqy amaliar haqida so ‘zlah hering.

3 Mantiqiy amatlar qanday ketma-ketlikda hajariladi?

4. Bimr mantiqiy amalni mstlik jadvali haqida so 'zlab bering.

5. Tarmoqlanish tuzilmasining qisqa kn ‘rinishi haqida so ‘zlab bering.

6. Tarmoqlanish tuzilmasining tn ‘liq kn ‘rinishi haqida so ‘zlab bering.

7. Tarmoqlanish tuzilmasi siklik tuzilmadan nimasi hitan farqtanadi?

8. Inson hayotidan tarmoqlanish tuzilmasiga misollar keltiring.

9. TOKI —BAJAR tuzilmasiga misollar keltiring.

91

Qo'shimcha masalalar

1- mantiqiy masala. EMAS(6>5) VA (7+7 = 15) YOKl (63-21 = 7) mantiqiy ifodaning qiymntini aniqlang.

2- mantiqiy masala. A = ROST, B = YOLG'ON, C = ROST bo'lsa, A VA EMAS B YOKI C mantiqiy ifodaning qiymatini aniqlang.

3- mantiqiy masala. EMAS(A VA B) « ((EMAS A) YOKI (EMAS B))

ayniyat o'rinli ekanligini rostlik jadvali yordamida isbotlang.

4- mantiqiy masala. EMAS(A YOKI B) = ((EMAS A) VA (EMAS B))

ayniyat o'rinli ekanligini rostlik jadvali yordamida isbotlang.

5- mantiqiy masala. Bir kishi aytdi: «Rost emaski men qoraman va to'g'riso'zman*. U kishi kim?

Mantiqiy masala-6. A kishi aytdi: «Hech bo'lmaganda birimiz qoramiz», B kishi aytdi: «Hech bo'lmaganda birimiz yolg'onchimiz*. Ular kimlar?

B-l. Baqa (I; 2; I; 2) n ta bargli nilufarning a tartib raqamli bargidan barcha pashshalarni yeb a+ I tartib raqamli baigiga kelitirish algoritmini tuzing.

B-2. Baqa (I; 2; 1; 2) n ta bargli nilufarning I tartib raqamli bargidan barcha pashshalarni, yeb b lartib raqamli bargiga kelitirish algoritmini tuzing.

B-3. Baqa (1; 2; 1; 2) n ta bargli nilufaming a tartib raqamli baigidan barcha pashshalarni yeb, a dan o'ngdagi b tartib raqamli bargiga kelitirish algoritmini tuzing.