Другие языки программирования и технологии

Последовательность Хэмминга образуют натуральные числа,

не имеющие других простых делителей кроме 2,3и5. Найти: а) первые N элементов этой последовательности; б) сумму первых N элементнов; в) первый элемент больший данного числа M, а так же номер этого элемента в послед. г) сумму всех элементов с номера N по номер M
Это известная задача.. .
Короче, понятно, что все элементы последовательности имеют вид:
2^i*3^j*5^k
Первым элементом принято считать 1, хоть оно и не попадает ни под какие критерии.
Элементы вычистяются так:
1
1*2 1*3 1*5 = 2 3 5
2*2 2*3 2*5 = 4 6 10
3*2 3*3 3*5 = 6 9 15
5*2 5*3 5*5 = 10 15 25
4*2 4*3 4*5 = 8 12 20
....
Аккуратно сложив это без повторений получаем:
1 2 3 4 5 6 8 9 10 12 15 (16) (18) 20 (24) 25 ...
То, что в скобках, мы бы получили на последующих шагах.

Если это реализовывать в таком виде, программка получится нетривиальная.. . Я бы делал рекурентную функцию, которая бы засовывала найденные значения в сбалансированное бинарное дерево без повторений (или в hash table если есть нормальная реализация) , пока количество элементов в дереве не превысит искомое Н.. . Тут меня кое-что смущает, а именно - эти "забегания назад" элементов, над этим надо подумать.. . Дальше из дерева засунуть в массив не штука и все остальное - дело техники.

Другой вариант - гоним цикл, ищем простые числа от 7 до к пополам по известному алгоритму поиска простых чисел и проверяем, что:
наше к не делится на эти числа и одно из трех:
к четное
к оканчивается на 5
к делится на 3

В общем, дерзай.. . Ничего заданьице такое.
Андрей Девятайкин
Андрей Девятайкин
80 226
Лучший ответ

Похожие вопросы