練習 － Self Numbers

題目：1949年，印度數學家D.R.Kaprekar發現了一類稱為自數（self-number）的數。
對任意的正整數n，定義d(n)是n與n每一位的總和再相加（d是代表digitadition，Kaprekar創造的術語）。例如，d(75) = 75 + 7 + 5 = 87。列出任意正整數n作為起始點，可始建構整數n的無限增量序列：d(n),d(d(n)),d(d(d(n))),⋯。例如，如果以33作為起始點，下一個數是33 + 3 + 3 = 39，再下一個數是39 + 3 + 9 =51，再下一個數是51 + 5 + 1 = 57，可以產生序列33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141,⋯。
整數n被稱為d(n)的生成數，在上述序列中，33是39的生成數，39是51的生成數，51是57的生成數，等等。一些數有一個以上的生成數：例如，101有兩個生成數，91和100。
沒有生成數的數稱為自數。在100內有13個自數：1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86和96。

輸入：沒有輸入。

輸出：寫一個程式，以遞增的次序輸出少於10000的自數，每個數一行。

public class SelfNumbers {

	final int N = 10000;
	int g[];

	public int sumOfDigits(int n) {
		if (n < 10)
			return n;
		return (n % 10) + sumOfDigits(n / 10); // 計算n的各位數字之和
	}

	public void generateSequence(int n) { // 建構整數nh旳無限增量序列
		while (n < N) {
			int next = n + sumOfDigits(n); // 計算d[n]
			if (next >= N || g[next] != next) // 若d[n]起過上限或非自數則返回
				return;
			g[next] = n; // 將d[n]放n的無限增量序列
			n = next;
		}
	}

	public SelfNumbers() {
		int n;
		g = new int[N];
		for (n = 1; n < N; ++n) { // 最初假設所有數為自數
			g[n] = n;
		}

		for (n = 1; n < N; ++n) {
			generateSequence(n);
		}

		for (n = 1; n < N; ++n) {
			if (g[n] == n) // 輸出篩中滿足g[x]=x條件的自數
				System.out.printf("%d\n", g[n]);
		}
	}

	public static void main(String[] args) {
		SelfNumbers sn = new SelfNumbers();
	}

}