Логика: применение силы тяжести к вектору

Question

Существует метод под названием gravity(Vector[] vector) Вектор содержит последовательность чисел. Функция гравитации должна возвращать новый вектор после приложения силы тяжести, который поясняется ниже.

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

Пусть вектор = [3, 7, 8]

Преобразование это в двоичную мы получаем:
0 0 1 1 для 3
0 1 1 1 для 7
1 0 0 0 для 8

Применение силы тяжести:
0 0 0 0 0 который
0 0 1 1, который является 3
1 1 1 1, который является 15

Таким образом, функция силы тяжести должна возвращаться [0, 3, 15].

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

То есть,
3 + 7 + 8 = 18 = 0 + 3 + 15 для вышеуказанного случая.

Answer 1

Единственное решения, которое я могу придумать до сих пор использует вложенную for петли:

• v является входным вектором N целых
• D этого количества цифр в каждом целом
• c отслеживает самого нижнего свободного места, где может упасть кирпич

Алгоритм проверяет, установлен ли i-й бит в числе n с использованием (n & (1<<i)), который работает на большинстве C-подобных языков.

Алгоритм в C:

for (int j=0; j<D; ++j) 
    int bit = 1<<j; 
    int c = N-1; 
    for (int i=N-1; i>=0; --i) 
     if (v[i] & bit) { // if bit j of number v[i] is set... 
      v[i] ^= bit; // set bit j in the number i to 0 using XOR 
      v[c] ^= bit; // set bottom-most bit in the number i to 1 using XOR 
      c -= 1;  //increment by bottom row 1 
     } 

---

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

Answer 2

Таким образом, я нашел решение, требующее рекурсии, я думаю. Хотя я не знаю условия, чтобы остановить рекурсию.

вектор v = [3, 7, 8] очень прост, что ее не представляется возможным объяснить, почему требуется рекурсия так подумывает новый вектор V = [3, 9, 7, 8, 5]

В двоичной форме:

0 0 1 1 - a4 
1 0 0 1 - a3 
0 1 1 1 - a2 
1 0 0 0 - a1 
0 1 0 1 - a0 

Итерация 1:

0 0 0 0 - b7 (b7 = a4 AND b5) 
0 0 1 1 - b6 (b6 = a4 OR b5) 
0 0 0 0 - b5 (b5 = a3 AND b3) ignore this 
1 0 0 1 - b4 (b4 = a3 OR b3) 
0 0 0 0 - b3 (b3 = a2 AND b1) ignore this 
0 1 1 1 - b2 (b2 = a2 OR b1) 
0 0 0 0 - b1 (b1 = a0 AND a1) ignore this  
1 1 0 1 - b0 (b0 = a0 OR a1) 

Intermediate vector = [b7, b6, b4, b2, b0] = [0, 3, 9, 7, 13] 

Итерация 2:

0 0 0 0 - c7 (c7 = b4 AND c5) 
0 0 0 1 - c6 (c6 = b4 OR c5) 
0 0 0 1 - c5 (c5 = b3 AND c3) ignore this 
0 0 1 1 - c4 (c4 = b3 OR c3) 
0 0 0 1 - c3 (c3 = b2 AND c1) ignore this 
1 1 0 1 - c2 (c2 = b2 OR c1) 
0 1 0 1 - c1 (c1 = b0 AND b1) ignore this 
1 1 1 1 - c0 (c0 = b0 OR b1) 

Intermediate vector = [c7, c6, c4, c2, c0] = [0, 1, 3, 13, 15] 

Итерация 3:

0 0 0 0 - d7 (d7 = c4 AND d5) 
0 0 0 1 - d6 (d6 = c4 OR d5) 
0 0 0 1 - d5 (d5 = c3 AND d3) ignore this 
0 0 0 1 - d4 (d4 = c3 OR d3) 
0 0 0 1 - d3 (d3 = c2 AND d1) ignore this  
1 1 1 1 - d2 (d2 = c2 OR d1) 
1 1 0 1 - d1 (d1 = c0 AND c1) ignore this 
1 1 1 1 - d0 (d0 = c0 OR c1) 

Resultant vector = [d7, d6, d4, d2, d0] = [0, 1, 1, 15, 15] 

Я получил это решение, перейдя в обратном направлении через вектор.

Другое решение:

1. Построить многомерный массив со всеми битами всех элементов в векторе (т.е.), если v = [3,7,8], а затем построить массив 3х4 и хранить все биты.
2. Подсчитайте количество 1 в каждом столбце и сохраните счет.
3. Заполните каждый столбец числом отсчета 1, начиная с нижнего бита.

Этот подход прост, но требует построения больших матриц.

Answer 3

Начало в нижней части. Любые кирпичи в ряду поверх этого будут падать, кроме тех случаев, когда на дне уже есть кирпич. Таким образом, новая нижняя строка:

bottom_new = bottom_old ИЛИ top_old

Новая вершина:

top_new = bottom_old И top_old

То есть, будет кирпича в новый нижний ряд, если в любой строке был кирпич, но в новой верхней строке будет только кирпич, если в обеих строках был кирпич.

Затем вы просто прокладываете себе путь вверх по стеку, а новый верхний ряд становится старой нижней строкой для следующего шага.

Answer 4

Я думаю, что это так же просто, как подсчет всего «1» бит каждой позиции ...

Пусть N быть входным вектор размером, б самой длинной двоичной длиной входных элементов

1. Предварительно вычислить общие # бит «1» в каждом положении, сохраненный в подсчете [], O (N * б)
2. запуск гравитации Функция, то есть, чтобы восстановить N чисел от графа [], O (N * б)

Общее время работы составляет O (N * б)

Ниже приведен пример кода в C++

#include<bits/stdc++.h> 
 
using namespace std; 
 
int v[5] = {3,9,7,8,5}; 
 
int cnt[5] = {0}; 
 
vector<int> ans; 
 

 
vector<int> gravity(){ 
 
\t vector<int> ret; 
 
\t for(int i=0; i<5;i++){ 
 
\t \t int s = 0; 
 
\t \t for(int j=0; j<5;j++) 
 
\t \t \t if(cnt[j]){ 
 
\t \t \t \t s += (1<<j); cnt[j]--; 
 
\t \t \t } 
 
\t \t ret.push_back(s); 
 
\t } 
 
\t return ret; 
 
} 
 

 
int main(){ 
 
\t 
 
\t // precompute sum of 1 of each bit 
 
\t for(int i=0, j=0, tmp=v[i]; i<5; i++, j=0, tmp=v[i]){ 
 
\t \t while(tmp){ 
 
\t \t \t if(tmp&1) cnt[j]++; 
 
\t \t \t tmp >>= 1; j++; 
 
\t \t } 
 
\t } 
 
\t 
 
\t ans = gravity(); 
 
\t 
 
\t for(int i=ans.size()-1; i>=0; i--) printf("%d ", ans[i]); 
 
\t 
 
\t return 0; \t 
 
}

Выход выглядит следующим образом:

Успех Время: 0 память: 3272 сигнал: 0