|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
Походу я немного неправ.Но реальная формула должна быть похожа на эту (понятно откуда она берется (?))
Наверное проще посчитать на компе: смотря что требуется ответ или асимптотика
|
|
|
Agassi
|
|
|
|
(172.16.3.63)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
|
|
|
Agassi
|
|
|
|
(172.16.3.63)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
"понятно откуда она берется"?
нет, пока не понятна
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
2^n - c(1)*2^(2n-2) - c(2)*2^(2n-4) - c(3)*2^(2n-6)-...
.. -c([n/2])*(2 или 1 в зависимости от четности n)
с(1)=2
c(2)=2
c(3)=4
c(4)=6
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
Меня с компа сейчас сгонят...
|
|
|
Solver
|
|
|
|
(172.16.2.160)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Ты попробуй туда что-нибудь подставить (2 например), короче это не она.
|
|
|
|
|
>>2^n - c(1)*2^(2n-2) - c(2)*2^(2n-4) - c(3)*2^(2n-6)-...
>>.. -c([n/2])*(2 или 1 в зависимости от четности n)
для n=4:
2^4-2*2^(2*4-2)-2*2^(2*4-4) = 16-128-32=-144 ?!?!?!
|
|
|
Agassi
|
|
|
|
(172.16.3.63)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Последнее соотношение точно неправильное, ведь 2^n - ... будет отрицательным числом
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
2^4-c(1)*2^2-c(2)*2^0=16-2*4-2*1=16-8-2=6
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
sorry там степени не 2^(2n-k) а 2^(n-k)
|
|
|
Edward
|
|
|
|
(172.16.4.30)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Каждая сложная проблема имеет простое, доступное для понимания неправильное решение. (с) 
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
2^n - c(1)*2^(n-2) - c(2)*2^(n-4) - c(3)*2^(n-6)-...
.. -c([n/2])*(2 или 1 в зависимости от четности n)
с(1)=2
c(2)=2
c(3)=4
c(4)=6
|
|
|
Agassi
|
|
|
|
(172.16.3.63)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Поясни немного, пожалуйста, как получилось это соотношение, тогда легче будет понять верно оно или нет.
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
Тут ведь был еще топик насчет неправильной формулы для 4х?  ))))
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
Считаем хорошие посл-ти как разность 2^n и плохие
а плохие получаются так: берем АВА
где А-хорошая посл-ть длины k
В - произвольная длины 2n-k
и суммируем по всем длинам А от 1 до [n/2]
причем с(1)=2
|
|
|
russoul
|
|
old hand
|
|
|
|
|
|
|
Рег.: 05.09.2002
|
|
Сообщений: 895
|
|
|
|
Рейтинг: -13
|
|
|
Меня с матом выгоняют из-за компа..
sorry
|
|
|
Agassi
|
|
|
|
(172.16.3.63)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Но тогда среди отнятых вида ABA будут попадаться и хорошие же? Не так ли?
|
|
|
Solver
|
|
|
|
(172.16.2.160)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Это я слегка ошибся, такая формула будет неверна, начиная с n=6.
|
|
|
Agassi
|
|
|
|
(172.16.3.63)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
Т.е. полученное выражение заведомо >= ответа
|
|
Список
Плоский
Дерево
