Число Хэмминга с использованием пользовательских функций вместо простых

Question

Проблема Хэмминга - известная проблема, которая в основном генерирует все целые числа, простые факторы которых {2,3,5}. (И это может быть распространено на любой набор основных факторов, я думаю)

Чтобы найти n-ое число Хэмминга, есть умный алгоритм построения O(N) Дейкстры, псевдокод которого выглядит следующим образом:

List<int> H
int i=0,j=0,k=0, n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
   int next = min(2*H[i], 3*H[j], 5*H[k])
   H.add(next)
   if(next == 2*H[i]) ++i
   if(next == 3*H[j]) ++j
   if(next == 5*H[k]) ++k

output(H[10])

Ключевым моментом в этом решении является то, что, если H является числом Хемминга, то 2H, 3H, 5H также является числом Хемминга

---

Я столкнулся с проблемой, которую я почувствовал, что она немного похожа на проблему Хэмминга, но она не строит число с использованием набора простых факторов, вместо этого, если я перефразирую формулировку задачи, она выглядит следующим образом:

1 находится в наборе результатов. Если H находится в наборе результатов, то 2H+1 и 3H+1 также находятся в наборе результатов. Найти n-й номер в наборе результатов

Тогда я задаюсь вопросом, работает ли тот же алгоритм построения для этой проблемы, оказывается, что он работает! (А я даже понятия не имею почему это работает)

Def f(x) 2x+1
Def g(x) 3x+1

List<int> H
int i=0,j=0,n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
   int next = min(f(H[i]), g(H[j]))
   H.add(next)
   if(next == f(H[i])) ++i
   if(next == g(H[j])) ++j

output(H[10])

---

Итак, мне интересно:

Работает ли этот алгоритм построения для задач генерации чисел, учитывая правило типа "Если x в результате, то все f(x), g(x), p(x), q(x)... также в результате ", при условии, что эти функции дадут результат> = x ?

Answer 1

Достаточным условием является то, что все функции f_i от целых чисел к целым числам должны быть монотонно возрастающими и иметь n < f_i(n) для всех i а также n,

Примером, демонстрирующим, что вам нужно что-то вроде целой части правила, является пара функций (n+0.5, (n + floor(n+1))/2), Это приведет к последовательности 1, 3/2, 7/4, 15/8, ... и ты никогда не доберешься до 2,

Функции (2^n, 20 - 5n + n^2) выходит в порядке 1, 2, 4, 16, 14, ... и явно не в порядке. Отсюда необходимость неубывания.

Функция (n-3) дает последовательность (1, -2, -5, ...) и показывает важность n < f_i(n),

Так почему это работает?

Прежде всего ясно, что все, что выводит этот алгоритм, находится в наборе.

Идя другим путем, предположим, что все три условия выполнены. Затем мы должны по индукции доказать, что, если вы принадлежите к последовательности, мы начнем искать вас, прежде чем доберемся до этого, а затем должны произвести это, когда проедем вас. (То, что мы передаем вас, гарантируется тем фактом, что последовательность представляет собой растущий набор целых чисел.) Доказательство немного грязное, но прямое.