数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定十进制表示的数字 N，找到其在任何基数（基数 b）下的位数。
问题陈述包括在任何基数 b 数制中表示 N 时找到其位数。最初，N 以基数 10 数制给出。
在问题中，我们将获得输入中的正整数 N，它将以基数 10 数制表示，以及大于 1 的正整数 b。我们的任务是找到 N 在基数 b 数制中表示时的位数。
任何以任何基数表示的数字，从右起每一位都表示该基数的幂的倍数，从 0 开始。
例如，当我们将 15 表示为基数 3 时。
它被表示为 120，即 $\mathrm{0*3^{0}+2*3^{1}+1*3^{2}=0+6+9=15}$
让我们通过以下示例更好地理解问题。
输入
N=16 b=5
输出
2
解释 - 在这里，我们以基数 10 表示的形式给出 N，即 16。我们需要计算 N 在基数 5 中表示时的位数。
16 在基数 5 中的表示为 31，即 $\mathrm{1*5^{0}+3*5^{1}=1+15=16}$
16 在基数 5 中表示的位数为 2（即 31），这是我们所需的输出。
输入
N= 22 b=3
输出
3
解释 - 以基数 10 数制表示的 N 的值为 22，并且我们给定的基数等于 3。22 在基数 3 中的表示为 211，即 $\mathrm{1*3^{0}+1*3^{1}+2*3^{2}=1+3+18=22}$
因此，22 在基数 3 中表示的位数为 3，这是我们所需的输出。
让我们探索从朴素到高效解决方案的不同方法来计算任何数字 N 在基数 b 中表示的位数。
方法 1（朴素方法）
该解决方案的朴素方法将是将 N 表示为基数 b 数制并计算位数。
为了找到 N 在基数 b 中表示的位数，我们将创建一个函数。我们将初始化一个变量来存储位数，并通过将 N 除以 b 来更新 N，直到 N 大于 0，并在每次迭代中增加位数。通过这种方式，我们可以计算 N 在基数 b 中表示的位数。
这可以更好地解释为，要将任何数字表示为任何基数，我们取该数字对基数的模，它表示从右起每一位，并通过将该数字除以基数值来更新该数字，并重复此过程，直到该数字大于 0。
在 C++ 中实现该方法的步骤
我们将创建一个函数来计算 N 在基数 b 中表示的位数。
初始化一个变量来存储位数。
在 while 循环中迭代，直到 N 大于 0。
在每次迭代中，通过将 N 除以 b 来更新 N，并将计数增加 1，因为要找到表示中的下一个左边的位，我们取 N 对 b 的模，并使用更新后的 N。
当 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)，因为我们在 while 循环中迭代，直到 N 大于 0，并不断将 N 除以基数值。
空间复杂度：O(1)，因为没有占用额外的空间来查找位数。
方法 2（高效方法）
我们可以使用数学中的对数函数的概念以更有效的方式解决问题。
N 在基数 b 中表示的位数与数字 N 和基数 b 之间存在数学关系。N 在基数 b 中表示的位数为（1 + N 以 b 为底的对数值）。
让我们通过下面的插图更好地理解这种关系。
假设，N 在基数b中表示的位数为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() 函数的恒定运行时内计算 N 在基数 b 中的位数，该函数返回等于传递的参数的自然对数的值。
在 C++ 中实现该方法的步骤
创建一个函数来计算 N 在基数 b 中的位数。
初始化一个变量来存储位数。
使用导出的公式，我们将计算位数。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++ 中对数函数概念的高效解决方案解决了该问题，并在恒定运行时和空间内实现了该问题。
希望您在阅读本文后能够理解问题以及解决问题的方法。
173 次浏览
