Nové výhodné předplatné namísto kreditů je tu! Více informací. Upravili jsme také naše provozní podmínky.
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:

Diskuze: Algoritmus změna jednoho slova za druhé

Aktivity
Avatar
Petr Malý
Člen
Avatar
Petr Malý:4.8.2019 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.8.2019 12:41
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petr Malý
DarkCoder:4.8.2019 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.8.2019 13:28
Jazyk C je jako formule. Můžete předjíždět ve 300 km/h. Každá drobná chyba vás ale nekompromisně pošle do zdi.
Avatar
Lukáš Křehula
Tvůrce
Avatar
Odpovídá na Petr Malý
Lukáš Křehula:5.8.2019 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.8.2019 8:57
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:5.8.2019 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.8.2019 9:24
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Peter Mlich
Peter Mlich:5.8.2019 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.8.2019 9:26
Avatar
ZemiakSK
Člen
Avatar
ZemiakSK:7.8.2019 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.8.2019 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.