Einführung in Algorithmen
Ein Algorithmus ist eine Folge von Schritten, die beschreiben, wie ein Problem gelöst werden kann. Jedes Computerprogramm, das mit einem Ergebnis endet, basiert grundsätzlich auf einem Algorithmus. Algorithmen sind jedoch nicht nur auf die Verwendung in Computerprogrammen beschränkt, sondern können auch zur Lösung mathematischer Probleme und für viele Fragen des täglichen Lebens verwendet werden. Basierend auf ihrer Funktionsweise können wir Algorithmen in mehrere Typen unterteilen. Schauen wir uns einige der wichtigsten an.
Arten von Algorithmen
Es gibt viele Arten von Algorithmen, aber die grundlegenden Arten von Algorithmen sind:
1) Rekursiver Algorithmus
Dies ist einer der interessantesten Algorithmen, da er sich selbst mit einem kleineren Wert als Eingaben bezeichnet, die er nach dem Auflösen der aktuellen Eingaben erhält. In einfacheren Worten, es ist ein Algorithmus, der sich wiederholt aufruft, bis das Problem gelöst ist.
Probleme wie der Tower of Hanoi oder die DFS eines Graphen können mit diesen Algorithmen einfach gelöst werden.
Zum Beispiel ist hier ein Code, der eine Fakultät unter Verwendung eines Rekursionsalgorithmus findet:
Fakt (y)
Wenn y 0 ist
return 1
return (y * Fakt (y-1)) / * hier findet die Rekursion statt * /
2) Algorithmus teilen und erobern
Dies ist ein weiterer wirksamer Weg, um viele Probleme zu lösen. Teilen Sie in Divide and Conquer-Algorithmen den Algorithmus in zwei Teile, der erste Teil unterteilt das vorliegende Problem in kleinere Unterprobleme desselben Typs. Im zweiten Teil werden diese kleineren Probleme gelöst und dann addiert (kombiniert), um die endgültige Lösung des Problems zu erhalten.
Mergesortierung und schnelle Sortierung können mit Divisions- und Eroberungsalgorithmen durchgeführt werden. Hier ist der Pseudocode des Merge-Sortier-Algorithmus, um Ihnen ein Beispiel zu geben:
MergeSorting (ar (), l, r)
Wenn r> l
- Suchen Sie den Mittelpunkt, um das angegebene Array in zwei Hälften zu unterteilen:
mittleres m = (l + r) / 2
- Rufen Sie mergeSorting für die erste Hälfte auf:
Rufe mergeSorting auf (ar, l, m)
- Rufen Sie mergeSorting für die zweite Hälfte auf:
Rufe mergeSorting auf (ar, m + 1, r)
- Füge die in Schritt 2 und 3 sortierten Hälften zusammen:
Merge aufrufen (ar, l, m, r)
3) Dynamischer Programmieralgorithmus
Diese Algorithmen erinnern sich an die Ergebnisse des letzten Laufs und verwenden sie, um neue Ergebnisse zu finden. Mit anderen Worten, der dynamische Programmieralgorithmus löst komplexe Probleme, indem er sie in mehrere einfache Teilprobleme aufteilt, diese dann jeweils einmal löst und für die spätere Verwendung speichert.
Die Fibonacci-Sequenz ist ein gutes Beispiel für dynamische Programmieralgorithmen. Sie sehen, dass sie im Pseudocode funktioniert:
Fibonacci (N) = 0 (für n = 0)
= 0 (für n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (für n> 1)
4) Gieriger Algorithmus
Diese Algorithmen werden zur Lösung von Optimierungsproblemen verwendet. In diesem Algorithmus finden wir eine lokal optimale Lösung (ohne Rücksicht auf zukünftige Konsequenzen) und hoffen, auf globaler Ebene die optimale Lösung zu finden.
Die Methode garantiert nicht, dass wir eine optimale Lösung finden können.
Der Algorithmus besteht aus 5 Komponenten:
- Der erste ist ein Kandidatensatz, aus dem wir versuchen, eine Lösung zu finden.
- Eine Auswahlfunktion, die bei der Auswahl des bestmöglichen Kandidaten hilft.
- Eine Machbarkeitsfunktion, die bei der Entscheidung hilft, ob der Kandidat zur Lösungsfindung herangezogen werden kann.
- Eine objektive Funktion, die einer möglichen Lösung oder einer Teillösung einen Wert zuweist
- Lösungsfunktion, die angibt, wann wir eine Lösung für das Problem gefunden haben.
Die Huffman-Codierung und der Dijkstra-Algorithmus sind zwei erstklassige Beispiele für die Verwendung des Greedy-Algorithmus.
Bei der Huffman-Codierung durchläuft der Algorithmus eine Nachricht und weist in Abhängigkeit von der Häufigkeit der Zeichen in dieser Nachricht für jedes Zeichen eine Codierung variabler Länge zu. Um eine Huffman-Codierung durchzuführen, müssen wir zuerst einen Huffman-Baum aus den eingegebenen Zeichen erstellen und dann den Baum durchlaufen, um den Zeichen Codes zuzuweisen.
5) Brute-Force-Algorithmus
Dies ist einer der einfachsten Algorithmen im Konzept. Ein Brute-Force-Algorithmus durchläuft blind alle möglichen Lösungen, um eine oder mehrere Lösungen zu suchen, die eine Funktion lösen können. Stellen Sie sich Brute Force vor, indem Sie alle möglichen Zahlenkombinationen verwenden, um einen Safe zu öffnen.
Hier ist ein Beispiel für die sequenzielle Suche mit Brute Force:
Algorithmus S_Search (A (0..n), X)
A (n) ← X
i ← 0
Während A (i) ≠ X tun
i ← i + 1
wenn ich <n gebe ich zurück
Andernfalls wird -1 zurückgegeben
6) Rückverfolgungsalgorithmus
Backtracking ist eine Technik, um eine Lösung für ein Problem in einem inkrementellen Ansatz zu finden. Es löst Probleme rekursiv und versucht, eine Lösung für ein Problem zu finden, indem jeweils ein Teil des Problems gelöst wird. Wenn eine der Lösungen fehlschlägt, entfernen wir sie und machen einen Backtrack, um eine andere Lösung zu finden.
Mit anderen Worten, ein Backtracking-Algorithmus löst ein Teilproblem. Wenn es das Problem nicht löst, macht er den letzten Schritt rückgängig und sucht erneut nach einer Lösung für das Problem.
Das N Queens-Problem ist ein gutes Beispiel, um den Backtracking-Algorithmus in Aktion zu sehen. Das N-Queen-Problem besagt, dass sich N Queens auf einem Schachbrett befinden und dass wir sie so arrangieren müssen, dass keine Queen eine andere Queen im Brett angreifen kann, wenn sie einmal organisiert ist.
Schauen wir uns nun den SolveNQ-Algorithmus und die Check Valid-Funktionen an, um das Problem zu lösen:
CheckValid (Schachbrett, Zeile, Spalte)
Start
Befindet sich links in der aktuellen Spalte eine Dame, wird false zurückgegeben
Wenn sich die Dame in der oberen linken Diagonale befindet, geben Sie false zurück
Befindet sich die Dame in der linken unteren Diagonale, geben Sie false zurück
Rückgabe wahr
Ende
SolveNQ (Board, Spalte)
Start
Wenn alle Spalten voll sind, geben Sie true zurück
Für jede im Schachbrett vorhandene Reihe
Tun
Wenn, CheckValid (board, x, column), dann
Setze die Dame in die Zelle (x, Spalte) auf der Tafel
Wenn SolveNQ (Board, Spalte + 1) = True ist, geben Sie true zurück.
Ansonsten entferne die Dame aus der Zelle (x, Spalte) vom Brett
Erledigt
Falsch zurückgeben
Ende
Schlussfolgerung - Arten von Algorithmen
Algorithmen stehen hinter den meisten beeindruckenden Funktionen, die Computer ausführen können, und diese bilden den Kern der meisten Computeraufgaben. Mit Algorithmen besser umzugehen, hilft Ihnen nicht nur, ein erfolgreicher Programmierer zu sein, sondern auch, effizienter zu werden.
Empfohlene Artikel
Dies war ein Leitfaden für die Arten von Algorithmen. Hier diskutieren wir die 6 wichtigsten Algorithmus-Typen mit ihren Funktionen. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren -
- Einführung in den Algorithmus
- Algorithmus in der Programmierung
- Algorithmus Interview Fragen
- Factorial in Python | Techniken
- Schnelle Sortieralgorithmen in Java
- Top 6 Sortieralgorithmus in JavaScript