Как подсчитать количество рекурсий? (Вычисление числа умножений при x ^ n)

minty59 спросил: 03 февраля 2018 в 11:34 в: c++

У меня возникли проблемы с выяснением того, как увеличивать счетчик (mults в моем коде) таким образом, что счетчик power2 эквивалентен power1. Моя программа сравнивает эффективность вычисления x ^ n по-разному. Я искал решения о том, как подсчитывать количество раз, когда рекурсия вызывает себя, но независимо от того, какой метод я реализую, я получаю неверный вывод. Любая помощь или рекомендации будут оценены!

Это часть моего кода до сих пор (power1 имеет правильный счетчик):

template <class T>
T power1(T x, unsigned int n, unsigned int& mults)
{
mults = 0;if (n == 0)
    return 1;
else if (n == 1)
    return x;
else
{
    T total = 1;    for (int i = 0; i < n; ++i)
    {
        total = total * x;
        ++mults;
    }
    mults -= 1;    return total;
}
}template <class T>
T power2(T x, unsigned int n, unsigned int& mults)
{
++mults;if (n == 0)
{
    mults = 0;
    return 1;
}
else if (n == 1)
    return x;
else
{
    if (n > 1)
    {
        return (x * power2(x, n - 1, mults));
    }
}return x;
}

Это часть моего выход:

Test for integer base:
2^0 = 1: mults1 = 0, mults2 = 0
2^1 = 2: mults1 = 0, mults2 = 1
2^2 = 4: mults1 = 1, mults2 = 3
2^3 = 8: mults1 = 2, mults2 = 6
2^4 = 16: mults1 = 3, mults2 = 10
2^5 = 32: mults1 = 4, mults2 = 15
2^6 = 64: mults1 = 5, mults2 = 21
2^7 = 128: mults1 = 6, mults2 = 28
2^8 = 256: mults1 = 7, mults2 = 36
2^9 = 512: mults1 = 8, mults2 = 45

0 ответов