Matematické Fórum

Seith · 03. 11. 2012 13:04

Dobrý den,

existuje nějaký postup jak pro dvě aritmetické posloupnosti zjistit hodnotu, která je v obou obsažena? Poslopnosti jsou rostoucí. Potřeboval bych nejnižší možnou hodnotu, která vyhovuje.

Nevím jestli jsem dostatečně pochopitelně formuloval můj problém, proto raději ještě uvedu příklad:

$a_1=13, d_a=2$

$b_1=9, d_b=7$

Posloupnost a: 13, 15, 17, 19, 21, 23, ...
Posloupnost b: 9, 16, 23, ...

Výsledkem je číslo 23.

JohnPeca18 · 03. 11. 2012 13:53

Mne napada napsat si to jako
$a_1+md_a=b_1+nd_b$
Vyjadrit jsi třeba m
$m=\frac{b_1+nd_b-a_1}{d_a}$
A zistit pro které nejmensi n je vyraz delitelny. Nevim teda jestli je na to nejaky algoritmus.
Pripadne si vyjadrit analogicky n a zkouset to z obou stran.
Totiz niekedy to ani nemusi mat riesenie.
Povedzme
pre
$a_1=0, d_a=5,b_1=1, d_b=5$

JohnPeca18

Jo to ze to nema reseni, se da zistit tak, ze zistime Nejvetsi spolecny delitel (NSD) $k=NSD(d_a,d_b)$ vydelime obidve strany rovnice $a_1+md_a=b_1+nd_b$ . $a_1$ a $b_1$ vydelim celociselne a pokial na obidvoch stranach neostane rovnaky zvysok po deleni, tak to riesenie nema. Pokial je zvysok rovnaky, tak by som tie zvysky odpocital a zostane mi jednoduchsia rovnica.
$\lfloor\frac{a_1}{k}\rfloor+m\frac{d_a}{k}=\lfloor\frac{b_1}{k}\rfloor+n\frac{d_b}{k}$

Seith · 03. 11. 2012 14:28 — Editoval Seith (03. 11. 2012 14:29)

↑ JohnPeca18:
Pomocí tohoto vzorce by šel realizovat algoritmus

krok 1: pokud $d_a<d_b$ , tak prohoď posloupnosti (algoritmus má pak méně iterací)
krok 2: $n = 0$
krok 3: platí $(a_1 + n d_a - b_1) mod\text{ } d_b = 0$ ?
-pokud ano $\text{společná hodota} = b_1+nd_b$
-pokud ne $n=n+1$ a znovu krok 3

Zkusím jej realizovat ve svém programu a uvidím, jestli projde kritériem časové složitosti, děkuji.

JohnPeca18

↑ Seith:
Urcite bych tam ale dal to ten test na soudelnost, jak sem psal v druhem prispevku, NSD se da rychle zistit Euklidovym algoritmem. Jinak se ti muze stat, ze program neskonci.

Seith · 03. 11. 2012 14:37

↑ JohnPeca18:
Ano, ten tam dám. Prý to jde lépe pomocí rozšířeného euklidova algoritmu, bohužel po prostudování materiálů na internetu a s mým současným matematickým aparátem nejsem schopen přijít na to, jak jej použít.

Magicmaster · 04. 11. 2012 14:50

↑ Seith:
Prošlo ti tohle řešení časově progtestem? Taky bojuju s tím, jak na to napasovat Eukleida, ale zatím nic

Matematické Fórum

#1 03. 11. 2012 13:04

Algoritmus pro shodný člen dvou aritmetických posloupností

#2 03. 11. 2012 13:53

Re: Algoritmus pro shodný člen dvou aritmetických posloupností

#3 03. 11. 2012 14:17 — Editoval JohnPeca18 (03. 11. 2012 14:24)

Re: Algoritmus pro shodný člen dvou aritmetických posloupností

#4 03. 11. 2012 14:28 — Editoval Seith (03. 11. 2012 14:29)

Re: Algoritmus pro shodný člen dvou aritmetických posloupností

#5 03. 11. 2012 14:32 — Editoval JohnPeca18 (03. 11. 2012 14:33)

Re: Algoritmus pro shodný člen dvou aritmetických posloupností

#6 03. 11. 2012 14:37

Re: Algoritmus pro shodný člen dvou aritmetických posloupností

#7 04. 11. 2012 14:50

Re: Algoritmus pro shodný člen dvou aritmetických posloupností

Zápatí