FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Kubas129
Člen
Avatar
Kubas129:17.11.2018 21:33

Ahoj, už si opravdu nevím vůbec rady lámu si nad tím hlavu celý den :(
na škole nám dali úkol, že máme navrhnout tunel o délce l pro vlak, který se bude skládat ze segmentů od firmy x a firmy y, které budou spojené vzduchotěsnou mezerou b. A začínat a končit má tou vzduchotěsnou mezerou. A máme najít všechny řešení se kterými by se dal ten tunel přesné délky postavit. Matematicky popsané rovnicí by to asi vypadalo nějak takto:
l = x*S1 + y*S2; kde
l je délka tunelu
S1 je délka segmentu od první firmy
S2 je délka segmentu od druhé firmy
x je neznámá kolikrát tam bude obsažen segment S1
y je neznámá kolikrát tam bude obsažen segment S2
tudíž mám jednu rovnici pro dvě neznámé a potřeboval bych nějaký rychlí algoritmus, který provede výpočet během jedné vteřiny můj algoritmus vypadá následovně a trvá okolo 30 vteřin

poc = len;
        int pocet;
        int reseni = 0;
        double sn1 = s1, sn2 = s2;
        for (int a = 0; a < len ; a++)
        {
                for (int b = 0; b < len ; b++)
                {

                        if (((a * s1 + b * s2) + 2 * bulkhead) == len) {
                                if (reseni == 0)
                                {
                                        *c1 = a;
                                        *c2 = b;
                                }
                                reseni++;

                        }
                }
        }
        return reseni;

kde s1,s2 jsou ty segmenty a bulkhead je ta mezera
Byl bych opravdu moc vděčný za pomoc :)

 
Odpovědět
17.11.2018 21:33
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Kubas129
Patrik Valkovič:17.11.2018 21:41

To vypadá jako úloha z FITu :D
To co hledáš jsou diofantické rovnice.
https://www.priklady.eu/…rovnice.alej

Nahoru Odpovědět
17.11.2018 21:41
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Kubas129
Člen
Avatar
Kubas129:17.11.2018 22:42

Já nerozumím tomu algoritmu u těch rovnicích s tím parametrem t
Oni vezmou ty parametry (v mým případě segmenty s1 a s2) a vypočítají z nich největšího společného dělitele
pak tu lineární rovnici o dvou neznámých vynásobí převrácenou hodnotou toho společného dělitele
poté rovnici upravý na tvar x/y=(b/D)/(-a/D) a tady se už ztrácím oni nějak to odtrhli a řekli že
x=(b/D)*t a zároven y=-(a/D)*t ;kde t je celočíselná proměnná nechápu :(
mohl by mi s tím nějak někdo pomoc? dík moc

 
Nahoru Odpovědět
17.11.2018 22:42
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:19.11.2018 15:55

To je jakasi cast kodu, ktera bez ostatnich casti nedava smysl.

Pokud len neni definovany, pak tam vlozi asi cely int, int32 = 2,147,483,647, int64 = 9,223,372,036­,854,775,807.
Ten cyklus tedy pocita miliarda * miliarda, to nejaky cas zabere. Ja bych zkusil prvne do te funkce natvrdo vntutit len a az pak bych caroval s pointery. Treba mas spatne vyreseny prave pointer.
Pro tvou zajimavost, serazeni 1.000.000 cisel pri pouziti spravneho algoritmu zabere 0.3s Takze tam mas urcite neco spatne, pokud se tu bavime o delce do 1000, rekneme :)
bulkhead - take z kodu nelze zjistit, kolik je.
Zkus tam pridat nejaky vypis na obrazovku vsech promennych. Pripadne vypisovat kazdy krok na obrazovku.

'ze segmentů od firmy x a firmy y, které budou spojené vzduchotěsnou mezerou b. A začínat a končit má tou vzduchotěsnou mezerou.'
Struktura tunelu ma vypadat takto:

* - X - * - X - * - y - * - y - * - y - * - y - * - y - * (* je b)

'A máme najít všechny řešení se kterými by se dal ten tunel přesné délky postavit.'
Neznamena to nahodou urcit pocet X, Y, a i promichani X Y?

* - y - * - X - * - y - * - y - * - X - * - y - * - y - *

Jinak, rovnice by mela byt asi takova:

b_n = x_n + y_n + 2;
x_n * x_delka + y_n * y_delka +  b_n * b_delka == len
Editováno
 
Nahoru Odpovědět
19.11.2018 15:55
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Kubas129
Patrik Valkovič:19.11.2018 17:40

t je parametr, do kterého můžeš vložit cokoliv.
Příklad:
l = 6
S1 = 21
S2 = 15
gcd(S1, S2) = 3 = D
D dělí l = 3 dělí 6 => existuje řešení

Teď je potřeba najít nějaké řešení, tj. D = S1 * x1 + S2 * x2
lze řešit rozšířeným euklidovým algoritmem

21 1 0  
15 0 1 1
6 1 -1 2
3 -2 3 2
0      

tj D = 3 = -2 * 21 + 3 * 15 (viz poslední řádek)

Protože D dělí pravou stranu (l), můžeme psát l=2 * D = 2 * ( -2 * 21 + 3 * 15) = -4 * 21 + 6 * 15 = 6
Máme tedy jedno možné řešení, kde x1 = -4 a x2 = 6

To ale není jediné řešení. Všimni si, že když zmenšíš levého sčítance o S1 / D a snížíš pravého sčítance o S2 / D, potom se výsledek nezmění.
Kompletní řešení je tedy x = x1 + (S2 / D) * t y=x2 - (S1 / D) * t kde za t můžeš dosadit libovolné číslo
Když to dosadíš do původní rovnice výjde ti že l = x * S1 + y * S2 = (x1 + (S2 / D) * t) * S1 + (x2 - (S1 / D) * t) = (-4 + 5 * t) * 21 + (6 - 7 * t) * 15
Například pro t = 0 je l = -4 * 21 + 6 * 15 (tj naše řešení)
Pro t = 1 je l = 1 * 21 - 1 * 15 = 6
pro t = 4 je l = 16 * 21 - 22 * 15 = 336 - 330 = 6

Řešení je nekonečně mnoho.

Nahoru Odpovědět
19.11.2018 17:40
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Kubas129
Člen
Avatar
Odpovídá na Patrik Valkovič
Kubas129:20.11.2018 21:52

Já jsem ten kod nějak dokázal vytvořit ale mám problém, že mi vycházejí jen záporná řešení té rovnice, že jsou správný hlediska rovnosti ale délka segmentu tunelu být záporná nemůže :( neporadil by mi tu někdo ještě s tímto? :) dik moc

 
Nahoru Odpovědět
20.11.2018 21:52
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Kubas129
Patrik Valkovič:20.11.2018 23:40

Ale notak...samozřejmě že u příkladů výše budou vycházet záporné indexy. Nemůžeš ze souctů 15 a 21 vytvořit 6.
Jinak pro nezáporné indexy není nic snazšího než vyřešit -4+5t>0 resp. 6-7t>0.

Nahoru Odpovědět
20.11.2018 23:40
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.