Arten von Algorithmen. Arten von Algorithmen: linear, verzweigend, zyklisch. Beispiele für grundlegende Arten von Algorithmen

Algorithmen können einfach oder komplex sein, aber das haben sie alle Gemeinsamkeiten. Basierend auf diesen Merkmalen ist es üblich, drei Arten von Algorithmen zu unterscheiden, mit denen wir uns vertraut machen werden.

In Algorithmen werden Befehle nacheinander in einer bestimmten Reihenfolge geschrieben. Sie werden nicht unbedingt in einer schriftlichen Reihenfolge durchgeführt. Möglicherweise gibt es interne Verweise auf unterschiedliche Befehle.

Generell erinnert die Ausführung von Befehlen nach einem Algorithmus ein wenig an Brettspiele, bei denen die Teilnehmer abwechselnd würfeln und über Felder laufen. Darüber hinaus können am Rand Kommentare im Stil „Gehe 2 Zellen zurück“ oder „Gehe 5 Zellen vorwärts“ stehen (Abb. 1).

Reis. 1. Brettspiel ()

Ein komplexeres Modell zur Ausführung des Algorithmus ist das bekannte Spiel „Monopoly“ oder „Manager“ (Abb. 2).

Reis. 2. Spiel „Monopol“ ()

Der wesentliche Unterschied zwischen diesem Spiel und der einfachen Ausführung eines Algorithmus besteht darin, dass das ultimative Ziel der Teilnehmer nicht darin besteht, den Weg zu vollenden, sondern durch bestimmte Aktionen Geld anzusammeln.

Abhängig von der Reihenfolge der Befehlsausführung können drei Arten von Algorithmen unterschieden werden:

Lineare Algorithmen;

Verzweigungsalgorithmen;

Algorithmen mit Wiederholungen.

"Monopol"

Monopoly ist eines der beliebtesten Brettspiele. Seine Regeln sind recht einfach und für jeden verständlich, der es mindestens einmal gespielt hat (Abb. 4).

Reis. 4. Spiel „Monopol“ ()

Zu Beginn verfügen die Spieler über die gleiche Menge Bargeld. Indem sie würfeln und ihre Spielsteine ​​auf dem umlaufenden Spielfeld bewegen, erwerben sie verschiedenfarbige Grundstücke. Sobald der Spieler das vom Feind erworbene Gelände erreicht, ist er verpflichtet, ihm die festgelegte Miete zu zahlen. Nach dem Kauf aller Grundstücke einer Farbgruppe kann der Teilnehmer darauf Häuser und Hotels bauen, wodurch sich die Miethöhe erhöht. Das Ziel von allem, was passiert, ist banal – alle Rivalen zu ruinieren.

Offiziellen Quellen zufolge – der Firma Parker Brothers, die seit 1935 bis heute Monopoly produziert – entstand das legendäre Brettspiel wie folgt. Im Jahr 1934 lud ein arbeitsloser Ingenieur, Charles Darrow (Abb. 5), das oben genannte Büro ein, ein von ihm erfundenes Spiel über den Immobilienhandel zu veröffentlichen.

Reis. 5. Charles Darrow ()

Nachdem sie 52 Designfehler im Brettspiel entdeckt hatten, lehnten die Parker-Brüder den Erfinder ab. Mit rein amerikanischem Unternehmertum ging er zur Druckerei, bestellte 5.000 Exemplare des Spiels und war ziemlich schnell ausverkauft. Parker Brothers erkannte, dass ihnen die Gewinne direkt vor der Nase wegschlugen, und erwarb hastig die Rechte an Monopoly. Schon im nächsten Jahr wurde es zum meistverkauften Brettspiel in den Vereinigten Staaten und Darrow wurde zur lebendigen Verkörperung des amerikanischen Traums.

Gleichzeitig gibt es aber auch frühere Spiele, die frappierend an Monopoly erinnern. Es stellt sich heraus, dass Darrow einfach der Erste war, der einsprang und ein Patent für diesen „volkstümlichen“ Zeitvertreib erhielt? Ja und nein. Untersuchungen der letzten Jahre haben Licht auf das Geheimnis der Ursprünge von Monopoly geworfen.

In der zweiten Hälfte des vorletzten Jahrhunderts lebte und arbeitete der politische Ökonom Henry George in den Vereinigten Staaten. Er schlug vor, alle Steuern durch eine einzige Steuer zu ersetzen – auf Grund und Boden. Begeistert von seinen Ideen erhielt Magee im Januar 1904 ein Patent für einen Schreibtisch Spiel Die Vermieterspiel, das sowohl Regeln als auch Regeln hat Aussehen Erinnert mich an das heutige Monopoly. Man geht davon aus, dass es beim „Landlord’s Game“ zwei Regelvarianten gab: Nachdem die Spieler ein Spiel nach den geltenden Steuergesetzen gespielt hatten, wechselten sie zu dem von George vorgeschlagenen Modell – und waren angeblich von dessen notwendigen Vorteilen überzeugt. Somit war das Spiel keine Unterhaltung, sondern ein Instrument des ideologischen Kampfes.

Es erreichte zwar keine Massenproduktion, aber „The Landlord’s Game“ verbreitete sich in handwerklichen Kopien nach und nach in ganz Nordamerika. Während der Weltwirtschaftskrise kam es zu einem starken Interesse am Brettspiel: Tausende Arbeitslose stellten sich zumindest am Spieltisch gerne als Geldsäcke vor. Das Erscheinen eines unternehmungslustigen Mannes wie Charles Darrow dauerte nur wenige Monate – und er erschien und erlangte jahrzehntelang den Ruhm des alleinigen Erfinders von Monopoly.

Natürlich gab es diejenigen, die es für notwendig hielten, den Urheberrechtsinhabern ein Stück zu entreißen. Nicht lizenzierte Monopole haben China überschwemmt. Und in unserem Land wurden und werden geordnete Reihen von Klonen produziert – „Makler“, „Genossenschaft“, „Manager“ (Abb. 6) ...

Reis. 6. Spiel „Manager“ ()

Angesichts des jüngsten Umdenkens über Darrows Rolle bei der Gründung von Monopoly und des Auslaufens des Urheberrechts werden solche Unternehmen nicht verklagt. Auch wenn wir davon ausgehen, dass es keine Elizabeth Magie auf der Welt gab, sind die Regeln von Monopoly längst gemeinfrei geworden. Einen Teil des Patents behält Hasbro jedoch weiterhin für sich: das Design der Chips, die grafische Gestaltung, die Abfolge der Zellen auf dem Spielfeld.

Ein Algorithmus, bei dem Befehle in der Reihenfolge ausgeführt werden, in der sie geschrieben wurden, also sequentiell nacheinander, wird aufgerufen linear.

Reis. 3. Glühbirne ()

Der folgende Algorithmus zum Ersetzen einer durchgebrannten Glühbirne ist beispielsweise linear (Abb. 3):

1. Schalten Sie den Lichtschalter aus;

2. Schrauben Sie die durchgebrannte Glühbirne heraus.

3. Eine neue Glühbirne einschrauben;

4. Schalten Sie den Schalter ein, um zu prüfen, ob das Licht eingeschaltet ist.

Anhand eines Blockdiagramms lässt sich dieser Algorithmus wie folgt darstellen:

(Blockschaltbild (Abb. 7.) siehe am Ende der Zusammenfassung)

Situationen, in denen die Reihenfolge der erforderlichen Aktionen im Voraus bekannt ist, kommen äußerst selten vor. Im Leben muss man Entscheidungen oft abhängig von der aktuellen Situation treffen. Wenn es regnet, nehmen wir einen Regenschirm und ziehen einen Regenmantel an; Wenn es heiß ist, tragen Sie leichte Kleidung. Es gibt auch komplexere Auswahlbedingungen. In manchen Fällen hängt das zukünftige Schicksal einer Person von der gewählten Entscheidung ab.

Die Entscheidungslogik kann wie folgt beschrieben werden:

WENN<условие>, DAS<действия 1>,

ANSONSTEN<действия 2>

WENN du Geld hast, DANN kaufe Brot, SONST kaufe es nicht.

WENN Du heute in der Mitte bist, DANN ruf mich an, SONST ruf mich nicht an.

WENN Sie Ihre Lektionen gelernt haben, DANN gehen Sie spazieren, andernfalls lernen Sie Ihre Lektionen.

In manchen Fällen<действия 2>kann fehlen. Dies kann sowohl an der Offensichtlichkeit liegen (wie zum Beispiel im ersten Beispiel – es ist klar, dass man Brot einfach nicht kaufen kann, wenn man kein Geld hat), als auch daran, dass kein Bedarf dafür besteht.

WENN<условие>, DAS<действия 1>

WENN du dich einen Milchpilz nennst, DANN geh hinten rein.

WENN Sie gesund sein wollen, DANN werden Sie härter.

Man nennt eine Form der Handlungsorganisation, bei der je nach Erfüllung oder Nichterfüllung einer Bedingung die eine oder andere Handlungsfolge ausgeführt wird Verzweigung.

Stellen wir in Form eines Flussdiagramms den Handlungsablauf eines Schülers der 6. Klasse dar, der die Wohnungsschlüssel vergessen hat, den er sich so vorstellt: „Wenn Mama zu Hause ist, dann komme ich und setze mich zum Machen.“ meine Hausaufgaben. Wenn meine Mutter nicht zu Hause ist, gehe ich mit meinen Freunden Fußball spielen, bis meine Mutter kommt. Wenn draußen keine Freunde sind, fahre ich auf der Schaukel, bis meine Mutter kommt.“

(Blockschaltbild (Abb. 8.) siehe am Ende der Zusammenfassung)

Notwendige und ausreichende Bedingungen

Wir haben bereits mit Ihnen besprochen, dass es notwendige und ausreichende Voraussetzungen gibt.

Ein Beispiel für eine notwendige Bedingung wäre:

Um Arzt zu werden, müssen Sie eine medizinische Ausbildung erwerben.

Die Voraussetzung einer medizinischen Ausbildung ist für die Tätigkeit als Arzt notwendig, aber nicht ausreichend. Tatsächlich werden nicht alle Absolventen medizinischer Fakultäten Ärzte.

Ein Beispiel für eine hinreichende Bedingung wäre:

Um es kühler zu machen, schalten Sie einfach die Klimaanlage ein.

Diese Bedingung ist ausreichend: Wenn Sie die Klimaanlage einschalten, wird es tatsächlich kühler. Diese Bedingung ist jedoch nicht notwendig, denn um dieses Ziel zu erreichen, können Sie den Ventilator einschalten, das Fenster öffnen usw.

Natürlich gibt es gleichzeitig notwendige und hinreichende Bedingungen (solche Bedingungen werden als „Bedingungen“ bezeichnet). Äquivalent). Zum Beispiel:

Damit der Sommer kommt, ist es notwendig und ausreichend, dass der Frühling zu Ende geht.

Denn wenn der Frühling vorbei ist, dann kommt der Sommer, und wenn der Frühling nicht vorbei ist, kann der Sommer nicht kommen. Das heißt, die Bedingungen für das Ende des Frühlings und den Beginn des Sommers sind gleichwertig.

Die Konzepte notwendiger, ausreichender und äquivalenter Bedingungen sind in einem Zweig der Mathematik wie der mathematischen Logik sehr wichtig. Darüber hinaus findet man sie sehr häufig beim Beweis verschiedener Theoreme.

In der Praxis kommt es oft zu Problemen, bei denen eine oder mehrere Aktionen mehrmals wiederholt werden müssen, bis eine vorher festgelegte Bedingung erfüllt ist.

Wenn Sie beispielsweise eine Kiste Äpfel sortieren müssen, um die faulen von den reifen zu trennen, müssen wir die folgenden Schritte wiederholen:

1. Nimm einen Apfel.

2. Sehen Sie, ob es faul ist.

3. Wenn es faul ist, werfen Sie es weg; wenn nicht, legen Sie es in eine andere Kiste.

Diese Aktionen müssen ausgeführt werden, bis die Äpfel in der Kiste aufgebraucht sind.

Eine Form der Organisation von Aktionen, bei der die gleiche Abfolge von Aktionen wiederholt wird, bis eine vorher festgelegte Bedingung erfüllt ist, wird aufgerufen Zyklus (Wiederholung).

Eine Situation, in der eine Schleife niemals endet, wird aufgerufen Schleife.

Es sollten Algorithmen entwickelt werden, die solche Situationen nicht zulassen.

Betrachten Sie den Algorithmus für einen Wecker auf einem Telefon, der um 8:00 Uhr morgens klingeln und dann alle 10 Minuten klingeln sollte, bis er ausgeschaltet wird.

In diesem Fall sieht sein Blockdiagramm so aus: (siehe Blockdiagramm (Abb. 9.) am Ende der Zusammenfassung)

In dieser Lektion haben wir drei Arten von Algorithmen besprochen – lineare Algorithmen, Verzweigungsalgorithmen und Wiederholungsalgorithmen.

In der nächsten Lektion besprechen wir das Schreiben von Algorithmen in der Praxis.

Sieb des Eratosthenes

Erinnern wir uns an die Definition einer natürlichen Primzahl.

Eine natürliche Zahl heißt Primzahl, wenn sie hat nur zwei Teiler: Eins und die Zahl selbst. Die restlichen Nummern werden angerufen zusammengesetzt. Darüber hinaus ist die Zahl 1 weder eine Primzahl noch eine zusammengesetzte Zahl.

Beispiele für Primzahlen: 2, 3, 5, 7.

Beispiele für zusammengesetzte Zahlen: 4, 6, 8.

Im 3. Jahrhundert v. Chr. schlug der griechische Mathematiker Eratosthenes den folgenden Algorithmus vor, um alle Primzahlen zu finden, die kleiner als eine bestimmte Zahl sind P:

1. Schreiben Sie alle natürlichen Zahlen von 1 bis auf N;

2. 1 durchstreichen;

3. Unterstreiche die kleinste der nicht markierten Zahlen;

4. Streichen Sie alle Zahlen durch, die ein Vielfaches der im vorherigen Schritt unterstrichenen Zahl sind.

5. Wenn die Liste nicht markierte Zahlen enthält, fahren Sie mit Schritt 3 fort, andernfalls sind alle unterstrichenen Zahlen Primzahlen.

Dies ist ein zyklischer Algorithmus. Bei der Ausführung werden die Schritte 3–5 wiederholt, bis in der ursprünglichen Liste nicht markierte Nummern vorhanden sind.

Betrachten wir das Ergebnis dieses Algorithmus. Schreiben wir alles auf Primzahlen von 1 bis 25.

Schreiben wir Zahlen von 1 bis 25 auf.

Streichen wir die 1 durch. Unterstreichen wir nun die beiden. Streichen wir alle geraden Zahlen durch.

Da nicht alle Zahlen markiert sind, unterstreichen wir die 3. Nun streichen wir alle Zahlen durch, die durch 3 teilbar sind.

Da nicht alle Zahlen markiert sind, unterstreichen wir die 5. Nun streichen wir die Zahl 25 durch.

Da nicht alle Zahlen markiert sind, betonen wir die 7.

Sie können nichts durchstreichen, aber nicht alle Zahlen sind markiert, daher unterstreichen wir 11.

Es kann nichts durchgestrichen werden, aber nicht alle Zahlen sind markiert, deshalb unterstreichen wir 13. Auch hier kann nichts durchgestrichen werden – wir unterstreichen 17, dann 19 und 23.

Jetzt sind alle Zahlen markiert.

Wir erhalten Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23.

Reis. 7.Flussdiagramm zum Auswechseln einer Glühbirne

Reis. 8. Flussdiagramm der Aktionen für einen Sechstklässler

Reis. 9. Blockschaltbild des Weckers

Referenzliste

1. Bosova L.L. Informatik und IKT: Lehrbuch für die 6. Klasse. - M.: BINOM. Wissenslabor, 2012.

2. Bosova L.L. Informatik: Arbeitsbuch für die 6. Klasse. - M.: BINOM. Wissenslabor, 2010.

3. Bosova L.L., Bosova A.Yu. Informatikunterricht in den Klassen 5-6: Methodenhandbuch. - M.: BINOM. Wissenslabor, 2010.

1. Internetportal „Unser Netzwerk“ ()

2. Internetportal „Knowledge Hypermarket“ ()

3. Internetportal „kaz.docdat.com“ ()

Hausaufgaben

1. §3.4 (Bosova L.L. Informatik und IKT: Lehrbuch für die 6. Klasse).

2. Seite 81 Aufgaben 2, 6 (Bosova L.L. Informatik und IKT: Lehrbuch für die 6. Klasse).

3. Seite 82 Aufgabe 9, 11, 13, 14 (Bosova L.L. Informatik und IKT: Lehrbuch für die 6. Klasse).

4. * Seite 83 Aufgabe 15 (Bosova L.L. Informatik und IKT: Lehrbuch für die 6. Klasse).

Anmerkung: Der Algorithmus ist ein Grundkonzept für diejenigen, die mit dem Programmieren in einer beliebigen Programmiersprache beginnen möchten. Jede Aufgabe kann algorithmisch formalisiert werden. Um zu verstehen, wo wir anfangen sollen, schauen wir uns die wichtigsten Arten von Algorithmen an. Ziel dieser Vorlesung ist es, den Studierenden das Konzept eines Algorithmus näher zu bringen; zeigen, dass uns im Alltag ein so abstraktes Ding wie ein Algorithmus umgibt.

Pseudocode-Beispiel:

alg Ermitteln des Quotienten zweier Zahlen zu Beginn der Ausgabe („Dividende und Divisor festlegen“) Eingabe (Dividende, Divisor) Wenn Divisor ≠ 0, dann Quotient = Dividende / Divisor Ausgabe (Quotient), andernfalls Ausgabe („keine Lösung“) con alg Ermitteln der Quotient zweier Zahlen

In diesem Beispiel werden drei Variablen verwendet: Dividende, Divisor und Quotient. Dividend und Divisor werden vom Ausführenden mit beliebigen Zahlen angegeben. Der Quotient wird nur gezählt, wenn der Divisor nicht Null ist.

Die grafische Umsetzung des Algorithmus ist ein Blockdiagramm. Ein Blockdiagramm besteht aus Blöcken einer bestimmten Form, die durch Pfeile verbunden sind. Die Antwort erhält eine Person, die Befehle gemäß dem Flussdiagramm ausführt. Blockdiagramme werden in Vorlesung 2 ausführlicher besprochen.

Die Softwareimplementierung des Algorithmus ist Computer Programm, geschrieben in einer beliebigen algorithmischen Programmiersprache, zum Beispiel: C++, Pascal, Basic usw. Ein Programm besteht aus Befehlen in einer bestimmten Programmiersprache. Beachten Sie, dass das gleiche Blockdiagramm implementiert werden kann verschiedene Sprachen Programmierung. In diesem Fall wird die Antwort von einem Computer und nicht von einer Person empfangen. Weitere Informationen zum Schreiben von Programmen in der Programmiersprache C++ finden Sie in Vorlesung 3.

Es gibt drei Haupttypen von Algorithmen:

1. linearer Algorithmus,
2. Verzweigungsalgorithmus
3. zyklischer Algorithmus.

Linearer Algorithmus ist ein Algorithmus, bei dem Aktionen einmalig und streng nacheinander ausgeführt werden.

Das einfachste Beispiel für die Implementierung eines linearen Algorithmus ist der Heimweg von der Universität.

Eine verbale Art, diesen Algorithmus zu schreiben:

1. Verlassen Sie die Universität an der Bushaltestelle.
2. auf den richtigen Bus warten;
3. nimm den richtigen Bus;
4. für die Reise bezahlen;
5. an der gewünschten Haltestelle aussteigen;
6. nach Hause kommen.

Es ist klar, dass dieses Beispiel bezieht sich auf den linearen Algorithmus, weil Alle Aktionen folgen nacheinander, ohne Bedingungen oder Wiederholungen.

Es gibt drei Arten von Algorithmen: linear, verzweigt und zyklisch.

Linearer Typ von Algorithmen

Algorithmen, bei denen Anweisungen unabhängig von Bedingungen nacheinander ausgeführt werden, werden als Algorithmen vom linearen Typ bezeichnet.

Zum Beispiel ein Berechnungsalgorithmus, der die einfachsten Formeln verwendet, die keine Einschränkungen hinsichtlich der Werte der darin enthaltenen Variablen haben.

Beispiel

Formulierung des Problems : Berechnen Sie die Fläche eines Kreises, wenn der Radius bekannt ist.

Gegeben : R ist der Radius des Kreises.

Finden Sie: S – Fläche des Kreises.

Lösung: S=3.14R 2

Verbale Form des Schreibens des Algorithmus

Wählen wir die russische Sprache, um den Algorithmus in dieser Form zu schreiben, und schreiben wir eine Befehlsfolge auf, deren Ausführung bei einem bestimmten Radiuswert es uns ermöglicht, die Fläche zu finden:

Lesen Sie den R-Wert ab.

Multiplizieren Sie den R-Wert mit 3,14.

Multiplizieren Sie das Ergebnis der zweiten Aktion mit dem Wert von R.

Notieren Sie das Ergebnis als S-Wert.

In der Sprache der Flussdiagramme - Reis. 8

Verzweigende Algorithmen

Die Lösung von Problemen kann nicht immer in Form eines linearen Algorithmus dargestellt werden.

Algorithmen, bei denen es notwendig ist, die Auswahl einer Aktionsfolge abhängig von bestimmten Bedingungen zu organisieren, werden als Verzweigungsalgorithmen bezeichnet.

Bei der grafischen Methode wird die Verzweigung mithilfe eines logischen Elements (Raute) mit einem Eingang und zwei Ausgängen organisiert. Der Zweck des logischen Elements besteht darin, eine gegebene Bedingung zu überprüfen. Abhängig von der Erfüllung (Wahrheit) oder Nichterfüllung (Falschheit) der geprüften Bedingung kann in den Zweig „Ja“ bzw. „Nein“ verzweigt werden.

Beispiel

Formulierung des Problems : Berechnung
.

Gegeben: x – Argumentwert.

Finden: y – Funktionswert.

Lösung:

y= x, wenn x  0

- x wenn x<0

Blockdiagramm - siehe Abb. 9.

Mündliche Präsentation

Im Pseudocode :

X-Wert lesen

Wenn x>0, dann

Ende der Verzweigung

Notieren Sie den Wert

Markieren vollständige und unvollständige bedingte Konstruktion .

Zyklische Art von Algorithmen

Bei der Entwicklung von Algorithmen zur Lösung einer größeren Bandbreite von Problemen besteht häufig die Notwendigkeit, dieselben Befehle immer wieder zu wiederholen.

Ein Algorithmus, der aus mehreren Wiederholungen derselben Aktionen (Zyklen) kompiliert wurde, wird aufgerufen Zyklische Algorithmen.

Allerdings bedeutet „wiederholt“ nicht „auf unbestimmte Zeit“. Die Organisation von Schleifen, die niemals zu einem Stopp in der Ausführung des Algorithmus führt (das sogenannte Looping), stellt einen Verstoß gegen die Anforderungen an seine Wirksamkeit dar.

Bei der Entwicklung eines zyklischen Strukturalgorithmus werden folgende Konzepte unterschieden:

Schleifenparameter – ein Wert, dessen Änderung mit der wiederholten Ausführung des Zyklus verbunden ist;

Anfangs- und Endwert des Parameters Zyklus ;

Zyklusschritt – Dies ist der Wert, um den sich der Schleifenparameter bei jeder Wiederholung ändert.

Der zyklische Algorithmus besteht aus Vorbereitung des Zyklus, Hauptteil des Zyklus, Bedingungen für die Fortsetzung des Zyklus .

IN Zyklusvorbereitung umfasst Aktionen im Zusammenhang mit dem Festlegen von Anfangswerten für einen Zyklusparameter (Anfangs- und Endwerte, Parameterschritt).

IN Schleifenkörper beinhaltet: wiederholte Aktionen zur Berechnung der benötigten Mengen; Vorbereiten des nächsten Werts des Schleifenparameters, Vorbereiten anderer Werte, die für die wiederholte Ausführung von Aktionen im Schleifenkörper erforderlich sind.

IN Bedingung der Fortsetzung die Notwendigkeit weiterer sich wiederholender Aktionen wird ermittelt. Wenn der Schleifenparameter den Endwert überschreitet, muss die Schleife beendet werden.

Betrachten wir eine grafische Darstellung des zyklischen Blocks des Algorithmus (siehe Abb. 10).

Zyklen können mit sein Voraussetzung(wenn die Bedingung vor dem Beginn des Schleifenkörpers überprüft wird) und mit Nachbedingung(wenn die Bedingung nach dem ersten Durchlauf durch den Schleifenkörper überprüft wird).

Schleife mit Nachbedingung