OT algoritmicka hadanka

Pavel Troller patrol@sinus.cz
Pondělí Červen 15 14:09:03 CEST 2009


> Ako az zlozity?
> 
> Uloha sice je myslena ako programatorska, s beznymi prostriedkami ktore sa daju najst v procesoroch; ale pokojne to mozeme pochopit aj ako ulohu na optimalizovanu logiku - aplikacia je sice v oboch pripadoch zriedkava, ale moze sa taka najst (nakoniec ta uloha je realna od mojho kolegu).
> 
> wek
> 
Zdar,
  napada mne (nechce se mi to ted kodovat, tak jen slovni popis algoritmu):
  - zacit s maskou s pulkou bitu 1 a pulkou 0 (napr. 0x00ff pro 16bit 
    promennou)
  - otestovat, zda AND promenne s maskou je nenulovy a AND s negaci masky 0
    nebo obracene (neplati-li, odchod)
  - dle vysledku upravit masku (predpokladejme, ze platila prvni kombinace,
    takze ted bude maska jen 0x000f)
  - Opet provest tentyz test - tentokrate napr. vyjde druhy pripad, tj.
    v dalsi iteraci bude maska 00c0 
  - Tento test byl pozitivni v prvnim pripade, takze zkousime 0040
  - V zaverecnem testu proverime, zda to to plati a jsme hotovi.
  Pokud budeme v pomocne promenne scitat vahy 8,4,2,1 nebo 0 podle toho, jak
  vyjde test, jako vedlejsi produkt ziskame cislo nenuloveho bitu.
  Tento algoritmus by mel jit implementovat v cyklu o poctu kroku rovnem
log2 velikosti promenne.

    S pozdravem Pavel Troller



Další informace o konferenci Hw-list