Іздеу алгоритмдерінің типтері және бейнеленуі. Мысал келтіріңіз
Алгоритмдердің құрылымдары
Кез келген алгоритмді (программаны) блоктардың өзара байланысуына қарай төмендегідей үш түрлі басқару құрылымын пайдалану арқылы жазып шығуға болатындығы дәлелденген:
• сызықтық құрылым немесе әрекеттер тізбегі (бірінен кейін бірі орындалып тізбектеле орналасқан бірнеше операторлардан тұрады);
• тармақты құрылым немесе шартты тексеру (шартқа байланысты екі оператордың бірінің орындалуы);
• қайталау немесе циклдік құрылым (операторлар бөлігінің бірнеше рет қайталана орындалуы).
Осындай негізгі (канондық) құрылымдардан тұратын алгоритмді регулярлық алгоритм (программа) деп атайды, олардың бір ғана кіру нүктесі мен бір ғана шығу нүктесі болады. Осы үшеуі құрылымдық программалаудың негізгі конструкциялары, яғни құраушылары болып саналады. Төменде алгоритмдердің бірыңғай құрылымдарының схемалық бейнеленуі көрсетілген
Іздеу алгоритмдерінің типтері және бейнеленуі. Мысал келтіріңіз.
Іздеу деп берілген жиында берілетін эталон шаблонның қасиеттеріне ие объектіні табуды атайды. Көп жағдайда жиын массив түрінде анықталады.
Сызықтық іздеу – қажетті элементті массив элементтерін қарапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура.
Кедергімен сызықтық іздеу – бұл ізделінді элемент массивтің шекаралық a[n+1] элементі болып қосымша енгізіліп, және іздеу үрдісінде a[i]=x болатындай i табылатын іздеу. Ал егер a[i]=x тек қана i=n+1 болса, онда массивте ізделінді элемент жоқ. Көп жағдайда іздеу реттелген массивте жүргізілген тиімді. Бұл жағдайларда тиімді әдістердің бірі – қақ бөлу бойынша іздеу. Қақ бөліп іздеу әдісінде ізделінді эталонды салыстыру массивтің ортасында орналасқан элементпен жүргізіледі, салыстыру нәтижесіне байланысты (артық немесе кем) ары қарай іздеу массивтің не сол жақ жартысында, не оң жақ жартысында жүргізіледі.
Іздеу есептерінде берілген шартқа сәйкес келетін элементті іздеп табу керек. Ол үшін жиым элементтерін біртіндеп тізбектей қарастырып отырып шартты тексеріп шығу керек. Осылай ету барысында циклден шығудың екі жолы бар:
· Керекті элемент табылғаннан кейін;
· Жиым элементтері тегіс қаралып шықты, керекті элемент табылмады.
1-есеп. Берілген к санына тең жиымның алғашқы элементін табу.
Int k;
Printf(“\nK=”);
Scanf(“%i“,&k);
Int ok=0; //элемент табылғаны/табылмағаны белгісі
Int I, nom;
For(i=0;i<n;i++)
If(a[i]==k) {ok=1;nom=i;break;}
If(ok==1) printf(“\nnom=”, nom);
Else printf(“\nk-ға тең элемент жоқ!”);