Практика программирования (Бейсик, Си, Паскаль)


Задачи,советы и ответы - часть 41


Совет 1 (общий)

Конечно, можно построить цикл по перебору всех длинных целых чисел (а их — порядка двух миллиардов), в теле которого выделяются все делители, кратные 2, 3 и 5. Если результат деления тестируемого числа оказывается равным 1, т. е. у числа никаких других делителей нет, то найдено очередное число Хэмминга. Однако такая программа будет очень долго работать (для сравнения мы приведем и текой вариант решения).

Гораздо более эффективный алгоритм базируется на определении следующего числа Хэмминга по уже построенной последовательности. При этом приходится запоминать, какое из ранее найденных чисел необходимо домножить на 2, какое — на 3 и какое — на 5. Из трех возможных вариантов следует выбирать минимальное произведение. На первом шаге мы знаем единственное число Хэмминга, равное 1, и именно оно может быть умножено на следующем шаге на один из трех возмож-

ных множителей. Минимальное произведение равно 2, и это — второе число Хэмминга. Теперь умножению на 2 должно быть подвергнуто второе число, а умножению на 3 и 5 — пока еще первое. Поэтому на втором шаге минимальное произведение равно 3. После этого умножению на 2 и 3 может быть подвергнуто второе число, а на 5 — пока еще только первое. Одним словом, когда определено минимальное произведение, использованный множитель должен "переместиться" на следующее, уже найденное число Хэмминга.

Совет 2 (общий)

Обозначим через kl, k2, k3 индексы чисел Хэмминга, которые будут множиться соответственно на 2, 3 и 5. Их начальные значения в программе на Бейсике можно не задавать, т. к. все числовые переменные перед началом работы программы сбрасываются в ноль.

Программа 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) ;




- Начало -  - Назад -  - Вперед -