给定十进制数 N，求出其在任何基数(基数 b)中的位数
问题陈述包括求出 N 在任何基数 b 数字系统中的位数。最初，N 以 10 进制数字系统给出。
在问题中，我们将在输入中提供一个正整数 N，它将以 10 进制数字系统给出，以及一个大于 1 的正整数 b。我们的任务是找出 N 以 b 进制数字系统表示时的位数。
任何以任何基数表示的数字，从右边开始的每个数字都代表从 0 开始的该基数的幂的倍数。
例如，当我们以 3 进制表示 15 时。
它被表示为 120，即 $\mathrm{0*3^{0}+2*3^{1}+1*3^{2}=0+6+9=15}$
让我们通过以下示例更好地理解问题。
输入
N=16 b=5
输出
2
解释 − 这里我们给出了以 10 为基数表示的 N，即 16。我们需要计算以 5 为基数表示的 N 的位数。
16 在 5 为基数的表示形式为 31，即 $\mathrm{1*5^{0}+3*5^{1}=1+15=16}$
16 在 5 为基数的表示形式中的位数为 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 的位数。
方法 1(简单方法)
解决方案的简单方法将表示 N 在以 b 为底的数字系统并计算位数。
为了找到以 b 为底的 N 表示中的位数，我们将创建一个函数。我们将初始化一个变量来存储位数的计数，并通过将 N 除以 b 来更新 N，直到 N 大于 0，并在每次迭代中不断增加位数。这样，我们就可以计算出以 b 为底数的 N 的位数。
这可以更好地解释为，为了用任何底数表示任何数字，我们用代表右侧每个数字的底数对该数字取模，并通过将该数字除以底数来更新该数字，并重复该过程，直到数字大于 0。
在 C++ 中实现该方法的步骤如下:
我们将创建一个函数来计算以 b 为底数表示的 N 的位数。
初始化一个变量来存储数字的计数。
在 while 循环中迭代，直到 N 大于 0。
在每次迭代中，通过将 N 除以 b 来更新 N，并将计数增加 1，因为要找到表示中的下一个左数字，我们用 b 对 N 取模，更新N。
当 N 等于零时，返回变量，该变量将是 N 在以 b 为基数的数字系统中表示的位数。
示例
//C++ 代码用于查找以 b 为基数表示的 N 的位数
#include <bits/stdc++.h>
using namespace std;
// 函数用于计算 B 进制中 N 的位数
int digits(long long int N, long long int b){
// 用于存储 B 进制中 N 的位数
int a=0;
// 迭代计算位数
while(N>0){
N = N/b; // 通过将 N 除以 b 来更新 N 以找到下一个数字
a++; // 将计数增加 1
}
return a;
}
int main()
{
long long int N,b; // 用于获取输入值
N=58734;
b=4;
// 调用函数
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) ，因为我们在while循环中迭代直到N大于0并继续将N除以基数。
空间复杂度:O(1) ，因为不需要额外的空间来查找数字的数量。
方法-2(高效方法)
我们可以使用数学中的对数函数概念以更有效的方式解决问题。
以b为底数的N的表示中的数字数量与数字N和底数b之间存在数学关系。以 b 为底数时，N 的位数为 (1+ N 以 b 为底数的对数值)。
让我们通过下图更好地理解这种关系。
假设以 b 为底数的 N 的表示形式中有 a 位数字。
N 的值将在 $\mathrm{b^{a−1}<=N<b^{a}}$ 范围内，因为每个数字都表示从 0 开始的底数的幂。因此，如果 N 有 a 位数字，则 N 的值必须等于或大于 $\mathrm{b^{a−1}}$，因为 a 从 0 开始，并且必须小于 $\mathrm{b^{a}}$，后者是 b 的下一个幂。
在等式的两边以 b 为底数取对数，我们获取
$$\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}}$
我们将使用上述公式，在恒定的运行时间内，使用 C++ 中的 log() 函数计算底数为 −b 的 N 的位数，该函数返回的值等于传递的参数的自然对数。
在 C++ 中实现该方法的步骤:
制作一个函数，用于计算以 b 为底数的 N 的位数。
初始化一个变量来存储位数。
使用导出的公式，我们将计算位数。log() 函数可能返回十进制值，因此我们将使用 floor() 函数来获取小于或等于 log() 函数返回值的最大整数，并确保 a 始终小于或等于 $\mathrm{\frac{\log\:N}{\log\:b}}$
返回使用公式计算的位数，这将是我们的输出。
示例
//C++ 代码用于查找以 b 为底数的 N 的位数
#include <bits/stdc++.h>
using namespace std;
//计算位数的函数
int digits(long long int N, long long int b){
//以 b 为基数存储 N 的位数
int a=0;
a = floor( log(N) / log(b) ) + 1; //使用公式计算位数
return a; //返回位数
}
int main()
{
long long int N,b; //用于获取输入值
N=1e15; //以 N 为基数存储 10^15
b=9;
//调用函数
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 中的位数的概念。我们使用一种简单的方法解决了这个问题，并使用 C++ 中对数函数的概念在恒定的运行时间和空间内找到了一个有效的解决方案。
我希望您在阅读本文后能够理解这个问题以及解决问题的方法。
