符合數(shù) A 定義的數(shù)
d(n) = n + n 的各位之和
d(78) = 78 + 7 + 8 = 93
定義數(shù) A ：數(shù) A 找不到一個(gè)數(shù) B 可有 d(B) = A ，即 A 不能由其他數(shù)生成。
找出 1 - 10000 里所有符合數(shù) A 的數(shù)。
根據(jù) d 的定義 d(a) = b，我們知道對(duì)每一個(gè) a 有 a < b
要找到 1 - 10000 里所有的符合 A 的數(shù)，即是找到不存在 d(B) = A 的數(shù) A 。
可以設(shè)定一個(gè) 10001 大小的數(shù)組，遍歷整個(gè)數(shù)組，計(jì)算每個(gè)下標(biāo) B 對(duì)應(yīng)的 d(B) A 。將以 A 為下標(biāo)的元素設(shè)置狀態(tài)。
遍歷完后，即可確定要找的符合數(shù) A 的數(shù)。
1 #include <iostream>
2 using namespace std;
3
4 int sum(int n)
5 {
6 int ret = 0;
7 while (n != 0)
8 {
9 ret += n % 10;
10 n /= 10;
11 }
12 return ret;
13 }
14
15 void findA(int a[], int n)
16 {
17 memset(a, 0, sizeof (*a) * n);
18 int t = 0;
19 for (int i = 1; i <= n; ++i)
20 {
21 if ((t = i + sum(i) <= n))
22 {
23 a[i + sum(i)] = 1;
24 }
25 }
26 }
27
28 int main()
29 {
30 int n;
31 const int size = 10001;
32 int a[size + 1];
33
34 findA(a, size);
35
36 for (int i = 1; i <= size; ++i)
37 {
38 if (a[i] == 0)
39 {
40 cout << i << ' ';
41 }
42 }
43 cout << endl;
44
45 return 0;
46 }
posted on 2011-07-19 21:59
unixfy 閱讀(150)
評(píng)論(0) 編輯 收藏 引用