Binárne reťazce

Ahoj Barboro,

asi by se na to dalo jít obyčejnou kombinatorikou...

Nevim co všechno musí splňovat binární řetězec, ale budu předpokládat, že může začínat nulou.

příklad 1) právě tři nuly. čili potřebujeme zjistit, kolika způsoby lze vybrat tři pozice z 10. To je kombinace třetí třídy z deseti. Nebo taky 10 nad 3.

Příklad 2) teď narychlo nevim, ale asi bych se zamyslel nad tím, jak to má vypadat., že by kolem každé nuly měly být jedničky. Takže budeš mít takové podřetězce délky 3, které budou vypadat 101. Akorát když t nula bude na kraji, tak to bude jinak. no a pak si potřebuješ rozmyslet, kolika způsoby tyhle podřetězce můžeš poskládat.

Příkald 3) tam bych si to asi rozdělil podle počtu nul které se tam budou vyskytovat. 0 nul: 1 řetězec 1 nula: 10 řetězců 2 nuly: nevim kolik... musí se to vymyslet :-).

Možná, že na to existuje úplně jiný aparát, který neznám. Třeba bude vědět Tomáš :-).

Dobrý deň,ďakujem Vám.

Mohla by som tú dvojku riešiť prosím aj tak, že tie 3 nuly vezmem za jeden prvok, ktorý môžem umiestniť na 8 pozícií a tým pádom aj reťazcov bude 8?

Prosím Vás a dala by sa tá možnosť ´´v kóde nie sú žiadne dve nuly vedľa seba´´ počítať tak,že od všetkých možností odpočítam tie, v ktorých sú aspoň 3 nuly vedľa seba ? Neviem, či to je správne,to mi len napadlo.

Ďakujem.

Vygeneruju všechny řetězce o délce n-1 a jejich počet označím F(n-1).

n-1: xx..xx

Potom řetězce o délce n zkonstruuju z řetězců o délce n-1 tak, že buď připojím na konec 1 (bez omezení) nebo 0 (pokud končí znakem 1).

n: xx..xx1 xx..x10

Protože jsou obě množiny (...xx1, ...x10) disjunktní, tak můžu použít pravidlo kombinatorického součtu a využít toho, že znám počty kratších řetězců: F(n) = F(n-1) + F(n-2)