Просто математика

[MIT]

Есть последовательность чисел
20
21
17
18
17
11
которая является результатом работы алгоритма кодирования, работающего следующим образом: изначально даются числа 7, 9, 3, 1, 8, 5, 4, 0, 2, затем по схеме изображенной ниже путем сложения и получается кодированная последовательность

Т.е. формула выглядит так:
7+9+3+1=20
9+3+1+8=21
3+1+8+5=17
1+8+5+4=18
...

Возможно ли имея последовательность 20, 21, 17 и т.д. восстановить исходную 7, 9, 3...?

[Amed]

Обычная СЛАУ.

a0, a1, ..., a8 - первая последовательность
b0, b1, ..., b5 - вторая последовательность

По твоей формуле получается, что

Код: Выделить всё

b0=a0+a1+a2+a3
b1=a1+a2+a3+a4
...

Следовательно, b1=b0-a0+a4
Из этого логично, что

Код: Выделить всё

b(i)=b(i-1)-a(i-1)+a(i+3)

или

Код: Выделить всё

b(i)-b(i-1)=a(i+3)-a(i-1)

Мгновенно делается система

Код: Выделить всё

b1-b0=a4-a0
b2-b1=a5-a1
...

Запишем ее как

Код: Выделить всё

c0=-1*a0+0*a1+0*a2+0*a3+1*a4+0*a5+0*a6+0*a7+0*a8
...

Левая часть известна, в правой - 9 неизвестных. Проверяем СЛАУ, находим корни

[Александр Дмитриев]

Однозначно восстановить невозможно, так как задача сводится к СЛАУ, число уравнений в которой всегда меньше числа неизвестных.

[Хакер]

Исходная последовательность: числа от 0 до 9, или произвольные? Если первое, то даже при недостатке уравнений в СЛАУ есть вероятность, что получится однозначно восстановить исх. посл.

[MIT]

Обычная СЛАУ.

Ой, это до завтра

Исходная последовательность: числа от 0 до 9, или произвольные?

произвальная

[Amed]

Если произвольная, то найдется только общее решение.

[Александр Дмитриев]

Если первое, то даже при недостатке уравнений в СЛАУ есть вероятность, что получится однозначно восстановить исх. посл.

Да, по-моему, действительно есть вероятность, и, по-моему, она ОЧЕНЬ мала.
UPD:
Кстати, например, для данной последовательности (20, 21, 17, 18, 17, 11) даже при таких ограничениях ответ будет неоднозначным: последовательность 5, 5, 5, 5, 6, 1, 6, 4, 0 также кодируется в неё. Но в общем случае, действительно есть вероятность.

[MIT]

произвальная

Хотя нет, не произвальная. Числа задаются в пределе 0-255.

Да, по-моему, действительно есть вероятность, и, по-моему, она ОЧЕНЬ мала.

Хм. А если помимо самой последовательности 20, 21, 17 у нас будет число 7 - первый элемент изначальной последовательности?
Или можно переформулировать: что надо иметь помимо последовательности, что бы расшифровка получилась однозначной?

[Александр Дмитриев]

Насилованием ГЛПК удалось получить список всех последовательностей, кодирующихся в данную 20 21 17 18 17 11. Комбайн из моей проги и ГЛПК висел с минуту! Прога и списки прилагаются (для случаев диапазона чисел 0-255 и 0-9).