1) Найти сумму всех 10-значных чисел, получаемых при всевозможных перестановках цифр 4, 5, 5, 6, 6. 6, 7, 7, 7, 7.
2) Найти число различных подпоследовательностей длины (n-2) в слове (101010...10). n - четное.
2) Найти число различных подпоследовательностей длины (n-2) в слове (101010...10). n - четное.
-
-
08.10.2008 в 10:17почти не нахожу у себя ошибок.
Вот смотри. Заново:
1) Любое изъятие 10 и 01 даст нам одну и ту же новую последовательность. n1=1
2) Зафиксируем первую единицу (чтобы убрать). К ней подходит n-2 элементов. Каждый раз оставшаяся последовательность будет новой. n2=n-2
3) То же самое для последнего нуля. n3=n-2
Все три пункта не содержат ни одной одинаковой подпоследовательности.
4) Теперь разберемся с центральными элементами:
101010101010...101010
Выбирая любой элемент, мы одновременно фиксируем два соседних, т.к. их трогать нельзя. Иначе вернемся к п.1
То есть выбор:
101010101010...101010
автоматически влечет за собой выбор двух соседних единиц:
101010101010...101010
Выбирать мы можем из любых n-2 элементов, кроме крайних.
Значит первый кандидат на удаление выбирается n-2 способами; второй: n-5, т.к. выбрав первый, мы зафиксировали три, да два нельзя было изначально.
Аааа! Погоди! Это касается всех, кроме вторых от краев! Черт! Тут малость сложнее выйдет (((
Или проще, только я пока не вижу, как.
-
-
08.10.2008 в 11:46Пусть нам известно число подпоследовательностей длины (n-4) - S(n-2). Попробуем найти число подпоследовательностей длины (n-2) - S(n).
10101010......10 - последовательность длины n-2
Приписываем к ней 10:
10101010......1010 - последовательность длины n
Очевидно, что если не трогать последнюю 10, то число подпоследовательностей будет S(n-2).
Теперь будем определять новые подпоследовательности.
1) Если вычеркнуть 10101010......1010 или 10101010......1010, новой подпоследовательности не получится.
2) Остальные подпоследовательности будут новыми.
2а) Фиксируем последний ноль. Число подбора пары к ней будет (n-2)
2b) Фиксируем предпоследнюю единицу. Число подбора пары к ней будет (n-3)
Вот и все комбинации.
S(n) = (2n-5) + S(n-2)
-------------------------------
Решением этой реккуренты и будет S(n) = C(n-1,2) + 1
Для проверки: S(n) - S(n-2) = (n-1)(n-2)/2 - (n-3)(n-4)/2 = (n^2-3n+2)/2 - (n^2-7n+12)/2 = 2n -5
-
-
08.10.2008 в 12:26так у тебя же то же самое, что и у автора получилось?
-
-
08.10.2008 в 12:41Но решение другое. Могу отсканировать и выложить.
-
-
08.10.2008 в 12:57выложи, если не трудно)
но я всё-таки постараюсь сначала своё домучить!
-
-
10.10.2008 в 23:34у меня вышло)))
перебором) Без рекуррентных формул)
n0=1 — как и было: при выбрасывании любой пары 10 или 01.
Далее.
Фиксируем первый член. К нему в пару на выброс подходят все, кроме второго:
n1=n-2
В пару ко второму подходят все, кроме первого и третьего:
n2=n-3
В пару к третьему подходят все, кроме предшествующих ему и четвертого:
n3=n-4
В пару к четвертому:
n4=n-5
и т.д.
В пару к (n-2)-му члену подходит один единственный последний ноль.
n(n-2)=1
Это арифметическая прогрессия. Количество членов в ней n-2
S=((n-2)+1)/2 * (n-2) = (n-1)(n-2)/2
Общее число вариантов: S+n0=S+1= (n-1)(n-2)/2 +1