Kompyuter ilmlari va dasturlashtirish

Mavzu: Algoritmlar kutubxonasi. Qidirish algoritmlari. Olimpiada masalalari va undagi algoritmlar tahlili
Odatda yangi boshlanuvchilar massiv elementlarini saralash, izlash yoki hisoblash kabi nisbatan sodda vazifalarni bajarish uchun odatiy ko’chadan yozishda ko’p vaqt sarflaydi. Ushbu ilmoqlar qanchalik osonlikcha xatoga yo’l qo’ishi mumkinligi nuqtai nazardan ham muammoli bo’lib qolishi mumkin. Bu ilmoqlarni tushinish qiyin bo’lib qolish mumkin.
Dasturlashda qidirish, hisoblash va saralash juda keng tarqalgan operatsiyalar bo'lgani uchun, C ++ standart kutubxonasi allaqachon bir nechta satr kodlarida ushbu vazifalarni bajaradigan katta funktsiyalar to'plamini o'z ichiga oladi. Bunga qo'shimcha ravishda, ushbu xususiyatlar allaqachon sinovdan o'tgan, samarali va har xil turdagi idishlarni qo'llab-quvvatlaydi. Va bu xususiyatlarning ba'zilari parallellashtirishni ham qo'llab-quvvatlaydi - uni tezroq bajarish uchun bir xil vazifa uchun bir nechta protsessor iplarini ajratish qobiliyati.
Algoritm kutubxonasi tomonidan taqdim etilgan funktsiyalar odatda uchta toifaga kiradi:
Tekshiruvchilar - konteynerdagi ma'lumotlarni (o'zgarishsiz) ko'rish uchun foydalaniladi (masalan, qidiruv operatsiyasi yoki hisoblash jarayoni).
Mutatorlar - konteynerdagi ma'lumotlarni o'zgartirish uchun ishlatiladi (masalan, elementlarni saralash yoki qayta tartiblash).
Fasilitatorlar - ma'lumotlar elementlari qiymatlari (masalan, qiymatlarni ko'paytiradigan ob'ektlar yoki elementlar juftligini qaysi tartibda saralash kerakligini aniqlaydigan ob'ektlar) asosida natija yaratish uchun foydalaniladi.
Ushbu algoritmlar algoritmlar kutubxonasida joylashgan (algoritm sarlavhali fayl). Ushbu qo'llanmada biz ba'zi keng tarqalgan algoritmlarni ko'rib chiqamiz.
Izoh: Ushbu algoritmlarning barchasi takrorlanuvchilardan foydalanadi.
Std :: find () algoritmi va qiymat bo'yicha elementni topish
Std :: find () funktsiyasi konteynerni berilgan qiymatning birinchi marta paydo bo'lishini qidiradi. Std :: find () argument sifatida 3 parametrni oladi:
ketma-ketlikdagi boshlang'ich element uchun iterator;
ketma-ketlikdagi so'nggi element uchun iterator;
qidirish uchun qiymat.
Natijada, iterator kerakli elementga (agar topilgan bo'lsa) yoki konteynerning oxiriga (agar bunday element c bo'lmasa) ishora qilgan holda qaytariladi, Izoh: Ushbu darsdagi barcha misollarning to'g'ri ishlashi uchun kompilyatoringiz sizning IDE-ning C ++ 17 funksiyalaridan foydalanish bo'yicha tafsilotlar, bu erda o'qing.
Element topilgan misol:
Qidirish va almashtirish uchun qiymatni kiriting:5 234
13 90 99 234 40 80

Element topilmaydigan misol:
Qidirish va almashtirish uchun qiymatni kiriting: 0 234
0 topilmadi
13 90 99 5 40 80
Std :: find_if () algoritmi va shartli elementlarni qidirish
Ba'zan biz konteynerda ba'zi bir shartlarga mos keladigan qiymatga ega ekanligini ko'rishni xohlaymiz (masalan, berilgan pastki qatorni o'z ichiga olgan qator).
Bunday holatlarda std :: find_if () funktsiyasi mukammal yordamchi bo'ladi. Bu std :: find () funktsiyasiga o'xshash ishlaydi, lekin qidirish uchun qiymatni berish o'rniga biz qo'ng'iroq qilinadigan ob'ektga o'tamiz, masalan funktsiya ko'rsatgichi (yoki lambda - bu haqda keyinroq), agar u tekshirilsa gugurt topildi. Std :: find_if () funktsiyasi har bir element uchun ushbu ob'ektni qidiradigan elementni topguncha chaqiradi (yoki idishda tekshirish uchun element qolmagan).
Ro‘yxatdan zarur axborotni qidirish - nazariy dasturlashning fundamental masalalaridan biri hisoblanadi. Qidiruv algoritmini tahlil qilishda, qidirilayotgan axborot kompyuterda ma‘lumotlar massivi ko‘rinishida joylashgan deb faraz qilamiz. Yozuvlar yoki ro‘yxat elementlari massivda ketma-ket joylashadi va ular o‘rtasida bo‘shliq yo‘q. Ro‘yxatdagi yozuvlar 1 dan N gacha tartiblangan bo‘ladi. Aslida yozuvlar maydonlardan tashkil topgan bo‘ladi, bizni kalit deb ataluvchi maydonlardan bittasining qiymati qiziqtiradi. Ro‘yxatlar kalit maydonlari qiymati bo‘yicha tartiblangan yoki tartiblanmagan bo‘lishi mumkin. Aniq qiymatni qidirish masalasi biror elementni tanlash masalasi bilan bog‘liq. Aytaylik, bizga kattaligi bo‘yicha beshinchi element, oxiridan yettinchi yoki o‘rta qiymatli element kerak.
Qidiruv - bu kompyuter xotirasida ma‘lumotlarni qayta ishlash jarayonida qo‘llaniladigan asosiy amallardan biri hisoblanadi. Bu amalning mazmuni shundan iboratki, berilgan argument bo‘yicha massiv elementlari orasidan shu argumentga mos ma‘lumotni (elementni) aniqlashdan iborat.
Ixtiyoriy ma‘lumot (yoki tuzilma) elementi qandaydir belgisi bilan boshqasidan farq qiladi. Ushbu belgi kalit deyiladi. Kalit takrorlanmas bo‘lishi mumkin, ya‘ni tuzimadagi mavjud bitta element uchun aynan shu kalit qo‘llaniladi. Bunday kalit birlamchi deb ataladi. Elementlarning ma‘lum guruhi uchun takrorlanishi mumkin bo‘lgan kalit ikkilamchi kalit deyiladi, ushbu kalit bo‘yicha ham qidiruv tashkil qilish mumkin. Ma‘lumot elementlarining kalitlari alohida joyda to‘plangan (boshqa jadvalda) bo‘lishi yoki o‘zi alohida yozuvdagi biror bir maydonda saqlanishi mumkin. Bunday ajratib olingan yoki alohida faylda saqlanadigan tashqi kalit deyiladi. Agar kalit yozuvda joylashgan bo‘lsa, u holda ichki kalit deyiladi.
Berilgan argument bo‘yicha qidiruv berilgan argument kaliti bilan aniqlangan algoritm deyiladi. Qidiruv algoritmi ishlashi natijasi ushbu ma‘lumotda joylashishi mumkin yoki u jadvalda mavjud bo‘lmasligi mumkin. Ma‘lumotning mavjud bo‘lmaslik holati ikkita amalda yuz berishi mumkin:
berilgan qiymatning yo‘qligini aniqlashda;
berilgan qiymatni jadvalga qo‘yishda.
Masalan, bizga ro‘yxat elementi kaliti sifatida k berilgan bo‘lsin. Har bir k(i) kalitda r(i)-ma‘lumot mavjud. Qidiruv argumenti - Key. Unga yozuv ma‘lumoti rec mos keladi. Jadvalda ma‘lumotlar tuzilmasiga bog‘liq holda qidiruvning bir nechta shakllari farqlanadi.
Bu masalani yechish uchun ikki xil yondoshuv mavjud: ketma-ket qidiruv va
indeksli ketma-ket qidiruv. Ushbu qidiruv algoritmlarini o‘rganib chiqamiz.
Ketma-ket qidiruv algoritmi
Qidiruv algoritmlarida biror aniq elementni mavjud ro‘yxat elementlarini birma-bir qarab chiqish orqali qidirib topish masalasi hal qilinadi. Ketma-ket qidiruv algoritmida ro‘yxatning saralanganligi ahamiyatga ega bo‘lmasa-da, lekin saralangan ro‘yxatda eng yaxshi natijaga erishiladi. Odatda qidiruv kerakli elementning ro‘yxatda bor yoki yo‘qligini shunchaki tekshirish uchun emas, balki shu kalit-qiymatga ega bo‘lgan ma‘lumotni ajratib olish uchun ham qo‘llaniladi.
Masalan, kalit-qiymat qidirilayotgan elementning tartib raqami yoki boshqa unikal (yagona) identifikator bo‘lishi mumkin. Kerakli kalit topilgandan so‘ng dastur shu kalitga mos ma‘lumotlarni o‘zgartirishi yoki shunchaki barcha yozuvlarni ajratib chiqarishi mumkin. Har qanday holatda ham qidiruv algoritmi kalitning joylashgan o‘rnini aniqlash masalasini yechish uchun qo‘llaniladi.
SHuning uchun ham qidiruv algoritmlari kerakli kalitdan tarkib topgan yozuv indeksini natija sifatida ajratib beradi. Agar kalit-qiymat topilmasa, u holda qidiruv algoritmi massivning yuqori chegarasidan katta bo‘lgan indeks qiymatini qaytaradi. Maqsadga erishish uchun ro‘yxat elementlari 1 dan N gacha bo‘lgan sonlar yordamida raqamlangan bo‘lsin deb faraz qilamiz. Bu holatda qidirilayotgan kalit ro‘yxatda mavjud bo‘lmasa, algoritm 0 qiymatni beradi. Soddalik uchun ajratib olinadigan kalit-qiymatlar ro‘yxatda takrorlanmaydi deb qabul qilinadi.
Ketma-ket qidiruv algoritmi ro‘yxatning birinchi elementidan boshlab oxirgi elementgacha qidirilayotgan elementni topilmaguncha qarab chiqiladi. Bundan kelib chiqadiki, kalit qiymati ro‘yxatda qancha uzoqda turgan bo‘lsa, qidiruv shuncha uzoq davom etadi (vaqtga nisbatan). Bu holatni ketma-ket qidiruv algoritmi tahlilida e‘tiborga olish zarur bo‘ladi.
Masala. Berilgan sonlar orasidan haqiqiy son bor yoki yo’qlini aniqlaydigan dastur tuzilsin.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp8

{
class Program
{
static void Main(string[] args)
{
{
int k = 0, b;
string s;
s = Console.ReadLine();
for (var i = 0; i < s.Length; i++)
{
b = (int)s[i];
if (b == 46 || b == 44)
{
b = (int)s[i - 1]; if (b <= 57 && b >= 48)
{
b = (int)s[i + 1]; if (b <= 57 && b >= 48)
{
Console.WriteLine("haqiqiy son bor");
k++;
break;
}
}
}
}
if (k == 0)
Console.WriteLine("haqiqiy son yoq!");
Console.ReadKey();
}
}
}
}