- Код: Выделить всё
in out
1 1
2 8
3 3
4 6
5 2
6 7
7 4
8 5
Нужно найти закономерность между входными и выходными данными. Закономерность должна быть безусловной (никаких «если») на уровне «поменять что-то местами» или «инвертировать такой-то бит».
Вот это простой пример с простой закономерностью. Она заключается в следующем:
Представленные выше числа — номера некоторых элементов. Обычные люди привыкли начинать нумерацию с единицы, а мы как программисты переиначим нумерацию так, чтобы она начиналась с нуля:
- Код: Выделить всё
in-1 in-0 out-0 out-1
1 0 0 1
2 1 7 8
3 2 2 3
4 3 5 6
5 4 1 2
6 5 6 7
7 6 3 4
8 7 4 5
Теперь у нас есть одно преимущество: 0-based индексы укладываются в 3 бита. Распишем (или иначе говоря: представим в двоичном виде):
- Код: Выделить всё
in-1 in-0 in-bin out-bin out-0 out-1
1 0 000 000 0 1
2 1 001 111 7 8
3 2 010 010 2 3
4 3 011 101 5 6
5 4 100 001 1 2
6 5 101 110 6 7
7 6 110 011 3 4
8 7 111 100 4 5
Тут уже можно кое-что увидеть. Для некоторых строек достаточным для преобразования входных данных в выходные было бы поменять местами биты. Давайте введём ещё колонку и пометим те строки, для которых это правило действует:
- Код: Выделить всё
in-1 in-0 in-bin out-bin out-0 out-1 swappable
1 0 000 000 0 1 Y
2 1 001 111 7 8 N
3 2 010 010 2 3 Y
4 3 011 101 5 6 N
5 4 100 001 1 2 Y
6 5 101 110 6 7 N
7 6 110 011 3 4 Y
8 7 111 100 4 5 N
Ага! Мы видим, что для нечетных строк перестановка бит работает, а для четных — нет. Но что нам может дать чётность/нечетность, если всё, что мы умеем делать это перестановки/реиндексации?
Отсортируем таблицу по первично последней графе и вторично по предпоследней:
- Код: Выделить всё
in-1 in-0 in-bin out-bin out-0 out-1 swappable
1 0 000 000 0 1 Y
5 4 100 001 1 2 Y
3 2 010 010 2 3 Y
7 6 110 011 3 4 Y
8 7 111 100 4 5 N
4 3 011 101 5 6 N
6 5 101 110 6 7 N
2 1 001 111 7 8 N
Ага, уже интересно! Простой перестановки битов будет достаточно если речь идёт о выходных данных в диапазоне 1—4. Для выходных данных 5—8 правило не работает.
Но посмотрим ещё чуть внимательнее на двоичное представлени последних 4 входов выходов. Внимательные заметят, что они тоже переставлены местами! in-bin на 5-ой строчке соответствут out-bin'у на 8-ой. in-bin на 6-ой строчке — out-bin'у на 7-ой. in-bin на 7-ой — out-bin'у на 6-ой.
Вобщем, последние 4 выходных варианта как бы «перекручены». А мы умеем менять что-нибудь местами. На этот раз поменяем местами нумерацию выходов по следующему правилу:
- Код: Выделить всё
5 => 8
6 => 7
7 => 6
8 => 5
С учётом этого переиначивания выходных данных, обратимся к изначальным условиям:
- Код: Выделить всё
in new-out out
1 1 1
2 5 8
3 3 3
4 7 6
5 2 2
6 6 7
7 4 4
8 8 5
Теперь перейдём на 0-based индексы:
- Код: Выделить всё
in in-0 new-out-0 new-out out
1 0 0 1 1
2 1 4 5 8
3 2 2 3 3
4 3 6 7 6
5 4 1 2 2
6 5 5 6 7
7 6 3 4 4
8 7 7 8 5
А теперь распишем in-0 и new-out-0 в двоичном виде:
- Код: Выделить всё
in in-0 in-bin out-bin new-out-0 new-out out
1 0 000 000 0 1 1
2 1 001 100 4 5 8
3 2 010 010 2 3 3
4 3 011 110 6 7 6
5 4 100 001 1 2 2
6 5 101 101 5 6 7
7 6 110 011 3 4 4
8 7 111 111 7 8 5
И что мы теперь видим
? Что зеркальное отражение битов теперь работает для всех строк, с учётом зеркального отражения выходов 5—8.Всё, закономерность (безусловная), основанная на отзеркаливаниях обнаружена.
_______________
Это была учебная задача. А теперь боевая:
- Код: Выделить всё
1 - 1
2 - 3
3 - 2
4 - 4
5 - 5
6 - 6
7 - 7
8 - 8
9 - 11
10 - 12
11 - 9
12 - 10
13 - 15
14 - 16
15 - 13
16 - 14
Кроме cross-over-отзеркаливания можно делать слияние половин в шахм. порядке, например:
- Код: Выделить всё
Отзеркаливание:
1 => 4
2 => 3
3 => 2
4 => 1
Слияние половин:
1 => 1
3 => 2
2 => 3
4 => 4
Композиция отзеркаливания и слияния:
1 => 1
4 => 2
3 => 3
2 => 4
Кстати, отзеркаливание, обычно делается либо полностью (как в случае со входами) либо, как и слияние, половинами.
Раскусит кто-нибудь?