Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Procedura Kropki - algorytm


  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
45 odpowiedzi w tym temacie

#21 myself

myself

    Ułamek

  • Użytkownik
  • 10 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 19.01.2012 - 18:07

O, fajnie, że ktoś odświeżył temat.

Okazuje się, że poprawnym rozwinięciem a_n = \sum_{i=1}^{n-1} a_i + n^2 jest ciąg
a_n=a_1+a_2+...+a_{n-1}+n^2
a_{n-1}=a_1+a_2+...+a_{n-2}+(n-1)^2<br />a_{n-2}=a_1+a_2+...+a_{n-3}+(n-2)^2<br />

itp. Może to było oczywiste, ale nie było podane.

Tylko teraz muszę z tego obliczyć wzór ogólny. Najprawdopodobniej poprawny podał Xitami a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}, gdyż zgadza się, że a_{10}=3049 (w przypadku wzoru Ereiniona a_{10}=3059, jeśli się nie walnąłem).

Więc Xitami, w jaki sposób wyszedł Ci taki wzór? Mógłbyś mi krok po kroku opisać? Bo chyba nie zgadywałeś :)

Czy można to obliczyć przez równanie charakterystyczne? Bo ono może być stosowane tylko do rekurencji liniowych.
  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#22 marcus

marcus

    Ułamek

  • Użytkownik
  • 6 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 19.01.2012 - 23:04

Jak już pisałem i suma i an podane przez Ereinion`a są poprawne zaimplementowałem wszystkie podane tutaj wzory i tylko to się zgadza w wynikach w przypadku n=10 wynik jest 3049 a wyraz następny z wzoru kolegi Ereinion`a 6119.
Więc chyba na pewno jest ok. Tylko cały czas nie wiem jak dojść do takiego rozwiązania bo suma wynika bezpośrednio z kodu programu, ale jak gość wykombinował an ??? To jest dla mnie zagadka. Ale cóż, stary jestem szkół nie mam co ja ta mogę wiedzieć. ;)
  • 0

#23 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 20.01.2012 - 17:33

Z którym konkretnie przejściem jest problem?
Z tym między a_n = \sum_{i=1}^{n-1} a_i + n^2 a a_{n+1} = 2a_n +2n +1,

czy może z tym między a_{n+1} = 2a_n +2n +1 a a_n = 2^{n+1} + 2^n -2n -3 ? :)
  • 0

#24 marcus

marcus

    Ułamek

  • Użytkownik
  • 6 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 20.01.2012 - 19:11

Z którym konkretnie przejściem jest problem?
Z tym między a_n = \sum_{i=1}^{n-1} a_i + n^2 a a_{n+1} = 2a_n +2n +1,

czy może z tym między a_{n+1} = 2a_n +2n +1 a a_n = 2^{n+1} + 2^n -2n -3 ? :)

Większy problem mam z a_{n+1} = 2a_n +2n +1 a a_n = 2^{n+1} + 2^n -2n -3 ?
Jakbyś mógł to rozpisać.
  • 0

#25 myself

myself

    Ułamek

  • Użytkownik
  • 10 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 20.01.2012 - 21:09

Jak już pisałem i suma i an podane przez Ereinion`a są poprawne zaimplementowałem wszystkie podane tutaj wzory i tylko to się zgadza w wynikach w przypadku n=10 wynik jest 3049 a wyraz następny z wzoru kolegi Ereinion`a 6119.


Ach, rzeczywiście zgadza się, niedokładnie liczyłem. Sorry.

Ereinion, ja bym prosił również o rozpisanie a_n = \sum_{i=1}^{n-1} a_i + n^2 => a_{n+1} = 2a_n +2n +1, bo nie za bardzo to rozumiem.
  • 0

#26 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 21.01.2012 - 00:20

Większy problem mam z a_{n+1} = 2a_n +2n +1 a a_n = 2^{n+1} + 2^n -2n -3 ?
Jakbyś mógł to rozpisać.


Jeśli wiemy już jaki jest jawny wzór na a_n, to wystarczy nam zwykła indukcja po n. Tzn sprawdzenie dla n=1 - OK, potem zakładamy, że dla jakiegoś n jest a_n = 2^{n+1} + 2^n -2n -3 i chcemy pokazać, że wtedy a_{n+1} = 2^{n+2} + 2^{n+1} -2n -5. No dobra, ale wiemy, że a_{n+1} = 2a_n +2n +1, no to podstawmy za a_n to co mamy w założeniu indukcyjnym, uprośćmy i powinno być ok.


Ereinion, ja bym prosił również o rozpisanie a_n = \sum_{i=1}^{n-1} a_i + n^2 => a_{n+1} = 2a_n +2n +1, bo nie za bardzo to rozumiem.


Ok, już się robi. Skoro a_n = \sum_{i=1}^{n-1} a_i + n^2, to jak sobie napiszę n+1 zamiast n to dostanę a_{n+1} = \sum_{i=1}^{n} a_i + (n+1)^2.

No fajnie, to odejmijmy stronami pierwsze równanie od drugiego i mamy:

a_{n+1} - a_n = \sum_{i=1}^{n} a_i - \sum_{i=1}^{n-1} a_i + (n+1)^2 - n^2

a_{n+1} - a_n = a_n + 2n+1

a_{n+1} = 2a_n + 2n+1

Koniec :)
  • 2

#27 marcus

marcus

    Ułamek

  • Użytkownik
  • 6 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 21.01.2012 - 09:49

no ok ale skąd wiemy jaki jest wzór na an bo an+1to rozumiem skąd się wzięło ale an po prostu nie czaje z jakiego założenia indukcyjnego ??
  • 0

#28 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 22.01.2012 - 01:11

Tak działa zasada indukcji matematycznej, po prostu.
http://lmgtfy.com/?q...ja matematyczna :)
  • 0

#29 marcus

marcus

    Ułamek

  • Użytkownik
  • 6 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 23.01.2012 - 18:29

ok. zrozumiałem. dzięki. to samo powiem na egzaminie tak działa indukcja panie prof.
  • 0

#30 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 23.01.2012 - 19:43

Możesz też podać panu profesorowi linka do tego tematu i w razie jakichkolwiek pytań niech tutaj napisze.
  • 0

#31 marcus

marcus

    Ułamek

  • Użytkownik
  • 6 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 25.01.2012 - 22:41

No na pewno by go zaciekawiło ;)
  • 0

#32 boowha

boowha

    Nowicjusz

  • Użytkownik
  • 1 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 23.03.2012 - 19:24

Witam. Mam problem z tym zadaniem. Rozumiem wyprowadzenie wzoru na a_{n+1} i jasny dla mnie jest powód późniejszego dowodu indukcyjnego wzoru a_{n} . Ale czy ktoś mógłby mnie oświecić jak wyprowadzić wzór na a_{n}?? czyli w skrócie jak poznać a_{n}. Z góry dziekuje za odpowiedzi. Nie musicie udzielać mi dokładnego opisu wystarczy powiedzieć jakiej metody użyć. Starałem sie użyć równań rekurencyjnych poziomu pierwszego ze stałymi współczynnikami ale powiem szczerze marnie to wyszło. Pozdrawiam.
  • 0

#33 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 24.03.2012 - 13:32

Jak wiesz już, że a_{n+1}=2a_n + 2n + 1 to dalej, trochę nieformalnie, możesz napisać

a_{n+1}=2a_n + 2n + 1 = 2(2a_{n-1 }+ 2(n-1) + 1) + 2n + 1 = 4a_{n-1} + 4(n-1) + 2 + 2n + 1 = 4(2a_{n-2 }+ 2(n-2) + 1) + 4(n-1) + 2 + 2n + 1 =

= 8a_{n-2} + 8(n-2) + 4 + 4(n-1) + 2 + 2n + 1 = \ldots = 2^n a_1 + (2^n + 2^{n-1} \cdot 2 + \ldots + 2^3 (n-2) + 2^2 (n-1) + 2^1 n) + (2^{n-1} + \ldots + 4+2+1) =

= 2^n + \sum_{k=0}^{n-1} 2^{k+1} (n-k) + 2^n - 1= 2^{n+1} - 1 + n \cdot \sum_{k=0}^{n-1} 2^{k+1} - 2 \sum_{k=1}^{n-1} 2^{k} k =

= 2^{n+1} - 1 + n(2^{n+1} - 2) - 2 (2^n \cdot n -2^{n+1} +2) =  2^{n+1} - 1 -2n + 2^{n+2} - 4 = 2^{n+2} + 2^{n+1} -2(n+1) - 3

No to jak zmienimy sobie n+1 na n, to dostaniemy a_n = 2^{n+1} + 2^{n} -2n - 3.

Użytkownik Ereinion edytował ten post 24.03.2012 - 13:33

  • 2

#34 Mariusz M

Mariusz M

    Wielki Analityk

  • Użytkownik
  • Redaktor
  • 859 postów
392
Instruktor II
  • Płeć:Mężczyzna

Napisano 09.10.2012 - 13:21

myself zdaje się że źle przeczytałem kod źródłowy
Pomysł Ereiniona powinien być dobry
  • 0

#35 ssid

ssid

    Nowicjusz

  • Użytkownik
  • 2 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 06.05.2013 - 02:32

podbiję ponieważ nie rozumiem ostatnich przejść

2^{n+1} - 1 + n \cdot \sum_{k=0}^{n-1} 2^{k+1} - 2 \sum_{k=1}^{n-1} 2^{k} k = 2^{n+1} - 1 + n(2^{n+1} - 2) - 2 (2^n \cdot n -2^{n+1} +2) = 2^{n+1} - 1 -2n + 2^{n+2} - 4 = 2^{n+2} + 2^{n+1} -2(n+1) - 3

dokładniej

jak 2ga suma zamieniła się na 2^n \cdot n -2^{n+1} +2

skąd się wzięła potęga n+2 w drugim od końca równaniu

i czemu -3 na samym końcu, (może przez porę) zdaje mi się że tam powinno być -5,(-1-4=-5) 

 

z góry dziękuję za pomoc, przepraszam za podbijanie starych tematów


Użytkownik ssid edytował ten post 06.05.2013 - 07:46

  • 0

#36 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 06.05.2013 - 21:34

1) spróbuj przez indukcję pokazać, ze ta druga suma właśnie tyle wynosi

 

2) stąd, że przy wymnażaniu drugiego nawiasu trafia się (-2) \cdot (-2^{n+1}) a to jest równe właśnie 2^{n+2}

 

3) temu, że -2 poszło do tego nawiasu: -2(n+1), więc zostało to -3, które sterczy samotnie na końcu :)

 

I nie musisz przepraszać, lepiej podbijać stare tematy, jeśli się czegoś z nich nie rozumie, niż zakładać bez sensu nowe :)


  • 2

#37 ssid

ssid

    Nowicjusz

  • Użytkownik
  • 2 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 21.05.2013 - 19:48

wybacz że znowu podbije temat jednak próbuje jakoś samemu dojść do tego jak przekształcić (jak to mówił mój wykładowca) to "łajno"

\sum_{k=1}^{n-1} 2^{k} k

ale coś mi chyba nie wychodzi

rozbijam to na 2 sumy

\sum_{k=1}^{n-1} 2^{k} \cdot \sum_{k=1}^{n-1} k

pierwszą jako szereg geometryczny obliczam 

\sum_{k=1}^{n-1} 2^{k} = 2 \cdot \frac{2^{n-1}-1}{2-1} = 2^{n} -2

drugą jako arytmetyczny

\sum_{k=1}^{n-1} k = \frac{2+(n-2) \cdot 1}{2} \cdot n-1 = \frac{n^{2}-n}{2}

 

co nie chce im się zsumować do 

2\cdot n-2^{n+1}+2

 

prosił bym o wskazówkę w którym miejscu robię błąd :)


Użytkownik ssid edytował ten post 21.05.2013 - 20:07

  • 0

#38 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 22.05.2013 - 19:46

\sum_{k=1}^{n-1} 2^{k} k

ale coś mi chyba nie wychodzi

rozbijam to na 2 sumy

\sum_{k=1}^{n-1} 2^{k} \cdot \sum_{k=1}^{n-1} k

 

 

Auć. Błąd jest już tutaj i to taki letalny...

 

Generalnie indukcja tu działa, ale jak miałeś już pochodne, to możesz też zbadać funkcję

 

f(x) = 2 \cdot \sum_{k=1}^{n-1} x^k = 2 \frac{x^n - x}{x-1}

 

Okazuje się, że ta suma, którą chcemy policzyć to po prostu f'(2). Wzór na pochodną ilorazu, podstawić x = 2 i gotowe.


  • 1

#39 dev

dev

    Nowicjusz

  • Użytkownik
  • 1 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 10.04.2014 - 21:33

Witam!

Przepraszam, że znowu odgrzebuję ten temat, ale jak widać zadanie z kropkami jest niesłabnącym szlagierem :D.

 

Drogi Ereinionie,

czy mógłbym prosić o dokładniejsze rozpisanie poniższych przejść? Zwłaszcza interesujące są dla mnie te tajemnicze 3 kropki w drugiej linii obliczeń:

 

Jak wiesz już, że a_{n+1}=2a_n + 2n + 1 to dalej, trochę nieformalnie, możesz napisać

a_{n+1}=2a_n + 2n + 1 = 2(2a_{n-1 }+ 2(n-1) + 1) + 2n + 1 = 4a_{n-1} + 4(n-1) + 2 + 2n + 1 = 4(2a_{n-2 }+ 2(n-2) + 1) + 4(n-1) + 2 + 2n + 1 =

= 8a_{n-2} + 8(n-2) + 4 + 4(n-1) + 2 + 2n + 1 = \ldots = 2^n a_1 + (2^n + 2^{n-1} \cdot 2 + \ldots + 2^3 (n-2) + 2^2 (n-1) + 2^1 n) + (2^{n-1} + \ldots + 4+2+1) =

= 2^n + \sum_{k=0}^{n-1} 2^{k+1} (n-k) + 2^n - 1= 2^{n+1} - 1 + n \cdot \sum_{k=0}^{n-1} 2^{k+1} - 2 \sum_{k=1}^{n-1} 2^{k} k =

= 2^{n+1} - 1 + n(2^{n+1} - 2) - 2 (2^n \cdot n -2^{n+1} +2) = 2^{n+1} - 1 -2n + 2^{n+2} - 4 = 2^{n+2} + 2^{n+1} -2(n+1) - 3

No to jak zmienimy sobie n+1 na n, to dostaniemy a_n = 2^{n+1} + 2^{n} -2n - 3.

 

Z góry dziękuję, chciałbym zrozumieć to rozwiązanie :).


Użytkownik dev edytował ten post 10.04.2014 - 21:34

  • 0

#40 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 11.04.2014 - 20:02

czy mógłbym prosić o dokładniejsze rozpisanie poniższych przejść? Zwłaszcza interesujące są dla mnie te tajemnicze 3 kropki w drugiej linii obliczeń:

 

Ten fragment =\ldots=, to miejsce gdzie ukrywa się indukcja matematyczna, dlatego napisałem, że taki zapis jest nieformalny.

Generalnie chodzi o to, że jak mam jakiś wyraz ciągu, to umiem go wyrazić przy pomocy poprzedniego wyrazu i jego indeksu: a_{n+1}=2a_n + 2n + 1


No i zaczynając od a_{n+1} cały czas korzystam z powyższej tożsamości i dostaję w wyniku wyraz ciągu o indeksie o 1 mniejszym plus jakieś "śmieci".
a_{n+1}=2a_n + 2n + 1 = 2(2a_{n-1 }+ 2(n-1) + 1) + 2n + 1 = 4a_{n-1} + 4(n-1) + 2 + 2n + 1 = 4(2a_{n-2 }+ 2(n-2) + 1) + 4(n-1) + 2 + 2n + 1 =

= 8a_{n-2} + 8(n-2) + 4 + 4(n-1) + 2 + 2n + 1 = \ldots =

 

No i teraz zastanawiam się, kiedy taka zabawa się skończy, tzn kiedy nie będę mógł już zastosować mojej świetnej tożsamości. Ano wtedy jak zjadę z indeksem wyrazu do 1.

Dobrze, ale co będzie stało przy a_{1}? Przy a_{n+1} stało 1, przy a_{n} stało 2, przy a_{n-1} było 2^2 a przy a_{n-2} stało 2^3.

To przez analogię, przy a_{1} obstawiam, że będzie 2^n.

Tak samo, patrząc jakie "śmieci" otrzymywałem w kolejnych krokach, próbuję wywnioskować jakie "śmieci" dostanę na końcu. Wychodzi mi coś takiego:

 

=2^n a_1 + (2^n + 2^{n-1} \cdot 2 + \ldots + 2^3 (n-2) + 2^2 (n-1) + 2^1 n) + (2^{n-1} + \ldots + 4+2+1) =

 

A teraz to już została tylko kosmetyka:

= 2^n + \sum_{k=0}^{n-1} 2^{k+1} (n-k) + 2^n - 1= 2^{n+1} - 1 + n \cdot \sum_{k=0}^{n-1} 2^{k+1} - 2 \sum_{k=1}^{n-1} 2^{k} k =

itd.

 

Mam nadzieję, że co nieco się wyjaśniło :)


  • 0