Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Procedura Kropki - algorytm


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

#1 goopek

goopek

    Nowicjusz

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

Napisano 27.12.2010 - 12:27

Witam,
Proszę kosmonautów matematycznych ;) o pomoc w rozwiazaniu 2 algorytmow, mam takie zadania do policzenia i szczerze mowiac mam z nimi olbrzymi problem.

Bardzo prosze o nawet najmniejsza pomoc w tym temacie:

1 zadanie:

Dana jest procedura Kropki, która wypisuje na ekranie pewną liczbę kropek.
Kropki(n)

 if n = 1
      then Write(¡)

      else for i ← 1 to n − 1

                do Kropki(i)

            for i ← 1 to n

                do for j ← 1 to n


                       do Write(¡)

Ile dokładnie zostanie wypisanych kropek w zależności od liczby n?

--------------------------------------------

2 zadanie:

Pudełka i kule

Dane są ponumerowne kule (od 1 do n) i ponumerowane pudełka (od 1 do n). Każdą
kulę umieszczamy w losowo wybranym pudełku.
Pudełko może zawierać więcej niż jedną kulę. Załóżmy, że X jest numerem
na pudełku, które ma najmniejszy numer spośród wszystkich niepustych pu-
dełek. Jaka jest wartość oczekiwana X?

Kule umieszczamy w pudełkach w ten sposób, że każde pudełko przecho-
wuje dokładnie jedną kulę. Jeśli numer kuli jest taki sam jak numer pudełka,
to mamy do czynienia z trafieniem. Jaka jest wartość oczekiwana liczby tra-
fień?
  • 0

Afroman

    Kombinator

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

Napisano 25.09.2011 - 17:55

#2 janusz

janusz

    Wielki Analityk

  • +Mods
  • 3035 postów
1407
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 27.12.2010 - 19:34

Witam,
Proszę kosmonautów matematycznych ;) o pomoc w rozwiazaniu 2 algorytmow, mam takie zadania do policzenia i szczerze mowiac mam z nimi olbrzymi problem.

Bardzo prosze o nawet najmniejsza pomoc w tym temacie:

1 zadanie:

Dana jest procedura Kropki, która wypisuje na ekranie pewną liczbę kropek.
Kropki(n)

 if n = 1
      then Write(¡)

      else for i ← 1 to n − 1

                do Kropki(i)

            for i ← 1 to n

                do for j ← 1 to n


                       do Write(¡)

Ile dokładnie zostanie wypisanych kropek w zależności od liczby n?

--------------------------------------------

2 zadanie:

Pudełka i kule

Dane są ponumerowne kule (od 1 do n) i ponumerowane pudełka (od 1 do n). Każdą
kulę umieszczamy w losowo wybranym pudełku.
Pudełko może zawierać więcej niż jedną kulę. Załóżmy, że X jest numerem
na pudełku, które ma najmniejszy numer spośród wszystkich niepustych pu-
dełek. Jaka jest wartość oczekiwana X?

Kule umieszczamy w pudełkach w ten sposób, że każde pudełko przecho-
wuje dokładnie jedną kulę. Jeśli numer kuli jest taki sam jak numer pudełka,
to mamy do czynienia z trafieniem. Jaka jest wartość oczekiwana liczby tra-
fień?

zad. 1
W zależności do liczby n zostanie dokładnie wypisanych
 1 + n(n-1). kropek
Jeden temat - jedno zadanie patrz regulamin Forum.
  • 1

#3 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

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

Napisano 27.12.2010 - 21:47

Trochę niezbyt czytelnie jest napisany ten kod. Ja bym raczej powiedział, że liczba kropek dana jest wzorem \frac{n(3n-1)}{2}, a dla n=1 będzie dana wzorem n^2+1 :shifty: Jeżeli brać pod uwagę grupowanie spacjami itp., to można pominąć opcję dla n=1, będzie taka sama jak w ogólnym wzorze.
  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#4 goopek

goopek

    Nowicjusz

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

Napisano 28.12.2010 - 08:22

Wielkie dzięki.
A moglbys pokrótce napisać jak doszedles do tego rozwiązania? Wykorzystales jakies funkcje tworzące w rozwiązywaniu zależności rekurencyjnych?
  • 0

#5 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

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

Napisano 28.12.2010 - 12:08

Nie no, bez przesady. Zależności opisane w algorytmie są na tyle proste że nie wypada wyciągać takiej armaty jak funkcje tworzące :D Założę więc, że algorytm jest właściwie pogrupowany, tzn. że dla n=1 wypisana jest jedna kropka, a dla n\not= 1 będzie wykonany algorytm:


for i ← 1 to n − 1
	do Kropki(i)

for i ← 1 to n
	do for j ← 1 to n
		do Write(¡)

Jak widzisz, można ten algorytm podzielić na dwie części, które będą wykonane niezależnie od siebie. Zacznijmy może od części pierwszej. Warto sobie wypisać parę pierwszych wartości: dla n=2 mamy kropek 1, dla n=3 kropek będzie 1+2 i ogólnie dla jakiegoś n mamy ich 1+2+3+...+(n-1). Jest to suma ciągu arytmetycznego, więc 1+2+3+...+(n-1)=\frac{(n-1)(1+n-1)}{2}=\frac{n(n-1)}{2}. Teraz druga część. Zauważ, że wypisanie kropki jest tam powtarzane w sumie aż n\cdot n=n^2 razy. Więc ...

Ostateczna liczba kropek będzie dana wzorem: \frac{n(n-1)}{2}+n^2=\frac{n(3n-1)}{2}

Mało tego, wzór ten pasuje dla n=1: wtedy mamy \frac{1(3-1)}{2}=\frac{2}{2}=1, więc przypadek dla n=1 jest także spełniony. I nie trzeba było korzystać przy tym z funkcji tworzących ;)
  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#6 goopek

goopek

    Nowicjusz

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

Napisano 28.12.2010 - 13:58

Dziękuje Tomalla, bardzo mi pomogłeś :)
  • 0

#7 myself

myself

    Ułamek

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

Napisano 14.12.2011 - 18:09

Odświeżam temat, ponieważ również mam problem z wypisaną powyżej procedurą Kropki. Niestety dowiedziałem się, że nie można tego obliczyć na zasadzie ciągu arytmetycznego, jak pokazał Tomalla. Zamiast tego trzeba wyznaczyć wzór na ciąg rekurencyjny (albo iteracyjny) i dopiero go obliczyć. Nie wiem jak to ugryźć, nie jestem dobry w tych sprawach, czy w związku z tym ma ktoś jakiś pomysł (może Ty Tomalla?)? :)
  • 0

#8 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

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

Napisano 15.12.2011 - 18:30

Moim zdaniem masz rację i zarówno Tomalla jak i janusz podali nieprawidłowe rozwiązania.
Ja bym raczej coś takiego proponował:
Niech a_n będzie liczbą kropek wypisaną przez funkcję Kropki(n).
Oczywiście a_1 = 1. Można też sprawdzić, że a_2 = 5. Ogólnie z treści procedury wynika, że a_n = \sum_{i=1}^{n-1} a_i + n^2.
To jest równoważne temu że a_{n+1} = 2a_n +2n +1. Jak to się rozwiąże uwzględniając warunek początkowy to powinno wyjść coś koło a_n = 2^{n+1} + 2^n -2n -3.
  • 1

#9 Xitami

Xitami

    Wymierny

  • Użytkownik
  • 40 postów
9
Mały Pomocnik I

Napisano 17.12.2011 - 20:37

a_n=4a_{n-1}-5a_{n-2}+2a_{n-2}
  • 0

#10 myself

myself

    Ułamek

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

Napisano 18.12.2011 - 14:46

Dzięki za odpowiedzi.

Ereinion, Twój wzór ma sens. Czyli wychodzi z tego, że np:
a_3= 2^4 + 2^3 - 2*3 - 3= 15
a_4 = 2^5 + 2^4 - 2*4 - 3 = 37
itp.

I pytanie dla upewnienia się co z czego wynika: Czy dobrze rozumuję, że
treść procedury => a_n = \sum_{i=1}^{n-1} a_i + n^2 => a_{n+1} = 2a_n +2n +1 => a_n = 2^{n+1} + 2^n -2n -3?


Xitami, skąd się wziął taki wzór? Wydaje mi się dziwny, bo obliczając np a_2 wychodzi 4a_1 - 5a_0 + 2a_0,a przecież chyba nie ma 0-go wyrazu ciągu.
  • 0

#11 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

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

Napisano 18.12.2011 - 20:59

W miarę dobrze rozumujesz, tylko ważny jest jeszcze warunek a_1 = 1, bez niego ostatnia implikacja nie byłaby prawdziwa :)
  • 0

#12 Mariusz M

Mariusz M

    Wielki Analityk

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

Napisano 19.12.2011 - 10:08

Suma ciągu arytmetycznego bylaby gdyby np j bylo w zakresie od i do n
Ten else to jaki blok obejmuje
Pomysł z wykorzystaniem równania rekurencyjnego jest ok jako że procedura jest rekurencyjna

Użytkownik Mariusz M edytował ten post 30.01.2012 - 11:43

  • 0

#13 myself

myself

    Ułamek

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

Napisano 19.12.2011 - 12:51

Ereinion - tak, tak, o a_1 pamiętam :)


Mariusz M - twierdzisz, że powinno to tak wyglądać?:

a_n = \sum_{i=1}^{n-1} a_i + \frac{a_1+a_n}{2}n

A jak to się będzie miało do wynikających z tego pozostałych dwóch wzorów (a_{n+1} i a_n), bo podejrzewam, że też się zmienią w takim razie...
  • 0

#14 Xitami

Xitami

    Wymierny

  • Użytkownik
  • 40 postów
9
Mały Pomocnik I

Napisano 19.12.2011 - 19:00

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

Przepraszam, powinno być
a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}\\a_0=0
  • 0

#15 myself

myself

    Ułamek

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

Napisano 20.12.2011 - 12:57

Przepraszam, powinno być
a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}\\a_0=0

To ja znów mam pytanie - jak obliczyć a_2, skoro w tym wzorze na końcu jest 2a_{n-3}, więc wychodziłoby 2a_{-1}...
  • 0

#16 Xitami

Xitami

    Wymierny

  • Użytkownik
  • 40 postów
9
Mały Pomocnik I

Napisano 23.12.2011 - 07:48

a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}\\a_0=0,\quad a_1=1,\quad a_2=5
lub
\frac{x^2 + x}{-2x^3 + 5*x^2 - 4*x + 1}=x+ 5 x^2+ 15 x^3+ 37 x^4+ 83 x^5+ 177 x^6+ 367 x^7+ 749 x^8+ \dots
  • 1

#17 myself

myself

    Ułamek

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

Napisano 23.12.2011 - 18:42

ok, dzięki, już powoli to zaczynam kumać.

W podziękowaniu na Święta dostajesz ode mnie plusa :)
  • 0

#18 Xitami

Xitami

    Wymierny

  • Użytkownik
  • 40 postów
9
Mały Pomocnik I

Napisano 23.12.2011 - 23:53

zauważ, że 4, -5 i 2 to bardzo tajemnicze współczynniki
pasują do iluś tam początkowych wyrazów, ale czy pasują do wszystkich?
nie wiem.
A i na wzajemnie, życzę smacznego i wesołego :)
  • 0

#19 myself

myself

    Ułamek

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

Napisano 25.12.2011 - 18:52

Policzyłem kilka wyrazów wg podanego przez Ciebie wzoru, Xitami, i wynik zgadza się z wynikiem ze wzoru Ereinion tylko do a_9. Więc któryś z tych dwóch wzorów jest niepoprawny :)

Spróbowałem też wyliczyć coś ze wzoru Mariusza M, ale wynik wychodzi całkiem inny, np:

a_n = \sum_{i=1}^{n-1} a_i + \frac{a_1+a_n}{2}n
a_3 = \sum_{i=1}^{2} a_i + \frac{1+3}{2}3 = 6 + 6 = 12
a_4 = \sum_{i=1}^{3} a_i + 10 = 21 + 10 = 31

Chociaż chyba źle to robię, bo zakładam, że a_n = n, czyli np. a_3 = 3. No ale ja nie wiem ile wynosi a_3, własnie chcę to obliczyć, więc skąd mam wiedzieć co podstawić :P

Na ciąg arytmetyczny jest jeszcze wzór \frac{2a_1 + (n-1)r}{2}n, ale tu taj jest nieznane r, więc też lipa...

Zrobił mi się mętlik, podaliście mi kilka ciekawych wzorów, ale tylko częściowo się one zgadzają, nie wiem jak to połączyć w kupę i który ew. jest tym w 100% właściwym :)

Spróbuję jeszcze poczytać gdzieś o ciągach rekurencyjnych, ale nie wiem czy coś z tego wymodzę...
  • 0

#20 marcus

marcus

    Ułamek

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

Napisano 18.01.2012 - 21:51

Moim zdaniem masz rację i zarówno Tomalla jak i janusz podali nieprawidłowe rozwiązania.
Ja bym raczej coś takiego proponował:
Niech a_n będzie liczbą kropek wypisaną przez funkcję Kropki(n).
Oczywiście a_1 = 1. Można też sprawdzić, że a_2 = 5. Ogólnie z treści procedury wynika, że a_n = \sum_{i=1}^{n-1} a_i + n^2.
To jest równoważne temu że a_{n+1} = 2a_n +2n +1. Jak to się rozwiąże uwzględniając warunek początkowy to powinno wyjść coś koło a_n = 2^{n+1} + 2^n -2n -3.


To jest jedyne słuszne rozwiązanie wg mnie a raczej mojej implementacji tej procedury / funkcji w java ale ;(
w jaki sposób przejść od równania sumy które jest ok to ciągu jak ktoś może mi to wytłumaczyć wiem że to może jest dla niektórych proste ale ja z ciągów jestem noga ;(
  • 0