Schéma výpočtu. Lineárne algoritmy - schéma, štruktúra a výpočet. Dva z troch sa prepínajú

2.1 Vývoj algoritmu.

Algoritmus- toto

a. opis postupnosti činností na vyriešenie problému alebo dosiahnutie cieľa;

b. pravidlá pre vykonávanie základných operácií spracovania údajov;

c. popis výpočtov matematickými vzorcami.

Pred začatím vývoja algoritmu je potrebné jasne pochopiť úlohu: čo je potrebné získať ako výsledok, aké počiatočné údaje sú potrebné a aké sú dostupné, aké sú obmedzenia pre tieto údaje. Ďalej si musíte zapísať, aké kroky je potrebné vykonať, aby ste získali požadovaný výsledok z počiatočných údajov.

V praxi sú najbežnejšie tieto formy reprezentácie algoritmov:

Verbálne (nahrávky v prirodzenom jazyku);

Grafika (obrázky z grafických symbolov);

Pseudokódy (poloformalizované popisy algoritmov v konvenčnom algoritmickom jazyku, vrátane prvkov programovacieho jazyka a fráz v prirodzenom jazyku, všeobecne akceptovaná matematická notácia atď.);

Program (texty v programovacích jazykoch).

Verbálny spôsob zápisu algoritmov je popisom po sebe nasledujúcich fáz spracovania údajov. Algoritmus je uvedený v ľubovoľnej prezentácii v prirodzenom jazyku.

Príklad. Napíšte algoritmus na nájdenie najväčšieho spoločného deliteľa (GCD) dvoch prirodzených čísel.

Algoritmus môže byť nasledovný:

1. nastaviť dve čísla;

2. ak sú čísla rovnaké, vezmite ktorékoľvek z nich ako odpoveď a zastavte sa, inak pokračujte v algoritme;

3. určiť najväčšie z čísel;

4. nahraďte väčšie z čísel rozdielom medzi väčším a menším z čísel;

5. zopakujte algoritmus z kroku 2.

Opísaný algoritmus je použiteľný pre akékoľvek prirodzené čísla a mal by viesť k riešeniu problému. Presvedčte sa sami pomocou tohto algoritmu na určenie najväčšieho spoločného deliteľa 125 a 75.

Verbálna metóda nie je široko používaná z nasledujúcich dôvodov:

Takéto opisy nie sú striktne formalizovateľné;

Trpieť výrečnosťou záznamov;

Umožňujú nejednoznačný výklad jednotlivých predpisov.

Grafický spôsob prezentácie algoritmov je kompaktnejší a vizuálnejší ako verbálny spôsob.

V grafickom znázornení je algoritmus znázornený ako postupnosť vzájomne prepojených funkčných blokov, z ktorých každý zodpovedá vykonaniu jednej alebo viacerých akcií.

Takéto grafické znázornenie sa nazýva vývojový diagram alebo vývojový diagram.

Pseudokód je systém notácie a pravidiel navrhnutý na jednotné zapisovanie algoritmov.

Zaberá medzipolohu medzi prirodzenými a formálnymi jazykmi.

Na jednej strane má blízko k bežnému prirodzenému jazyku, takže algoritmy sa v ňom dajú písať a čítať ako obyčajný text. Na druhej strane sa v pseudokóde používajú niektoré formálne konštrukcie a matematická symbolika, čím sa zápis algoritmu približuje všeobecne akceptovanému matematickému zápisu.

Pseudokód neprijíma prísne syntaktické pravidlá pre písanie príkazov, ktoré sú vlastné formálnym jazykom, čo uľahčuje písanie algoritmu v štádiu návrhu a umožňuje použiť širšiu množinu príkazov určených pre abstraktného vykonávateľa. V pseudokóde však zvyčajne existujú určité konštrukcie vlastné formálnym jazykom, ktoré uľahčujú prechod od písania v pseudokóde k písaniu algoritmu vo formálnom jazyku. Najmä v pseudokóde, rovnako ako vo formálnych jazykoch, existujú pomocné slová, ktorých význam je určený raz a navždy. Neexistuje žiadna jednotná alebo formálna definícia pseudokódu, takže sú možné rôzne pseudokódy, ktoré sa líšia množinou servisných slov a základných (základných) štruktúr.

2.2 Bloková schéma.

Blokový diagram je grafické znázornenie algoritmu, v ktorom je znázornený ako postupnosť vzájomne prepojených funkčných blokov, z ktorých každý zodpovedá vykonaniu jednej alebo viacerých akcií.

V blokovom diagrame každý typ akcie (zadávanie počiatočných údajov, výpočet hodnôt výrazu, kontrola podmienok, riadenie opakovania akcií, dokončovanie spracovania atď.) zodpovedá geometrickému útvaru reprezentovanému ako symbol bloku. Symboly blokov sú spojené prechodovými čiarami, ktoré určujú poradie vykonávania akcií.

Tu sú najčastejšie používané symboly.

Názov symbolu	Príklad označenia a plnenia	Vysvetlenie
Proces		Výpočtová akcia alebo postupnosť akcií
Riešenie		Kontrola podmienok
Modifikácia		Začiatok cyklu
vopred definovaný proces		Výpočty podľa podprogramu, štandardného podprogramu
Vstup výstup		I/O všeobecne
štart stop		Začiatok, koniec algoritmu, vstup a výstup do podprogramu
dokument		Výsledky tlače

Blok „proces“ sa používa na označenie akcie alebo postupnosti akcií, ktoré menia hodnotu, formu prezentácie alebo umiestnenie údajov. Na zlepšenie viditeľnosti diagramu je možné spojiť niekoľko samostatných blokov spracovania do jedného bloku. Prezentácia jednotlivých operácií je celkom voľná.

Blok "rozhodnutie" sa používa na označenie riadiacich prechodov podľa podmienky. Každý blok „rozhodnutia“ musí špecifikovať otázku, podmienku alebo porovnanie, ktoré definuje.

Blok "modifikácie" sa používa na organizáciu cyklických štruktúr. (Slovo modifikácia znamená modifikáciu, premenu). Vo vnútri bloku je zapísaný parameter cyklu, pre ktorý je uvedená jeho počiatočná hodnota, okrajová podmienka a krok pre zmenu hodnoty parametra pre každé opakovanie.

Blok "preddefinovaný proces" sa používa na označenie volaní pomocných algoritmov, ktoré existujú autonómne vo forme nejakých nezávislých modulov, a volaní podprogramov knižnice.

Príklad. Zostavte blokovú schému algoritmu na určenie výšok ha, hb, hc trojuholníka so stranami a, b, c, ak

kde p = (a + b + c) / 2.
Riešenie. Zavádzame notáciu potom h a = t/a, h b = t/b, h c = t/c. Vývojový diagram musí obsahovať začiatok, vstup a, b, c, výpočet p, t, h a, h b, h c , vypíšte výsledky a zastavte.

2.3 Štruktúry algoritmov.

Algoritmy môžu byť reprezentované ako nejaké štruktúry pozostávajúce zo samostatných základných (t. j. hlavných) prvkov. Prirodzene, s týmto prístupom k algoritmom by štúdium základných princípov ich návrhu malo začať štúdiom týchto základných prvkov.

Logická štruktúra každého algoritmu môže byť reprezentovaná kombináciou troch základných štruktúr: nasledovať, vetviť, cyklus.

Charakteristickým znakom základných štruktúr je, že majú jeden vstup a jeden výstup.

1. Nasleduje základná štruktúra. Tvorí ho postupnosť akcií, ktoré nasledujú po sebe:

2. Základná štruktúra vetvenia. Poskytuje v závislosti od výsledku kontroly stavu (áno alebo nie) výber jedného z alternatívnych spôsobov algoritmu. Každá cesta vedie k spoločnému východu, takže algoritmus bude pokračovať bez ohľadu na zvolenú cestu.

Štruktúra vetvenia existuje v štyroch hlavných variantoch:

Ak-tak-inak;

Výber je iný.

1) ak-potom ak podmienka, potom akcia skončí ak 2) if-then-else if podmienka then action 1 else action 2 end if 3) voľba voľby za podmienky 1: akcia 1 za podmienky 2: akcia 2. . . . . . . . . . . . pod podmienkou N: akcie N koniec voľby 4) voľba-inak voľba za podmienky 1: akcia 1 za podmienky 2: akcia 2. . . . . . . . . . . . pod podmienkou N: akcie N inak akcie N+1 koniec voľby

Príklad. Zostavte blokovú schému algoritmu výpočtu funkcie

Základná štruktúra cyklu. Poskytuje opakované vykonávanie určitého súboru akcií, ktoré sa nazývajú telo slučky.

Štruktúra cyklu existuje v troch hlavných variantoch:

Typ slučky pre.

Dáva pokyn na vykonanie tela slučky pre všetky hodnoty nejakej premennej (parametra slučky) v zadanom rozsahu.

Typ slučky do.

Inštrukcie na vykonanie tela cyklu, kým nie je splnená podmienka zapísaná za slovom while.

Typ slučky robiť, kým.

Inštrukcie na vykonanie tela cyklu, kým nie je splnená podmienka zapísaná za slovom while. Podmienka sa skontroluje po vykonaní tela slučky.

Všimnite si, že slučky for a while sa tiež nazývajú slučky pred testovaním stavu a slučky do-while sa tiež nazývajú slučky po vykonaní testu. Inými slovami, telá cyklov for a while sa nemusia vykonať ani raz, ak podmienka na ukončenie cyklu spočiatku nie je pravdivá. Telo cyklu do-while sa vykoná aspoň raz, aj keď podmienka konca cyklu nie je na začiatku pravdivá.

Slučka pre i od i1 do i2 krok i3 telo slučky (postupnosť akcií) koniec slučky slučka, kým sa telo slučky podmienky (postupnosť akcií) skončí loop robte telo cyklu (postupnosť akcií), kým podmienkou nie je koniec cyklu

s danou presnosťou (pre daný znamienkovo ​​striedavý výkonový rad sa požadovaná presnosť dosiahne, keď sa ďalší člen v absolútnej hodnote zmenší).

Počítanie súm je typická cyklická úloha. Charakteristickým znakom nášho konkrétneho problému je, že počet termínov (a následne počet opakovaní tela cyklu) nie je vopred známy. Vykonávanie slučky preto musí skončiť, keď sa dosiahne požadovaná presnosť.

Pri zostavovaní algoritmu treba brať do úvahy, že sa striedajú znamienka pojmov a zvyšuje sa stupeň čísla x v čitateloch pojmov.

Vyriešte tento problém priamo výpočtom čiastkového súčtu v každom i-tom kroku

S:=S+(-1)**(i-1)*x**i/i,

dostaneme veľmi neefektívny algoritmus, ktorý vyžaduje veľké množstvo operácií. Oveľa lepšie je usporiadať výpočty nasledovne: ak označíme čitateľa ľubovoľného členu písmenom p, nasledujúci člen bude mať čitateľ rovný -p * x (znamienko mínus zaisťuje striedanie znamienok členov ), a samotný pojem m

sa bude rovnať p/i, kde i je číslo termínu.

Algoritmus, ktorý zahŕňa iteračný cyklus, sa nazýva iteračný algoritmus. Iteračné algoritmy sa používajú pri implementácii iteračných numerických metód. V iteračných algoritmoch je potrebné zabezpečiť povinné splnenie podmienky pre výstup zo slučky (konvergencia iteračného procesu). V opačnom prípade sa algoritmus zacyklí, t.j. hlavná vlastnosť algoritmu - účinnosť - nebude splnená.

vnorené slučky.

Existujú prípady, keď je potrebné zopakovať určitú postupnosť príkazov vo vnútri tela slučky, t.j. zorganizovať vnútornú slučku. Táto štruktúra sa nazýva slučka v rámci slučky alebo vnorené slučky. Hĺbka vnorenia cyklov (teda počet vnorených cyklov) môže byť rôzna.

Pri použití takejto štruktúry je pre úsporu strojového času potrebné presunúť z vnútornej slučky do vonkajšej všetky príkazy, ktoré nezávisia od parametra vnútornej slučky.

Príklad vnorené slučky pre. Vypočítajte súčet prvkov danej matice A(5,3).

Príklad zatiaľ vnorené slučky. Vypočítajte súčin tých prvkov danej matice A(10,10), ktoré sa nachádzajú na priesečníku párnych riadkov a párnych stĺpcov.

Pri implementácii algoritmov spracovania analógových signálov je často potrebné vypočítať matematické funkcie. Najbežnejšie funkcie sú logaritmické a exponenciálne funkcie. Tieto funkcie sa používajú v schémach na znižovanie a zvyšovanie dynamického rozsahu prenášaného alebo zaznamenávaného signálu (komandovanie). Ďalšou bežnou aplikáciou schém exponenciálnych a logaritmických matematických výpočtov je výpočet súčinu a delenia vstupných signálov.

Na výpočet nelineárnej funkcie sa často používa operačný zosilňovač pokrytý negatívnou spätnou väzbou. Ako príklad je na obrázku 1 znázornený diagram logaritmického zosilňovača.

Obrázok 1. Schéma logaritmického zosilňovača

V tomto obvode je v obvode negatívnej spätnej väzby zahrnutý nelineárny prvok (polovodičová dióda), ktorý má exponenciálnu závislosť prúdu od použitého napätia. V dôsledku spätnej väzby sa závislosť výstupného napätia na vstupe stáva logaritmickou. Zisk tejto logaritmickej schémy je určený R1. Typicky sa logaritmická schéma vypočítava pre jednotkový zisk.

Ak je v tomto obvode použitá dióda s kvadratickou charakteristikou prúdového napätia, potom vypočíta druhú odmocninu vstupného signálu. Je vhodné ho použiť v obvodoch na určenie amplitúdy signálu pri kvadratúrnom spracovaní signálu.

(1),

Podobným spôsobom sa vypočíta funkcia, inverzná k logaritmickej - exponent. Iba v tomto prípade nie je nelineárny prvok pripojený k obvodu spätnej väzby, ale k vstupu zosilňovača. Obrázok 2 znázorňuje schému výpočtu exponentu na operačnom zosilňovači.

Obrázok 2. Schéma výpočtu exponentu

Ak je v tomto obvode použitá dióda s kvadratickou charakteristikou prúd-napätie, potom obvod vypočíta druhú mocninu vstupného napätia a môže byť použitý ako obvod na určenie výkonu vstupného signálu.

Pomocou týchto schém na výpočet matematických funkcií môžete vypočítať súčin dvoch analógových signálov. V tomto prípade sa používa dobre známa vlastnosť logaritmov na nahradenie súčinu premenných súčtom logaritmov týchto premenných. Pre inverznú transformáciu sa používa funkcia výpočtu exponentov. V tomto prípade na základni logaritmu vôbec nezáleží.

(2),

Multiplikačný obvod, ktorý implementuje vzorec (1) na operačných zosilňovačoch, je znázornený na obrázku 3.

Obrázok 3. Obvod multiplikátora operačného zosilňovača

Napriek jednoduchosti implementácie sa takáto schéma používa pomerne zriedkavo, pretože. násobenie je možné len pre kladné vstupné hodnoty. Preto sa zvyčajne používajú multiplikačné schémy postavené na základni.

Na výpočet funkcií nie je vždy možné vybrať nelineárny prvok s danou charakteristikou prúdového napätia. V tomto prípade môžete použiť po častiach lineárnu aproximáciu funkcie. Na operačnom zosilňovači je ľahké implementovať akýkoľvek zisk jednoduchou zmenou hodnoty odporu v obvode spätnej väzby, čím sa nastaví strmosť funkcie. Prepínanie odporov pri zmene vstupného napätia je najjednoduchšie vykonať na diódových spínačoch, ktoré sú napájané nami nastaveným blokovacím napätím. Podobná schéma je znázornená na obrázku 4.

Obrázok 4. Obvod funkčného zosilňovača

Na výpočet zložitejších funkcií sa často používajú multiplikátory založené na tranzistoroch. V najjednoduchšom prípade je možné skombinovať vstupy X a Y, aby sa získal obvod na výpočet štvorca zo vstupného signálu ( Y=X 2).

Môžu byť použité ako elektronické regulátory napätia. Privedením konštantného napätia na jeden zo vstupov je možné nastaviť úroveň striedavého napätia dodávaného na výstup na výstupe.

Literatúra:

Spolu s článkom „Schémy na výpočet matematických funkcií“ čítajú:

Všeobecné pokyny
Pre syntézu obvodov v odd. 5.1 popisuje nasledujúce kroky:
1. Popis funkcie požadovaného obvodu.
2. Priradenie vstupných a výstupných premenných a priradenie hodnôt 0 a 1.
3. Zostavenie pravdivostnej tabuľky.
4. Stanovenie potrebných logických operácií.
5. Zjednodušenie av prípade potreby transformácia schémy.
Ak je známa pravdivostná tabuľka, potom je teraz vhodné začať 4. etapu s kompiláciou normálneho tvaru OR. Pomocou Carnotovho diagramu sa to maximálne zjednoduší. Na konci kroku 4 sa získa zjednodušená logická funkcia, podľa ktorej možno zostaviť logický digitálny obvod.
Krok 5 kontroluje, či je možné a racionálne ďalšie zjednodušenie funkcie nájdenej pomocou logickej algebry. Ak áno, malo by sa vykonať zjednodušenie.
Teraz musíme zistiť, aké logické prvky sú k dispozícii. Logická funkcia musí byť konvertovaná tak, aby obsahovala iba existujúce logické prvky. Potom môžete zostaviť schému.

Digitálny obvod zapnutia/vypnutia z viacerých miest

Pomocou logických prvkov je potrebné z niekoľkých miest syntetizovať obvod, ktorý funguje ako obvod zapnutia a vypnutia. Stav výstupu by sa mal zmeniť iba vtedy, ak sa zmení stav jedného zo vstupov. Ak oba vstupy zmenia svoj stav, potom by sa výstupný stav nemal zmeniť. Obvod musí byť postavený na prvkoch OR-NOT.
Požadovaný obvod má dva vstupy a jeden výstup. Vstupné premenné sa nazývajú A a B. Výstupná premenná je označená Z (obrázok 5.47).
Pravdivostná tabuľka obvodu s dvomi vstupnými premennými má 4 možnosti (obr. 5.48). Počiatočný stav Z pre prvú možnosť je možné nastaviť ľubovoľným spôsobom. Zvolené Z = 0.
Pri prechode z možnosti 1 na možnosť 2 mení premenná A svoj stav. Premenná B nemení stav. Ak zmení stav len jeden zo vstupov, potom podľa zadanej úlohy musí výstup Z zmeniť svoj stav. Z sa musí rovnať 1.
Pri prechode z možnosti 2 na možnosť 3 menia premenné A a B svoj stav. Z by sa nemalo meniť. Pri prechode z možnosti 3 na možnosť 4 mení premenná A svoj stav z 0 na 1. B zostáva rovná 1. Z teda musí zmeniť stav z 1 na 0. Pravdivostná tabuľka je hotová. Mohlo by to vyzerať inak, keby sme v možnosti 1 zvolili Z = 1.
Pre pravdivostnú tabuľku (obr. 5.48) je potrebné napísať normálny tvar OR. Vyzerá takto:
Z = (AaB)w(AaB).
Ak do Carnotovho diagramu vnesieme normálnu formu OR, potom je jasné, že ďalšie zjednodušovanie je nemožné (obr. 5.49).
Pretože obvod musí byť postavený na prvkoch OR-HE, je potrebné transformovať rovnice:
Z = (AaB)w(AaB)-,
Z = (AaB)v(AaB),
Z = AaBaAaB.

Ryža. 5,50 Digitálny obvod

Obvod zostrojený podľa transformovanej rovnice je znázornený na obr. 5,50.

Dva z troch sa prepínajú

Vysoko rizikové systémy, ako napríklad jadrová elektráreň, musia byť v prípade havárie okamžite odstavené. Vypnutie prebieha automaticky pomocou digitálneho obvodu. V núdzových senzoroch zodpovedných za vypnutie sa môžu vyskytnúť falošné poplachy. Preto sú na každom kritickom mieste umiestnené tri rovnaké havarijné snímače (obr. 5.51).
Vypnutie by malo nastať len vtedy, keď boli spustené aspoň dva z troch alarmových senzorov. Tento prístup predchádza zbytočným odstávkam systému, ktoré prinášajú finančné straty. Po spustení majú núdzové snímače stav 1. K vypnutiu systému by malo dôjsť, ak je na výstupe okruhu aktívny stav 1.
Vyžaduje sa teda obvod, ktorého výstup je v stave 1, keď sú aspoň 2 z 3 vstupov v stave 1. Takýto obvod sa nazýva spínač dvoch z troch.
Vstupné premenné sú pomenované A, B a C. Výstupná premenná je Z. Zostavme pravdivostnú tabuľku podľa slovného popisu princípu obvodu. Vždy, keď sa dve vstupné premenné rovnajú 1, Z = 1. Ak sú všetky tri vstupné premenné rovné 1, musí sa Z rovnať aj 1. Takáto pravdivostná tabuľka je znázornená na obr. 5.52.
Ďalej, podľa zostavenej pravdivostnej tabuľky sa normálny tvar OR píše:

Ryža. 5.51.

Z = (A a B a C) v (A a B a C) v a5aC|v(^aSaC).

Normálny tvar OR je zjednodušený pomocou Carnotovho diagramu (obr. 5.53). Môžu byť vytvorené tri dvojité skupiny. Zjednodušená rovnica je:
Z = (AaB)w(BaC)w(AaC).
Podľa tejto rovnice môžete zostaviť obvod (obr. 5.54).
Často sú po ruke iba prvky OR-HE. Aby sme zostavili obvod iba na prvkoch OR-HE, transformujeme rovnicu: na °-
Z = (AaB)v(BaC)v(AaC);
======= CO.
Z \u003d (Al B) v (B aC) v ​​(A lC);
—=====—= Obr. 5.55. Spínací obvod "dva
Z = AlVlVlSlAlS. z troch“ o prvkoch SH1I-NOT.
Príslušný obvod je znázornený na obr. 5.55.

Schéma kontroly parity

Na detekciu chýb v kódoch (pozri časti 8.7 a 8.8), ako aj na monitorovanie a monitorovanie problémov je často potrebný obvod, v ktorom je výstup 1, keď párny počet vstupov má stav 1.
Takáto schéma sa nazýva schéma kontroly parity.
Je potrebné syntetizovať obvod so štyrmi vstupmi. Vstupné premenné sú A, B, C a D. Výstupná premenná je Y.
Najprv musíte vytvoriť pravdivostnú tabuľku. Y bude vždy 1, ak 0, 2 alebo 4 vstupné premenné sú 1 (obrázok 5.56).
Z pravdivostnej tabuľky sa získa normálny tvar OR:
Y \u003d (A l B lC l D)\/ ^A l B lC l (A l B lC l (A l B aC l
v(A l V lS l [A l V lS l (A l V lS l (A l V lS l D).

Jednotlivé úplné spojky sú očíslované. Skúsme si zjednodušiť normálnu formu OR pomocou Karnaughovej mapy (obr. 5.57). Tu sa stretávame s ojedinelým prípadom, kedy nie je možné vytvárať skupiny. To znamená, že táto normálna forma OR nie je zjednodušená a jej schéma je znázornená na obr. 5.58.

Prahový logický obvod je obvod, v ktorom musí mať určitý minimálny počet vstupných premenných stav 1, aby sa výstup javil ako logická 1.
Napríklad potrebujete vypočítať obvod s piatimi vstupnými premennými. Výstup by mal byť 1 iba vtedy, keď sú aspoň 4 vstupy 1.
Vstupné premenné sú pomenované A, B, C, D a E. Výstupná premenná je Z. Najprv musíte definovať pravdivostnú tabuľku. S piatimi premennými je možných 32 možností (obr. 5.59):
Z =¦ (A l B lC l D l E^v (A l B lC l D l E)v (A l B lC l D l v^A l V lC l D l E^v [A l B lC l DlE^v (AlBlClDlE).
Normálny tvar OR pozostáva zo šiestich úplných spojok.
Normálny tvar OR je zjednodušený pomocou Carnotovho diagramu (obr. 5.60). Môžete vytvoriť 5 dvojitých skupín. Ukazuje sa nasledujúca zjednodušená logická funkcia:
Z = (A aBaCaE)v (A aBaDaE)v (A aBaCaD)v v(A aC a D a E)v (B aC a D a E).

Obvod pre zjednodušenú funkciu je znázornený na obr. 5.61. Táto rovnica môže byť ďalej zjednodušená pomocou algebry logiky. Pri prvých troch úplných spojkách môže byť v zátvorke (AaB), pri posledných dvoch - (C l D). Ukazuje sa funkcia:
Z = [(A A B) A ((CA E) V (D A E) A CA X>))] V [(C AD) A ((A A E) V (BA Z))]. Nedosiahlo sa však žiadne výrazné zjednodušenie.

Komparačný obvod (komparátor)

V digitálnom inžinierstve je často potrebné porovnávať digitálne dáta medzi sebou. Najjednoduchší porovnávací obvod, takzvaný komparátor, porovnáva stav dvoch premenných navzájom.
Nech sú premenné označené A a B. A a B sa môžu rovnať. A môže byť viac ako B a naopak. Komparátor má tri výstupy pre tieto tri možnosti. Sú označené X, Y a Z a ich stavy sú priradené takto:
A \u003d Z \u003d X \u003d 1;
A > B^ > Y= 1;
ALE< В =>Z = 1.
Preto je potrebné syntetizovať obvod s dvomi vstupnými premennými A a B a s výstupnými premennými X, Y a Z.
Pri vytváraní pravdivostnej tabuľky by sa mali dodržiavať pravidlá: A je väčšie ako B, ak A = 1 a B = 0. Podľa toho je B väčšie ako A, ak B = 1 a A = 0. Pravdivostná tabuľka je znázornená na obr. 5.62.
Logické funkcie sa získajú z pravdivostnej tabuľky:
X = (AaB)v(AaB);
Y = A a B;
Z = A a B.
Tieto rovnice nie sú ďalej zjednodušované Požadovaná schéma je znázornená na obr. 5.63.

Ryža. 5.62.

Ryža. 5.63.

Pred opustením továrne sa tranzistory testujú, aby sa zabezpečilo, že štyri dôležité parametre A, B, C a D sú v prijateľnom rozsahu. Na meranie sa používajú štyri digitálne snímače. Snímač vydá 1, ak je nameraná hodnota v povolenom rozsahu. Ak je nameraná hodnota mimo rozsahu prijateľných hodnôt, potom snímač vydá 0.
Triedenie tranzistorov prebieha pomocou digitálneho obvodu. Ak sú všetky štyri hodnoty v rozsahu prijateľných hodnôt, výstupná premenná M sa nastaví do stavu 1. Ak je len B mimo rozsahu prijateľných hodnôt, potom sa výstupná premenná N nastaví do stavu 1. Ak iba B a D sú mimo rozsahu prijateľných hodnôt, potom výstupná premenná U dostane stav 1. Vo všetkých ostatných prípadoch je výstup Z 1, čo znamená, že tranzistor je chybný.
Je potrebné vypočítať obvod a postaviť ho iba na prvkoch AND-NOT (hovorí sa tiež „v základe AND-NOT“).
Vstupné premenné sú A, B, C a D. Výstupné premenné sú M, N, U a Z. M sa zmení na 1, ak A=1, 5=1, C=1 a D=1. Toto je možnosť 16c pravdivostná tabuľka (obr.
5,64). bude 1, ak A = \, 5 = 0, C = 1 a D = 1 (možnosť 14). U sa bude rovnať 1, ak A je 1, 5 = 0,
C = 1 a D = 0 (možnosť 6). Vo všetkých ostatných prípadoch, okrem 6, 14 a 16, je Z 1.

Ryža. 5.64. Tabuľka pravdivosti pre obvod triedenia tranzistorov. Pre prehľadnosť sa nuly pre výstupnú premennú nepíšu.

Výsledkom sú nasledujúce logické funkcie:
M = AaBaCaD;
N = A a B a C a D; U = A a B a C a D. Funkcia Z obsahuje 13 úplných spojok. Z je vždy 1, ak ani M, N ani U nie sú 1. Pre Z je lepšie písať normálny tvar OR (pozri obrázok 5.64):
Z = (^4a5aCaD)v^a5aCaD^v^aBaCaZ));
Z = M v N v U. Potom pre priamu hodnotu Z:
Z = M v N v U.

Ryža. 5,65.

Nájdené funkcie pre M, Nn U nie je možné zjednodušiť. Musia sa prepočítať spolu s rovnicou pre Z na základ NAND:
M = AaBaCaD\
N = A a B a C, D;
U = AlVlSlo",
Z = MvNvU = MaNaU;
Z = M a N a U.
Z týchto rovníc obvod znázornený na obr. 5,65. Prostredníctvom výstupov M, N, U a Z je možné ovládať mechanické zariadenie, ktoré rozdeľuje tranzistory do 4 rôznych kontajnerov.

zhrnutie ďalších prezentácií

"Základné algoritmické štruktúry" - Vykonávanie príkazov "tela slučky". Bloková schéma "vetvenia" algoritmickej štruktúry. Nech n=5; i=4. Bloková schéma cyklického algoritmu. Koniec. Algoritmická štruktúra "výber". Nech n=5; i=5. Štart. Štruktúra pobočky. Nech n=5; i=6. Hlavné typy algoritmických štruktúr. Algoritmická štruktúra "cyklus". Kladné číslo. Bloková schéma algoritmickej štruktúry "výber". Bloková schéma lineárneho algoritmu.

"Typy algoritmov" - Upratovanie bytu. Otvorte vrecko. Motto lekcie. Hanojské veže. Názov postavy. Pozrite si karikatúru. Úroda. Úvod do algoritmu. Pristúpte k prechodu. Cyklické algoritmy. Vojdite do záhrady. Ruky. Algoritmus ľudských akcií. Grafický diktát. Algoritmy nahrávania. Algoritmus.

Zaznamenávanie cyklu v procedúre. Úprava postupu. Primárne farby. Nakreslíme stenu. Čo je Algoritmus. Príkaz. Interaktívny tutoriál. Nakreslíme strechu. Kreslíme dom. Kreslíme. Kreslíme okná. Dom je pripravený. Cyklus. Vedomosti. Zmeňte farbu pera.

"Problémy pre lineárny algoritmus" - X = 0 Neexistujú žiadne riešenia. Y = 2. X = 3 Y = 1/48. Sú uvedené súradnice vrcholov trojuholníka ABC. Vypočítajte hodnotu funkcie Y pri X=2 pomocou vývojového diagramu. Previesť A na väčšie jednotky informácií. Algoritmizácia je proces vývoja algoritmu (akčného plánu) na riešenie problému. X = -1 Žiadne riešenia. Príklady riešenia problémov. Vzhľadom na dĺžky strán trojuholníka A, B, C. Nájdite oblasť trojuholníka S. Vytvorte blokovú schému algoritmu na riešenie problému.

"Algoritmické konštrukcie" - Spôsob znázornenia algoritmov vo forme grafu. Vetvenie. Znázornenie algoritmov vo forme popisu postupnosti akcií. Formy reprezentácie algoritmov. Vývojový diagram algoritmu "Tapeta". Algoritmické konštrukcie. Algoritmus na riešenie problému. Bloková schéma. Grafický spôsob prezentácie algoritmov. Spôsoby reprezentácie algoritmov. Algoritmus. Komplexný algoritmus. Blokové schémy základných štruktúr.

"Hlavné typy algoritmických štruktúr" - Zapíšte si algoritmy vo verbálnej forme. Skupinová práca. Štruktúra. Pravopisné predpony. Hlavné typy algoritmických štruktúr. Kontrola samostatnej práce. Fizminutka. Úlohy na upevnenie vedomostí. Algoritmus. Základná štruktúra. Nastavenie počiatočných parametrov. Recept na prípravu čaju. Vetvenie. Nájdite koreň. Slučka s dodatočnou podmienkou. Cyklus. Blokové symboly. Koniec algoritmu. Hlavné typy agrorytmických štruktúr.

Každodenný život každého človeka spočíva v riešení obrovského množstva úloh rôznej zložitosti v práci alebo pri štúdiu. Niektoré úlohy sú také jednoduché, že keď ich vykonávame, niektoré činnosti robíme automaticky bez toho, aby sme o tom premýšľali. Riešenie akéhokoľvek problému, dokonca aj najjednoduchšieho, sa spravidla vykonáva postupne v niekoľkých krokoch. Tento druh postupnosti pri riešení problémov sa nazýva algoritmus. Dnes zvážime, čo sú lineárne algoritmy, ako je znázornená ich štruktúra, ako sú riešené a programované.

Algoritmický jazyk

Tento koncept je presnou inštrukciou pre interpreta, aby vykonal určitú postupnosť akcií, ktorá je zameraná na vyriešenie úlohy.

Tento jazyk je prostriedkom na popis algoritmov, ktoré sú zvyčajne orientované na používateľa.

• Blok začiatku-konca algoritmu. Na bloku je nápis „začiatok“ alebo „koniec“.
• Blok "vstup-výstup dát". Tento blok je znázornený ako rovnobežník. Sú na ňom umiestnené tieto nápisy: "vstup", "výstup", "tlač". Sú sprevádzané aj zoznamom vstupných alebo výstupných premenných, resp.
• Aritmetický blok alebo rozhodovací blok. Zodpovedá obdĺžniku. Na bloku by mal byť nápis: „operácia“, „skupina operácií“.

Tu je pomocou takýchto blokových schém znázornené riešenie lineárnych algoritmov. Ďalej si povieme niečo o vlastnostiach priraďovania hodnôt.

Lineárne výpočtové algoritmy

Hlavnou elementárnou akciou vo výpočtovom algoritme je priradenie určitej hodnoty premennej. V prípade, že je hodnota konštanty určená typom jej zápisu, hodnota premennej získa konkrétnu hodnotu výlučne ako výsledok priradenia. Dá sa to urobiť dvoma spôsobmi: pomocou príkazu priradenia; pomocou príkazu input.

Príklad riešenia lineárneho algoritmu

Uveďme príklad popisu pravidiel delenia obyčajných zlomkov pomocou lineárneho algoritmu, ktorý má v školských učebniciach nasledujúci obsah:

• čitateľ zlomku 1 musí byť vynásobený menovateľom zlomku 2;
• menovateľ zlomku 1 musí byť vynásobený čitateľom zlomku 2;
• je potrebné zapísať zlomok, v ktorom čitateľ je výsledkom vyplnenia bodu 1 a menovateľ je výsledkom vykonania bodu 2. Algebraická forma tohto pravidla je nasledovná:

a/b: c/d=(a*d)/(b*d)=m/n.

Poďme teda zostaviť algoritmus na delenie zlomkov pre počítač. Aby sme sa nemýlili, použijeme pre premenné rovnaké označenia ako vo vzorci, ktorý bol naznačený vyššie. a, b, c, d - počiatočné údaje vo forme celočíselných premenných. Výsledkom budú tiež celočíselné hodnoty. Riešenie v algoritmickom jazyku bude nasledovné:

alg Delenie zlomkov

celý a, b, c, d, m, n

vstup a, b, c, d

kon

Grafická podoba riešenia

Schéma vyššie opísaného lineárneho algoritmu vyzerá takto:

Príkaz priradenia hodnoty má nasledujúci formát:

Premenná:=výraz.

Znak ":=" sa číta ako priradiť.

Priradenie je príkaz, ktorý sa vyžaduje, aby počítač vykonal nasledovné:

• hodnotenie prejavov;
• priradenie prijatej hodnoty k premennej.

Vyššie uvedený algoritmus obsahuje dva príkazy ako priradenie. Vo vývojovom diagrame musí byť pokyn na zadanie napísaný v obdĺžniku nazývanom výpočtový blok.

Pri popise lineárnych algoritmov nie je pri písaní výrazov žiadna zvláštna potreba povinného dodržiavania prísnych pravidiel. Môžete ich napísať pomocou obvyklého matematického formulára. Koniec koncov, toto nie je striktná syntax programovacieho jazyka.

V uvedenom príklade algoritmu existuje aj vstupný príkaz:

Zadajte a, b, c, d.

Vstupný príkaz v blokovej schéme je zapísaný v paralelograme, to znamená v I/O bloku. Vykonaním tohto príkazu procesor preruší prácu, kým používateľ nevykoná určité akcie. Konkrétne: používateľ musí zadať vstupné premenné (ich hodnoty) na (klávesnici) a stlačiť Enter, ktorý funguje ako kláves enter. Je dôležité, aby boli hodnoty zadané v rovnakom poradí ako zodpovedajúce premenné vo vstupnom zozname.

Lineárny algoritmus. Jeho programovanie

Ako už bolo spomenuté na začiatku článku, lineárne programy môžu obsahovať tieto príkazy:

• zadanie;
• vstup;
• výkon.

To znamená, že pomocou uvedených operátorov sa implementujú algoritmy.

Takže v programovacom jazyku je to napísané takto:

NECH A = B, kde A je premenná, B je výraz. Napríklad A = Y + 20.

Vstupný operátor vyzerá takto:

INPUT, napríklad: INPUT C

Operátor pre výstup údajov, hodnôt, je napísaný takto:

TLAČIŤ. Napríklad PRINT C.

Uveďme si jednoduchý príklad. Musíme napísať program, ktorý nájde súčet čísel A a B zadaných z klávesnice.

V programovacom jazyku dostaneme program, ktorého text je uvedený nižšie.

Vstupné, výstupné operátory v programovacom jazyku Pascal

Pascal neposkytuje špeciálne operátory pre vstupné alebo výstupné operácie, ktoré používajú lineárne algoritmy. V programoch sa výmena informácií uskutočňuje pomocou vstavaných postupov. Keďže nie je potrebný predbežný popis štandardného postupu, je dostupný každému programu, ktorý obsahuje jeho volanie. Taktiež názov spomínaného postupu nie je žiadne vyhradené slovo.

Pri zadávaní údajov sa takéto príkazy používajú na odkazovanie na štandardný postup zadávania údajov, ktorý je už zabudovaný v programe.

Čítanie (A, B, C), kde A, B, C sú premenné, ktoré je potrebné zadať do pamäte RAM na zapamätanie.

Readlnn (x1, y, x2) - po ukončení zadávania sa kurzor presunie na začiatok nového riadku.

readlnn; - označuje očakávanie stlačenia tlačidla "Enter". Toto vyhlásenie sa spravidla vkladá do textu pred posledný "Koniec", aby sa uložili výsledky vykonávania programu na obrazovke s obsahom.

Zobrazenie údajov na obrazovke monitora sa vykonáva pomocou nasledujúcich príkazov:

Zápis (A, B, C) - zadanie hodnôt A, B, C v jednom riadku, kurzor neopustí aktuálny riadok.

Writeln (z, y, z2) - po ukončení výstupu hodnôt sa kurzor na tejto pozícii presunie na nový riadok.

Writeln; - označuje preskočenie jedného riadku a prechod na začiatok nového.

Pomocou takýchto jednoduchých operátorov sa údaje zadávajú a vydávajú v jazyku Pascal.