Как определить вышестоящую ячейку в пирамиде?

Question

[nepster-web]

Есть пирамида из чисел, выглядит вот так:


Каждая ячейка имеет свой номер и начинается с 0.
Таким образом выходит, что координаты ячейки: уровень и номер.

Вопрос такой, как можно подняться к самой верхней ячейке через родителей ?

Тоесть, к примеру определяем ячейку, с которой будем подниматься:
4 уровень (счет с 0), номер 1.
Нужно получить следующие ячейки:
- 3 уровень номер 1
- 2 уровень номер 0
- 1 уровень номер 0
- 0 уровень номер 0

Естественно, что матрица может быть любая и кол-во ячеек сколько угодно. Подскажите пожалуйста как это можно просчитать?

Answer 1

[tsarevfs]

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

4 уровень (счет с 0), номер 1.
Нужно получить следующие ячейки:
- 3 уровень номер 1

Вроде 0 для 1 ячейки родитель должен быть?
Если это опечатка, то при вашем способе хранения достаточно взять целую часть от деления номера ребенка на 3.

Comments

[nepster-web]

Стремно как-то, поэтому не до конца обратил внимание на подход. Проверил, все работает, спасибо.

Answer 2

[AlikDex]

для начала нужно осилить вводную часть по матрицам, и потом уже задавать правильные вопросы

Comments

[nepster-web]

это не совсем то

[Дмитрий Ковальский]

nepster09: Просто не надо использовать математические термины там где ими даже не пахнет.

[nepster-web]

Дмитрий Ковальский: специально для вас поправил.