- 注册时间
- 2008-2-6
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 51573
- 在线时间
- 小时
|
楼主 |
发表于 2008-12-27 15:59:03
|
显示全部楼层
-
- #include <stdlib.h>
- #include <stdio.h>
-
- #define BLen 1024* 1024
-
- int B[BLen][3];
- int Temp[BLen];
- int powD[10];
- int N, pos;
-
- void init(void)
- {
- int i, j;
- for (i = 0; i < BLen; i ++)
- B[i][0] = B[i][1] = B[i][2] = 0;
- for (i = 0; i <= 9; i ++)
- {
- powD[i] = i;
- for (j = 2; j <= N; j ++) powD[i] *= i;
- }
- pos = 0;
- }
-
- int circle(int n, int b, int num, int ps)
- {
- int i, j, k;
- if (n == 0)
- {
- B[pos][0] = num;
- B[pos++][1] = ps;
- }
- else
- {
- for (i = 1; i <= b; i ++)
- circle(n-1, i, num*10+i, ps + powD[i]);
- }
- }
-
- int binsearch(int key, int low, int hi)
- {
- int m;
- if (low > hi) return (-1);
- if (low == hi)
- if (key == B[low][0]) return low; else return -1;
- if (key == B[low][0]) return low;
- if (key == B[hi][0]) return hi;
- if (low + 1 == hi) return -1;
- m = (low + hi) >> 1;
- if (key == B[m][0])
- return m;
- else
- if (key < B[m][0])
- return binsearch(key, low, m);
- else
- return binsearch(key, m, hi);
- }
-
- int toSort(int n)
- {
- int D[10];
- int i, j;
- for (i = 1; i <= 9; i ++) D[i] = 0;
- while (n > 0)
- {
- D[n % 10]++;
- n /= 10;
- }
-
- D[0] = 0;
- for (i = 9; i >= 1; i --)
- if (D[i])
- for (j = 0; j < D[i]; j++)
- {
- D[0] *= 10;
- D[0] += i;
- }
-
- return D[0];
- }
-
- void mark(int pos)
- {
- int i, next, j, k;
- for (i = 0; i < pos; i ++)
- if (B[i][0] == B[i][1])
- B[i][2] = 1;
- else
- if (B[i][2] == 0)
- {
- next = binsearch(B[i][1], 0, pos-1);
- if (B[next][2] != 0)
- B[i][2] = -1;
- else
- {
- j = 0;
- Temp[j++] = i;
- Temp[j++] = next;
- B[i][2] = 2;
- while (B[next][2] == 0)
- {
- B[next][2] = 2;
- next = binsearch(B[next][1], 0, pos-1);
- Temp[j++] = next;
- }
- k = j;
- if ((B[next][2] == -1) || (B[next][2] == 1))
- for (j = 0; j < k - 1; j ++) B[Temp[j]][2] = -1;
- else
- {
- for (j = 0; j < k - 1; j ++)
- B[Temp[j]][2] = -1;
- B[next][2] = 1;
- }
- }
- }
- }
-
- int powerDigit(int n)
- {
- int r = 0, k = n;
- while (k > 0)
- {
- r += powD[k % 10];
- k /= 10;
- }
- return r;
- }
-
- void write(int n)
- {
- int first, next;
- first = powerDigit(n);
- printf("%d -> ", first);
- next = first;
- next = powerDigit(first);
- while (next != first)
- {
- printf("%d -> ", next);
- next = powerDigit(next);
- }
- printf("%d\n", next);
- }
-
- int main(void)
- {
- int i;
- printf("Input N: ");
- scanf("%d", &N);
- init();
- for (i = 1; i <= N + 1; i ++)
- circle(i, 9, 0, 0);
-
- for (i = 0; i < pos; i ++)
- B[i][1] = toSort(B[i][1]);
-
- mark(pos);
-
- // for (i = 0; i < pos; i ++) printf("(%d, %d, %d) ", B[i][0], B[i][1], B[i][2]);
- printf("\n");
-
- for (i = 0; i < pos; i ++)
- if (B[i][2] == 1)
- {
- printf("(%d, %d)\n ", B[i][0], B[i][1]);
- write(B[i][1]);
- }
- return 0;
- }
复制代码 终于正确了,都是瞬间完成
增加了输出
N > 8的只要修改使用大数运算和有足够的缓存,也是能求出的 |
|