Ako vyriesit rovnicu – C / C++ – Fórum – Programujte.com

Caute,

chcel by som vas poprosit o radu ako zapisat riesenie rovnice v C.

t = ( s1/(v1+k) ) + ( s2/(v2+k) ) + ( sn/(vn+k) )

t,s,v poznam, mam zistit k, s tym ze pocet s,v moze byt od 1 do 1000 (1<= n <=1000) t.j. pocet zlomkov moze  byt 100 alebo 200 az 1000.

#1 Navi
Dakujem vopred za kazdu radu uz sa s tym kaslem strasne dlho a neviem na nic prist

(1 ≤ t ≤ 10^6),  (1 ≤ s ≤ 1000), (|v| ≤ 1000)

Nevím, jestli to k jde nějak spočítat, ale určitě ho jde najít. Když za něj dosadíš nějakou hodnotu a výsledek nesedí, tak aspoň poznáš, jestli by mělo být větší, nebo menší. Půlením intervalu ho tak s omezenou přesností můžeš poměrně rychle najít.

Tady jsem to někomu pro jednodušší funkci ukazoval v Pythonu.

Odhadem bych to pocital jako
| * k, dostanes zhruba
t * k = s1 + s2 + sn
Presne, viz gna, dopocitavanim, pulenim intervalu. Urcis si interval, pro jake k ma rovnice reseni. Dosadis nejakou hodnotu, treba polovinu. Na leve strane vyjde 5, na prave treba 20. Dosadis jinou, vyjde l=1, p=0.123. Takze viz, ze k je mezi 1/2 intervalu a 3/4.

Napr, mas interval <-1; nekonecno)
k1 = 0 - zvolis si treba nulu, kdyz je v intervalu, s tou se dobre pocita, obvykle
k2 = 1000
...

Ve tvem pripade
v1 + k <> 0
v2 + k <> 0
vn + k <> 0
intervalu: (-nek, -v1) (-v1; -v2) (-v2, -vn) (-vn; nekonecno)
za predpokladu, ze -v1<-v2<-vn, samozrejme. Cili, to poradi muze byt opacne.

----

Existuje neco jako soucet posloupnosti. Za predpokladu, ze mezi temi zlomky dokazes urcit vztah a bude stejny pro kazdy nasledujici zlomek.
Napr
1 + 2 + 3 + 4 + 5 + 6 = 21
sn = n/2 * (n+1)
s6 = 6/2 * (6+1) = 3 * 7 = 21

Nejdřív trochu matematiky - rovnici bych si upravil do tvaru k = .... a pak programoval. Ve výsledku tam moc programování nebude. Bude to jednodušší než "hádací" algoritmus. 

Co se týče úpravy rovnice. Je to rovnice parametrická a obsahuje zlomky. Odstranění zlomků by neměl být problém. Na závěr zřejmě příjde dělení výrazem obsahujícím parametry. Zde je důležité vyhnout se dělení nulou a současně brát v potaz, že i pro ty hodnoty parametrů, pro které by k dělení nulou došlo, může mít rovnice řešení. 

hu

#6 hlucheucho
Uz pro tri useky ti tam zacnou vychazet takovy rovnice, ze budes mit co delat uhlidat jen exponenty a indexy

t =  s1/(v1 + k)  +  s2/(v2 + k)  +  s3/(v3 + k)      // cele vynasobit  (v1 + k)(v2 + k)(v3 + k) 

t(v1 + k)(v2 + k)(v3 + k)  =  s1(v2 + k)(v3 + k) + s2(v1 + k)(v3 + k) + s3(v1 + k)(v2 + k)

No a ted vyjadruj k pro kazdou variantu az do 1000 useku.

Puleni intervalu ma sanci dokoncit jeste v tomhle stoleti :D

#7 KIIV
On to zadání nenapsal zrovna moc srozumitelně. Až teď jsem pochopil, že mu výjde parametrická rovnice n-tého řádu. Do 4 řádu jsou Cardanovy vzorce, lze řešit úpravou výrazu a dosazováním do vzorečků.. Co se týče půlení intervalu - maximální počet kořenů rovnice je roven jejímu řádu, je otázka, zda je lze (všechny?) takto najít.

Tohle není SŠ matematika a jít obtěžovat za matematikama Matematického ústavu AV ČR se mi nechce. Takže to vzdávám. Asi by se měl obrátit na matematiky na matematickém fóru.

hu

#8 hlucheucho
On to ma opravdu popsane priserne, ale nedlouho pred tim tu bylo to same, vcetne kompletniho zadani:

http://it4kt.cnl.sk/c/pvjc/2018/problemset.racer.html

Proste tomu zavodnikovi upadla rucicka na tachometru a pridelal ji tam pod spatnym uhlem. Z namerenych dat se pak snazi zjistit, jak to ma "opravit"...

pokud je to zadání dle odkazu KIIV, tak bych viděl několik drobností které mohou, alespon trošku pomoci:

1 pokud některé S se rovná 0 auto stálo, tzn k by se mělo rovnat -V, problémem je tu to, že nelze určit dobu stání

2 pokud jsou jsou některé hodnoty V < 0 najít Vmin

3 pokud S>0, tak V+K musí být také >0, otázka limit při V=0 by byl čas úseku nekonečný

výchozí hodnoty pro intervalový algoritmus K0= 0 nebo lVminl dle bodu 2, Km = horní limit V - Vmax ze seznamu hodnot

Výpočet T0 a Tm (cyklus nad počtem párů S,V)  jen poprvé mimo hledací cyklus

*hledací cyklus - začátek

Ks = (Km-K0)/2

výpočet Ts

lT-Tsl < odchylka konec hledání

podmínka Ts<T  pak Km=Ks a aby se nemuselo počítat znovu Tm=Ts 

TS>T pak K0=Ks a T0=TS

opakovat cyklus

t =  s1/(v1 + k)  +  s2/(v2 + k)  +  s3/(v3 + k) ...

(v1+k) * (v2+k) ... = z

t = (s1 * z/(v1+k) + s2 * z/(v2+k) ... ) / z
t * z = s1 * z/(v1+k) + s2 * z/(v2+k) ...

Nejvyssi 'k' v 'z' budou k^n + k ^(n-1) + k ^(n-2) + k ^(n-3) (n je 1000), rekneme, ze necham jen k^1000
A pak tam budou v1 * v2 * v3...  = vL

t * (vL + k^1000) = ...

z / (v1+k) se nebude prilis lisit od z / (v2+k)

Takze se da opet udelat prumer
vP = (suma(v) + suma(k)) / n = suma(v) / n + k
t * z = z/vP * (s1 + s2 ...)
t * vP = suma(s)
t * (suma(v) / n + k) = suma(s)
suma(s) / t - suma(v) / n = k ... To by mohl byt priblizny vysledek. Tipuji +-10%.

---

t =  s1/(v1 + k)  +  s2/(v2 + k)  +  s3/(v3 + k)
s: 5, 4, 3
v: 3, 2, 1
t: 15
n: 3
k  = suma(s) / t - suma(v) / n
k = 12 / 15 - 6 / 3 = 4/5 - 2 = -6/5 (zhruba -1, aby se mi lip pocitalo)
15 =  5/(3 - 1)  +  4/(2 -1)  +  3/(1 - 1)
15 = 5/2 + 4
A, mi to teda moc nevychazi :)

15 =  5/(3 - 6/5)  +  4/(2 - 6/5)  +  3/(1 - 6/5)
15 =  5/(9/5)  +  4/(4/5) +  3/(1 - 6/5)
15 =  9  +  5  - 15
15 =  -1

Zas tak moc zaokrouhlovat se nesmi, ale stejne to vyjde jinak. Neva. Dopocitavanim, pulenim intervalu, jsem dosel, ze by to mohlo byt kolem k = -0.75
Dobre se tohle dela v excelu. Ale ne pro 1000 hodnot * 1000 hodnot :)

#10 MilanL

chybička se vloudila, čekal na mě kolega s autem, tak jsem to nezkontrolovasl

Ks=K0+(Km-K0)/2

#12 peter

přes průměry to nepůjde každej ůsek má jinej čas, já zkoušel i otočení zlomků (umocnění na -1), ale nevím jak to udělat v řadě.

jinak jestli je to úloha z programování, tak určitě nejsou očekávány nějaké velké matematické úpravy vzorce, spíš o zpracování hledacího algoritmu, práce s poli a cykly.

#1 Navi
Za předpokladu, že se skutečně jedná o úlohu, kterou zde KIIV odkazoval, je to nakonec poměrně jednoduché.

Metoda půlení intervalu, kterou zde navrhovali, je skutečně průchozí cesta. Nicméně, podobně jako u všech numerických metod, vyžaduje určité podmínky:

1. funkce, jejíž kořeny řešíte, musí být spojitá (to zde platí),
2. musíte znát interval, kde se kořen nachází,
3. funkce musí na daném intervalu být monotónní.

Podmínky jsou poměrně přímočaré. Pokud není splněná druhá, pak můžete na intervalu půlit, jak chcete, ale k řešení se nedostanete. Druhá je nutná, aby fungovalo porovnání "jsem výš, půjdu dolů, jsem níž, půjdu nahoru." Pokud funkce není spojitá nebo monotónní a může vám různě skákat nahoru a dolu, nemáte zaručeno, že se ke kořeni dostanete.

Tedy, pokud chcete dopočítat kořen, musíte funkci nejdříve podrobit určité analýze. Pro ni je důležitá informace uvedená v KIIVově odkazu: každý zlomek v součtu musí být kladný - vzdálenost úseku je kladná, skutečná rychlost úseku je kladná, celkový čas je kladný. Pokud je každý zlomek kladný (> 0), pak funkce na definičním oboru je monotónní - s rostoucím k všechny zlomky klesají, a protože nejsou záporné a "nejdou proti sobě", pak celkový součet s rostoucím k také klesá (limitně k nule).

Podmínku 3 jsme splnili, takže je potřeba určit interval hodnot k, ve kterém se řešení zaručeně nachází. Jako spodní mez lze použít kraj definičního oboru. Všechny zlomky musí být kladné, tzn. pokud najdeme vm = min{v1, ..., vn}, pak spodní mez kl musí být -vm. Pro každé k menší než -vm by už nebylo splněné, že zlomky jsou kladné. Povšimněte si ovšem, že tato hodnota není součástí definičního oboru, protože byste ve zlomku s minimálním v dělil nulou. To ovšem nevadí - při půlení intervalu se stejně do krajní meze nikdy reálně nedostaneme.

Určit horní mez je trochu složitější. Víme, že funkce s rostoucím k monotónně klesá. Můžeme tedy najít maximum z poměrů sm/vm = max{s1/v1, ..., sn/vn} a následně vyřešit rovnici t = n.sm/(vm + kh). Je to, jako bychom měli všechny zlomky v součtu stejné. Když do původní funkce dosadíme kh, pak každý zlomek v součtu bude zaručeně <= sm/(vm + kh) (proto jsme hledali maximum) a tudíž celkový součet bude zaručeně <= t.

Takže, suma sumárum, výsledný algoritmus je následující:

1. nalézt minimální vm a jako dolní mez kl prohlásit -vm,
2. nalézt maximální poměr sm/vm a z něho určit horní mez kh (viz. výše),
3. půlením intervalu (kl, kh) se přiblížit k hodnotě, kde se součet zlomků rovná t.