|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Slobodskoy 2:5015/128.22 23 Dec 2001 02:50:06
To : Medvedev Michael
Subject : RE:Помогите найти решение
--------------------------------------------------------------------------------
MM> Может кто-то подскажет мне идею решения задачи 1142 Relation с сайта
MM> acm.timus.ru - ну хотя бы математическую идею.
MM>
MM> --------------
MM> Дано натуральное n, 2 <= n <= 10
MM> За заданным n строются всевозможные отношения со знаками <, >, =. Hадо
MM> для заданного n найти количество таких отношений.
MM>
MM> Hапример, для n = 2 ответ 3. Всевозможные отношения: a = b, a < b, b <
MM> a. Для n = 3 ответ 13. Всевозможные отношения:
MM> a = b = c, a = b < c, c < a = b, a < b = c,
MM> b = c < a, a = c < b, b < a = c, a < b < c,
MM> a < c < b, b < a < c, b < c < a, c < a < b,
MM> c < b <a
Если я правильно понял условие, то у тебя, по-моему, неверный пример для n=3,
т.к. отсутствуют такие комбинации как, например, a<c=b, a=b>c,...
Общее решение должно выражаться формулой
[[n]C[2]]C[n-1]*3^(n-1),
где [n]C[r]: r
C
n
... если я, конечно, все правильно понял...
ПОКА!
--- F.I.P.S./32 v1.0r W95/NT [M]
* Origin: Жить вредно - от этого умирают! (2:5015/128.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
RE:Помогите найти решение 
