C++ 给定一个十进制数N，找出以任意底数b表示时的位数

问题要求确定在以任意底数b的数制中，以N表示时的位数。初始情况下，N是以十进制数制表示的。

问题中，输入时给定一个正整数N，它以十进制数制表示，并且给定一个大于1的正整数b。我们的任务是确定在以基数为-b的数制中，N表示时的位数。

在任意数制中，每个数字都表示着从0开始的以该数制为底数的幂次的次数。

例如，当我们以-base-3表示15。

它被表示为120，即$\mathrm{03^{0}+23^{1}+1*3^{2}=0+6+9=15}$

让我们通过以下示例更好地理解这个问题。

输入

N=16   b=5

输出结果

2

说明 − 我们给出的是基数为10的N，即16。我们需要计算当N表示为基数为5时的数字个数。

基数为-5时16的表示为31，即15^0 + 35^1 = 1 + 15 = 16.

基数为5时16表示的数字个数为2（即31），这是我们需要的输出。

输入

N= 22    b=3

输出结果

3

解释 - N在十进制数系统中的值为22，我们给定的基值为3。在三进制中，22的表示形式为211，即
\mathrm{1_3^{0}+1_3^{1}+2*3^{2}=1+3+18=22}

所以，22在三进制表示中的位数为3，这是我们需要的输出。

让我们从简单到高效地探索不同的方法来计算任何数N在基数为b的情况下的位数。

方法1（简单的方法）

解决这个问题的简单方法是将N表示为基数为b的数，并计算位数。

为了求出N在基数为b的表示中的位数，我们将创建一个函数。我们将初始化一个变量来存储位数的计数，并通过将N除以b来更新N，直到N大于0，并在每次迭代中增加位数的计数。通过这种方式，我们可以计算N在基数为b的表示中的位数。

这可以更好地解释为：为了将任何数表示为任何基数的数，我们取该数除以基数的余数，该余数表示每位数字（从右往左），然后用该数除以基数的商来更新该数，并重复这个过程，直到该数大于0。

用C++实现这个方法的步骤：

• 我们将创建一个函数来计算在基数为b的情况下，N的位数。

• 初始化一个变量来存储位数的计数。

• 在一个while循环中迭代，直到N大于0。

• 在每次迭代中，通过将N除以b并将位数增加1来更新N，以便于找到表示中的下一个左侧数字，我们需要用更新后的N对b取模。

• 当N等于零时，返回该变量，该变量将是N在基数为b的数系统中的位数。

例子

//C++ code to find the number of digits of N when represented in base b

#include <bits/stdc++.h>

using namespace std;

//function to calculate the number of digits of N in base b
int digits(long long int N, long long int b){
    //to store the number of digits of N in base b
    int a=0;

    //iterating to calculate the number of digits
    while(N>0){
        N = N/b; //update N by dividing it with b to find the next digit
        a++; //increase the count by 1 
    }

    return a;
}

int main()
{
    long long int N,b; //for taking input values

    N=58734;
    b=4;
    //calling the function
    cout<<"No. of digits of "<<N<<" in base-"<<b<<" :"<<digits(N,b)<<endl;

    return 0;
}

输出

No. of digits of 58734 in base-4 :8

时间复杂度：O(log N) ，因为我们在一个循环中迭代，直到N大于0，并通过基值除以N。

空间复杂度：O(1) ，因为没有额外的空间用于计算数字的数量。

方法-2（高效方法）

我们可以利用数学中的对数函数概念以更高效的方式解决这个问题。

在N的表示中，数字的位数与数字N和基数b之间存在数学关系。当在基数b中表示N时，N的位数为 （1 + 以b为底N的对数值） 。

让我们通过下面的示例更好地理解这种关系。

假设，用基数b表示的N的表示中有 a 个数字。

N的值将位于范围\mathrm{b^{a−1}<=N<b^{a}}，因为每个数字表示从0开始的基数的幂。因此，如果N有a个数字，那么N的值必须等于或大于\mathrm{b^{a−1}}，因为a从0开始且必须小于下一个b的幂\mathrm{b^{a}}。

在方程两边都使用以b为底的log运算，我们得到

\mathrm{(a−1)*\log_{b}b<=\log_{b}N}

任何以等于基数的底数取对数，结果总是1。因此，最终的表达式是

\mathrm{a<=\frac{\log:N}{\log:b}+1}，因为\mathrm{\log_{b}N}可以写成\mathrm{\frac{\log:N}{\log:b}}

我们将使用上述公式在常数运行时间内计算基-b表示中N的数字的数量，通过在C++中使用 log() 函数，该函数返回等于所传参数的自然对数的值。

在C++中实现该方法的步骤：

• 创建一个函数来计算基b中N的数字的数量。

• 初始化一个变量来存储数字的数量。

• 使用推导出的公式，我们将计算数字的数量。log()函数可能返回小数值，因此我们将使用floor()函数以获取最大的整数，该整数小于或等于log()函数返回的值，并确保a始终小于或等于\mathrm{\frac{\log:N}{\log:b}}

• 返回使用公式计算的数字的数量，这将是我们的输出。

例子

//C++ code to find the number of digits of N when represented in base b

#include <bits/stdc++.h>

using namespace std;

//function to calculate number of digits
int digits(long long int N, long long int b){
    //to store the number of digits of N in base b
    int a=0;

    a = floor( log(N) / log(b) ) + 1; //using the formula to calculate number of digits

    return a; //return number of digits
}

int main()
{
    long long int N,b; //for taking input values

    N=1e15; //storing 10^15 in N
    b=9;
    //calling the function
    cout<<"No. of digits of "<<N<<" in base-"<<b<<" :"<<digits(N,b)<<endl;

    return 0;
}

输出

No. of digits of 1000000000000000 in base-9 :16

时间复杂度 − O(1)，因为log()函数在返回值时需要恒定的时间。

空间复杂度 − O(1)，因为没有使用额外的空间。

结论

本文讨论了在任何基数b下将N表示时，找到N的数字个数的概念，并通过使用C++中的对数函数的概念，从一个朴素的方法解决问题到一个高效的解决方案。该解决方案具有恒定的运行时间和空间。

希望阅读本文后，您能理解这个问题以及解决问题的方法。