Publicité R▼
⇨ voir la définition de Wikipedia
Publicité ▼
Wikipedia
Der Hase-Igel-Algorithmus ist ein Verfahren, mit dem in einer einfach verketteten Liste Schleifen mit der Zeitkomplexität und einer Platzkomplexität von gefunden werden können. Mathematisch betrachtet dient der Algorithmus zum Auffinden von Zyklen in Folgen. Er ist auch unter dem Namen Floyds Algorithmus zum Auffinden von Schleifen (englisch Floyd's cycle-finding algorithm) bekannt und darf nicht mit Floyds Algorithmus aus der Graphentheorie verwechselt werden.
Inhaltsverzeichnis |
Neben der trivial ersichtlichen Verwendung zum Auffinden von Schleifen in zur Ablage von Daten genutzten Listen ist der Hase-Igel-Algorithmus die Grundlage der Pollard-Rho-Methode zur Bestimmung der Periodenlänge einer Zahlenfolge einschließlich der darauf zurückführbaren Primfaktorzerlegung.
Der Algorithmus wird auch im Themenfeld der pseudozufälligen Folgen eingesetzt.
Der Algorithmus besteht aus dem gleichzeitigen Durchlauf der Liste mit unterschiedlichen Schrittweiten. Dabei werden zwei Zeiger auf Listenelemente benutzt, von denen der eine (Igel) bei jeder Iteration auf das nächste Element verschoben wird, während der andere (Hase) bei derselben Iteration auf das übernächste Element verschoben wird. Wenn die beiden Zeiger sich begegnen, also dasselbe Element referenzieren, hat die Liste eine Schleife. Wenn einer der beiden Zeiger das Ende der Liste erreicht, hat sie keine Schleife.
Am besten kann die Vorgehensweise visualisiert werden, indem in einem gezeichneten Diagramm der Weg der beiden Zeiger verfolgt wird. Es ist leicht ersichtlich, dass sowohl bei einer Schleife mit ungerader Anzahl von Elementen als auch bei einer Schleife mit gerader Anzahl der Hase in höchstens einem Durchlauf des Igels auf diesen trifft.
Weil mit jedem Schritt des Igels der Hase einen Schritt näher an den Igel heran kommt, terminiert der Algorithmus in endlicher Zeit.
Im besten Fall (best case performance) sind bei einer zyklischen Liste mit Elementen mit als Länge des Zyklus und als Anzahl der Elemente vor dem Beginn des Zyklus Schritte notwendig, da der Igel mindestens den Anfang des Zyklus erreichen muss, bevor der Hase ihn auf einer zweiten Runde einholen kann.
Im schlechtesten Fall (worst case performance) sind Schritte notwendig, das heißt der Hase erreicht den Igel erst auf dem letzten Element der Liste. Zu diesem Zeitpunkt hat der Igel die Schleife genau einmal durchlaufen, der Hase jedoch zweimal.
# include <stdio.h> # include <stdlib.h> int main() { struct liste { struct liste *next; } *root, *el, *hase, *igel; int i; /* Liste erzeugen. */ root = el = malloc(sizeof(struct liste)); for(i=0; i<5; ++i) { struct liste *eneu = malloc(sizeof(struct liste)); el->next = eneu; el = eneu; } /* Zyklischen Verweis vom letzten auf das zweite Element anlegen. */ el->next = root->next; /* Hase-Igel-Algorithmus. */ igel = root; hase = root->next; while(hase && hase != igel) { printf("%p %p\n", hase, igel); igel = igel->next; hase = hase->next; if(hase) hase = hase->next; } if(hase) puts("Zyklus gefunden!"); else puts("Liste ist nicht zyklisch!"); return 0; }
with Ada.Text_IO; use Ada.Text_IO; procedure Hase_Igel is package Int_IO is new Integer_IO(Integer); use Int_IO; type Liste; type Liste_P is access Liste; type Liste is record Name : Integer; Next : Liste_P; end record; Root, Last, Hase, Igel : Liste_P; begin -- Liste erzeugen Root := new Liste'(Name => 0, Next => null); Last := Root; for I in 1..12 loop Last.Next := new Liste'(Name => I, Next => null); Last := Last.Next; end loop; -- zyklischen Verweis erzeugen Last.Next := Root.Next.Next; -- Hase-Igel-Algorithmus Igel := Root; Hase := Igel.Next; while Hase /= null and Hase /= Igel loop Put(Hase.Name, 4); Put(Igel.Name, 4); New_Line; Igel := Igel.Next; Hase := Hase.Next; exit when Hase = null; Hase := Hase.Next; end loop; if Hase = null then Put_Line("Liste ist nicht zyklisch"); else Put_Line("Zyklus gefunden"); end if; end Hase_Igel;
(define (is-mlist? lst) (define (iter hase igel counter) ; hase und igel sind meine zeiger, (cond ((null? hase) #t) ;ist a null >#t ((eq? (mcar hase) (mcar igel)) #f) (else (if (= counter 1) ;sezte couner auf startwert 1 (iter (mcdr hase) (mcdr igel) 0) (iter (mcdr hase) igel 1))))) ;igel startet bei plus 1 (iter (mcdr lst) lst 0)) ;(define a (mlist 2 3 5 7)) ;prüfbeispiel ;(is-mlist? a)
Ansatz
Jeder durchlaufene Knoten wird in einer geeigneten Struktur gespeichert.
Probleme
Ansatz
In einer doppelt verketteten Liste hat jedes Element sowohl einen Zeiger auf das folgende als auch auf das vorhergehende Element. Beim Durchlauf einer solchen Liste muss also jedes Element das vorher besuchte als vorhergehendes Element referenzieren. Wenn das nicht so ist, muss die Liste eine Schleife haben, da – Korrektheit der Verkettung vorausgesetzt – zu diesem besuchten Element zwei Zeiger existieren.
Probleme
Ansatz
Die Liste wird durchlaufen; dabei wird jeder Knoten markiert. Wenn ein markierter Knoten getroffen wird, hat die Liste eine Schleife.
Probleme
Ansatz
Der Zeiger auf das nächste Element jedes Listenelements wird mit dem Startelement verglichen. Wenn ein Element auf das Startelement zeigt, hat die Liste eine Schleife.
Probleme
Contenu de sensagent
dictionnaire et traducteur pour sites web
Alexandria
Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !
Essayer ici, télécharger le code;
SensagentBox
Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.
Solution commerce électronique
Augmenter le contenu de votre site
Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.
Parcourir les produits et les annonces
Obtenir des informations en XML pour filtrer le meilleur contenu.
Indexer des images et définir des méta-données
Fixer la signification de chaque méta-donnée (multilingue).
Renseignements suite à un email de description de votre projet.
Jeux de lettres
Les jeux de lettre français sont :
○ Anagrammes
○ jokers, mots-croisés
○ Lettris
○ Boggle.
Lettris
Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.
boggle
Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer
Dictionnaire de la langue française
Principales Références
La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).
Copyright
Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.
Traduction
Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.
calculé en 0,032s