從2到n-1不同進位制下數字的各位數字之和

---

問題陳述包括列印使用者輸入的數字N在從2到N-1的不同進位制下的各位數字之和。

在這個問題中，我們將得到任意正整數N，我們需要將該數字表示為從2到N-1的不同進位制數系統，並找到每個不同進位制數系統中數字的和。

在n進位制數系統中，任何數字在該數系統中的表示形式中的每個數字從右到左分別代表n的0次冪到31次冪的倍數。

例如，當5用2進位制數系統表示時，

它表示為101，即 $\mathrm{2^{2}+2^{0}=5}$

同時，當5用3進位制數系統表示時，

它表示為12，即 $\mathrm{3^{1}+2*3^{0}=3+2=5}$

讓我們透過下面的例子來理解這個問題。

輸入

N=6

輸出

2 2 3 2

解釋 - 給定的輸入是6。因此，我們需要找到N（即6）在從2到5的不同進位制數系統中表示時的各位數字之和。

當6用2進位制數系統表示時，它寫為110，即$\mathrm{2^{2}+2^{1}=6}$

6在2進製表示下的各位數字之和為2

6在3進位制數系統中的表示為20，即$\mathrm{2*3^{1}=6}$。6在3進位制下的各位數字之和為2。

6在4進位制數系統中的表示為12，即$\mathrm{4^{1}+2*4^{0}=4+2=6}$。6在4進製表示下的各位數字之和為1+2=3。

6在5進位制數系統中的表示為11，即$\mathrm{5^{1}+5^{0}=6}$。6在5進位制數系統中的各位數字之和為2。

因此，我們需要的輸出是2 2 3 2。

輸入

N=9

輸出

2  1  3  5  4  3  2

解釋 - 由於輸入是9，我們需要將9表示為從2到8的不同進位制數系統，並找到每個表示的各位數字之和。因此，

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，以獲得該數字在特定進位制數系統中的表示。

例如，我們需要將9表示為5進位制數系統。

將9除以5得到餘數4，因此最右邊的數字將是4，然後透過將9除以5來更新N，得到1。

現在，將1除以5得到餘數1，因此前一個數字左邊的下一個數字將是1，然後N將為0。

因此，9在5進位制數系統中的表示將是14，表示$\mathrm{5^{1}+4*5^{0}=9}$

由於我們只需要N在不同進位制值中表示的各位數字之和，我們將簡單地將N除以進位制值得到的餘數加到儲存各位數字之和的變數中，然後透過將N除以進位制值來更新N，直到N大於0，以獲得N在不同進位制值中表示時的各位數字之和。

為了解決這個問題，我們將使用此演算法來計算我們在方法中從2到N-1的不同進位制值中表示的N的各位數字之和。

方法

在我們的方法中實現上述演算法的步驟

• 我們將簡單地建立一個函式，用於給出N在從2到N-1的不同進位制值中表示時的各位數字之和，其中傳遞的引數將是N和進位制數。

• 我們將在一個while迴圈中迭代，直到N大於0，在該迴圈中，我們將找到N除以進位制數的餘數，並將其新增到儲存各位數字之和的變數中，然後透過將N除以進位制數來更新N。

• 一旦N變為0，返回儲存在變數中的各位數字之和。

• 在一個for迴圈中從i=2迭代到i<=N-1，以找到N在不同進位制數中表示時的各位數字之和，其中i代表特定的進位制數。

• 我們將透過呼叫函式來列印每個不同進位制的各位數字之和，該函式用於計算N在for迴圈中從2到N-1的每個i值的不同進制中表示時的各位數字之和。

示例

// 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在從2到N-1的不同進制中表示時的各位數字之和的概念。我們使用了一種有效的方法，在C++中以(log N)的執行時間和常量空間內找到N在不同進位制值中的各位數字之和。

我希望您在閱讀本文後能夠理解這個概念和問題的解決方案。