[Algo] Stampa stringhe binarie

[Pablitos23]

Dare lo pseudocodice di un algoritmo che dato l'intero n, stampa tutte le stringhe binarie lunghe n in cui non compaiono mai uni consecutivi.

Qua ho utilizzato la tecnica del BackTracking.

StampaStr(n:lunghezza, h:index, S:array della stringa)
   if n==h then
      OUTPUT S
   else
      for i=1 to n do
         for y in {0,1} do
             if (isSafe(S,h+1)) then
                  S[h+1] = y
                  StampaStr(n,h+1,S)

isSafe(S,h) -> boolean
   boolean f = true
   if (h>1 and (S[h-] == 1 or (h<n and S[h+1] == 1 ) ) ) then f = false

   return f

La complessità è pari a O(nS(n)), con S(n) pari a $4^n$, ovvero la generazione di tutte le possibili disposizioni con ripetizioni di 4 elementi che possono assumere 2 valori.

Può andare?

Grazie

[vict85]

Siccome una volta introdotto un \(\displaystyle 1 \) il valore seguente è uno \(\displaystyle 0 \) allora il numero di elementi di quella forma è nell'ordine dei \(\displaystyle 2^{\frac{n}{2}} \). Il tuo \(\displaystyle n4^n \) mi sembra quindi decisamente troppo grande (forse anche sbagliato, non ho controllato ma forse confondi un \(\displaystyle 2\cdot 2^n \) con un \(\displaystyle 4^n = 2^n\cdot 2^n \) ).

Se \(\displaystyle n \) è inferiore o uguale a \(\displaystyle 63 \) allora potresti anche semplicemente generare tutti i numeri tra \(\displaystyle 0 \) e \(\displaystyle 2^{n}-1 \) e "convertirli" in una stringa binaria qualora si abbia x & (x >> 1) uguale a \(\displaystyle 0 \). Questo ha una complessità di \(\displaystyle 2^n \) (il convertire il numero in una stringa binaria ha complessità n ma lo si fa solo su \(\displaystyle 2^{\frac{n}{2}} \) e \(\displaystyle n2^{\frac{n}{2}} \) è asintoticamente più piccolo di \(\displaystyle 2^n \)).

Un algoritmo con complessità ottimale è possibile in quanto basta generare direttamente stringhe binarie con la proprietà cercata.

[Pablitos23]

Capito grazie anche se ho appena visto che il mio pseudocodice è leggermente sbagliato. Non rispetta bene i vincoli con isSafe.