Друзья, помогите решить задачу:

Допустим имеется двоичный код n-ной длинны - 0*********1. Он всегда начинается
с 0, а заканчивается на 1. Между 0 и 1 может быть абсолютно любой код. К
примеру 0100111101 или 0001011001 и т.д. Единственное, что неизменно - 0
вначале и 1 в конце. Так вот задача заключается в том, чтобы привести этот код к
такому виду: 0****0**1 - т.е. четвертый с конца бит должен стать равным 0. Но надо
знать, какое значение было на самом деле в оригинальном коде, не увеличивая
длинну строки кода и восстановить остальной код по результату (таким образом
получется что-то вроде заложенного алгоритма восстановления кода тем же кодом)
Пример 1:
имеем код: 1) 0011101101 - видно, что четвертый с конца бит равен 1.
2) Преобразовываем код так, чтобы 4-ый с конца бит стал равен нулю,
а история преобразования была заложена в результирующем коде. Получаем код:
0*****0**1 - вместо звездочек должен быть код, который говорит, как построить
оригинал (0011101101).

Пример 2:
01101110001
0******0**1

Какие есть идеи ?

Имхо не возможно здать любые к бит в к-1 бит.


Ответ: такой алгоритм не существует и не будет существовать.

Чтобы обнулить 4 бит с конца, можно сделать логический AND:
01101110001
AND
11111110111
=
01101110001

--------------------------
01101111001
AND
11111110111
=
01101110001

=============================
Узнать 4 бит с конца
01101111001
AND
00000001000
=
00000001000

Теперь сделаем SHIFT-RIGHT 3 раза, получим:

00000000001

Это сообщение отредактировал(а) djGri - 2.7.2005, 16:28

djGri , твой метод не решает задчу.
Мы не сможем во всех случаях востановить исходную последовательность, да и вообще без дополнительных условий это невозможно.

Это не возможно, в начальном коде содержится n бит данных, а в производном (n-1), это попытка сжать данные, для некоторых данных это возможно, но не для всех.

Ок. Тогда делаем так:

Допустим есть такая строчка

0101010101010101111110001001
AND 1000
=
0000000000000000000000001000

NOT 0000000000000000000000001000
= 1111111111111111111111110111

0101010101010101111110001001
AND
1111111111111111111111110111
=
0101010101010101111110000001

Цитата(linuxoid @ 29.6.2005, 15:14)

надо знать, какое значение было на самом деле в оригинальном коде, не увеличивая длинну строки кода и восстановить остальной код по результату

Если на исходную последовательность нет ограничений, задача нерешаема в принципе. Диагноз окончателен и обжалованию не подлежит.

Dixi

V ishodnom kode tak zhe n simvolov. Glavnoe, 4tobi ih bilo ne n+1. Prosto nuzno, 4tobi 4j sleva bit bil raven 0, no pri etom mozhno bilo uznatj bil li tam 1 ili 0 na samom dele. 4isto teoriti4eski vigladit eto tak:

imeem: 01101111011
polu4aem: 0******0**1 - (vmesto zvezdo4ek kod, kotorij po suti javlaetsa algoritmom vosstanovlenija) i tut vse govorat: aga! zna4it tak vosstanavlivaetsa ishodnij kod i mi polu4aem rezultat 01101111011

Drugoj primer: to zhe samoe, no 4j s konca = 0: 01101110011 . Po algoritmu vivodim 0******0**1 - i opjatj znaem, kak vosstanovitj original!

Eto 4to-to tipo rebusa. Predpolozhim, 4to v kode vsegda suwestvuet hotjabi 4 nulja. Togda k primeru budet takoj kod: 010101101101 . Mozhno-li znaja, 4to vkode estj nulj (ili mnogo nulej) kak-nibudj smestitj ego (ih) (ili 1 iz nih) imenno na 4j s konca bit, i 4tobi pri vosstanovlenii mozhno bilo ponjatj (po algoritmu vosstanovlenija) gde on(i) bil(i) na samom dele ?

naprimer ishodnik 01101001101 - nuli ne izvestno gde (pri4em odin iz nih mozhet bitj dazhe na 4-om s konca bite, no mi etogo ne znaem!). Zatem po algoritmu smewaem ih i polu4aem kod, v kotorom raspisana posledovatelnostj vosstanovlenija i 4j sleva bit raven 0 !

*glavnoe pri etom ne menatj na4alnij i kone4nij bit (0 vna4ale i 1 v konce stroki bitov)

Это сообщение отредактировал(а) linuxoid - 6.7.2005, 16:11

По моему нерешабельно. Нужно изменить всю строку

linuxoid, кто вам такую задачку задал? это же психом надо быть, чтобы пытаться сжать два байта без потерь!

da tak... estj odin 4elove4ik.
Ok, dopustim 0 i 1 tozhe mozhno menjatj. Mozhno-li 4to-to predprinatj v etom slu4ae ?

Ну нельзя, говорят Вам! Недавно поднли тему, теоретически спихали 600 МБ на дискету, о вот достать не смогли. Этот человек не сок случаем?

SoWa 4to ti imel v vidu "Нужно изменить всю строку" ? Esli mozhno izmenitj vsju stroku, kak eto budet vigladetj ?

Опять пытаемся законы гравитации отменить

Нельзя решить эту задачу...
Что ни делай, все равно однозначного обратного преобразования не будет. Нужно дополнительно хранить код операции.

Цитата(Alex101 @ 8.7.2005, 11:24)

Нужно дополнительно хранить код операции

В данном случае тот же один бит который и пытаемся сьэкономить - элементарная теория о кол-ве информации

Zapominatj ne trebuetsa. Vopros drugoj - v kode imejutsa nuli. Mozhno ih sdvigatj tak, 4tobi hotjabi 1 iz nih zanal 4uju s konca poziciju ili net. Na to i nuzhen algoritm, 4tobi ni4ego ne zapominatj. Ladno. Puskaj eto ne 4ij bil sleva. Puskaj 10j ili 100j - ne vazhno. No vsegda 10j ili 100j ili n-nij... Dumajte kollegi, dumajte.

linuxoid
МОДЕРАТОР: При написании своих постингов ПОЛЬЗУЙТЕСЬ АВТОТРАНСЛИТЕРАЦИЕЙ.

Цитата(linuxoid @ 8.7.2005, 12:11)

Mozhno ih sdvigatj tak, 4tobi hotjabi 1 iz nih zanal 4uju s konca poziciju ili net.

Ну а почему нет?

a - исходная последовательность бит
b=a and 11110111
в b 4й слева всегда будет ноль.
Добавлено @ 13:16
djGri Это уже написал, кстати.

попробуй так инвертируещь первый , четвертый и последний бит! Потом делаешь сдвиг битов вправо! Потом опять инветируешь первый четвертый и последий бит и опять сдвигаешь вправо и так пока не получиться! Я на бумажке сделал 4 разных примера все они сошлись уже на 4 повторе!

Da, no v dannom slu4ae polu4aetsa randomnoe kol-vo variantov i v slepuju k originalu uzhe nikogda ne vernutsa