Задачи,советы и ответы - часть 41
Совет 1 (общий)
Гораздо более эффективный алгоритм базируется на определении следующего числа Хэмминга по уже построенной последовательности. При этом приходится запоминать, какое из ранее найденных чисел необходимо домножить на 2, какое — на 3 и какое — на 5. Из трех возможных вариантов следует выбирать минимальное произведение. На первом шаге мы знаем единственное число Хэмминга, равное 1, и именно оно может быть умножено на следующем шаге на один из трех возмож-
ных множителей. Минимальное произведение равно 2, и это — второе число Хэмминга. Теперь умножению на 2 должно быть подвергнуто второе число, а умножению на 3 и 5 — пока еще первое. Поэтому на втором шаге минимальное произведение равно 3. После этого умножению на 2 и 3 может быть подвергнуто второе число, а на 5 — пока еще только первое. Одним словом, когда определено минимальное произведение, использованный множитель должен "переместиться" на следующее, уже найденное число Хэмминга.
Совет 2 (общий)
Программа 2_24.bas (оптимальный вариант)
DEFLNG A-Z
DIM Xam(1000)
CLS
Xam(0)=l
PRINT 1,1
FOR J=l TO 999
x2=Xam(k2)*2
x3=Xam(k3)*3
x5=Xam(k5)*5
IF x2<=x3 AND x2<=x5 THEN Xam(J)=x2: k2=k2+l
IF x3<=x2 AND x3<=x5 THEN Xam(J)=x3: k3=k3+l
IF x5<=x2 AND x5<=x3 THEN Xam(J)=x5: k5=k5+l
PRINT USING "###:########## "; J,Xam(J) ;