Что делает программа

@vadyansky · Регистрация: 04.10.2021

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

C++

#include <iostream>
using namespace std;
 
void f(int n, int k) {
    if (k > n / 2) { 
        cout << n << " "; 
        return; 
    }
    if (n % k == 0) { 
        cout << k << " "; 
        f(n / k, k); 
    }
    else f(n, ++k);
}
int main() {
    int N = 19;
    f(125 + N,2);
 
    return 0;
}

Вывод:

Код

2 2 2 2 3 3

Есть программа с рекурсивной функцией, она делает что-то, возможно находит какие то определенные элементы, или считает что-то по какойто формуле. Надо разгадать загадку, надеюсь на вашу помощь!

@zss · 18.05.2022, 19:51

Выводит делители числа n

@vadyansky · 18.05.2022, 20:04 **[ТС]**

zss, делители или множители? 2 * 2 * 2 * 2 * 3 * 3 = 144, в функцию передаем 125 + 19 = 144

@TheCalligrapher · 18.05.2022, 20:06

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

Что делает программа

Программа выполняет факторизацию числа, то есть разложение числа на простые множители, при условии что функция f изначально вызывается с параметром k = 2 (как это и сделано).

@vadyansky · 18.05.2022, 20:09 **[ТС]**

TheCalligrapher, Спасибо, а что в функции значит это самое k = 2, за что оно отвечает? ?

@TheCalligrapher · 18.05.2022, 20:10

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

Надо разгадать загадку

Неужели по приведенному выводу 2 2 2 2 3 3 не очевидно, что делает программа?

@vadyansky · 18.05.2022, 20:10 **[ТС]**

TheCalligrapher,

, не приходило это в голову мне к сожалению

@TheCalligrapher · 18.05.2022, 20:10

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

а что в функции значит это самое k = 2 ?

Мне не ясен вопрос.

Еще раз: для получения факторизации числа N функция должна изначально вызываться как f(N, 2).

@vadyansky · 18.05.2022, 20:11 **[ТС]**

TheCalligrapher, я имею ввиду почему именно 2, а не 4 например?

@TheCalligrapher · 18.05.2022, 20:16

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

я имею ввиду почему именно 2, а не 4 например?

Ну видимо потому, что автору этого кода поставили задание: написать программу, которая будет выполнять факторизацию числа, а также "обязательно использовать рекурсию". Вот они и написал. Чтобы программа соответствовала заданию, надо чтобы в самый верхнем вызове было f(..., 2). Потому что 2 - минимальное простое число. Чтобы получить факторизацию нужно начинать поиск факторов с минимального простого числа.

Реализован простейший общеизвестный алгоритм факторизации (Получить все простые делители числа), но вместо привычной циклической реализауции сделана рекурсивная. Видимо, это было требованием задания.

Можете вызвать f(..., 4). Получится что-то другое, скорее всего бесполезное.

Что делает программа

Решение

Решение

@zss Модератор 13507 / 10757 / 6412 Регистрация: 18.12.2011 Сообщений: 28,713
	18.05.2022, 19:51	2
	Выводит делители числа n 0

@vadyansky 7 / 6 / 1 Регистрация: 04.10.2021 Сообщений: 268
	18.05.2022, 20:04 [ТС]	3
	zss, делители или множители? 2 * 2 * 2 * 2 * 3 * 3 = 144, в функцию передаем 125 + 19 = 144 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,071
	18.05.2022, 20:06	4
	Сообщение было отмечено vadyansky как решение Решение Сообщение от vadyansky Что делает программа Программа выполняет факторизацию числа, то есть разложение числа на простые множители, при условии что функция `f` изначально вызывается с параметром `k = 2` (как это и сделано). 0

@vadyansky 7 / 6 / 1 Регистрация: 04.10.2021 Сообщений: 268
	18.05.2022, 20:09 [ТС]	5
	TheCalligrapher, Спасибо, а что в функции значит это самое k = 2, за что оно отвечает? ? 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,071
	18.05.2022, 20:10	6
	Сообщение от vadyansky Надо разгадать загадку Неужели по приведенному выводу `2 2 2 2 3 3` не очевидно, что делает программа? 0

@vadyansky 7 / 6 / 1 Регистрация: 04.10.2021 Сообщений: 268
	18.05.2022, 20:10 [ТС]	7
	TheCalligrapher, , не приходило это в голову мне к сожалению 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,071
	18.05.2022, 20:10	8
	Сообщение от vadyansky а что в функции значит это самое k = 2 ? Мне не ясен вопрос. Еще раз: для получения факторизации числа `N` функция должна изначально вызываться как `f(N, 2)`. 0

@vadyansky 7 / 6 / 1 Регистрация: 04.10.2021 Сообщений: 268
	18.05.2022, 20:11 [ТС]	9
	TheCalligrapher, я имею ввиду почему именно 2, а не 4 например? 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,071
	18.05.2022, 20:16	10
	Сообщение было отмечено vadyansky как решение Решение Сообщение от vadyansky я имею ввиду почему именно 2, а не 4 например? Ну видимо потому, что автору этого кода поставили задание: написать программу, которая будет выполнять факторизацию числа, а также "обязательно использовать рекурсию". Вот они и написал. Чтобы программа соответствовала заданию, надо чтобы в самый верхнем вызове было `f(..., 2)`. Потому что `2` - минимальное простое число. Чтобы получить факторизацию нужно начинать поиск факторов с минимального простого числа. Реализован простейший общеизвестный алгоритм факторизации (Получить все простые делители числа), но вместо привычной циклической реализауции сделана рекурсивная. Видимо, это было требованием задания. Можете вызвать `f(..., 4)`. Получится что-то другое, скорее всего бесполезное. 0