Не понятен алгоритм-нумерация клеток полосы длиной 2^k при сворачивании пополам

[faustofel]

Помогите,пожалуйста разработать алгоритм для следующей задачи:

Заданна полоса длиной 2к клеток и шириной в одну клетку. Полосу несколько раз сгибают пополам так, чтобы ее правая половина оказывалась под левой. Этот процесс продолжается до тех пор, пока сверху остается больше одной клетки. Написать программу STRIPE, которая пронумерует клетки таким образом, что после завершения сгибания полосы номера клеток в полученной колонке будут упорядочены: 1, 2, 3, 4, ..., 2к.

[Abstraction]

Простите, а какой-нибудь пример нумерации можно? А то пока я не понимаю, что за операция проделывается и каким образом получится "колонка".
Ну, то есть, пусть k=3 и мы пронумеровали клетки, слева направо, (1, 2, 3, 4, 5, 6). Применили описанную операцию. Как будут упорядочены номера клеток в колонке?

[faustofel]

Прошу прощения, но там маленькая неточность: длина полосы 2^k
Пример: допустим k=3

т.о. исходная полоса: 1 2 3 4 5 6 7 8
перенумерованная полоса: 1 8 5 4 3 6 7 2

сворачиваем в столбик:
1
2
3
4
5
6
7
8

Основной вопрос: какая закономерность (формула) перенумерования полосы перед сворачиванием для любых 2^k

[Abstraction]

Можете вначале объяснить, как "складывается", "сворачивается" полоса? А то у меня при сворачивании Вашей "перенумерованной" получается (1, 2, 4, 3, 8, 7, 5, 6).

[faustofel]

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

т.е. 1 8 5 4 3 6 7 2

1 8 5 4
2 7 6 3

1 8
2 7
3 6
4 5

1
2
3
4
5
6
7
8

[Abstraction]

То есть, правая половина отображается центрально-симметрично от середины низа?
Что мешает проделать ту же процедуру в обратном порядке? Определение того, куда "переедет" число n в обратном преобразовании, занимает O(k):

int InitialPosition(int pos, int K){
  int x=0, y=pos-1; //Начальная позиция в столбике
  for(int d=0; d<K; ++d){
    if(y > (1 << (K-d-1))){ //Если мы в "нижней" половине столбика
      x = (2 << d) - x - 1;
      y = (2 << (K-d-1)) - y - 1;
    }
  }
  return y+1;
}

[faustofel]

Но мне нужно не обратное преобразование, мне нужна формула, по которой происходит перестановка, причем, для любого k. И, если можно, объясните, пожалуйста, центрально-симметрично относительно середины низа, это как.

[BDA]

Если я правильно понял назначение функции Abstractionа, то Вы просто вызываете эту функцию для всех чисел от 1 до 2k и ставите их в нужные ячейки массива (функция вернет позицию). После этого массив будет хранить номера в нужном порядке.

[Abstraction]

Но мне нужно не обратное преобразование, мне нужна формула, по которой происходит перестановка, причем, для любого k. И, если можно, объясните, пожалуйста, центрально-симметрично относительно середины низа, это как.

Формулу я попробовал вывести, посмотрел на получающегося крокодила и плюнул. Вам советую сделать то же - это тот случай, когда проще посчитать значение, чем записать аналитическое выражение.

Насчёт симметрии... вернитесь к Вашему примеру и мысленно поставьте точку в низу исходной строки, между 4 и 3. Все числа справа от точки переезжают на центрально-симметричное относительно неё место на первом шаге.
На втором шаге, поставьте новую точку, в низу второй строки между 7 и 6. Опять все числа переезжают по законам центральной симметрии (ну, нарисуйте стрелочки - как перемещается каждое число, они пересекутся в одной точке).
А точки эти, если мерить от верхнего-левого угла, имеют координаты (1,4), (2,2), (4,1). Для k=4 они будут (1,8), (2,4), (4,2), (8,1)... видите закономерность? Вот это у меня и отражено в коде (1 << x - это 2^x).

[s-andriano]

Сообщение от faustofel

Но мне нужно не обратное преобразование, мне нужна формула, по которой происходит перестановка, причем, для любого k. И, если можно, объясните, пожалуйста, центрально-симметрично относительно середины низа, это как.

В исходной постановке формула не требовалась.
Требовался алгоритм.
А к алгоритму требование одно - он должен завершаться через конечное число шагов. Это условие выполнено.
Собственно, формулы бывают рекурентные, которые тоже дают результат не сразу, а лишь после некоторого количества итераций.

PS. Самое скверное, это когда условия задачи изменяются уже после того, как найдено решение.