Найти первый элемент последовательности Хемминга больший заданного числа

@Олег1000 · Регистрация: 21.04.2019

Author24 — интернет-сервис помощи студентам

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

@Royal_X · 11.10.2021, 11:27

Сообщение от Олег1000

Массивы не использовать.

а контейнеры STL можно использовать?

@Annemesski · 11.10.2021, 11:28

Сообщение от Royal_X

а контейнеры STL можно использовать?

нет необходимости

наивное решение:

C++

#include <iostream>
 
int isHamming(int n)
{
    int c = n;
    while (n > 1)
    {
        if (!(n % 2))
            n /= 2;
        else if (!(n % 3))
            n /= 3;
        else if (!(n % 5))
            n /= 5;
 
        if (n == c)
            break;
 
        c = n;
    }
 
    return c == 1;
}
 
int main()
{
    int M;
    std::cin >> M;
 
    int n = 0;
 
    int i = 0;
    for (; i < M; ++i)
    {
        if (isHamming(i))
            ++n;
    }
 
    while (!isHamming(++i));
    std::cout << i << "  (" << n + isHamming(M) + 1 << ")" << std::endl;
 
    return(0);
}

@Олег1000 · 11.10.2021, 12:55 **[ТС]**

Сообщение от Annemesski

return c == 1;

Для чего это нужно?

Сообщение от Annemesski

while (!isHamming(++i));

Для чего это нужно?

И еще вопрос, функция isHamming() возвращает наибольшее простое число кроме 2,3,5 до текущего числа i?

@Annemesski · 11.10.2021, 13:12

Олег1000, функция isHamming возвращает истину если переданное n - число Хэмминга, иначе ложь (поправьте возвращаемый тип на bool)

C++

1	return c == 1;

в функции число делилось на 2 или 3 или 5 пока могло, если в конце результат стал равен 1 - то это число имеет среди делителей только или 2 или 3 или 5, то есть это число Хэмминга, иначе число содержит другие делители.

Сообщение от Олег1000

Для чего это нужно?

по заданию цикл идет пока не встретится следующее число Хэмминга.

@Олег1000 -1 / 18 / 7 Регистрация: 21.04.2019 Сообщений: 493
		1
	Найти первый элемент последовательности Хемминга больший заданного числа 11.10.2021, 10:14. Показов 1274. Ответов 4 Метки нет (Все метки) Написать программу по следующему заданию: Последовательность Хэмминга образуют натуральные числа, не имеющие других простых делителей, кроме 2, 3 и 5. Найти первый элемент, больший данного числа M, а также номер этого элемента в последовательности. Массивы не использовать. 0

@Royal_X 3249 / 1470 / 468 Регистрация: 01.06.2021 Сообщений: 4,965
	11.10.2021, 11:27	2
	Сообщение от Олег1000 Массивы не использовать. а контейнеры STL можно использовать? 0

@Олег1000 -1 / 18 / 7 Регистрация: 21.04.2019 Сообщений: 493
	11.10.2021, 12:55 [ТС]	4
	Сообщение от Annemesski return c == 1; Для чего это нужно? Сообщение от Annemesski while (!isHamming(++i)); Для чего это нужно? И еще вопрос, функция isHamming() возвращает наибольшее простое число кроме 2,3,5 до текущего числа i? 0

	11.10.2021, 13:12

Опции темы

Найти первый элемент последовательности Хемминга больший заданного числа

Решение