Reszta Mac Donald: Zadanie dla LWG/Mariusz Oblicz resztę z dzielenia x¹⁰⁰⁰⁰ przez x⁵⁷−2x⁴ Zadanie na poziomie licealnym

Mariusz: Jakoś wpisy wskazują na coś innego

Mariusz: Moje wpisy pokazują aby nie oczekiwać pomocy na forach internetowych I miałem racje że Metis napisał "Zrozum kod w Pascalu i napisz kod w C++ od zera" dlatego że nie umie programować w C++ ani w Pascalu (później się do tego przyznał Ambitnemu) Twój spam też może wskazywać na to że nie umiesz pisać programów Znalazłem takie zadanie Masz punkt P o współrzędnych Xp, Yp, Zp oczywiście w przestrzeni. Masz punkt K kamery Xk, Yk, Zk. Masz też punkt, na który skierowana jest kamera Xc, Yc, Zc. No i jest jeszcze szerokość widzenia A (w stopniach lub radianach). Jak ze współrzędnych trójwymiarowego punktu P(Xp, Yp, Zp) uzyskać współrzędne 2D. Algorytm obowiązkowy przy drukowaniu trójwymiarowych scen. Wiadomo, że na drukarce (mimo że ma kontekst urządzenia) nie można (jako wektor) wydrukować scen wygenerowanych za pomocą OpenGL. Trzeba stworzyć algorytm rzutujący punkty, trójkąty, wieloboki, czyli stworzyć nowe obiekty 2D i przesłać np. przez GDI/GDI+ do drukarki Jeszcze napisz jakbyś wyeliminował punkty niewidoczne, tzn znajdujące się poza polem widzenia. Na zadania z sortowaniem takie jak np void Przesiewanie(int l, int p, int A[100]) { int x,i,j; x=A[l]; i=l; j=(2*i)+1; while(j<=p) { if(j<p && A[j]<A[j+1]) j++; if(x<A[j]) { A[i]=A[j]; i=j; j=(2*i)+1; } } A[i]=x; } void BudujStog(int n, int A[100]) { for(int i=(n−2)/2;i>=0;i−−) Przesiewanie(i,n−1,A); } void SortowanieStogowe(int n, int A[100]) { BudujStog(n,A); int x; for(int i=n−1;i>=1;i−−) { x=A[0]; A[0]=A[i]; A[i]=x; Przesiewanie(0,i−1,A); } } Gdzie tutaj jest błąd ? U Cormena można znaleźć taki pseudokod sortowania przez scalanie Merge(A,p,q,r) n₁←q−p+1 n₂←r−q for i←p to q do L[i−p+1]←A[i] for i←q+1 to r do R[i−q]←A[i] L[n₁+1]←∞ R[n₂+1]←∞ i←1 j←1 for k←p to r do if(L[i]≤R[j])then A[k]←L[i] i←i+1 else A[k]←R[j] j←j+1 MergeSort(A,p,r) if(p<r)then q←(p+r)/2 MergeSort(A,p,q) MergeSort(A,q+1,r) Merge(A,p,q,r) Pseudokod można by zmodyfikować 1. Wartownicy są niepotrzebni 2. Można użyć jednej tablicy pomocniczej zamiast dwóch 3 Można usunąć rekurencję z algorytmu Wyszukiwanie binarne Jeśli chodzi o algorytm rekurencyjny to najpierw sprawdzamy czy indeks początkowy jest większy od indeksu końcowego jeśli tak to zwracamy liczbę poza zakresem przedziału dla indeksów tablicy // dla tablic w stylu C może to być liczba −1 w przeciwnym przypadku liczymy środkowy indeks który przechowujemy w jakiejś zmiennej lokalnej Jeśli A[s]==x gdzie s− środek przedziału x podzukiwany element zwracamy indeks s w przeciwnym przypadku Jeżeli A[s]>x przeszukujemy tablice o indeksach p..s−1 w przeciwnym przypadku przeszukujemy tablice o indeksach s+1..r Tak zapisany algorytm rekurencyjny można zapisać w postaci iteracyjnej

Mariusz: Sata co do tego zadania z resztą to obliczenia pisemne trwałyby dość długo i zajęłyby dość dużo miejsca na papierze ale można napisać programik do dzielenia wielomianów z resztą Zdaje się że w Numerical recipes in C mają przykładową funkcję

Dziadek Mróz: Źle piszesz Mariusz Nie ten temat

Mariusz: Swoją drogą sprawdziłem tę funkcję do dzielenia wielomianów z resztą z Numerical Recipes in C i po zmianie z float na double działał z tym że miał dokładność obliczeń pozostawiała wiele do życzenia aby to poprawić trzeba by napisać własną arytmetykę zmiennoprzecinkową np na łańcuchach (w C mamy do dyspozycji jedynie tablice znakowe , w C++ ostatnio dopisali klasę łańcucha w Borland C++ 3.1 w którym to środowisku pisałem na lekcjach informatyki takiej klasy jeszcze nie mieli) Gdybyśmy w funkcji zostawili float to najprawdopodobniej doszłoby do przekroczenia zakresu Gdy napisałem tę procedurę w Pascalu to tylko Free Pascal skompilował ze względu na DOSowe ograniczenia środowiska borlandowskiego Gdybyśmy nie mieli pod ręką tej funkcji z Numerical Recipes to trzeba by było rozpisać dzielenie pisemne i na tej podstawie napisać odpowiednią funkcję czy procedurę Ciekawe czy da się zejść z czasem poniżej O(n²) w pesymistycznym przypadku Dziadek próbowałem się bawić klasami w C++ http://codepad.org/zn1NelMj Przydałoby się dopisać iteracyjną wersję sortowania przez scalanie , może łączenie naturalne a także usuwanie powtórzeń aby móc użyć tej klasy np do znajdowania otoczki na podstawie pseudokodu Cormena Funkcje tutaj napisałem na podstawie nieoptymalnego pseudokodu poza tym wstawianie w sposób uporządkowany może być zbyt wolne

Adamm: ja tą resztę obliczyłem jedynie za pomocą kalkulatora, i to w kilku linijkach pozdrawiam

Mariusz: Za pomocą programu w C (gcc) oraz w Pascalu (Free Pascal) wyszło 2¹⁸⁸x³⁶ Ciekawe jak te wielomiany dobrał Nie sądzę aby zrobił to losowo Jak na kogoś kto pisze odpowiedzi które nie wnoszą nic do wątku to podejrzane Ciebie Adasiu nie ciągnie do programowania ? Nawet tak dla zabawy albo aby raz na jakiś czas napisać programik na własne potrzeby

Adamm: ogólnie to wymyśliłem taki algorytm algorytm jest do dzielenia dowolnych wielomianów przez wielomiany typu xⁿ−ax^k gdzie n>k skupiamy się na jednym z jednomianów takiego wielomianu, np. x^m postępujemy w ten sposób, dokonujemy kolejnych dzieleń jak niżej m=m₁*n+r₁ k*m₁=m₂*n+r₂ ... k*m_n=0*n+r_n teraz reszta z dzielenia wielomianu x^m przez xⁿ−ax^k będzie taka sama jak wielomianu a^{(m₁+m₂+...+m_n)}*x^{(r₁+r₂+...+r_n)}=a^m'x^r jeśli r<n to mamy naszą resztę, jeśli r≥n, to postępujemy jak poprzednio tutaj n=57, a=2, k=4, m=10000 10000=175*57+25 700=12*57+16 48 <− już reszty nie daje x¹⁰⁰⁰⁰ <−> 2¹⁸⁷x⁸⁹ 89=57+32 4 <− nie daje reszty 2¹⁸⁷x⁸⁹ <−> 2¹⁸⁸x³⁶ czyli reszta: 2¹⁸⁸x³⁶

jc: Właśnie tak. Już nie raz tak liczyłeś.