Matematické Fórum

leniczka · 22. 11. 2008 10:29

ahoj, mám za úkol najít algoritmus který převede zlomek do tvaru v nadpisu... například 4/5 = 1/2 + 1/4 + 1/20... Alogoritmus má tedy převést zlomek p/q kdy 1<p<q... Už nad tím přemýšlím druhý den, dokonce i v pátek:), a nic mě nenapadlo...díky za rady...

ttopi · 22. 11. 2008 11:47

V podstatě mně už něco napadlo a mohlo by to fungovat.

Vezmu příklad $\frac45$ .

Určím si první sčítanec, například $\frac12$ . Vím, že k $\frac12$ musím přičíst ještě $\frac45-\frac12$ abych dostal celkem ony $\frac45$ .

Takže $\frac{4}{5}-\frac{1}{2}=\frac{8-5}{10}=\frac{3}{10}$ .
Dostávám tedy, že $\frac{4}{5}=\frac{1}{2}+\frac{3}{10}$

My ale vyžadujem, aby v čitateli byla 1. Proto si určím další sčítanec, který od $\frac{3}{10}$ odečtu, ale pozor, musí být menší. Takže volím $\frac14$ a počítám $\frac{3}{10}-\frac{1}{4}=\frac{6-5}{20}=\frac{1}{20}$
a jsem u konce, konečný výpočet je tedy $\frac{4}{5}=\frac{1}{2}+\frac{1}{4}+\frac{1}{20}$ .

Další příklad:
Volím zlomek $\frac35$
Opět volím první sčítanec (nižší) $\frac12$ a počítám $\frac{3}{5}-\frac{1}{2}=\frac{6-5}{10}=\frac{1}{10}$ a jsem hned u konce.

Konečný výsledek je tedy $\frac{3}{5}=\frac{1}{2}+\frac{1}{10}$

Další příklad:
Volím $\frac79$

Volím první sčítanec $\frac12$ a počítám $\frac{7}{9}-\frac{1}{2}=\frac{14-9}{18}=\frac{5}{18}$ opět ale vyžadujem ,aby v čitateli byla 1, proto volím další sčítanec $\frac14$ (1/3 nelze, protože je větší než 5/18 a algoritmus je dán tak, že sčítanec musí být menší).
Počítám $\frac{5}{18}-\frac{1}{4}=\frac{10-9}{36}=\frac{1}{36}$ a jsem u konce.
Konečný výsledek je $\frac{7}{9}=\frac{1}{2}+\frac{1}{4}+\frac{1}{36}$ .

Zřejmě to funguje, takže jsem takový algoritmus našel.

ttopi · 22. 11. 2008 11:53 — Editoval ttopi (22. 11. 2008 11:57)

Další příklad:
Počítám $\frac{13}{15}$
$\frac{13}{15}=\frac{1}{2}+...\nl\frac{13}{15}-\frac{1}{2}=\frac{26-15}{30}=\frac{11}{30}\nl \frac{13}{15}=\frac{1}{2}+\frac{1}{3}+...\nl\frac{11}{30}-\frac{1}{3}=\frac{11-10}{30}=\frac{1}{30}\nl \rightarrow \frac{13}{15}=\frac{1}{2}+\frac{1}{3}+\frac{1}{30}$

Abych to srhnul, volíme si postupně menší a menší sčítance tak, abychom skončili tím, že vyjde 1/něco a pak všechny ty sčítance sečtem a máme původní zlomek.

leniczka · 22. 11. 2008 11:59

Díky Toppi, vypadá to dobře:) Jen by mě zajímalo... Ten první sčítanec to je vždycjy jedna polovina nebo proč ji tam furt dáváš? Díky moc

leniczka · 22. 11. 2008 12:03

Už to chápu:) Jen ten uplně první příklad z 6/7 máš myslím špatně, ne?

ttopi · 22. 11. 2008 12:05

Protože začínám prostě od nejmenšího možného zlomku :-)

Ale pozor, jak jsem řekl, první sčítanec musí být menší než zlomek, který vyjadřuješ.
Takže třeba pro $\frac{3}{14}$ nemůže být první sčítanec $\frac12$ ale něco, co je menší než $\frac{3}{14}=0,2142...$ takže třeba $\frac15$ by byl prvním sčítancem. A tenhle příklad si schválně zkus dodělat, co ti vyjde :-)

ttopi · 22. 11. 2008 12:06

↑ leniczka:Samozřejmě, protože jsem ho nedělal podle svého algoritmu, ale už jsem ho smazal :-)

leniczka · 22. 11. 2008 12:13

OK, já nad tím přemýšlím dva dny a ty to máš za pět minut:) Asi fakt Einstein:)

Jinak těch 3/14... První sčítanec je 1/5... 3/14 - 1/5 je 1/70. Takže 3/14 = 1/70 + 1/5. Fakt fo funguje, díky moc:)

ttopi · 22. 11. 2008 12:14

↑ leniczka:
V žádném případě, Einsteini jsou tu jiní (BrozekP, Pavel, Marian, Kondr - namátkou)...

Super, máš to správně :-)

Pavel Brožek · 22. 11. 2008 12:17

ttopi napsal(a):
Zřejmě to funguje, takže jsem takový algoritmus našel.

Algoritmus by měl být konečný. Můžeš tedy ukázat, že dříve nebo později pro každý zlomek algoritmus skončí? (Příklady, které fungují mě nepřesvědčí :-) )

ttopi · 22. 11. 2008 12:26

No od čísla x/y když postupně budeš ubírat a ubírat čísla ve tvaru 1/z, tak jednou musíš skončit na 0, protože x/y lze vyjádřit v desetinném čísle a 1/z také. Pokud budu ubírat od čísla 0,6 třeba pořád 0,1 tak skončím na 0 určitě.

Já bych spíš použil oblíbenou větu většiny učitelů - Tvrdíš snad, že to nefunguje? Tak mi to své tvrzení dokaž :-)

Kondr · 22. 11. 2008 12:39

↑ ttopi:Když budu od zlomku 1/1 odebírat 1/2, 1/4, 1/8,.... tak nikdy neskončím. To sice není případ tvého algoritmu, ale chtělo by to zdůvodnit.

Řečeno jinak: Nejde argumentovat tím, že se zmenšuje hodnota zlomku. Musí se v každém kroku zmenšvat něco, co se může zmenšit jen konečně-krát, třeba p, q, p+q, p*q,....

ttopi · 22. 11. 2008 12:41

↑ Kondr:
V zadání je ale 1<p<q.

Chtělo se najít algoritmus, byl nalezen, kdo tvrdí, že nefunguje, ať udá jeden příklad čísel p a q, kde 1<p<q , pro která to neplatí :-)

Pavel Brožek · 22. 11. 2008 12:52

↑ ttopi:

Zajímavý přístup, proč se vlastně lidé zabývali důkazem Velké Fermatovy věty? Stačilo říct "Ukažte mi čísla, která ji vyvrací! Nemáte? Tak věta platí." :-)

ttopi · 22. 11. 2008 13:08

↑ BrozekP:
Děláš z komára velblouda. Úkolem bylo nalézt algoritmus a nic víc. Pro mě zřejmě funguje, pokud pro tebe ne, zkus si důkaz udělat sám :-)

Pavel Brožek · 22. 11. 2008 16:01

Myslím, že jsem našel důkaz, že algoritmus je správný. Zatím ho zde nebudu uvádět, řekl bych, že není příliš těžký, takže by si ho myslím mohl zkusit i lukaszh a ostatní, kdo rádi dokazují a úlohy na důkazy co se tu objevují jsou pro ně příliš těžké.

Pavel Brožek · 19. 01. 2009 17:11

↑ BrozekP:

Po téměř dvou měsících se vracím k tomuto tématu a uvedu svůj postup důkazu:

Máme tedy čísla 1<p<q.

a) Pokud p dělí q, pak jednoduše $\frac{p}{q}=\frac1{\frac{q}{p}}$ je hledaný rozklad.

b) Pokud p nedělí q, pak jistě exisuje $n\in\{1,2,\ldots,p-1\}$ takové, že p dělí $q+n$ . Platí tedy

$\frac pq=\frac{p(q+n)}{q(q+n)}=$

čitatel i jmenovatel je dělitelný p, budu proto krátit p a stále budu mít v čitateli a jmenovateli přirozená čísla

$=\frac{q+n}{q\frac{q+n}{p}}=\frac{q}{q\frac{q+n}{p}}+\frac{n}{q\frac{q+n}{p}}=\frac{1}{\frac{q+n}{p}}+\frac{n}{q\frac{q+n}{p}}$

Rozložil jsem tedy zlomek $\frac pq$ na součet zlomku s čitatelem 1 a zlomku s čitatelem menším než p. Protože

$q\frac{q+n}{p}=\frac{q+n}{\frac pq}>\frac{q+n}1>n$ ,

můžu na druhý zlomek použít stejný postup rozkladu. Protože je čitatel n menší než p, pak tento postup budu opakovat nejvýše p krát a pak se určitě dostanu na n=1 a mám tedy požadovaný rozklad. Tento postup také zajišťuje, že se v rozkladu nebudou opakovat stejní jmenovatelé (protože $\frac{n}{q}<1$ , je druhý zlomek $\frac{n}{q\frac{q+n}{p}}$ menší než první $\frac{1}{\frac{q+n}{p}}$ )

musixx · 19. 01. 2009 17:24 — Editoval musixx (19. 01. 2009 17:27)

↑ BrozekP: Rekl bych, ze timto jsi dokazal, ze nejaky takovy soucet existuje. Podle me jsi ale nedokazal, ze kdyz pouziju postup od ttopi (ktery vzdy jako dalsi scitanec bere nejvetsi mensi 1/x nez je aktualni zbytek), tak ze skoncim. Nebo se pletu?

Pavel Brožek · 19. 01. 2009 17:58

↑ musixx:

Pokud bych nevzal zlomek $\frac{1}{\frac{q+n}{p}}$ ale zlomek s o jedna menším jmenovatelem $\frac{1}{\frac{q+n}{p}-1}$ , tak platí (použiju $n-p<0$ )

$\frac{1}{\frac{q+n}{p}-1}=\frac{p}{q+n-p}>\frac{p}{q}$ .

$\frac{1}{\frac{q+n}{p}}$ je tedy největší zlomek s čitatelem 1 menší než $\frac pq$ .

Matematické Fórum

#1 22. 11. 2008 10:29

zlomek jako součet převrácených hodnot různých celých čísel

#2 22. 11. 2008 11:47

Re: zlomek jako součet převrácených hodnot různých celých čísel

#3 22. 11. 2008 11:53 — Editoval ttopi (22. 11. 2008 11:57)

Re: zlomek jako součet převrácených hodnot různých celých čísel

#4 22. 11. 2008 11:59

Re: zlomek jako součet převrácených hodnot různých celých čísel

#5 22. 11. 2008 12:03

Re: zlomek jako součet převrácených hodnot různých celých čísel

#6 22. 11. 2008 12:05

Re: zlomek jako součet převrácených hodnot různých celých čísel

#7 22. 11. 2008 12:06

Re: zlomek jako součet převrácených hodnot různých celých čísel

#8 22. 11. 2008 12:13

Re: zlomek jako součet převrácených hodnot různých celých čísel

#9 22. 11. 2008 12:14

Re: zlomek jako součet převrácených hodnot různých celých čísel

#10 22. 11. 2008 12:17

Re: zlomek jako součet převrácených hodnot různých celých čísel

ttopi napsal(a):

#11 22. 11. 2008 12:26

Re: zlomek jako součet převrácených hodnot různých celých čísel

#12 22. 11. 2008 12:39

Re: zlomek jako součet převrácených hodnot různých celých čísel

#13 22. 11. 2008 12:41

Re: zlomek jako součet převrácených hodnot různých celých čísel

#14 22. 11. 2008 12:52

Re: zlomek jako součet převrácených hodnot různých celých čísel

#15 22. 11. 2008 13:08

Re: zlomek jako součet převrácených hodnot různých celých čísel

#16 22. 11. 2008 16:01

Re: zlomek jako součet převrácených hodnot různých celých čísel

#17 19. 01. 2009 17:11

Re: zlomek jako součet převrácených hodnot různých celých čísel

#18 19. 01. 2009 17:24 — Editoval musixx (19. 01. 2009 17:27)

Re: zlomek jako součet převrácených hodnot různých celých čísel

#19 19. 01. 2009 17:58

Re: zlomek jako součet převrácených hodnot různých celých čísel

Zápatí