Просто торможу как удав по песку.
Сейчас я вас насмешу. Есть такой простейший код:
f += df;
df += ddf;
ddf += dddf;
Допустим, что он выполняется 2 раза. Надо написать код, дающий результат, эквивалентный выполнению приведенного кода дважды, но тоже в три выражения, а не в шесть. На самом деле все сложнее. Вместо 2 может быть некое K, необязательно целое. Может быть как меньше единицы, так и больше. И может быть отрицательным, что эквивалентно откату назад.
MS>Допустим, что он выполняется 2 раза. Надо написать код, дающий результат, эквивалентный выполнению приведенного кода дважды, но тоже в три выражения, а не в шесть. На самом деле все сложнее. Вместо 2 может быть некое K, необязательно целое. Может быть как меньше единицы, так и больше. И может быть отрицательным, что эквивалентно откату назад.
По рекурентным соотношениям можно вывести все что угодно:
fi+1 = fi + dfi;
dfi+1 = dfi + ddfi;
ddfi+1 = ddfi + dddfi;
dddfi+1 = dddfi;
Пусть K = 3, тогда
f1 = f0 + df0;
df1 = df0 + ddf0;
ddf1 = ddf0 + dddf0;
dddf1 = dddf0;
f2 = f1 + df1 = f0 + df0 + df0 + ddf0 = f0 + 2df0 + ddf0;
df2 = df1 + ddf1 = df0 + ddf0 + ddf0 + dddf0 = df0 + 2ddf0 + dddf0;
ddf2 = ddf1 + dddf1 = ddf0 + dddf0 + dddf0 = ddf0 + 2dddf0;
dddf2 = dddf0;
f3 = f2 + df2 = f0 + 2df0 + ddf0 + df0 + 2ddf0 + dddf0 = f0 + 3df0 + 3ddf0 + dddf0;
df3 = df2 + ddf2 = df0 + 2ddf0 + dddf0 + ddf0 + 2dddf0 = df0 + 3ddf0 + 3dddf0;
ddf3 = ddf2 + dddf2 = ddf0 + 2dddf0 + dddf0 = ddf0 + 3dddf0;
dddf3 = dddf0;
Для отрицательных K:
fi+1 = fi + dfi; -> fi = fi+1 - dfi = fi+1 - dfi+1 + ddfi = fi+1 - dfi+1 + ddfi+1 - dddfi+1;
dfi+1 = dfi + ddfi; -> dfi = dfi+1 - ddfi = ...;
ddfi+1 = ddfi + dddfi; -> ddfi = ddfi+1 - dddfi = ...;
dddfi+1 = dddfi; -> dddfi = dddfi+1 = ...;
Правда, на обобщение чего-то голова уже не варит.
Здравствуйте, McSeem2, Вы писали:
MS>Просто торможу как удав по песку.
MS>Сейчас я вас насмешу. Есть такой простейший код:
MS>MS>f += df;
MS>df += ddf;
MS>ddf += dddf;
MS>
MS>Допустим, что он выполняется 2 раза. Надо написать код, дающий результат, эквивалентный выполнению приведенного кода дважды, но тоже в три выражения, а не в шесть. На самом деле все сложнее. Вместо 2 может быть некое K, необязательно целое. Может быть как меньше единицы, так и больше. И может быть отрицательным, что эквивалентно откату назад.
Пусть у нас
Ai = Ai-1 + Bi-1
Bi = Bi-1 + Ci-1
Ci = Ci-1 + D
И известны D, C0, B0, A0
Тогда для положительных
Ak = A0 + k*B0 + F(k-1)*C0 + G(k-2)*D
Bk = B0 + k*C0 + F(k-1)*D
Ck = C0 + k*D
Где F(k) = 0, если k < 0 и F(k) = СУММ(1,k), если k >= 0 (1, 3, 6, 10...)
G(k) = 0, если k < 0 и G(k) = СУММ(F(i)), если k >=0 (1, 4, 10, 20...)
Для отрицательных
A-k = A0 - k*B0 + F(k-1)*C0 - G(k-2)*D
B-k = B0 - k*C0 + F(k-1)*D
C-k = C0 - k*D
(Если нигде не ошибся)
Для вещественных можно получить значения до ближайшего меньшего по модулю целого, а потом выполнить преобразование для дробной части.
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
Здравствуйте, McSeem2, Вы писали:
Обозначения в топку (хотя я так понимаю, что это какие-то производные, но боюсь запутаться в количестве f после буквы d)
a += b
b += c
c += d
ПРЯМОЙ ХОД
Как же значиния будут менятся?
k = 1 k = 2 k = 3 k = 4 k = 5
a[n] = a a + b a + 2b + c a + 3b + 3c + d a + 4b + 6c + 4d
b[n] = b b + c b + 2c + d b + 3c + 3d b + 4c + 6d
c[n] = c c + d c + 2d c + 3d c + 4d
Откуда бпрутся коэффициенты? Они берутся из треугольника (кажется Паскаля)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Он строится очень просто: по краям единички, для остальных позиций значение равно сумме двух сверху.
Дополним треугольник нулями и срежем полосу в 4 единички шириной
1 0 0 0
1 1 0 0
1 2 1 0
1 3 3 1 0
1 4 6 4 1
1 5 10 10 5 1
Удалим ненужное и дурацкие отступы
1 0 0 0
1 1 0 0
1 2 1 0
1 3 3 1
1 4 6 4
1 5 10 10
Получили то, что надо.
ОБРАТНЫЙ ХОД
Надо найти такие x, y, z, чтобы
a = x + y
b = y + z
c = z + d
значит
x = a — b + c — d
y = b — c + d
z = c — d
для второй итерации
x = a — 2b + 3c
y = b — 2c + d
z = c — 2d
для третьей
x = a — 3b + 6с — 10d
y = b — 3c + 6d
z = c — 3d
Коэффициенты (постараемся и здесь найти закономерность) для первого шага
+1 -1 +1 -1
+1 -1 +1
+1 -1
для второго шага
+1 -2 +3 0
+1 -2 +1
+1 -2
для третьего шага
+1 -3 +6 -10
+1 -2 +6
+1 -3
Как видим коэффициенты это члены наклонных рядов треугольника паскаля каждый второй из которых умножен на -1
Что делать с не целыми K русть решает сам автор вопроса, потому что ИМХО нецелое количество итераций цикла вешь неопределённая.
Здравствуйте, McSeem2, Вы писали:
MS>Просто торможу как удав по песку.
MS>Сейчас я вас насмешу. Есть такой простейший код:
MS>MS>f += df;
MS>df += ddf;
MS>ddf += dddf;
MS>
MS>Допустим, что он выполняется 2 раза. Надо написать код, дающий результат, эквивалентный выполнению приведенного кода дважды, но тоже в три выражения, а не в шесть. На самом деле все сложнее. Вместо 2 может быть некое K, необязательно целое. Может быть как меньше единицы, так и больше. И может быть отрицательным, что эквивалентно откату назад.
1) Прежде всего, сведем аффинную задачу к линейной, добавив
dddf+=0;
2) Заметим, что все операции можно сгруппировать в одну векторную (здесь важен порядок исходных операций)
(f,df,ddf,dddf)+=(df,ddf,dddf,0);
3) Иными словами,
(f,df,ddf,dddf) = (I+N) (f,df,ddf,dddf)
Здесь I -- единичная матрица, N -- нильпотентная.
N(f,df,ddf,dddf) = (df,ddf,dddf,0)
N^4 = 0
4) Говоря математическим языком, автор хочет возвести I+N в некоторую вещественную степень, не обязательно целую положительную (композиция отображений соотвествует умножению матриц).
5) Список желаемых свойств такой степени F(x) состоит из:
a) F(0) = I
b) F(1) = I+N
c) F(x+y) = F(x) * F(y)
d) F(x) непрерывна
6) Такая функция называется однопараметрической подгруппой группы матриц ( 4 порядка в нашем случае, GL(R,4) ) (условие нормировки b) в общем случае исключается, естественно).
7) Вспоминая теорию групп Ли, выводим, что F(x) = exp(L*x), где L -- некоторая матрица.
8) Матрица L может быть найдена из условий нормировки b),
exp(L) = I+N
9) Данное уравнение имеет единственное решение, причина -- в нильпотентности матрицы N.
10) Собственно говоря, решение находится подстановкой N в ряд для логарифма,
L = N - (N^2)/2 + (N^3)/3 (остальные члены равны нулю)
L^4 = 0
exp(L*x) = I + L*x/1 + (L^2)*(x^2)/2! + (L^3)*(x^3)/3! (остальные члены равны нулю)
11) Вспомним ещё бином Ньютона.
exp(L*x) = (I+N)^x (для целых положительных x)
= I + C(x,1) * N + C(x,2) * N^2 + C(x,3) * N^3 (хорошая штука -- нильпотентность, остальные члены опять равны нулю)
C(x,1) = x
C(x,2) = (x*(x-1))/2
C(x,3) = (x*(x-1)*(x-2))/6
Эта формула справедлива и в общем случае. Просто потому, что два многочлена, совпадающих на бесконечном множестве точек, тождественно равны.
12) Очко! (Т.е. дюжина
).
op(x) : (f,df,ddf,dddf) -> (f+C(x,1)*df+C(x,2)*ddf+C(x,3)*dddf,df+C(x,1)*ddf+C(x,2)*dddf,ddf+C(x,1)*dddf,dddf)
Здравствуйте, Шахтер, Вы писали:
Ш>1) Прежде всего, сведем аффинную задачу к линейной, добавив
. . .
Шахтер, ты реально крут!
Спасибо!
