Diskuze: Algoritmus

Naučíme tě pracovat na home-office.

Zjistit více...

V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Kubas129

Člen

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

Patrik Valkovič

Tvůrce

Patrik Valkovič:17.11.2018 21:41

To vypadá jako úloha z FITu
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.

Kubas129

Člen

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

Peter Mlich

Člen

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 19.11.2018 15:57

Nahoru Odpovědět

19.11.2018 15:55

Patrik Valkovič

Tvůrce

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.

Kubas129

Člen

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

Patrik Valkovič

Tvůrce

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.