Newsgroup: it.hobby.enigmi
Titolo: apalindromia

Chiamiamo grado di apalindromia il numero minimo di caratteri che misogna
togliere ad una stringa per renderla palindroma.
se x e` palindroma ovviamente  ap(x) = 0
ap("ciccio")=2 perche` _icci_ e` palindroma.
Se prendiamo le espansioni binarie dei naturali, "0", "1", "10" con un
massimo di 8 bit, qual e' il grado di apalindromia media? Quante sono le
stringhe *quasi* palindrome (ap=1)?
Ciao, Silv:o)

Rispondo solo alla seconda domanda, alla prima ci pensero' meglio.
Direi che le stringhe di n bit palindrome sono 2^(n/2) se n e' pari e
se n e' dispari sono 2^((n+1)/2).
Quindi abbiamo (2+4+8+16)*2=60 stringhe palindrome nel caso in cui si vada
fino
a n=8, considerando come nell'esposto
0 diverso da 000 per esempio.
Ora da una stringa di n bit palindroma ne posso ottenere n+1 il cui ap(x)=1.
Esempio dalla struinga "0" ottengo "10" e "01", per cui il numero
degli x tali che ap(x) = 1 e' = 2*2+2*3+4*4+4*5+8*6+8*7+16*8+16*9=422
dove il primo termine e' il numero di stringhe palindrome con n = 1,2,3 etc.,
moltiplicato per n+1.
Semper che non abbia sbagliato calcoli o metodo!
Ciao
Andrea


Mi sembra che, nelle costruzioni delle n+1 stringhe a partire da
quelle palindrome lunghe n, tu non abbia considerato le ripetizioni e
le stringhe che si formano ma che hanno ap(x) = 0: ad es.
per n=2 le stringhe palindrome sono 00 e 11; i tuoi calcoli mi dicono
che ci sono 2*3=6 stringhe x lunghe 3 tali che ap(x) = 1, ma
risultano 100 001 011 110.
ciao
Adriano


 massimo di 8 bit
Mettiamoci d'accordo. Io intendevo non permettere gli zeri a sinistra, ma
non l'ho spiegato con la dovuta chiarezza. In fondo mi interessa sapere se
ci sono metodi meno stupidi di quello che ho usato io (ho calcolato ap(x)
caso per caso, con tutte le insidie del paper&pencil), quindi credo sia piu'
semplice permetterli, e considerare stringhe di lunghezza fissa, 8 nel
nostro caso.
Ciao, Silv:o)

risultano 100 001 011 110.
Ecco cosa succede a postare alle 8 e mezzo della mattina!
Hai perfettamente ragione, ok, come non detto ritiro tutto, a parte
il numero degli ap(0) :-)
Mi sembra meglio contare il numero degli ap(0) (noto) e ap(2) etc,
e calcolare il numero degli ap(1) per sottrazione.
Ad esempio n= 4 ap(0) = 4 ap(2) =2, in tutto essendo 16 le combinazioni
possibili
risulta che ap(1) = 10 per n=4. Per generalizzare il tutto con un
procedimanto logico
ci pensero'!
Ciao
Andrea
--
Posted from [212.17.205.1] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 ha scritto nel messaggio
news:alCXqGx9$GA....@news-02.uni.net...

Per le stringhe di 8 bit il max grado di apalindromia puo' essere 4 (e in
genere per le stringhe di 2n bit puo' essere al max. n)
Inoltre ho osservato (salvo errori) che:
il grado di apalindromia e' pari  se la ripartizione delle cifre zero ed uno
e' 4-4 6-2  o 8-0
e' dispari se la ripartizione e' 5-3 o 7-1
Non so se queste proprieta' possano essere utili, per il momento non ho
trovato altro
ciao
paolo

 trovato altro
Riepilogando, per le stringhe di 8 bit:
stringhe totali 2^8=256
ripartizioni di "1" e "0"
7-1      8 stringhe  tutte ap=1
1-7      8 stringhe  idem
5-3     56 stringhe  di cui x ap=3 e 56-x ap=1
3-5     56 stringhe  idem
altre  128 stringhe  nessun ap=1
il problema diventa trovare x senza ricorrere alla forza bruta, e
possibilmente generalizzare per stringhe di n bit
ciao
paolo