Newsgroup: it.comp.lang.visual-basic
Titolo: consigli su algoritmo

Ciao a tutti.
Immaginate una matrice bidimensionale fatta di caratteri.
dovete ricercare una stringa (di caratteri) all'interno di questa matrice.
la stringa assume qualsiasi direzione e verso, per cui la si può ricercare
da sinistra verso destra, dall'alto verso il basso, in obliquo... insomma in
ogni modo...
Qualche suggerimento?
Grazie :)
Max

"Max" <m@a.x> ha scritto nel messaggio news:40b1...@x-privat.org...

Flood-filling ricorsivo.
Solo che esci quando la stringa non coincide e tieni conto della direzione.


una cosa tipo quel gioco delle riviste di enigmistica?
ciaociao

 obliquo... insomma in ogni modo...
Problemi con la settimana enigmistica?? :-)
MIk

Rispondo a chi mi chiede se ho problemi con la settimana enigmistica...
a mano nessun problema :)
volevo informatizzarlo e volevo trovare un modo un po' intelligente, cmq si
tratta proprio del crucipuzzle :)
Max

 Solo che esci quando la stringa non coincide e tieni conto della
direzione.
flood-filling? se magna?  :)
scherzi a parte, non ho trovato niente a riguardo, eccetto ovviamente quello
che riguarda il flood-fill grafico...
Max

"Max" <m@a.x> ha scritto nel messaggio news:40b2...@x-privat.org...

Lascia, ho la sensazione d'aver detto una minchiata :-)
(ci sono metodi piu' efficenti)

 Max
ciaociao

> Qualche suggerimento?
Si, quello che utilizzo io al crucipuzzle: cerco in tutta la matrice la 
prima lettera della parola da cercare, e allora (una volta trovata) 
cerco se nei dintorni c'è il resto della parola.
Per cercare in orizzontale c'è instr, che procede però solo verso avanti.
Potresti costruirti la tua funzione instr che, dato un riferimento della 
matrice, il limite orizzontale e verticale, e la parola da cercare in 
équel* punto (quello in cui trovi la lettera) vada a controllarsi 
*l'intorno completo* (auhauhauha matematica) per vedere se esiste la parola.
Forse per velocizzare l'algoritmo potresti, dopo aver ottenuto l'intera 
matrice iniziale, espandere su righe orizzontali anche le verticali e le 
obblique...
A B C D
D D A C
I E E E
E A D C
Diventerebbe
A B C D
D D A C
I E E E
E A D C
A D I E
B D E A
C A E D
D C E C
(ho aggiunto le sequenze verticali in orizzontale)
e poi ancora
A B C D
D D A C
I E E E
E A D C
A D I E
B D E A
C A E D
D C E C
A D E C
B A E
C C
D E D
I A
Ho aggiunto le oblique (da dx vs sx)
e fare lo stesso con le altre oblique, in modo da ottenere 
l'orizzontalizzazione di tutta la matrice e ricomporla come un elenco di 
stringhe, così da velocizzare la ricerca...
Ma ora scappo che sono in ritardo a lavoro!!!!
-- 
Rivolterò il mondo per trovarlo, e anche se andasse in Indocina uno dei 
nostri starà nascosto in una ciotola di riso pronto a sparargli nel culo.
(Pulp Fiction)

per queste cose ci vorrebbe il termoPilucco...
Eccomi :)
Il problema mi solletica, però non ho tempo di pensare... sono preso dalle mie
divisioni con resto negativo :)
Esempio?
100/10=11?
verifichiamo
11*10=110
100-110=-10 --> resto negativo
-10/10=-1
11+(-1)=10 
verifichiamo
10*10=100 --> bingo :)
Credo che con questo risolverò i problemi dell'umanità :P
termoPilucco, matto, forse.

> termoPilucco, matto, forse.
Toglierei il forse... :-P
Però mi piace la pensata di dimostrare le divisioni in questo modo....
bye
-- 
Esistono 10 tipi di persone: chi conosce il binario e chi no.
Gestione Ottica - Gestionale per Ottici e Programmi Gratuiti su:
http://www.nicolaottomano.it

> 100/10=11?
E chi ti dà questo risultato?


 termoPilucco, matto, forse.
forse?
tu hai bisogno di una donna.... :-D
ciaociao

Ciao,
"Max" scrive:

per semplificare l'algoritmo direi che dovresti lavorate sulla stringa e
l'inverso della stessa, questo ti permette di limitare il TIPO (non il
numero) di operazioni di ricerca in avanti, basso, obliquo destra basso,
obliquo sinistra basso.
beppe

 E chi ti dà questo risultato?
è una prima approssimazione.
La ottengo per mancanza di conoscenza di tutte le cifre esatte del
divisore e del dividendo.
In pratica, la classe di numeri a precisione arbitraria che ho scritto,
permette di fare facilmente moltiplicazioni di numeri di qualsivoglia
cifre, ma si trova in difficoltà ad eseguire le divisioni.
Quindi anzichè dividere A e B (con A e B numeri grandissimi) divido una
piccola parte di A con una piccola parte di B e poi aggiusto tutto man
mano che procedo utilizzando la verifica (moltiplicazione, che riesce
bene) e i resti negativi (o positivi, se capitano).
termoPilucco, chiaro no?
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 tu hai bisogno di una donna.... :-D
Donna?
Ho premuto F1 ma la guida non dice nulla :(
Forse stanotte provo con Google, chissa'...
termoPilucco


 
Meglio google Images! ;-)
	maxx
-- 
NOSPAM: Rimuovere i trattini dallo username!
Cut hyphens from my username!

 obliquo sinistra basso.
Sto seguendo il tuo consiglio e ho già implementato la ricerca dx, sx, su,
giù e obliquo verso destra.
In pratica prendo tutta una riga di caratteri e verifico con la parola e il
suo inverso...
Grazie per l'help.
Max

> termoPilucco, chiaro no?
Come Micheal Jackson :D


 capitano).
non so se hai gia' questa passione, ma ti consiglio di buttarti sul mondo
dell'obfuscated code e della crittazione ... secondo me ci sei molto portato
^_^
PS: alle superiori a matematica avevi 8 vero ?
-- 
<Gigio2K>
--- 
http://www.g2kweb.it/gigio2k
 ---
Nokia -> I.T.H.N. -> 
http://www.ithn.it/
VB -> I.C.L.VB -> 
http://www.it-lang-vb.net/

 PS: alle superiori a matematica avevi 8 vero ?
I miei voti variavano anno per anno (cambiato prof. quattro volte). E 8
non è stato predominante, il cazzeggio al pomeriggio si'...
In compenso ho avuto un 30 in "calcolo della probabilita' e statistica" :)
Comunque tornando al topic iniziale, forse mi sta venendo in mente
qualcosa di veloce... ci penserò su.
termoPilucco


 qualcosa di veloce... ci penserò su.
( sti secchioni... :pppppp )
Ti invidio : calcolo alle superiori : 4 fisso. (sara' per quello che al
lotto non vinco mai ? )
-- 
-Gigio@Work(?)-

 lotto non vinco mai ? )
Eh... prima e unica legge del lotto: i numeri non hanno memoria (come
potrebbero delle palline ricordarsi che sono X settimane che non escono?
E, nel caso si ricordassero, come potrebbero convincere la mano ad
afferrarle?).
Quindi qualsiasi ragionamento sui numeri estratti precedentemente non
aumenta ne' diminuisce le probabilità di vincere.
Il 99% della persone crede il contrario per via la "legge dei grandi
numeri": 
1) ogni numero prima o poi uscirà tante volte quanto gli altri, 
2) quindi se un numero è in ritardo ha maggiori possibilità di uscire.
Vera la prima, falsa la seconda, perchè la tendenza è vera solo
all'infinito. Supponendo infinite estrazioni, usciranno infinite volte
tutti i numeri in percentuali uguali.
Il che rende trascurabile il contributo delle estrazioni del passato.
termoPilucco, dov'ero rimasto?


 qualcosa di veloce... ci penserò su.
Dimmi a cosa stai pensando e ti dirò se è lo stesso che sto pensando io...


Dimmi a cosa stai pensando e ti dirò se è lo stesso che sto pensando io...
Boh, pensavo di usare dei crc o hash delle parole, molto più veloci da
confrontare rispetto alle parole stesse.
Magari implementando il confronto con un albero binario bilanciato... però è
tutto ancora da ponderare bene...
termoPilucco

Oggi ho parlato col mio prof.di Analisi Matematica (Politecnico di Milano) e
gli ho posto il problema di velocizzare le divisioni.
Io per ora ho elaborato un procedimento di fattorizzazione del denominatore
molto grande, ma non è eccessivamente veloce... Potrei velocizzarlo di molto
ma perderei di precisione.
Il prof mi ha proposto di usare Taylor o le serie Geometriche.
Non so che precisione possano dare (anzi, lo so, ma non saprei a che
precisione arrivare con i PC attuali).
Tu come hai implementato le divisioni? Mi daresti uno schema del
ragionamento che hai fatto (vorrei proporlo al prof)?


ragionamento che hai fatto (vorrei proporlo al prof)?
Ho implementato due metodi *osceni* e ne ho teorizzato un terzo, non ancora
implementato.
La mia classe si basa su una rappresentazione interna del numero sotto forma di
stringa per la mantissa, enum per il segno e long per il numero delle cifre
decimali.
Es: 15,7:      "157", più , 1 (una cifra decimale)
Es: -1323325,43347:      "132332543347", meno , 5 (cinque cifre decimali)
Il vantaggio è che posso moltiplicare o dividere per 10, 100, 1000, spostando la
posizione del decimale e/o aggiungendo zeri a destra della mantissa.
L'altro vantaggio è che la stringa può contenere 2 miliardi di cifre, se
qualcuno ha voglia di scriverle/leggerle.
Metodo1 per la divisione (*osceno*)
N=numeratore
D=divisore
moltiplico il numeratore o il divisore per 10 finchè i due numeri non hanno la
stessa quantità di cifre.
Se N<=D, moltiplico ulteriormente N per 10.
In questo modo ho la certezza che il risultato è della forma k,abcdef..., con k
compreso tra 1 e 9.
a questo punto comincio per tentativi!
provo k=1
se k*D=N il risultato è 1
se k*D<N il risultato è > 1 quindi pongo k=2
se (k-1)*D<N e k*D>N significa che k-1 è la prima cifra del risultato (da poco
sono passato a troppo).
Quindi continuo iterando per tentativi sulla seconda cifra. E così via.
Svantaggio enorme: fino a 9 tentativi (ovvero moltiplicazioni a cifre
arbitrarie) per ogni cifra trovata.
Vantaggio: so esattamente quante cifre corrette ho trovato.
Metodo2 (*oscenissimo*)
vado per tentativi anche in questo caso, ma usando il metodo dicotomico.
Il risultato è 1? no  è maggiore, provo 2 (raddoppio). E' minore di 2? provo 1,5
(fra 1 e 2) e così via.
Svantaggi: tutti.
Vantaggio: facile da implementare.
Il terzo metodo più o meno è come il primo, solo che invece di andare per
tentativi cerca di sfruttare la divisione hardware dei processori (che funziona
egregiamente su numeri interi piccoli). Per fare ciò devo comunque verificare
ogni risultato con la moltiplicazione a precisione arbitraria per determinare il
nuovo resto (positivo o negativo che sia).
Vantaggio: dovrei riuscire ad ottenere 4 cifre e passa a botta... quindi i tempi
di risposta dovrebbero divenire accettabili.
Il bello della classe è che ogni operatore si basa su altri: se riesco a
velocizzare la somma, velocizzo anche la moltiplicazione, a sua volta la
divisione, a sua volta la radice quadrata e il calcolo di PI-Greco. 
'na pacchia insomma :)
termoPilucco

Ho studiato i tuoi metodi e credo che differiscano leggermente dal mio.
Ora sto provando a fare un "merge" delle tue teorie con le mie... chissà che
non venga fuori qualcosa di carino.
Ti faccio sapere non appena mi viene in mente qualcosa.
