index de tableau de comptage

Question

Si j'ai un tableau de nombres comme [5, 2, 3, 2, 0, 2]

Je veux compter le nombre de fois où je peux l'indice continue du tableau jusqu'à ce que nous arrivons à un index que nous avons déjà visité, comme ceci:

A[0] = 5 
A[5] = 2 
A[2] = 3 
A[3] = 2 stop here because we already indexed 2. 

donc mon problème est: sans utiliser la structure de données supplémentaires pour stocker les indices, est-il un moyen déjà visité, je peux dire à mon programme quand arrêter l'indexation?

Answer 1

Il apparaît que vous traitez ce tableau comme un graphe orienté. Si c'est le cas, ce que vous demandez vraiment, c'est comment détecter les cycles dans un graphe orienté.

Voir:

• Best algorithm for detecting cycles in a directed graph
• Find all paths with cycles in directed graph, given the source vertex
• How to detect if a directed graph is cyclic?

Pour répondre précisément à votre question si: Si vous erraient dans un labyrinthe, comment voulez-vous dire si vous Avons-nous été à une jonction particulière avant? Vous pourriez envisager de laisser tomber la chapelure ou de dérouler un fil pour vous rappeler où vous avez été. C'est la même chose ici. Vous devez soit annoter votre tableau d'origine avec un indicateur "visité", soit conserver une copie des index que vous avez visités dans votre propre tableau.

Answer 2

Si vous commencez avec vos éléments de tableau initialisés à une valeur non valide, dites -1, alors vous pouvez arrêter si un élément de tableau a déjà été attribué, comme dans le pseudo-code suivant:

if (A[x] == -1) 
    A[x] = y 
else 
    stop