Издөө жана иреттөө: сиздин биринчи алгоритмдериңиз
Компьютерди нерселерди табууга жана иретке келтирүүгө үйрөтүңүз
- элементтерди бирден текшерип, сызыктуу издөө жүргүзө аласыз,
- иреттелген массивди экиге бөлүп, экилик издөө жүргүзө аласыз,
- массивди көбүк иреттөө жана тандап иреттөө менен иреттей аласыз,
- кээ бир кадамдар башкаларынан эмне үчүн бир топ тезирээк экенин түшүндүрө аласыз.
1. Алгоритм деген эмне?
Алгоритм — бул ар дайым аягына чыгып, жооп бере турган так, кадам-кадам көрсөтмөлөрдүн жыйындысы. Тамак-аштын рецепти — алгоритм. Бут кийимдин боосун байлоо кадамдары да — алгоритм. Программалоодо биз алгоритмдерди C++ коду менен жазабыз, ошондо компьютер аларды аткара алат.
Компьютердин эң көп жасаган эки иши — бул издөө (көптүн ичинен бир элементти табуу) жана иреттөө (элементтерди тартип менен коюу, мисалы кичинесинен чоңуна). Китепкананы элестетиңиз: сиз китепти тез табасыз, анткени китептер текчелерде мурунтан эле иреттелген. Издөө менен иреттөө дайыма чогуу иштешет.
for жана while циклдерин колдонуп иштейт. Жаңы эч нерсе жок — сизге тааныш циклдерди акылдуу жайгаштыруу гана.2. Сызыктуу издөө: бирден текшеребиз
Сызыктуу издөө — бир нерсени табуунун эң жөнөкөй жолу. Сиз биринчи элементтен баштап, бирден алдыга жылып, каалаганыңызды тапканга чейин же аягына жетким чейин барасыз. Бул сиз топтун ичинен досуңузду ар бир жүздү карап издегениңиздей эле.
Төмөнкү функция табылган элементтин индексин кайтарат, же маани массивде жок болсо -1 кайтарат. Биз -1 колдонобуз, анткени массивде терс позиция болбойт, ошондуктан бул «табылган жок» деген коопсуз белги.
#include <iostream>
using namespace std;
// target индексин кайтарат, массивде жок болсо -1 кайтарат.
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // табылды - токтоп, кайда экенин билдир
}
}
return -1; // бүт массивди айланып чыктык, бул жерде жок
}
int main() {
int nums[5] = {4, 8, 15, 16, 23};
cout << linearSearch(nums, 5, 15) << endl; // 2
cout << linearSearch(nums, 5, 99) << endl; // -1
return 0;
}Күтүлгөн натыйжа:
2
-1Сызыктуу издөө ар дайым иштейт, атүгүл иретсиз, иреттелбеген массивде да. Анын кемчилиги — ылдамдык: эгер маани акыркы болсо (же жок болсо), ар бир элементти текшерүү керек.