jak sprawdzić punkty wspólne dwóch ciągów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Rebus27
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 mar 2012, o 12:18
Płeć: Mężczyzna
Lokalizacja: Informatyka

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: Rebus27 » 22 wrz 2013, o 14:43

Mam takie dwa ciągi i chciałbym wyliczyć szybko ile mają w danym przedziale punktów wspólnych i jakie te punkty są:
Pierwszy ciąg \(\displaystyle{ x+y}\) wynik to pierwszy wyraz ciągu następny to wynik + y powiększony o 8 i znowu w następnym kroku wynik + y powiększony o 8 czyli np \(\displaystyle{ x=1, y=1}\) to tak \(\displaystyle{ 2,11,28,53...}\)
A drugi ciąg jest trochę inny i zawsze taki sam \(\displaystyle{ 0,8,24,48,80...}\) albo zaczynający się nie od 0 tylko od 4
czyli: \(\displaystyle{ 0,0+(1 \cdot 8)=8,8+(2 \cdot 8)=24,24+(3 \cdot 8)=48...}\)
w zasadzie potrzebuję jakiegokolwiek wspólnego punktu w danym przedziale
Czy istnieje jakaś metoda żeby to szybciej wyliczyć niż generować ciągi i porównywać ich kolejne wyrazy?
Ostatnio zmieniony 23 wrz 2013, o 09:57 przez yorgin, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7250
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 210 razy
Pomógł: 2879 razy

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: kerajs » 22 wrz 2013, o 18:30

Piszesz ten post już trzeci raz, a wciąż mętnie opisujesz powyższe ciągi .

Chyba chodzi ci o ciągi rekurencyjne:
\(\displaystyle{ a _{1} =x \wedge a _{n}=a _{n-1}+y+(n-1) \cdot 8}\)
\(\displaystyle{ b _{1} =t \wedge b _{n}=b _{n-1}+(n-1) \cdot 8}\)

Nie rozumiem dlaczego szukasz ,,łatwiejszego "sposobu. Przecież algorytm wyliczania wszystkich wyrazów obu ciągów w konkretnym przedziale i znalezienia powtarzających się liczb jest o wiele prostszy niż programowanie ,,łatwiejszego" sposobu, o ile taki by istniał.
A jeśli przedział w którym mogą być wspólne wyrazy obu ciągów jest duży to podziel go na mniejsze. Dla każdego dokonuj sprawdzenia i opróżniaj rejestry przechowujące wyliczone, zbędne już dane.
Ostatnio zmieniony 23 wrz 2013, o 09:57 przez yorgin, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.

Rebus27
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 mar 2012, o 12:18
Płeć: Mężczyzna
Lokalizacja: Informatyka

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: Rebus27 » 22 wrz 2013, o 22:06

No a gdyby istniała metoda która zamienia te dwa ciągi na jakieś równania nie wiem może nawet kwadratowe nie znam się na tyle po czym rozwiązanie od razu dałoby punkt wspólny to by nie było szybciej? Normalnie nic nie trzeba zapisywać po prostu dwie zmienne które są porównywane jeżeli wartość pierwszego ciągu jest większa to przejdź do następnego wyrazu ciągu drugiego i porównaj znowu jeśli mniejsza to przejdź do następnego wyrazu ciągu pierwszego... ale gdy moje przedziały będą może od 0 do 1000 cyfrowej liczby to ile ja mam czekać? Gdybym mieścił się w long longu to bym nie narzekał.

Awatar użytkownika
yorgin
Gość Specjalny
Gość Specjalny
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: yorgin » 22 wrz 2013, o 22:53

W innym temacie napisałem Ci, jak wygląda rozwiązanie rekurencji, z którą masz problem. Wzór ogólny to wielomian stopnia drugiego ze względu na \(\displaystyle{ n}\). Dwa wielomiany drugiego stopnia albo są równe wszędzie, albo mają jeden punkt wspólny, albo dwa. Pierwszy wariant wynika wprost z równości obu wielomianów. Drugi i trzeci to rozwiązanie równania kwadratowego ze względu na \(\displaystyle{ n}\) - to jest łatwe do zaimplementowania oraz wyliczenia. Poza tym przy takich ciągach oraz stosunkowo niskich wartościach początkowych \(\displaystyle{ x}\) oraz \(\displaystyle{ y}\) nie będziesz długo czekał na albo równe, ale brak równości. Wystarczy trywialna analiza na poziomie szkoły średniej, by to stwierdzić.

Rebus27
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 mar 2012, o 12:18
Płeć: Mężczyzna
Lokalizacja: Informatyka

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: Rebus27 » 23 wrz 2013, o 08:09

Ok to dobrze. A jeszcze jedno przy stosunkowo niskich wartościach \(\displaystyle{ x i y}\) ? A co gdy będą tak liczbami wielkości 100-cyfrowymi albo większe komputer mam nadzieję że nie będzie miał problemu. Kurcze muszę sobie poprzypominać wielomiany na co dzień się tego do programowania nie stosuje także dobrze że się da ale dziś mam korepetycje na gg więc jakiś tam matematyk mi to wyjaśni krok po kroku co ja muszę zrobić nie będę wam już zawracał głowy

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7250
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 210 razy
Pomógł: 2879 razy

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: kerajs » 23 wrz 2013, o 08:11

No to może dokończę, choć Yorgin już ci to napisał już dwa razy .

Powyższe ciągi mają wzory ogólne
\(\displaystyle{ a _{n} =x+(n-1) \cdot y+ \frac{(n-1) \cdot n}{2} \cdot 8}\)
\(\displaystyle{ b _{n} =t+ \frac{(n-1) \cdot n}{2} \cdot 8}\)
(lub takie jak podano ci w poprzednim poście, którego niestety wcześniej nie przeczytałem do końca )
Po podstawieniu za x,y,t odpowiednio 1,1,0 masz
\(\displaystyle{ a _{n} =4 \cdot n ^{2}-3 \cdot n}\)
\(\displaystyle{ b _{n} =4 \cdot n ^{2}-4 \cdot n}\)

Ineresuje cię aby \(\displaystyle{ a _{p}=b _{q}}\)
co daje równanie \(\displaystyle{ 4 \cdot p ^{2}-3 \cdot p=4 \cdot q ^{2}-4 \cdot q}\)
(dla innych x, y t będzie ono miało postać
\(\displaystyle{ x+(p-1) \cdot y+4 \cdot p ^{2}-4 \cdot p=t+4 \cdot q ^{2}-4 \cdot q}\) )


Równanie \(\displaystyle{ 4 \cdot p ^{2}-3 \cdot p=4 \cdot q ^{2}-4 \cdot q}\) ma dwie niewiadome więc jedną potraktuj jak parametr. Dla niewiadomej q masz równanie kwadratowe
\(\displaystyle{ q ^{2}-q+(0.75 \cdot p-p ^{2})=0}\)
które zwyczajnie rozwiązujesz, lub raczej piszesz program który sprawdza dla jakich naturalnych p otrzymane q jest naturalne.
Ostatnio zmieniony 23 wrz 2013, o 09:58 przez yorgin, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.

Rebus27
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 mar 2012, o 12:18
Płeć: Mężczyzna
Lokalizacja: Informatyka

jak sprawdzić punkty wspólne dwóch ciągów

Post autor: Rebus27 » 23 wrz 2013, o 23:52

I to jest odpowiedź, trzeba było tak od razu. Nie przypomina mi się, żeby mi ktoś coś takiego pisał. Albo ja nie umiem korzystać z tego forum... Mniejsza o to, ale i tak jutro mam korepetycje online z matematyki i się wszystko wyjaśni. Dzięki kerajs
Ostatnio zmieniony 24 wrz 2013, o 11:10 przez bakala12, łącznie zmieniany 1 raz.
Powód: Stosuj interpunkcję, bo zupełnie nie można zrozumieć co napisałeś.

ODPOWIEDZ