Geek tričko zdarma Geek tričko zdarma
Tričko zdarma! Stačí před dobitím bodů použít kód TRIKO15. Více informací zde

Diskuze: Algoritmus změna jednoho slova za druhé

Aktivity (2)
Avatar
Petr Malý
Člen
Avatar
Petr Malý:4. srpna 12:41

Ahojte, chtěl bych se zeptat, zda byste mi mohli pomoci s jedním algoritmem, který mi už dlouho vypí v hlavě. Zkoušel jsem to prvně vyřešit sám, ale nemám s algoritmizací velké zkušenosti a pak bych vás chtěl poprosit o radu.
Jde o to, že mi uživatel zadá dvě slova a cílem je ze slova A udělat slovo B pomocí operací "přidej písmeno, odeber písmeno a nahraď písmeno".
Program poté vypíše minimální počet operací, které musel podniknout.
Dám příklad. Slovo A = "ast" a slovo B = "test"
Program tedy nahradí prvně nahradí písmeno "a" za "t" a pak za něj přidá písmeno "e". Program tedy vypíše, že za potřebí byly potřeba dvě operace.
Za jakékoli rady děkuji :-)

Zkusil jsem: Vyřešit to pomocí rekurze.

Chci docílit: viz. výše

 
Odpovědět 4. srpna 12:41
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petr Malý
DarkCoder:4. srpna 13:28

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.

  • první řetězec je kratší než druhý
  • první řetězec je delší než druhý
  • oba řetězce jsou stejně dlouhé

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í.

Nahoru Odpovědět 4. srpna 13:28
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Avatar
Lukáš Křehula
Redaktor
Avatar
Odpovídá na Petr Malý
Lukáš Křehula:5. srpna 8:57

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.

 
Nahoru Odpovědět 5. srpna 8:57
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:5. srpna 9:24

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.

 
Nahoru Odpovědět 5. srpna 9:24
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Peter Mlich
Peter Mlich:5. srpna 9:26

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.

 
Nahoru Odpovědět 5. srpna 9:26
Avatar
ZemiakSK
Člen
Avatar
ZemiakSK:7. srpna 0:09

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

  • saturn
  • sturn
  • strn // tu máme najdlhší podreťazec aky sa da ziskať
  • stro
  • strov
  • ostrov

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

  • ohodnoť si kroky

Nahradenie je vždy výhodnejšie ako odobratie a pridanie

 
Nahoru Odpovědět 7. srpna 0:09
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.