Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1 2
Zdravím, podle mě to nejde.
Já jsem vytvořil algoritmus, který najde první platnou kombinaci a skončí, má neomezený počet vnoření a chodí velmi rychle:
kill(all); load("opsubst"); Par(X,Y):=X*Y/(X+Y); Najdi(R, G):=block([M, N, P, S, D:[], Q:0, J, K:0], N: gcd(R,G), M: R/N, N: G/N, while is(N>0 and M>0) do ( K: K+1, if N<M then ( M: M-N, D: cons(P,D) ) else( N: N-M, D: cons(S,D) ) ), print("Počet odporů:",K), for J:1 thru length(D) do ( if D[J]=S then Q: Q+R else Q:'Par(Q,R) ), opsubst("Par", "Par", Q) )$ compile(Najdi); Najdi(1000, 420); ev(%);
Výsledek:
Počet odporů: 9 Par(Par(Par(Par(2000,1000)+1000,1000)+2000,1000),1000) 420
Pokud chceme najít všechny kombinace pak jsem se inspiroval kódem od Aleše. Ten prohledává všechny větve a pokud v nějaké větvi najde platné řešení pak tuto větev ukončí. Jeho složitost je 4^(N-1) testů (N je počet potřebných odporů), což jej dělá nepoužitelné pro větší počet odporů (zejména pro mého PC stařečka z roku 2008).
kill(all); load("opsubst"); Par(X,Y):=X*Y/(X+Y); Kombinace(Rz, W, N):= block([Q:[], R], Komb(U, X, Y, H, S):=block([Z, T], if H<N then ( /* Sériově - doleva */ Z: float(X+Y), T: S+R, if abs(Z-W)<1e-8 then ( Q: cons(T, Q) ) else ( Komb(U, Z, U, H+1, T) ), /* Sériově - doprava */ Z: float(X+Y), T: R+S, if abs(Z-W)<1e-8 then ( Q: cons(T, Q) ) else ( Komb(U, U, Z, H+1, T) ), /* Paralelně - doleva */ Z: float(X*Y/(X+Y)), T: 'Par(S,R), if abs(Z-W)<1e-8 then ( Q: cons(T, Q) ) else ( Komb(U, U, Z, H+1, T) ), /* Paralelně - doprava */ Z: float(X*Y/(X+Y)), T: 'Par(R,S), if abs(Z-W)<1e-8 then ( Q: cons(T, Q) ) else ( Komb(U, Z, U, H+1, T) ) ) ), Komb(Rz, Rz, Rz, 0, R), Q )$ compile(Kombinace); showtime: all$ /* první parametr - jednotná hodnota použitých odporů */ /* Druhý parametr - cílová hodnota odporu */ /* Třetí parametr - počet spojení (sériových a paralelních) pro 9 odporů to dělá 8 spojení */ L: Kombinace(1000, 420, 8)$ L: unique(sort(L))$ /* vyloučí opakující se zapojení */ showtime: false$ Vzorce: opsubst("Par", "Par", at(L, R=1000)); /* výpis všech nalezených zapojení */ Value: ev(Vzorce); /* číselné vyhodnocení všech zapojení pro kontrolu - musí dát 420 Ω */ length(Value); /* počet všech platných řešení */
Výsledek jsem uvedl v příspěvku 20#
Všechno běží pod Maximou.
Offline
↑↑ MichalAld:
Ty sérioparalelní kombinace myslím půjdou vygenerovat rekurzivní funkcí viz můj kód výše (měl jsem tam chybu, musí se doplnit 3 rekurzivní volání funkce (děkuji ↑↑ check_drummer: za upozornění)) a potom abecedním setříděním s odstraněním duplicit. Co se týká té polské notace, rozdíl mezi infixovou a postfixovou notací je jen v pořadí zápisu operátoru a nepoužití závorek ve výpisu:
kombinace(vnoreni-1, seriove, paralelne, '('+k1+'+'+k2+')', '('+k1+'|'+k2+')'); // infix kombinace(vnoreni-1, seriove, paralelne, k1+' '+k2+'+', k1+' '+k2+'|'); // postfix
Co přetrvává je, že neumím dokázat, jestli je takový výpis úplný.
Offline
↑↑ MichalAld:
Já používám P(,) a S(,) a můžeš zanořovat. Podle mě zjistit že jsou dva obvody ekvivalentní, bude NP úplný problém, ale možná se pletu.
Obecně musíš ověřit, že mají oba stejný symbol, tedy řekněme P a P(x,y) a P(u,v) se rovnají, pokud se rovnají první i druhé služby a nebo první s druhou a druhá s první.
Offline
Podle mě se bude muset v tom algoritmu někde udržovat nějaký seznam už vygenerovaných obvodů a ty pak mezi sebou kombinovat - jenom přikombinovávat další namísto ukládání si myslím nevygeneruje všechny možnosti.
Ale je možné že když jde o obvod s odporem o jedné hodnotě tak ano.
Já ten svůj program psal jak popisuju výše, ale je zmatečný, tak ho sem nechci dávat abych neztatil moc reputace. :-)))
v podstatě začnu s obvodem o jednom odporu a vždy se snažím vytvořit všechny kombinace (nxn - x2 - seriový a paralelní) z již doposud sestrojených n obvodů. A to opakuju stále dál. A ukládám je ty, kde jsem vygeneroval novou hodnotu odporu a nebo sice existující, ale s méně odpory.
Takže u mě je důkaz správnosti téměř triviální, ale nevím zda je to postup alespoň blízký optimálnímu.
Offline
Stránky: 1 2