мультипликативное постоянство - рекурсия?

Question

Я работаю над этим:

Напишите функцию постоянства, которая принимает положительный параметр num и возвращает его мультипликативное постоянство, которое является числом раз, которое вы должны умножить в num, пока вы не достигнете одного di git.

Например:

постоянство (39) == 3 //, потому что 3 * 9 = 27, 2 * 7 = 14, 1 * 4 = 4 // и 4 имеет только одну ди git

постоянство (999) == 4 // потому что 9 * 9 * 9 = 729, 7 * 2 * 9 = 126, // 1 * 2 * 6 = 12, и, наконец, 1 * 2 = 2

постоянство (4) == 0 //, потому что 4 уже является единичным git числом

Это вот что я попробовал:

  public static int Persistence(long n)
        {
            List<long> listofints = new List<long>();

           while (n > 0)
            {
                listofints.Add(n % 10);
                n /= 10;
            }
            listofints.Reverse();
            // list of a splited number

            int[] arr = new int[listofints.Count];
            for (int i = 0; i < listofints.Count; i++)
            {
                arr[i] = (int)listofints[i];
            }
            //list to array

            int pro = 1;
            for (int i = 0; i < arr.Length; i++)
            {
                pro *= arr[i];
            }
            // multiply each number
            return pro;
        } 

У меня проблема с пониманием рекурсии - возможно, есть место, где ее использовать. Может кто-нибудь дать мне совет, а не решение, как с этим бороться?

Answer 1

Похоже, у вас есть полная функция для обработки одной итерации. Теперь все, что вам нужно сделать, это добавить рекурсию. В конце функции снова вызовите постоянство с результатом первой итерации в качестве параметра.

Persistence(pro);

Это будет рекурсивно вызывать вашу функцию, передавая результат каждой итерации в качестве параметра для следующей итерации.

Наконец, вам нужно добавить некоторый код, чтобы определить, когда вы должны остановить рекурсию, поэтому вы хотите вызывать Persistence(pro), только если ваше условие истинно. Таким образом, когда ваше состояние станет ложным, вы прекратите рекурсию.

if (some stop condition is true)
{
    Persistence(pro);
}

Answer 2

public int PerRec(int n)
{
    string numS = n.ToString();

    if(numS.Length == 1)
        return 0;

    var number = numS.ToArray().Select(x => int.Parse(x.ToString())).Aggregate((a,b) => a*b);

    return PerRec(number) + 1;
}

Для каждой рекурсии у вас должно быть условие остановки (в данном случае один ди git).

• Идея здесь состоит в том, чтобы взять ваш ввод и преобразовать его в строку в рассчитать эту длину. Если это 1, то вы возвращаете 0
• Тогда вам нужно выполнить преобразование. Возьмите все цифры из строкового представления (в этом случае из массива char, проанализируйте их все, после получения IEnumberable<int>, умножьте каждый di git, чтобы вычислить следующий параметр для вашего рекурсивного вызова.
• Окончательный результат - новый рекурсивный вызов + 1 (который представляет предыдущее преобразование)

Вы можете сделать этот шаг по-разному:

var number = numS.ToArray().Select(x => int.Parse(x.ToString())).Aggregate((a,b) => a*b);

1. convert numS в массив символов с вызовом ToArray ()
2. итерация по коллекции и преобразование каждого символа в целочисленное представление и сохранение его в массив или список
3. итерация по списку int, умножая все цифры для следующего номера вашей рекурсии

Надеюсь, это поможет

Answer 3

Позвольте мне попытаться объяснить, когда вам стоит подумать об использовании рекурсивного метода.

Пример факториала: Factorial of n определяется умножением 1*2*3*4*..*n.

Предположим, вы хотите узнать, что такое факториал числа. Чтобы найти ответ, вы можете написать foreach l oop, в котором число умножается на следующее число и следующее число, пока оно не достигнет 0. Как только вы достигнете 0, все готово, вы вернете свой результат.

Вместо использования циклов вы можете использовать Рекурсию, потому что процесс на каждом этапе одинаков. Умножьте первое число на результат следующего, результат следующего определяется умножением этого следующего числа на результат следующего и т. Д.

5 * (result of rest)
  4 * (result of rest )
    3 * (result of rest)
      ...
      1 (factorial of 0 is 1).---> Last Statement.

В этом случае, если мы выполняем рекурсию , у нас есть терминатор последовательности, последнее утверждение, где мы знаем для факта, что факториал равен 0 = 1. Итак, мы можем записать это как,

FactorialOf(5) = return 5 * FactorialOf(4) = 120 (5 * 24)
FactorialOf(4) =    return 4 * FactorialOf(3) = 24 (4 * 6)
FactorialOf(3) =      return 3 * FactorialOf(2) = 6 (3 * 2)
FactorialOf(2) =        return 2 * FactorialOf(1) = 2 (2 * 1)
FactorialOf(1) =          return 1 * FactorialOf(0) = 1 (1 * 1)
FactorialOf(0) = Known -> 1.

Итак, было бы целесообразно использовать один и тот же метод снова и снова, и как только мы добираемся до нашего терминатора, мы останавливаемся и начинаем возвращаться вверх по дереву. Каждый оператор, который вызывал FactorialOf, начинал возвращать числа, пока не достигнет вершины. Вверху у нас будет наш ответ.

Ваш случай персистентности

Он требует рекурсивного метода, а также вы берете результат и делаете тот же процесс на это каждый раз.

Persistence(39) (not single)   = return 1 + Persistence(3 * 9 = 27) = 3
Persistence(27) (not single)   =   return 1 + Persistence(2 * 7 = 14) = 2
Persistence(14) (not single)   =     return 1 + Persistence(1 * 4 = 4) = 1
Persistence(4)  (single digit) = Known -> 0  // Terminator.

В конце дня, если у вас есть один и тот же процесс, выполняемый после каждого вычисления / обработки с завершением, вы, скорее всего, сможете найти способ использовать рекурсию для этого процесса .

Answer 4

Разработка простого рекурсивного решения обычно состоит из двух этапов: - Определите тривиальный базовый случай, на который вы можете легко рассчитать ответ. - Узнайте, как превратить сложный случай в более простой, таким образом, чтобы он быстро приблизился к базовому случаю.

В вашей задаче: - Любое число с одним ди-ди git имеет простое решение, которое постоянство = 1. - Умножение всех цифр числа приводит к меньшему числу, и мы знаем, что постоянство большего числа больше, чем сохранение меньшего числа ровно на единицу.

Это должно привести вас к ваше решение. Все, что вам нужно сделать, это понять вышесказанное и написать это в C#. Есть только несколько модификаций, которые вам нужно внести в существующий код. Я не дам вам готового решения, так как это побеждает цель упражнения, не так ли? Если у вас возникли технические проблемы с кодификацией вашего решения в C#, вы можете задать еще один вопрос.

Answer 5

public static int Persistence(long n)
{
    if (n < 10) // handle the trivial cases - stop condition
    {
        return 0;
    }

    long pro = 1; // int may not be big enough, use long instead
    while (n > 0) // simplify the problem by one level
    {
        pro *= n % 10;
        n /= 10;
    }

    return 1 + Persistence(pro); // 1 = one level solved, call the same function for the rest
}

Это классическое c использование рекурсии. Вы обрабатываете базовые случаи c, упрощаете задачу на один уровень и затем снова используете ту же функцию - это рекурсия.

Вы можете переписать рекурсию в циклы, если вы sh, вы всегда может.

Answer 6

Вы определенно можете вызывать ваш вызов умножения рекурсивно. Вам понадобится начальное состояние (0 умножений) и продолжайте вызывать ваш метод, пока не достигнете условия остановки. Затем вы возвращаете последнюю полученную итерацию в качестве результата и проходите ее до конца:

int persistence(int input, int count = 0) {} // this is how I would define the method
// and this is how I see the control flowing
var result = persistence(input: 39, count: 0) {
    //write a code that derives 27 out of 39
    //then keep calling persistence() again, incrementing the iteration count with each invocation
    return persistence(input: 27, count: 1) {
        return persistence(input: 14, count: 2) {
            return persistence(input: 4, count: 3) {
                return 3
            }
        }
    }
}

приведенное выше, очевидно, не является реальным кодом, но я надеюсь, что это иллюстрирует достаточно хорошо, чтобы вы могли исследовать его дальше