Перечислим алгебраическое выражение в порядке возрастания
У меня есть следующее выражение: (2 ^ i * 3 ^ j), i, j> = 0, и мне нужно перечислить его в порядке возрастания, т.е. 1 2 3 4 6 8 9 12 ….
Я думал сделать следующее: Поддерживать приоритетную очередь. Для тока (i, j) мы можем либо увеличить i, либо увеличить j. Вычислите выражение для этих новых значений и поместите их в очередь с приоритетами. Выскочить из очереди и продолжить. Начнем с (0,0). Нам также нужно будет поддерживать (i, j) вместе с вычисленным выражением. Также нужно игнорировать дубликаты.
Я хотел знать, есть ли более быстрый способ перечислить вышеупомянутое выражение, поддерживая меньшее состояние?
Решение
Что-то в этом роде.
results = [1]
i_index = 0
j_index = 0
for(count=0, count<n, count ++){
i_incr = results[i_index]*2 // next value of expression by incrementing i
j_incr = results[j_index]*3 // next value of expression by incrementing j
if (i_incr > j_incr)
results << j_incr
j_index += 1
else if (i_incr < j_incr)
results << i_incr
i_index += 1
else
results << i_incr
i_index += 1
j_index += 1
end
}
Государство поддерживается i_index а также j_indexони отслеживают последнее значение, которое не было увеличено для этих индексов, соответственно. ,
Другие решения
Других решений пока нет …