Bonjour,

je révise pour un contrôle et il y a un exo sans correction que je n'arrive pas à faire. Je vous mets l’énoncé :

Problème :

On considère l'ensemble A = {1,2,....,n}. Un sous-ensemble non-vide S de A est Safe si et seulement si il n'y a pas deux entiers x et y dans S tels que abs(x-y) = 1. (abs = valeur absolue). par exemple si n = 5, alors les sous ensembles {1,3,5}, {2,5}, {4} sont safe, tandis que {1,3,4} n'est pas safe car abs(3-4)=1.

Travail demandé :

Écrire un algorithme efficace SAF (O(n) en temps et espace) qui renvoie le nombre de sous ensemble safe de A. Par exemple, si n= 5 alors SAF(5) = 12 (car les sous-ensembles de A sont {1}, {2}, {3}, {4}, {5}, {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5} et {1,3,5}. Justifier la correction de votre algorithme et calculer formellement sa complexité en temps et en espace. On suppose que toute opération arithmétique et logique est en O(1).
Je pense que mon programme doit trouver tous les sous-ensembles et calculer si abs(x-y) = -1, mais je ne vois pas comment faire cela.

Merci de votre aide.