C++ 2到n-1不相同的进制数位之和

问题任务是计算数字N在进制数从2到N-1时的数位之和。

对于这个问题，我们会得到一个任意正整数N，我们需要将该数字表示为从2到N-1的进制数，并计算每个进制数的数位之和。

在以-n为底的进制数系统中， 每个数字的表示中，从右向左的每个数位表示的是n的0次方到31次方的次数。

例如，当5以-2为底的进制数系统表示时，它表示为101，即2^{2}+2^{0}=5。

同时，当5以-3为底的进制数系统表示时，它表示为12，即3^{1}+2*3^{0}=3+2=5。

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

输入

N=6

输出

2 2 3 2

解释 - 给定输入是6。所以，我们需要找到数字N的各位数之和，也就是用不同的基数从2到5表示时的数字6。

当6用二进制表示时，写作110，即\mathrm{2^{2}+2^{1}=6}。

6在二进制表示中的各位数之和为2。

6在三进制表示中写作20，即\mathrm{2^{2}*3^{1}=6}。6在三进制中的各位数之和为2。

6在四进制表示中写作12，即\mathrm{4^{1}+2*4^{0}=4+2=6}。6在四进制表示中的各位数之和为1+2=3。

6在五进制表示中写作11，即\mathrm{5^{1}+5^{0}=6}。6在五进制中的各位数之和为2。

因此，我们要求的输出是2 2 3 2。

输入

N=9

输出结果

2  1  3  5  4  3  2

说明 - 由于输入为9，我们需要以2到8的不同基数进制表示9，并找到每个表示法的数字之和。 因此，

9在基数-2中：1001，因此数字之和为2。

9在基数-3中：100，因此数字之和为1。

9在基数-4中：21，因此数字之和为3。

9在基数-5中：14，因此数字之和为5。

9在基数-6中：13，因此数字之和为4。

9在基数-7中：12，因此数字之和为3。

9在基数-8中：11，因此数字之和为2。

因此，我们需要的输出是2 1 3 5 4 3 2。

让我们了解在不同基数进制中打印数字的各位数之和的算法。

算法

由于我们需要找到数字N在2到N-1的每个基数表示法的各位数之和，我们将创建一个函数来找到每个基数表示法下的N的和。

要以任意基数数字表示任意数字N，我们取该数字与右边每位所代表的基数数字的模数，然后将数字除以基数一直到N变为0，以获得该数字在特定基数进制中的表示方法。

例如，我们需要在基数-5的数字体系中表示9。

将9除以5得出余数4，所以最右边的数字为4，然后将N除以5得到1。

现在，将1除以5得出余数1，所以下一个数字是上一个数字左边的数字，结果为1，然后N将变为0。

因此，基数-5数字体系中9的表示方法为14，表示为\mathrm{5^{1}+4*5^{0}=9}

由于我们只需要找到N在不同基数值下表示的各位数之和，我们将简单地将N除以基数值得到余数，并将其添加到N的和中，然后更新N为除以基数值，直到N大于0为止，以获得N在不同基数值下的各位数之和。

我们将使用此算法来计算N在2到N-1的不同基数值下表示时的各位数之和，以解决问题。

方法

实施以上算法的步骤：

• 我们只需创建一个函数，计算在不同进制下表示的数字N的各位数字之和，进制范围为2到N-1，函数的参数为N和进制数。

• 我们使用一个while循环，直到N大于0为止。在循环中，我们将N除以进制数得到的余数加到一个变量中，用于存储各位数字之和，并且更新N为N除以进制数。

• 一旦N变为0，返回存储在变量中的各位数字之和。

• 使用一个for循环从i=2到i<=N-1，计算数字N在不同进制下的各位数字之和，其中i代表特定的进制数。

• 通过调用计算数字N在不同进制下各位数字之和的函数，在for循环中，对于每个i从2到N-1的值，打印出不同进制下的各位数字之和。

示例

// C++ program to print the Sum of digits written in different bases from 2 to N-1
#include<bits/stdc++.h>

using namespace std;

//function to give the sum of digits of N when represented in a particular base
int sumOfDigit(int N,int B)
{
    int sum = 0;  //variable to store the sum of digits
    //iterate until N is greater than zero
    while(N > 0)
    {

     int rem=N % B;  //finding the remainder of N when divided by base number 

     sum=sum + rem;  //add remainder with sum  to store the sum of digits

     N=N / B;  //update N by dividing N by base number

    }

    return sum;  //return the sum of digits stored in the variable
}
int main()
{
    int N=10;

    cout<<"Sum of digits written in different bases from 2 to N-1 : " <<endl;

    //using for loop from i=2 to i<=N-1 to find the sum of digits of N when represented in different base number
    for(int i =2; i<=N-1; i++){

        //printing the sum of digits of each different bases by calling the function to calculate the sum of digits of N 
        cout<<sumOfDigit(N,i)<<"  ";

    }
    return 0;
}

输出

Sum of digits written in different bases from 2 to N-1 
2  2  4  2  5  4  3  2

时间复杂度 − O(N*logN)，因为计算不同进制下数字位数之和需要log N的时间。

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

结论

文章讨论了在不同进制下表示的N的数字位数之和的打印概念。我们使用了一种高效的方法来在C++中以(log N)的运行时间和常数的空间复杂度找到N的不同进制下的数字位数之和。

希望您在阅读本文后能理解这个概念和问题的解决方案。