Matematické Fórum

↑ hessyk:
To bude asi nejdříve chtít si sehnat četnost výskytu písmen v psaném textu viz.

a potom ty s největším počtem výskytů dát na tlačítko na první místo (aby stačilo zmáčknout klávesu pouze jednou)

jo cetnost zname...a nevim jak to myslis... o slozitosti nepadla vubec rec...

tak to jsem vubec nepochopil...mohl bzs mi to prosim ukazat na nejakem priklade?

↑ hessyk:

Já možná jen zopakuju jinými slovy postup (případně popíšu obdobný), který popsal ↑ FailED::

Mějme k tlačítek a n písmen

Předvýpočet:

(četnost j-tého tlačítka budu značit w(j) )

Vytvoříme matici s políčky Cij - kde Cij bude cena, kterou nás bude stát vytvořit tlačítko, na kterém budou písmena i, i+1, ... j

Tedy Cij=1*w(i)+2*w(i+1)+3*w(i+2)...+(j-i+1)*w(j)
(když chci první písmeno z klávesy, musím ji zmáčknout jednou, když druhé, dvakrát, třetí třikrát... atd)

Hledání optimálního rozložení:

Budu vyplňovat další tabulku, a sice o rozměrech k x n - kde políčko Sij bude značit "optimální konfigurace i tlačítek taková, že i-té tlačítko končí na j-té klávese" (v políčku bude uložena vždy optimální cena)

První řádek (tedy políčka S1j pro j=1...n) lze zřejmě vyplnit for cyklem - je vždy jen jedna konfigurace, která se k tomu hodí, a ta odpovídá předvypočítaným číslům C1j pro j=1...n.
První políčko druhého řádku pro nás zřejmě nebudemít smysl (nemůžu použít dvě klávesy tak, aby druhá končila prvním písmenem).
Druhé políčko druhého řádku (S22) získám zřejmě tak, že vezmu S11 a přičtu k němu C22 (jinou možnost nemám - lze snadno rozmyslet)
Obecné políčko (tj. takové, kterým nezačíná řádek - rozuměj políčka tvaru Sii) Sij vyplním následovně:

někam si ukládej pomocnou proměnnou min; na začátku nechť je min=nekonečno (MaxInt apod)

(EDIT:chyba v řídící proměnné cyklu, opravena)

Pro m:=(i-1) do (j-1) dělej:

Vezmi S(i-1)m a přičti k němu C(m+1)j //// (oprava z m na m+1)
Je-li tato hodnota menší než min, pak min změn na tuto hodnotu

(konec cyklu)

Ulož min do Sij

(proč to funguje? při tvorbě optimální konfigurace takové, že i-té tlačítko končí j-tým písmenem, využijeme toho, že máme už spočítány optimální konfigurace pro rozložení (i-1) tlačítek tak, že (i-1)-té tlačítko končí písmenem (i-1), i, ... (j-1). K tomu máme spočteno, kolik nás bude ke každé této volbě stát "dodělat" potřebné tlačítko a minimum z těchto možností je optimálním řešením pro rozvržení, kde i-té tlačítko končí j-tým písmenem)

Takto postupně vyplníme celou tabulku. Protože nás zajímá optimum pro k tlačítek, kde k-té tlačítko končí n-tým písmenem, bude hledaná optimální cena rovna hodnotě Skn .

Pokud nás nezajímá jenom cena, ale i konkrétní rozložení, stačí jenom lehce upravit algoritmus - nebudu si pamatovat jenom dosavadní optimální cenu, ale zároveň s ní i políčko z předchozího řádku, kterého jsem pro výpočet tohoto optima využil. Pak stačí projít z Snk na políčko, které si pamatujeme u Snk, z toho políčka na políčko, které si pamatujeme tam atd až na nějaké políčko na prvním řádku. Tato políčka nám udávají, kterým písmenem bude která klávesa při optimálním rozložení končit.

ahoj, tak jsem si myslel ze jsem to pochopil ale nejak mi to nevychazi...mohl bys mi to prosim ukazat na nejakem jednoduchem priklade?treba ze mame a-f a cetnosti jsou 3,4,8,1,7,4 a mame to dat na 3 tlacitka...diky moc

Omlouvam se, ze do toho vstupuju, vsimnul jsem si, ze by melo podle me vyjit spis rozlozeni  a b | c d | e f ktere ma vahu 36, ale nechci do toho rypat :-)

prosimte promin, ale ja porad nechapu jak si prisel na tu tabulku...ty indexy a pak na tu 36..muzes se mi to prosim pokusit nejak vysvetlit?dekuju moc

Ahoj,

dekuju ti za radu, je hezky ze se mi snazite pomoct. Chapu tuhletu cast jak jsi naposled vysvetloval a chapu i vytvoreni te tabulky "C" ale rozhodne nechapu jak tvoris tabulku "S". Nemohl bys mi sem napsat kusy kodu jak vyplnujes tabulku "S" nebo to nejak vysvetlit pro ten priklad co se tu resi. Zkousel jsem si to napsat ale ztratim se na tom ze nevim odkud nakonec nektere hodnoty beres a jak je mozny ze ti vznikne ta hodnota co je zrovna v tabulce.

Predem dekuju ze nejake rady a reakce.

tak mam tu tuhle ulohu:

Na 50 klavesách (čínskeho) mobilního telefonu ma být rozloženo 2000 znaků (písmen) v pevně danem pořadí (podle abecedy). Písmeno, které je na nejake klávese uvedeno jako k-te,
se zapíše k stisky této klávesy. Přitom víte, jak často se které písmeno používa
(třeba jako pravděpodobnost nebo jako počet výskytů písmene v průmerné zpráve).
Program ma určit, na které klávese budou která písmena,
aby k napsáni průmerné 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 rozdelit
seznam četností jednotlivých znaků v průměrné zpravě.

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áteho znaku

Výstup:
Jedno z rešení je rozložit znaky nasledovně:
1 2 | 3 4 | 5
Pro první klávesu vypadá vážený součet takto:
1*1 + 2*1 = 3
Pro druhú:
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


napsal jsem tenhle program:
Program mobil;
var
klavesy,znaky,min,i,konec,j,vysledek:longint;
cetnost,mezery,pomoc:array[0..3000] of longint;

Procedure start;
var i:longint;
Begin
     For i:=0 to znaky do
       BEGIN
        mezery[i]:=1;
        pomoc[i]:=0;
       END;
     pomoc[1]:=0;
     For i:=2 to znaky do
        Begin
             pomoc[i]:=cetnost[i]*2;
        end;
End;

Function minimum:longint;
var i,min:longint;
Begin
     min:=0;
     For i:=1 to znaky do
        If pomoc[i]>0 then
          Begin
             If min>1 then
                Begin;
                      If pomoc[i]<pomoc[min] then min:=i;
                End
             else min:=i;
          End;
     minimum:=min;
end;

Procedure prepocet;
var i,stupen:longint;
begin


For i:=2 to znaky do
        Begin
        If mezery[i-1]=1 then
                Begin
                stupen:=mezery[i-2]+1;
                pomoc[i]:=stupen*cetnost[i];
                j:=i;
                while mezery[j-1]<mezery[j] do
                        Begin
                        stupen:=stupen+1;
                        pomoc[i]:=pomoc[i]+stupen*cetnost[j+1];
                        j:=j+1;
                        end;
                End;
        End;
pomoc[1]:=0;
For i:=2 to znaky do
        If mezery[i-1]>1 then pomoc[i]:=0;
End;

Procedure vypis(pole:array of integer);
var i:longint;
Begin
     For i:=1 to znaky do
        write(pole[i],' ');
     writeln;
End;

Begin
readln(klavesy);
readln(znaky);
For i:=1 to znaky do
    readln(cetnost[i]);
cetnost[znaky+1]:=0;
start;
While znaky-klavesy>0 do
        Begin

        min:=minimum;
        If min>1 then mezery[min-1]:=mezery[min-2]+1 else mezery[min-1]:=2;
        j:=min;
        If min=znaky then konec:=0 else konec:=1;
        While konec=1 do
                Begin

                If mezery[j]>1 then mezery[j]:=mezery[j-1]+1 else konec:=0;
                if j=znaky then konec:=0;
                j:=j+1;
                End;
        prepocet;
        klavesy:=klavesy+1;

        End;
vysledek:=0;
For i:=1 to znaky do
        vysledek:=vysledek+cetnost[i]*mezery[i-1];
writeln(vysledek);
readln;
readln;
End.


porad mi to ale vypisuje spatnou odpoved muzete mi prosim nekdo tedy ukazat jak by mel vypadat spravny program nebo mi prepsat v tom mem programu chybu?nemuzu totiz na nic prijit...dekuju moc