Matematické Fórum

Zdravím,

prosím Vás, potřeboval poradit s touto úlohou.

Předem děkuji za každou radu.



Zadání:
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ě. Není mi úplně jasný, jak mám napsat ty operace, pomocí kterých dostanu přesně výsledky, které jsou v tabulce.

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

Našel jsem tohle řešení:

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



Pro tento případ jsem vytvořil tabulku SxS s těmito hodnotami

1 3 6 10 15
0 1 3  6  10
0 0 1  3   6
0 0 0  1   3
0 0 0  0   1

a Tabulku KxS

1 3 6 10 15
0 2 4  6   9
0 0 3  5   7

Vím jak sestavit tabulku, ale úplně si nejsem jistý, jak to mám naprogramovat. Úplně mi není jasné, jaké operace mám naprogramovat, abych dostal přesně ty stejné výsledky v tabulce.