Diskuze: Úloha čínský mobil

V předchozím kvízu, Test znalostí C# .NET online, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Martin Studna

Člen

Martin Studna:28.5.2016 6:30

prosím vás, potřeboval bych poradit s touto úlohou:

Na 50 klavesách (čínskeho) mobilního telefonu ma být rozloženo 2000 znaků (písmen) v pevně daném pořadí (podle abecedy). Písmeno, které je na nějake klávese uvedeno jako k-té, se zapíše k stisky této klávesy. Přitom víte, jak často se které písmeno používá (třeba jako pravděpodobnost nebo jako počet výskytů písmene v průměrné zprávě). Program má určit, na které klávese budou která písmena, aby k napsání průměrné zprávy byl potřeba nejmenší možný počet stisků.

Na vstupu váš program dostane:
počet kláves
počet znaků, které je nutno rozdělit
seznam četností jednotlivých znaků v průměrné zprávě.

Na výstup program vypíše vážený součet všech četností znaků.

Příklad:
3 //počet kláves
5 //počet znaků
1 //četnost prvního znaku
1 //četnost druhého znaku
1 //četnost třetího znaku
1 //četnost čtvrtého znaku
1 //četnost pátého znaku

Výstup:
Jedním z řešení je rozložit znaky následovně:
1 2 | 3 4 | 5
Pro první klávesu vypadá vážený součet takto:
1*1 + 2*1 = 3
Pro druhou:
1*1 + 2*1 = 3
Pro třetí:
1*1 = 1
Celkový výstup je tedy: 3+3+1=7
Program na výstup vypíše číslo: 7

S tím, že řešení jsem nasel tohle, ale uplně mi není jasný

Značíme-li počet kláves jako K a počet znaků jako S, jsou hlavní ideje řešení následující:

použijeme tabulku velikosti K x S(K řádků a S sloupců)
buňka na pozici [i,j] obsahuje údaj o optimální ceně pro podúlohu, kdy bereme symboly pouze po j-tý znak dělíme je na i tlačítek
první řádek snadno vyplníme - jde o úlohu, kdy dáváme všechny symboly až po j-tý na jedno tlačítko
každý další řádek vyplňujeme s použitím hodnot z předchozího řádku. Zkoumáme vlastně jak rozšířit optimální řešení pro i tlačítek o další tlačítko. Ze všech možných způsobů jak to lze udělat přitom vybíráme ten nejlevnější.
můžeme si předem předpočítat tabulku velikosti S x S cen všech možných tlačítek, ve které buňka [i,j] obsahuje cenu tlačítka, které začíná i-tým symbolem a končí j-tým

Odpovědět

28.5.2016 6:30

Martin Studna

Člen

Martin Studna:28.5.2016 6:33

Pokud chápu dobře, tak na první řádek (první tlačítko) dám ty četnosti jednotlivých znaků ... ale úplně nechápu, jak pokračuju dál, a kde najdu výsledek.

Editováno 28.5.2016 6:34

Nahoru Odpovědět

28.5.2016 6:33

coells

Tvůrce

coells:28.5.2016 12:25

Tomuhle postupu se říká dynamické programování a z algoritmu se obvykle chápe hodně špatně.
Je to otočení rekurzivního postupu, kdy bys zkoušel dát písmeno na tlačítko a zkoušel podproblémy.
Rekurze je v tomhle případě sice snadno pochopitelná, ale neefektivní.
Jestli jsi dynamické programování ještě nepoužíval, tak radši začni něčím jednodušším, od Fibonacciho čísel až po hledání vzdálenosti dvou řetězců.

Výsledek najdeš v posledním vyplněném řádku pod posledním písmenem, pokud S>K, tak na pozici [K, S].
Rozložení klávesnice se získá zpětnou rekonstrukcí z tabulky.

Nahoru Odpovědět

28.5.2016 12:25

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 3 zpráv z 3.