Perles de Dijkstra

Les Perles de Dijkstra sont un problème de backtracking en programmation énoncé par Edsger Dijkstra dans les Communications of the ACM au début des années 1970[réf. nécessaire].

L'intérêt du problème vient du fait qu'il est difficile de le programmer sans instruction goto[1], mais que si on le programme avec une telle instruction, on a de fortes chances aussi de se tromper, et de rendre le programme très dur à corriger.

Il a donné lieu aussi à des développements mathématiques simples.

Le problème

Soit un fil sur lequel on désire enfiler des perles de trois couleurs. Dijkstra propose bleu, blanc et rouge, couleurs du drapeau néerlandais, mais on peut dans une formulation plus neutre les nommer 0, 1 et 2.

Une seule contrainte existe : il ne doit pas y avoir sur le fil deux séquences adjacentes identiques.

Questions :

  • Combien de perles peut-on ainsi enfiler ?
  • Écrire l'algorithme qui réalise la plus longue séquence possible, ou le cas échéant celui qui pourra continuer indéfiniment.
Other Languages