Una sequenza di bit si dice quadrata quando è data dalla concatenazione di due sequenze uguali, ad es.:
00,11, 0101, 000000,...
sono tutte quadrate.
Generare sequenze quadrate non è difficile. Provate invece a dare un algoritmo che dato N genera una sequenza di N bit che non contiene sottosequenze quadrate di lunghezza strettamente maggiore di 2 (quindi può contenere 11 e 00), dimostrando in questo modo anche la sua esistenza. Ad esempio, per N = 5, 01001 è un output valido mentre 01011 non lo è perchè contiene 0101 che è quadrata.
Qual è la migliore complessità sia in tempo che spazio che riuscite a raggiungere con il vostro algoritmo?
Una particolare sequenza di bit
Il problema l'ho formulato in una maniera che un pò confonde, perchè
il fatto è che esiste almeno una sequenza infinita di bit libera da quadrati, cosa però non evidente. Il problema vero è trovare una procedura che la genera un bit alla volta, dopodichè ne deriva una soluzione del problema di sopra che ha tempo lineare e spazio costante.
il fatto è che esiste almeno una sequenza infinita di bit libera da quadrati, cosa però non evidente. Il problema vero è trovare una procedura che la genera un bit alla volta, dopodichè ne deriva una soluzione del problema di sopra che ha tempo lineare e spazio costante.
Si, in realtà è più difficile di quanto pensassi! Avevo letto su un libro di algoritmi quella che credevo una soluzione elegante, ma mi sono reso conto che c'è un' incompletezza, e che la soluzione vera è in realta più complessa.
Comunque chi vuol sapere come costruire una sequenza infinita square-free può provare a fare una ricerca in rete sulle Thue-Morse words , un argomento che in realtà è combinatoria e ha poco legame con l'algoritmica in senso stretto.
Comunque chi vuol sapere come costruire una sequenza infinita square-free può provare a fare una ricerca in rete sulle Thue-Morse words , un argomento che in realtà è combinatoria e ha poco legame con l'algoritmica in senso stretto.
Re: Una particolare sequenza di bit
Riesumo per dire che o c'ho un bug o il testo era sbagliato o l'ho letto male...
Perchè con l'ausilio di potenti mezzi dovrei aver trovato tutte le stringhe di cui parla il testo... e in particolare la più lunga è lunga 18 caratteri!
Per gli interessati questo è il codice (c++) (con qualche giochetto idiota con i bit perchè pensavo che dovessi rendere il tutto veloce mentre invece vista la finitezza delle stringhe ciò non serviva! )
Perchè con l'ausilio di potenti mezzi dovrei aver trovato tutte le stringhe di cui parla il testo... e in particolare la più lunga è lunga 18 caratteri!
Per gli interessati questo è il codice (c++) (con qualche giochetto idiota con i bit perchè pensavo che dovessi rendere il tutto veloce mentre invece vista la finitezza delle stringhe ciò non serviva! )
Codice: Seleziona tutto
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int k=18;
vector <int> belle[k+1];
bool test(int N,int bit){
for(int l=2;l<=N/2;l++){
if( (bit & ((1<<l)-1) )== ( (bit>>l) & ((1<<l)-1) ) )return false;
}
return true;
}
void aumenta(int it){
for(int i=0;i<(int)belle[it].size();i++){
if(test(it+1,(belle[it][i]<<1)))belle[it+1].push_back((belle[it][i]<<1));
if(test(it+1,(belle[it][i]<<1)+1))belle[it+1].push_back((belle[it][i]<<1)+1);
}
}
string stampa(int bit,int N){
string res;
for(int i=0;i<N;i++)res+=(bit&(1<<i))?'a':'b';
return res;
}
int main(){
belle[0].push_back(0);
for(int i=0;i<k;i++){
aumenta(i);
}
for(int i=0;i<(int)belle[k].size();i++)cout << stampa(belle[k][i],k) << "\n";
cout << "Totale= " << belle[k].size() << "\n";
for(int i=0;i<=k;i++)cout << i << ": " << belle[i].size() << "\n";
}
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai