Skocz do zawartości


Zdjęcie

Dzielenie wielomianów, schemat blokowy


  • Zaloguj się, aby dodać odpowiedź
791 odpowiedzi w tym temacie

#21 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 20 sierpień 2015 - 15:06

Podsumowując. W wolnej chwili wkleję wyprowadzenie wzoru, bez przekształcania. Właściwie jest więcej operacji, bo wyprowadzamy osobno wynik i osobno R(n), ale jest mniej pętli i wychodzi znacznie oszczędniejszy program. Szkoda, że mam tak mało odpowiedzi. Już dawno wkleiłbym rozwiązanie gdyby była jakaś dyskusja a tak nie widzę sensu.


  • 0


#22 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 15 październik 2015 - 09:13

Żeby nie pozostać gołosłownym. Właściwie zastanawiam się czy ten sposób jest prawidłowy, więc wkleje to co mam i prosiłbym o komentarz w tej sprawie. 
Z założenia powinno wyjść to samo co ręcznę przekształcanie, ale wiecie założenia swoję a realia pokazują co innego. A więc do dzieła:
1. Zaczynamy od zwykłego dzielenia metodą Hornera
2. Otrzymujemy pierwszy współczynnik i tu wskakują moję zmiany, 
bo żeby otrzymać upragniony wielomian, musimy zastosować wybieg, w którym do x dopisujemy jeden z pierwiastków dzielnika.
Komplikuje to nieco obliczenia, ale całościowo wychodzi mniej obliczeń niż przekształcanie ręczne.
3. Po przekształceniu wielomianu otrzymujemy Resztę , którą przekształcamy, 
sposobem z liczenia pochodnej. jest to bardzo przyjemny wzór. 
Pierwszy n jest znany, a kolejne wychodzą rekurencujnie.

Teraz moję pytania? Czy takie rozumowanie nie jest zbyt naiwne, 
ponieważ przy ręcznym przekształcaniu, niejako dzielę osobno przez każdy pierwiastek 
i otrzymuję, minimalną resztę. 
Tym sposobem omijam to przekształcanie, ale nie mam pewności czy reszta będzie minimalna.

Mniej więcej podobnie ma się sprawa z wzorem Taylora.
Właściwie chodzi o wyprowadzenie pochodnych wyniku, z wyżej zaprezentowanej metody, wynika, 
że się da. O ile ta metoda jest prawidłowa. Znając pochodne można łatwo wyznaczyć wzór Taylora. 

  • 0

#23 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 16 październik 2015 - 09:30

Właśnie. Dla mnie ten wzór wydaje się prosty, bo zapomniałem dopisać o jednym udogodnieniu. Jak dla człowieka wszystko wydaje się oczywiste to później są takie skróty myślowe. A więc aby nie przekształcać ręcznie całego wzoru, stosuję wybieg, w którym przed całym dzieleniem przekształcam dzielną i dzielnik w  Sumę a(k) (x-y)^k. Gdzie (x-y) jest pierwiastkiem który użyłem do dzielenia. Pozwala nam to ominąć dzielenie wzorem Hornra i skraca algorym do przysłowiowego dodawania i odejmowania współczynnika t= (x-y). Teraz myślę, że zgrabniej to wygląda. Sorki za skróty myślowe.


  • 0

#24 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 17 październik 2015 - 09:27

Jak już tyle napisałem, to w wolnej chwili wkleje wzór z pochodnymi. Tylko na razie nie mam motywacji, ale trzeba w końcu to skończyć.


  • 0

#25 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 17 październik 2015 - 17:46

Piszę z tableta więc nie będę wyprowadzał teraz wzoru. Tylko wypunktuje sobie założenia. Kiedy polaczymy sumę ciągu i inkrementcję nie musimy przejmować się silnia. Wychodzi zgrabny program do liczenia pochodnych, a co za tym idzie nie musimy przekształcać za pomocą t. Tylko liczymy pochodne. Wydaje mi się jednak, że sumarycznie wykonany więcej kroków. Po za tym nie obejdzie się bez przekształcenia funkcji a to jest bardzo obciążające programowo.

 

 Próbowałem na szybko wyprowadzić ten wzór, ale z nim jest problem. mianowicie. Koncepcje mam, ale jest tam tyle operacji, jak z tym pierwszym programem, ile razy bym go nie wyprowadzał zawsze mam inny efekt koncowy. Nie chcę też żeby ktoś za samo techniczne poprawienie gotowca, cały splendor zgarnął.

 

ps. Nie naleze do ludzi, którym zależy, wiec prawdopodobnie, któregoś dnia , pod wplywem impulsu, wkleje niekompletny algorytm, a wy sobie poprawiajcie. Póki co planuje sam go skończyć.


  • 0

#26 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 20 październik 2015 - 00:19

Ok. To w końcu napiszę wyprowadzenie wzoru taylora. Więc zacznijmy od tego, że pochodne to nic innego jak początkowe zawirowania proporcji dla poszczególnych F(y) funkcji x^n. Wykorzystując wzór Suma a(k) (x-p)^n +R(n) jasno to widzimy. Tu powinienem zakończyć, bo reszta jest oczywista, ale przejdzmy do konkretów. Musimy dla dobra przekształcenia poczynić pewne założenie. A więc f(x) nas kompletnie nie interesuje, więc dla dobra przekształceń, weźmy najmniejszy możliwy do tych celów x, a jest nim stopień n dzielnej. A więc, na chwile, zakładamy, że x jest stały równy n-temu stopniowi dzielnika. Musimy więc policzyć F(n) dzielnika i dzielnej, to nieuniknione. A pisałem już wcześniej, że n wyniku równa się n dzielnej - n dzielnika pozostaje ustalić a(k). Dzielimy więc otrzymane F(n) i wychodzi gotowe. a z indeksem (n) zarazem 1 pochodną, reszta jest banalna. Mamy a(k)(x-p) dzielnej wykonujemy obliczenia jak w przypadku współczynnika t i mamy wielomian o stopień niższy. Pamiętamy, że z dzielenia f(n) pozostała reszta posłużymy się nią do wyliczenia pozostałych pochodnych. Skoro dzielna jest już podzielona i mamy wyliczoną pochodną dla ntego stopnia, to interesuję nas dzielnik o stopniu Suma a(k-1)^n-1, liczymy więc F(n-1) pozostałego ciągu. Kolejną pochodną będzie wynik dzielenia reszty z poprzedniego dzielenia i Suma a(k-1)^n-1 dzielnej, i analogicznie do końca.


  • 0

#27 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 20 październik 2015 - 00:33

Gdzieś zrobiłem literowke jak wrócę z urlopu to poprawie
  • 0

#28 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 25 październik 2015 - 23:04

Trochę myślałem o tym ostatnim sposobie. Doszedłem do wniosku, że chciałem zrobić za dużo rzeczy na raz. W tym algorytmie kryją się dwa wzory jeden na a(k), drugi na pochodne. Ten na a(k) jest banalny i myślę, że na dniach wkleję go tutaj, a wzór z pochodnymi wydaje się bardziej złożony i muszę go jeszcze dopracować.


  • 0

#29 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 26 październik 2015 - 06:29

Ok. Teraz mam chwilę to napisze małe co nieco. Zacznę od wychwalania tej metody. Czyli nie przekształcamy tutaj współczynników 9c5c7d22e5aac671da54634e0b6d29f8.png, więc nie interesują nas skrajnie duże współczynniki k, po prostu przekształcamy wzór na całkiem nowy, a nie stosujemy pitu pitu, jak przy innych wzorach. Kolejnym plusem jest to, że nasze 7faabc116725287b21a12179fff0819f.png jest znacznie mniejsze i przy dokładnym liczeniu, wynosi niewiele ponad 3438618650e2b7ab10d4cb7ffcd8408c.png, pokusiłbym się o samą liczbę, ale zostawiam margines na przybliżenia. Minusem jest duże obciążenie programowe.
Teraz przejdźmy do konkretów:
1 Co zauważyłem:
Weźmy zwykłe dzielenie.
-Przykładowe dc42fc78532e17c6df7ca6a58e4e005c.png bierzemy
da4fb5c6e93e74d3df8527599fa62642.png czyli mamy zmienną tablicę a i sprawdzamy czy dzielnik jest większy od pierwszego elementu czyli c4ca4238a0b923820dcc509a6f75849b.png,
- jeśli nie bierzemy kolejny kolejny element tablicy i porównujemy
- kolejnym elementem jest wiadomo odejmowanie tego nie trzeba tłumaczyć pozostaje d3d9446802a44259755d38e6d163e820.png
- następnie niejako "dopisujemy" do d3d9446802a44259755d38e6d163e820.pngd02c4c4cde7ae76252540d116a40f23a.png i dodajemy e4da3b7fbbce2345d7772b0674a318d5.png, ja spojrzałem na zagadnienie inaczej:


 


  • 0

#30 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 26 październik 2015 - 06:30

Mianowicie patrze na system liczbowy, czyli u podstawy mamy d3d9446802a44259755d38e6d163e820.png,
-czyli dzielnik wygląda na początku: da6cc7670977a8251015284be504a45b.png
- obecnie dzielna wynosi 65ec1ccfb92ecf964ab9643c24f64a50.png a dzielna 919d64948ba7c3c1e4af473249c8faae.png
- czy coś to zmienia, oczywiście, że nie wynik pozostaję ten sam, ale zauważcie idę.
- Gdy zamiast systemu dziesiętnego użyjemy inny system liczbowy, teraz jesteśmy sobie w stanie z tym poradzić. Wcześniej była by to dla nas czarna magia. Dalsze liczenie mija się z celem, już osiągnąłem swój skutek. icon_smile.gif
2 Jakie wyciągnąłem wnioski:
- można to zastosować dla dowolnego systemu liczbowego nie koniecznie liniowego, ale wielomian, czy logarytm też się nada.


  • 0

#31 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 26 październik 2015 - 06:30

3. Przejdźmy do sedna:
-Bierzemy Wielomiany: dzielnik, dzielna i wynik
a29b87ca913ada8421eeeb15525bcecf.png
4 Założenia
-50bbd36e1fd2333108437a2ca378be62.png nas nie interesuje, więc bierzemy najmniejszy możliwy 9dd4e461268c8034f5c8564e155c67a6.png, czyli równy 7b8b965ad4bca0e41ab51de7b31363a1.pngdzielnika, i będzie on podstawą liczbową naszego ciągu.


 


  • 0

#32 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 26 październik 2015 - 06:30

- liczymy a2f04f05381d50c6b30a094fdae98b25.png dzielnej, otrzymujemy liczbę.
- O czym musimy pamiętać naszym systemem liczbowym jest system o podstawie 9dd4e461268c8034f5c8564e155c67a6.png, czyli nie kończymy na 9 tylko lecimy dalej a, b, aż do x (to ważne w dalszej części), ale my przekształcamy ten system dla ułatwienia wizualnego, komputer wcale nie musi w programie przekształcać, zaoszczędzi nam to kilka cykli icon_smile.gif
-bierzemy a z indeksem 7dbac31d74aa59a0615ff8d710e631f7.png
-sprawdzamy czy otrzymana liczba nie jest większa od naszego f(y) dzielnika
- jeśli nie dopisujemy kolejny 53b5242f6dfb4ae87fd54adc38ed57c0.png, pamiętając o tym, że u podstawy mamy 9dd4e461268c8034f5c8564e155c67a6.png, więc wychodzi np. 74aefa13d6ab8e4bfbd241583749dfe8.png czyli 331e9ee589219df2a941fe5f15267fc6.pngczyli 9143bc5385030be08b0d58a60336b1e3.png


  • 0

#33 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 26 październik 2015 - 06:30

- jednocześnie zmniejszamy stopień wielomianu dzielnika na 34d290b0b8cc714cc1d50dc6586885d4.png
- liczymy a2f04f05381d50c6b30a094fdae98b25.png dzielnika, sprawdzamy czy otrzymana dzielna jest większa od naszego a2f04f05381d50c6b30a094fdae98b25.pngdzielnika
- jeśli nie powtarzamy procedurę aż do skutku.
- otrzymujemy 0cc175b9c0f1b6a831c399e269772661.png z indeksem 8ce4b16b22b58894aa86c421e8759df3.pngwyniku.
- "Wiemy", że 9c5c7d22e5aac671da54634e0b6d29f8.pngwyniku to liczby całkowite, więc nie musimy liczyć dzielnej do nie wiadomo ilu miejsc po przecinku, to także duże ułatwienie icon_smile.gif
- powtarzamy procedurę do końca

W razie pytań piszcie.


  • 0

#34 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 26 październik 2015 - 06:31

Nie myślcie, że nabijam sobie posty, zwyczajnie ilość grafik miałem przekroczoną


  • 0

#35 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 29 październik 2015 - 08:48

Czy widzicie to co ja? Ten ostatni algorytm jest wprost idealny do porównywania wielomianów. Wychodzi piękny algorytm sortowania.


  • 0

#36 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 29 październik 2015 - 09:36

Więc do dzieła. Zauważmy, że w otrzrymanym ciągu, maksymalna proporcja w pojedynczym x^n do sumy pozostałych a(k-1) x^(n-1), dla . Wynosi 2^n, może oczywiście być mniejsza, ale to granica. Co nam to mówi, że jeśli weźmiemy, dowolną ilość, wielomianów. To porównując wielomiany, przekształcone tym algorytmem, nie musimy porównywać całych ciągów. a tylko do momentu gdy współczynniki z indeksem x^n nie są równe. Zauważmy, że dobrym pomysłem byłoby, wyprowadzać te ciągi z użyciem tego samego x, również ułatwi nam to porównywanie.


  • 0

#37 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 25 listopad 2015 - 06:10

Żeby nie było, ta liczba może być ogromna, a mówimy tu o proporcji, Zastanawiam się czy nie wkleić wyprowadzenia kolejnego wzoru, właściwie większa część już tu jest. Wy to byście się podknęli o wzór i byście go obeszli i powiedzieli kto normalny postawił tu tą górę. :)


  • 0

#38 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 05 grudzień 2015 - 09:19

Witam ostatnio obejrzałem program o nowinkach technologicznych. Bardzo mnie on poruszył. Mówiono w nim, że pomysł jest bezwartościowy a cała gloria należy się techniką. To zamyka moją kariere wynalacy, niech sobie sami wynajdują jak są tacy bystrzy. Najchętniej pokasowałbym przy tym wszystkie moję wpisy, niestety to awykonalne, bo na pewno one już dawno krążą w sieci. Nie dość, że kradną to jeszcze nie mają szacunku do pracy włożonej w to dzieło.


  • 0

#39 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 07 grudzień 2015 - 08:27

Z nowuw nie mogę edytować.

 

Zauważcie, że dopierto jeden z tych wzorów bazuję na zagłębieniu się w algorytm. Ja proponuję pójście tą drogą, jak już pewnie zauważyliście (algorytm jest prosty). Jeśli nic nie znajdziecie wkleję to rozwiązanie. Liczę jednak na was.


  • 0

#40 Dreamer

Dreamer
  • Użytkownicy
  • 870 postów

Napisano 07 grudzień 2015 - 21:35

wlasciwie chcialem spróbować z proporcją z poszczegolnymi n ami, ale utknalem w martwym punkcie. nie wszystko musi się udawac. jak wiecie do policzenia ciagu wystarcza 3 elementy a tu mamy dowolną ich ilosc, musze jeszcze nad tym pomyslec. wystarczyłoby wyprowadzic ciag na podstawie znannych nów tym badziej, że max stopien wielomianu koncowego jest znany


  • 0


Użytkownicy przeglądający ten temat: 0

0 użytkowników, 0 gości, 0 anonimowych