Welcome Guest ( Log In | Register )

Help | Search | Members | Calendar

Pages: (4) « First ... 2 3 [4]   ( Go to first unread post )
Задачка из олимпиады
« Next Oldest | Next Newest » Track this topic | Email this topic | Print this topic
firewall
Posted: Mar 1 2009, 09:48

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

DZUK, лучше бы объяснил решение smile.gif оно то же, что и при двоичных числах с фибоначи, что значит... что он все-таки и так не догадается)

--------------------
Newbie(g)
 
     Top
DZUK
Posted: Mar 1 2009, 14:04

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

Ну тут все просто: определим f(n) как количество слов длиной n, подходящих нашим условиям. Предположим мы уже решили задачу для m<n, попробуем решить ее для n. На первое место у нас k-1 кандидатов (1,2,...,k). Тоесть искомое решение есть чето-то типо (k-1)*b, где b это количество слов длиной n-1, где не идут подряд два нуля(в этих словах на первом месте может быть и 0). Подсчитаем b. Если на первом месте не ноль, то количество таких слов по индуктивному предположению мы уже знаем - f(n-1), в противном случае где на втором месте не ноль будет опять-таки по индуктивному предположению как раз f(n-2). Отсюда получаем b=f(n-1)+f(n-2). Подставляем b и получаем искомую формулу- f(n)=(k-1)(f(n-1)+f(n-2)).

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
nop
Posted: Mar 1 2009, 17:55

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Спасибо, я и так понял, не нужно было обьяснять...

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
firewall
Posted: Mar 2 2009, 10:16

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of nop, since Mar 1 2009, 17:55...)
не нужно было обьяснять...

мб другим поможет

--------------------
Newbie(g)
 
     Top
DZUK
Posted: Mar 2 2009, 23:06

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

QUOTE (In the immortal words of firewall, since Mar 2 2009, 11:16)
мб другим поможет

Ну будем надеятся

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
DZUK
Posted: Mar 2 2009, 23:08

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

QUOTE (In the immortal words of nop, since Mar 1 2009, 18:55)
Спасибо, я и так понял, не нужно было обьяснять...

Пожалуйста

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
DZUK
Posted: Mar 3 2009, 00:11

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

Ну если вам интересно, то вот вам исчо задачка из олимпиады. На эллипсе располаются n точек. Соединяем их все вместе. Вывести максимальное число кусков эллипса.

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
66 replies since Oct 20 2008, 19:29 Track this topic | Email this topic | Print this topic
Pages: (4) « First ... 2 3 [4] 
<< Back to Programming languages

 




Arminco Global Telecommunications