Diskuze: Algoritmus změna jednoho slova za druhé
Zobrazeno 6 zpráv z 6.
To co uvádíš je spíše takové "hraní si" s algoritmizací. Smyslem toho celého je naučit se práci se znaky a řetězci než to jak by měl algoritmus skutečně fungovat. Je třeba uvědomit si, co vše záměna slova obnáší. Operace přidej, odeber, nahraď totiž nejsou jediné. Při tom jak to popisuješ pracuješ také s operace porovnání. Porovnání plus operace dohromady je pomalé.
Ve tvém případě potřebuješ znát tři stavy týkající se délky řetězce.
V prvním případě nahrazuješ a přidáváš
V druhém případě nahrazuješ a odebíráš
Ve třetím případě pouze nahrazuješ
Všimni si že porovnávání není třeba.
Budu-li brát tvůj případ, kde slovo A je "ast" a slovo B je "test", tak
operace budou následovné:
nahraď, nahraď, nahraď, přidej. Tedy 4 operace.
Počet operací bude roven délce delšího řetězce.
Skutečný algoritmus funguje tak, že najdeš pozici prvního slova a zapíšeš přímo na ni druhé slovo bez jakéhokoli porovnávání.
Ahoj,
zkus se podívat po internetu na Levenshteinovu vzdálenost. Myslím, že je to
to, co hledáš. Určitě najdeš i nějaké příklady pro různé jazyky, ale
to si samozřejmě můžeš vyzkoušet implementovat do Pythonu sám.
Mozna te zajima pocet rozdilnych znaku, pokud od poctu stejnych, ktere jdou po sobe, ne?
A = "ast" a slovo B = "test"
stejne AB = st
rozdilene A = a, B = te
Takze 3 operace?
Teoreticky by melo stacit pismena seradit a pak pismena vyskrtavat. Ale pro tvuj
pripad to mozna nebude pouzitelne, protoze potrebujes konkretni poradi
pismen.
Jinymi slovy, by to mel byt algoritmus pro verzovani textu. Ve verzi A provedes zmeny, vyznac zmeny. Umi to treba TotalCommander, porovnat 2 soubory a vyznacit rozdilne radky.
Jo, a jeste to samozrejme umi asi tisic redakcnich systemu. Treba v pythonu je napsany CMS Plone. Pri uprave nebo zobrazeni stranky se to jmenuje Historie. Odkaz je takovy sedy, nenapadny.
Tu sa uplatni vyhľadávanie podreťazcov
Napríklad v tvojom príklade je spoločným podreťazcom "st"
A program sa bude snažiť tento podreťazec rozšíriť aby nakoniec bol
podreťazec rovnaky ak to čo potrebujeme
Ďalším príkladom je "ostrov" a "saturn"
Spoločné časti sú 's' ,'t' a 'r'
Program vyhodnotí , že odstránením 2 písmen získame podreťazec "str"
A potom už iba doplní alebo vymení podľa potreby
Išlo by to takto
Najprv sme chceli získať najdlhší podreťazec z toho čo máme a potom sme už iba ten podreťazec predlžovali aby sme dostali výsledok
Nahradenie je vždy výhodnejšie ako odobratie a pridanie
Zobrazeno 6 zpráv z 6.