Algoritmus faktoriál graficky

Problém algoritmu jako složitost podmínek.
Problém algoritmu jako složitost podmínek.

Pokud se chcete podívat jak vypadá celá množina faktoriál klikněte sem Množina 6!

Za všechny problematiky si vysvětlíme problém řádku 161 množiny 6!

Řádek 161 jako volba z možností rozsahů pozic.
Řádek 161 jako volba z možností rozsahů pozic. Je to problém obecného řádku “x”.

Lze to také ukázat názorněji. Takže ta samá problematika krok po kroku Fact_6_row161_step_To_step

Vysvětlení podstaty problému algoritmu na množině 5!

Umístění vzorců a syntaxe
Umístění vzorců a syntaxe – lexikální algoritmus
1. řádek A1 = 1, B1 = 2, C1 = 3, D1 = 4, E1 = 5

V prvním řádku jsou pouze číselné hodnoty 1 až 5. Jsou to startovní hodnoty, které pro správnou funkci vzorců musí ležet na naždém MODULO řádku ROW(xxxx)/120 = 0. Tedy na 1. řádku, nebo 121. řádku, 241. řádku a tak dál. Ve druhém řádku jsou vzorce, které se kopírují do úseku řádků 2 – 120. Startovní hodnoty jsou pouze v 1. řádku – nikam jinam se nedávají.

2. řádek buňka A2
{=MAX(IF(COUNTIF(A2:D2;A1:E1)=1;0;A1:E1))}
2. řádek buňka B2
{=IF(MOD(ROW()-(1+0);2)=0;LARGE(IF(COUNTIF(A2:C2;A1:E1)=1;0;A1:E1)2);MAX(IF(COUNTIF(A2:C2;A1:E1)=1;0;A1:E1)))}
2. řádek buňka C2
{=IF(AND(B1=B2;MOD(ROW()-(1+0);FACT(2))<>0)=1;C1;LARGE(IF(COUNTIF(A2:B2;A1:E1)=1;0;A1:E1);3-(MOD(ROW()-(1+0);FACT(3))-MOD(ROW()-(1+0);2))/2))}
2. řádek buňka D2
{=IF(AND(A1=A2;MOD(ROW()-(1+0);FACT(3))<>0)=1;B1;LARGE(IF(COUNTIF(A2:A2;A1:E1)=1;0;A1:E1);4-(MOD(ROW()-(1+0);FACT(4))-MOD(ROW()-(1+0);FACT(3)))/FACT(3)))}
2. řádek buňka E2
{=LARGE(A1:E1;5-(MOD(ROW()-(1+0);FACT(5))-MOD(ROW()-(1+0);FACT(4)))/FACT(4))}

Vzorce jsou provedeny do otevřeného cyklu. Když bychom například kopírovali vzorce přes počet 120, pak se jako 121. řádek vygeneruje řádek 1, 2, 3, 4, 5 – tedy řádek startovní. To samozřejmě nemusí být vždy žádoucí a proto je ke vzorcům zpracován návod. Tedy co se s tím dá dělat. Vzorce fungují v každém typu tabulkového procesoru, pokud tento umí pracovat s maticovými vzorci. Předpokládám,že dnes už to umí všechny tabulkové procesory. Problém by mohly mít starší verze.

Princip lexikálního algoritmu 5!

První pozice (sloupec) : V první pozici se postupně vystřídají všechna čísla od 1 do 5. Faktoriál čísla 5 obsahuje 120 řádků, a proto se v první pozici opakuje za sebou číslo 1 → 24x, následuje číslo 2 samozřejmě také 24x …. až číslo 5 → posledních 24 řádků. Počet opakování každého čísla následně za sebou je dán jako faktoriál čísla 4. Je zřejmé, že z 5 různých čísel se každé opakuje 4! = 24 krát následně za sebou. Proto 5 * 4! = 5!
Pro opakování jednotlivého čísla obecného faktoriálu (n!) v první pozici platí počet opakování = (n – 1)! Pro určení správného čísla v určité pozici platí zjištění podílu z počtu (pořadí) aktuálního řádku. Například číslo řádku 28 → 28/4! = (28/24) = 1,16. Z toho plyne, že na prvé pozici je číslo 2. Pokud by výsledkem (podílem) bylo číslo < 1, je tam číslo 1 a tak dál. Prakticky to zjišťujeme pomocí funkce INT, která vrací celočíselnou část podílu. Bylo by sice výhodnější použít zaokrouhlení směrem nahoru, ale tato funkce nebývá integrována do knihoven programovacích jazyků (tedy jak který). Proto je číslo na první pozici dáno jako INT[ROW/(n-1)!]+1. Poznámka → číslo 1 patří do všech pozic, které mají INT = 0. Proto platí, že správné číslo na první pozici a na určitém řádku je dáno jako INT[X/(n-1)!]+1.

Druhá pozice (sloupec) : Ve druhé pozici se postupně vystřídají všechna různá čísla která nejsou na první pozici. Například když je v první pozici číslo 1 ve druhých pozicích se postupně vystřídají čísla 2 – 5. Nejprve tedy číslo 2 → 6x, následuje číslo 3 → 6x, až číslo 5 → 6x.
Když ale bude například v první pozici číslo 4 ve druhých pozicích se postupně vystřídají čísla 1, 2, 3, 5. Nejprve tedy číslo 1 → 6x, následuje číslo 2 → 6x, číslo 3 → 6x a nakonec číslo 5 → 6x. Pravě toto řazení a výběr je problémem algoritmu, respektive mechanizmus, který ze 4 možností vybere správnou číslici. Právě proto si mnoho autorů scriptů vybere snadnější podmínky, které vedou ke konstrukci množiny, která není lexikálně uspořádaná.
Pro opakování jednotlivého čísla obecného faktoriálu (n!) na druhé pozici platí počet opakování = (n – 2)! Pro určení správného čísla v určité pozici platí zjištění podílu z počtu (pořadí) aktuálního řádku. Například číslo řádku 28 → 28/3! = (28/6) = 4,66. Z toho plyne, že číslo 4 reprezentuje 4! a zbytek 0,66 odpovídá číslu 1 Rozsah pro číslo 1 = x (4 < x < 5]. Když by podíl překročil číslo 5, odpovídá to číslu 3 (druhá pozice v array = zbytek), protože dvojka je v první pozici a do druhé pozice lze zadat jen čísla 1, 3, 4, 5. číslo na určité pozici je dáno jako pozice v array INT[MOD(X,(n-1)!)/(n-2)!]. Samozřejmě číslování v array začíná nulou. Vlastní pozici v array zjišťujeme z funkce MODULO (MOD), tedy z celočíselného zbytku podílu na první pozici.
Opět platí, že je lepší obrázek nežli mnoho vět :

První a druhá pozice
První a druhá pozice

Na obrázku vidíme jak se řídí opakování stejných čísel pomocí faktoriálu, respektive pomocí INT a nebo MOD. Podobně je tomu pro 3. a 4. pozici:

opakování v 3. a 4. pozici
opakování v 3. a 4. pozici

Nakonec využijeme pro poslední pozici například rozdíl, nebo podíl, či jinou metodu, která určí poslední číslo. Na následujícím obrázku jsem to vyjádřil jako podíl 5! / součin čísel v předcházejících pozicích. Je ale celkem jedno jak zjistíme číslo, které není v pozicích 1. – 4.

Poslední pozice - nalezení posledního čísla z podílu.
Poslední pozice – nalezení posledního čísla z podílu.
Digiprove sealCopyright secured by Digiprove © 2013 Petr Neudek

Napsat komentář

Přejít k navigační liště