Matematické Fórum

maestorm · 26. 01. 2014 22:55

Hezký večer,
již delší dobu si lámu s příklady tohoto typu:
V následujícím zadání je popsán (formální) algoritmus pracující s jedním celočíselným vstupem a jedním výstupem.

Vstup celočíselného parametru n .

Do a přiřadíme hodnotu 1 .

Do b přiřadíme hodnotu 1 .

Pro všechna celá i = 1 ... n provedeme tyto (odsazené) kroky:

Do a přiřadíme hodnotu 2·a+1 .

Do b přiřadíme hodnotu 2·a+b-1 .

Výstup (celočíselné proměnné) b .

Vaším úkolem je zjistit a doplnit (ručně, bez počítače) tři chybící celočíselné koeficienty v následující formuli tak, aby platilo:

Pro každé celé n>0 na vstupu je výsledná hodnota b rovna
b(n)=x*2^n+y*n+z

Pro úplnost uvádím ještě symbolický formální zápis téhož algoritmu:

input n;
a ← 1;
b ← 1;
for i ← 1 to n do
a ← 2·a+1;
b ← 2·a+b-1;
done
output b;

řešení má vyjít:
b(n)=8*2^n-3*n-7

ale počítám to:
i 0 1 2 3
a 1 3 7 15
b 1 6 19 48

a následně pomocí Cramerova pravidla: -16/-2 = 8;
22/-2 = -11;
-18/-2 = 9

Můžete mi prosím někdo poradit jak mám tento typ příkladů počítat správně, už několikátý den s tím bojuji přičemž počítám s tím, že mám někde chybu ve výpočtu, ale za nic na světě mi nejde přijít na to, kde a jakou, či je má metoda chybná?

Předem děkuji za pomocnou ruku.

Brano · 26. 01. 2014 23:54 — Editoval Brano (27. 01. 2014 00:00)

Nech $a_i, b_i$ su hodnoty $a,b$ v i-tom kroku.
Potom $a_0=1=b_0$ , $a_i=2a_{i-1}+1$ a $b_i=2a_i+b_{i-1}-1$ .
Mozes to riesit ako diferencne rovnice - najprv vyriesime $a_i$ - charakteristicka rovnica homogennej casti je
$x=2$ teda riesenie homogennej je $a_i=A2^i$ a partikularne riesenie nehomogennej mozme hladat metodou neurcitych koeficientov v tvare konstanty $a_i=p$ t.j.
$p=2p+1$ cize $p=-1$ a vseobecne riesenie je $a_i=A2^i-1$ a uz staci dosadit $a_0=1$ cize
$1=A2^0-1$ teda $A=2$ a nakoniec mame $a_i=2^{i+1}-1$ . To dosadime do rovnice pre $b_i$ a dostaneme
$b_i=b_{i-1}+2^{i+2}-3$
znova najprv riesime homohennu cast - char. rovnica je $x=1$ a teda homogenne riesenie je $b_i=B$ - t.j. lubovolna konstanta. Pre parikularne riesenie pouzime znova metodu neurcitych koeficientov. Clenu $2^{i+2}$ zodpoveda $x2^i$ a clenu $-1$ by zodpovedala konstanta, ale kedze konstanta je riesenie homogennej rovnice, tak mame rezonanciu a musime pouzit clen $yi$ - cize dosadime $b_i=x2^i+yi$ (co sa uz dost podoba na hint zo zadania)
$x2^i+yi=x2^{i-1}+y(i-1)+2^{i+2}-3$ cize
$2^{i-1}(2x-x-8)+y+3=0$ pre vsetky $i$ a teda $x=8$ a $y=-3$ cize mame partikularne riesenie
$b_i=8\cdot2^i-3i$ a ked pridame homogenne, tak vseobecne je $b_i=8\cdot2^i-3i+B$ a staci dosadit $b_0=1$ cize
$1=8+B$ cize $B=-7$ a spolu mame
$b_i=8\cdot2^i-3i-7$ teda pre $i=n$ to len prepiseme
$b_n=8\cdot2^n-3n-7$ a to je aj hodnota vystupu.

PS: metod ako riesit diferencne rovnice je pomerne dost, tak ak sa ti tato nepaci, tak skus napisat ako ste to pocitali v skole a uvidime.

maestorm

↑ Brano:
Děkuji ti/vám za vysvětlení, zběžně se na to dívám a nevím kde se tam vzalo to -3 a také to $2^{i+2}$ při dosazení do $b_i$ :
$b_i=b_{i-1}+2^{i+2}-3$

A také bych se chtěl zeptat, jestli by to skutečně nešlo řešit stejným, respektive podobným způsobem, jak jsem to řešil já?

Na každý pád velice děkuji za rychlou odpověď, zítra tedy vlastně už dnes :D to budu zkoušet!
S přáním krásného večera Tomáš.

Brano · 27. 01. 2014 00:53 — Editoval Brano (27. 01. 2014 00:55)

↑ maestorm:
no urcite by sa to dalo riesit nejak podobne ako si to riesil, len ty si ziaden postup nenapisal (takze neviem ako si to pocital) - napisal si iba prvych par hodnot, a potom spominas Cramerove pravidlo, ktore ja poznam ako metodu na pocitanie algebraickych linearnych rovnic a nic nepises o tom ako by to malo suvisiet s touto ulohou.

a co sa tyka otazky $2(2^{i+1}-1)-1=2^{i+2}-3$

maestorm · 27. 01. 2014 01:02

↑ Brano:
Ty algebraické rovnice jsem měl na mysli:
6 = x*2^n+y*n+z
19= x*2^n+y*n+z
48= x*2^n+y*n+z

tj. pro n = 1...n:

6 = 1*2^n+1*n+1
19= 4*2^n+2*n+1
48= 9*2^n+3*n+1

následně jsem na tuto matici aplikoval Cramerovo pravidlo:
1 1 1
4 2 1
9 3 1

následně mi tímto postupem vyšlo:
-16/-2 = 8;
22/-2 = -11;
-18/-2 = 9

a to bylo špatně, proto se ptám, jestli by to nešlo řešit tímto mým způsobemm a omlouvám se za nejasnosti.

Brano · 27. 01. 2014 01:13

↑ maestorm:
tak uz mi to dava zmysel, ze co si chcel zhruba robit, ale robil si to uplne zle - ved predsa dosadzas za $n$ a hladas $x,y,z$ a nie naopak

a preco by si v tom pripade zostavoval tri rovnice ak by ti mala ostat iba jedna neznama $n$ ?

maestorm · 27. 01. 2014 11:16

↑ Brano:
Hezký den,
pokouším se pochopit metodu, kterou jste/jsi mi to tu řešil, ale rozumím tomu jen po $b_i=b_{i-1}+2^{i+2}-3$ , potom se v tom už ztrácím, kde se tam bere to B,... Potřeboval bych poradit pokud by to bylo možné s tím mým řešení, jak ho na tento typ příkladů aplikovat korektně.
Smím tě/vás o to požádat?

S přáním krásného dne Tomáš.
P. S. Děkuji za dosavadní pomoc, velmi si toho cenním matematika je krásná, ale pro toho kdo si jí jako já ještě neosvojil tak dobře, je dosti zmatečná. Rád bych si tento zmatek v hlavě co nejrychleji uspořádal, ale potřebuji s tím pomoci.

Brano · 27. 01. 2014 12:43

Vacsia cast toho co som robil sa venuje tomu zistit, ze v akej forme bude vystup - t.j. ze to bude
$b=x2^n+yn+z$ - a pocas toho aj postupne zistuje konstanty $x,y,z$

Ale z toho, ze vam v zadani ucitel povedal ze v akej forme ten vysledok hladat, zacinam usudzovat, ze ste asi riesenie diferencnych rovnic vobec nemali - teda asi by bolo lepsie to robit tym tvojim postupom, lebo nastudovat si to ako sa riesia diferencne rovnice (ak ste to vobec nemali) zodpoveda standardnej semestralnej prednaske

ale teda spat k rieseniu:
mas hint - $b_n=x2^n+yn+z$ , tak do tej rovnice dosad $n=1$ potom $n=2$ a potom $n=3$ - s tym, ze si si uz predtym vypocital, ze $b_1=6,\ b_2=19,\ b_3=48$ .

maestorm · 27. 01. 2014 13:06

↑ Brano:
a jak z toho dál vypočítat ten správný výsledek prosím? Stále mi to nevychází ať to zkouším pomocí Gaussovy eliminace, či pomocí Cramerova pravidla... Jak z $b_1=6,\ b_2=19,\ b_3=48$ dostat: $b_n=8\cdot2^n-3n-7$ ?

Brano · 27. 01. 2014 22:40

↑ maestorm:
najprv urob to co som ti povedal
dosad $n=1$ do rovnice $b_n=x2^n+yn+z$

maestorm · 27. 01. 2014 23:29

↑ maestorm:
Tak tohle je vtipný děkuji ti Brano za pomoc, už to mám, já hlupák tady počítám už tolik příkladů na tenhle způsob, že mi vyšel výsledek a já se rozčiloval, že nesedí k příkladu, který měl jiné zadání. Já už mám fakt dost a omlouvám se. Tohle byla vážně stupidita.

Přeji krásný večer a doufám, že se i přes svou protivnost mohu v budoucnu spolehnout na možnou pomoc zde.

Matematické Fórum

#1 26. 01. 2014 22:55

Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#2 26. 01. 2014 23:54 — Editoval Brano (27. 01. 2014 00:00)

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#3 27. 01. 2014 00:32 — Editoval maestorm (27. 01. 2014 00:34)

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#4 27. 01. 2014 00:53 — Editoval Brano (27. 01. 2014 00:55)

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#5 27. 01. 2014 01:02

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#6 27. 01. 2014 01:13

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#7 27. 01. 2014 11:16

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#8 27. 01. 2014 12:43

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#9 27. 01. 2014 13:06

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#10 27. 01. 2014 22:40

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

#11 27. 01. 2014 23:17 Příspěvek uživatele maestorm byl skryt uživatelem maestorm. Důvod: autorova hloupost

#12 27. 01. 2014 23:29

Re: Formální algoritmus pracující s jedním celočíselným vstupem, 1výstupem

Zápatí