c813 - 11332 - Summing Digits

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個正整數經過重複計算各位數字和的過程，直到結果為一位數。這個一位數就是題目定義的 g(n)。

解題思路

題目要求計算數字根。數字根的計算可以通過重複計算各位數字的和來實現，直到結果為一位數。由於數字根的特性，也可以使用模 9 的方法來計算，但題目給定的輸入範圍較小，直接迭代計算各位數字的和更為簡潔易懂。程式碼中，使用一個 while 迴圈來迭代計算各位數字的和，直到數字小於等於 9。

複雜度分析

• 時間複雜度: O(log10(n))。 每次迭代都會減少數字的位數，最壞情況下需要 log10(n) 次迭代。
• 空間複雜度: O(1)。 程式碼只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	int a;
	while(cin >> a){
		if(a==0)
			break;
		while(a>9){
			int b=0;
			while(a!=0){
				b+=a%10;
				a/=10;
			}
			a=b;
		}
		cout << a << "\n";
	}
}