A lineáris keresés

Ez a tétel nagyon hasonlít az eldöntés algoritmusára, de mégsem egyezik meg azzal. Talán szemléletes példa lehet a hétköznapi életből az a jól ismert probléma, amikor valaki nem találja a kulcscsomóját, pedig tudja, hogy a lakásban kell lennie valahol. Így azután módszeresen végigkutatja a lakást, szobáról-szobára járva, és csak akkor áll meg, ha valahol (még a lakásban) megtalálta (a megvan logikai változó értéke itt lesz igaz), azután pedig felírja magának egy noteszbe, hol találta meg, hiszen máskor is szüksége lehet rá.

Adott egy n elemű M sorozat és egy T tulajdonság. Keressük meg az első olyan elemét M-nek, amely rendelkezik a T tulajdonsággal, és adjuk meg, hogy hányadik!

A megvalósítás gondolatmenete:

Induljunk el a sorozat első elemétől, és vizsgáljuk meg az elemeket egyenként! Az eljárást addig kell folytatnunk, amíg

(a) nem találtunk adott tulajdonságú elemet, és

(b) még van további elem is.

A (b) feltétel egyszerűen ellenőrizhető, ha ugyanis az i-edik elemnél járunk, csupán annak kell teljesülnie, hogy i < n legyen.

Az (a) feltételt egy logikai változóval kezeljük. A van logikai változó értéke kezdetben legyen Hamis, ám ha találunk egy adott tulajdonságú elemet, állítsuk Igazra.

Az algoritmus mondatszerű leírással:

Eljárás lineáris_keresés:

i = 1

Ciklus amíg i < = n és M[ i ] nem T tulajdonságú

i = i + 1

Ciklus vége

van = (i < = n)

Ha van Akkor

Sorszam = i

Elágazás vége

Eljárás vége

Feladat:

Addig kérjünk be egy cm értéket, amíg az nem felel meg egy legalább 1000 cm3 térfogatú gömb sugarának! A bevitelt akkor is befejezzük, ha végjelet (nullát) ütnek. Végül írjuk ki a jó gömb térfogatát, vagy az „Egyik sem volt jó!” szöveget!

Program gomb:

megvan = False    'Hamisra állítjuk a logikai változó értékét

Ki: "Kérem a gömb sugarát:"

Be: sugar    'Beolvassuk a gömb sugarát

Ciklus amíg (Sugar <> 0) És Nem Megvan    'Feltétel - vizsgálat

terfogat = (4 * sugar * sugar * sugar * Pi)/3;

Megvan = (Terfogat > = 1000)    'Logikai vizsgálat

Ha Nem Megvan akkor    'Nem volt jó, így újra bekérjük a sugarat

Ki: "Kérem a gömb sugarát:"

Be: sugar

Elágazás vége

Ciklus vége

Ha Megvan akkor    'Kaptunk egy megfelelő adatot, kiírjuk a térfogatot

Ki: "Ez jó sugár, a térfogat:", terfogat

Egyébként

Ki: "Egyik adat sem felelt meg."    '0 – át ütöttek

Elágazás vége

Program vége.

Házi feladat:

Készítsünk programot, amely egy autóbusz-menetrend alapján megállapítja, van-e A városból B-be közvetlen járat, s ha van, akkor megad egy ilyet. (A menetrendben indulási és végállomások szerepelnek.)