Matematické Fórum

misha2015 · 03. 11. 2015 13:12

Napište program, který dostane na první řádce vstupu číslo N.

Na druhé řádce bude N čísel, které odpovídají celočíselným zbytkům po dělení čísel po řadě: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

A zrekonstruuje z ních původní číslo X, které je reprezentováno těmito zbytky.

Vaším úkolem je vypsat neznámé číslo X.

Příklad 1:

Vstup:
4
1 1 1 1

Výstup:
1

Příklad 2:

Vstup:
4
1 1 0 4

Výstup:
25
v Pascalu

Formol · 03. 11. 2015 13:56 — Editoval Formol (03. 11. 2015 13:57)

↑ misha2015:
Ahoj,
finta je jednoduchá. Označme si neznámé číslo X, zbytek po dělení prvočíslem p Rp a násobek prvočísla Mp. Pak jistě pro tvoje neznámé číslo platí:
$X = p M_p + R_p$

Když bude např. N=3, pak budeš mít soustavu rovnic:
$X = 2 M_2 + R_2$
$X = 3 M_3 + R_3$
$X = 5 M_5 + R_5$

Protože Rp máš zadané, můžeš si to upravit do tvaru:
$X - 2 M_2 = R_2$
$X - 3 M_3 = R_3$
$X - 5 M_5 = R_5$

Tedy máš soustavu tří rovnic pro čtyři neznámé (X, M2, M3, M5). Pokud má taková soustava řešení, je jich nekonečně mnoho, vesměs neceločiselných. Podobně pro n prvočísel by soustava měla n+1 rovnic. Ještě taková poznámka, podle tvaru matice soustavy lze uhádnout, že bude mít řešení vždy.

Tak jak najít řešení? Nejlépe na papíře ;-) Řešení bude záviset na parametru. Parametr si zvolíme X. Pak pro neznámé Mp vyjde:
$M_p = \frac{X - R_p}{p}$

Tedy hledáš nejmenší takové celočíselné X, pro které je podíl $\frac{X - R_p}{p}$ ve všech zvolených prvočíslech celočíselný. Tj. např. pokud zadáš N=2 a zbytky 1 a 2, tak hledáš nejmenší takové číslo, pro které budou celočíselné zlomky:
$\frac{X - 1}{2}$
a
$\frac{X - 2}{3}$

Ještě k otázce celočíselnosti toho zlomku. Nejsnazší způsob testování je prostě testovat zbytek po dělení čitatele jmenovatelem na nulovost.

(Šlo to trochu oklikou, ale jde mi o to, abys viděla, že ten myšlenkový postup není vůbec složitý.)