找回密码
 欢迎注册
楼主: 无心人

[讨论] 方幂圈问题

[复制链接]
 楼主| 发表于 2008-12-27 09:10:25 | 显示全部楼层
打算这么做 假设表项有三个部分 1、key,就是降序排列的数字 2、Value,是Key的方幂和的数字的降序排列,去掉0 3、tag,标志,预置0 想这么处理,假设当前是prev 1、如果prev.value = prev.key,则保留,prev.tag = 1,表示关键点 2、如果通过prev.value查询key表,对应的项的next.tag是0, 1,则置prev.tag = -1表示处理项 3、如果对应项next.tag是-1,则置prev.tag = 1表示关键点 输出所有关键点 即可得到所有的环和数字 但需要再处理,才能翻译成真实数字环
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-27 14:12:51 | 显示全部楼层
这个题目比回归数还是要复杂很多的。相对来说,计算所有的回归数还是不难的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 15:09:53 | 显示全部楼层
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #define BLen 1024* 1024
  4. int B[BLen][3];
  5. int Temp[BLen];
  6. int powD[10];
  7. int N, pos;
  8. void init(void)
  9. {
  10. int i, j;
  11. for (i = 0; i < BLen; i ++)
  12. B[i][0] = B[i][1] = B[i][2] = 0;
  13. for (i = 0; i <= 9; i ++)
  14. {
  15. powD[i] = i;
  16. for (j = 2; j <= N; j ++) powD[i] *= i;
  17. }
  18. pos = 0;
  19. }
  20. int circle(int n, int b, int num, int ps)
  21. {
  22. int i, j, k;
  23. if (n == 0)
  24. {
  25. B[pos][0] = num;
  26. B[pos++][1] = ps;
  27. }
  28. else
  29. {
  30. for (i = 1; i <= b; i ++)
  31. circle(n-1, i, num*10+i, ps + powD[i]);
  32. }
  33. }
  34. int binsearch(int key, int low, int hi)
  35. {
  36. int m;
  37. if (low > hi) return (-1);
  38. if (low == hi)
  39. if (key == B[low][0]) return low; else return -1;
  40. if (key == B[low][0]) return low;
  41. if (key == B[hi][0]) return hi;
  42. if (low + 1 == hi) return -1;
  43. m = (low + hi) >> 1;
  44. if (key == B[m][0])
  45. return m;
  46. else
  47. if (key < B[m][0])
  48. return binsearch(key, low, m);
  49. else
  50. return binsearch(key, m, hi);
  51. }
  52. int toSort(int n)
  53. {
  54. int D[10];
  55. int i, j;
  56. for (i = 1; i <= 9; i ++) D[i] = 0;
  57. while (n > 0)
  58. {
  59. D[n % 10]++;
  60. n /= 10;
  61. }
  62. D[0] = 0;
  63. for (i = 9; i >= 1; i --)
  64. if (D[i])
  65. for (j = 0; j < D[i]; j++)
  66. {
  67. D[0] *= 10;
  68. D[0] += i;
  69. }
  70. return D[0];
  71. }
  72. void mark(int pos)
  73. {
  74. int i, next, j, k;
  75. for (i = 0; i < pos; i ++)
  76. if (B[i][2] == 0)
  77. if (B[i][0] == B[i][1])
  78. {
  79. B[i][2] = 1;
  80. }
  81. else
  82. {
  83. next = binsearch(B[i][1], 0, pos);
  84. if (next == -1)
  85. printf("\nError: (%d, %d)", B[i][0], B[i][1]);
  86. else
  87. if (B[next][2] != 0)
  88. B[i][2] = -1;
  89. else
  90. {
  91. j = 0;
  92. Temp[j++] = i;
  93. Temp[j++] = next;
  94. B[i][2] = 2;
  95. B[next][2] = 2;
  96. while ((B[next][2] == 0) && (B[next][0] != B[next][1]))
  97. {
  98. next = binsearch(B[next][1], 0, pos);
  99. Temp[j++] = next;
  100. B[next][2] = 2;
  101. }
  102. k = j;
  103. if ((B[next][2] == -1) || (B[next][2] == 1))
  104. for (j = 0; j < k; j ++) B[Temp[j]][2] = -1;
  105. else
  106. {
  107. for (j = 0; j < k - 1; j ++)
  108. B[Temp[j]][2] = -1;
  109. B[next][2] = 1;
  110. }
  111. }
  112. }
  113. }
  114. int main(void)
  115. {
  116. int i;
  117. printf("Input N: ");
  118. scanf("%d", &N);
  119. init();
  120. for (i = 1; i <= N + 1; i ++)
  121. circle(i, 9, 0, 0);
  122. for (i = 0; i < pos; i ++)
  123. B[i][1] = toSort(B[i][1]);
  124. mark(pos);
  125. for (i = 0; i < pos; i ++)
  126. if (B[i][2] == 1)
  127. printf("(%d, %d)\n", B[i][0], B[i][1]);
  128. // printf("\n");
  129. // for (i = 0; i < pos; i ++)
  130. // printf("(%d: %d, %d, %d)", i, B[i][0], B[i][1], B[i][2]);
  131. // printf("\n%d\n", pos);
  132. }
复制代码
===================== 输入N 范围[2..8] 输出对应的环的起始数字的数字降序排列形式 未写恢复自然形式数字的代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 15:10:20 | 显示全部楼层
N = 2的输出 (1, 1) 1 -> 1 (4, 61) 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 (9, 81) 9 -> 81 -> 65 -> 61 -> 37 (52, 92) -> 4 (62, 4) -> 4 (63, 54) -> 4 (64, 52) -> 4 (71, 5) -> 4 (72, 53) -> 4 (73, 85) -> 4 (81, 65) -> 4 (85, 98) -> 4 (86, 1) -> 1 (94, 97) -> 1 (98, 541) -> 4 (311, 11) -> 4 (621, 41) -> 4 (711, 51) -> 4 (821, 96) -> 4 (921, 86) -> 1 (941, 98) -> 4 ================== 还是存在多余的行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 15:33:38 | 显示全部楼层
手工分析N=2 仅有一个环 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 15:59:03 | 显示全部楼层
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #define BLen 1024* 1024
  4. int B[BLen][3];
  5. int Temp[BLen];
  6. int powD[10];
  7. int N, pos;
  8. void init(void)
  9. {
  10. int i, j;
  11. for (i = 0; i < BLen; i ++)
  12. B[i][0] = B[i][1] = B[i][2] = 0;
  13. for (i = 0; i <= 9; i ++)
  14. {
  15. powD[i] = i;
  16. for (j = 2; j <= N; j ++) powD[i] *= i;
  17. }
  18. pos = 0;
  19. }
  20. int circle(int n, int b, int num, int ps)
  21. {
  22. int i, j, k;
  23. if (n == 0)
  24. {
  25. B[pos][0] = num;
  26. B[pos++][1] = ps;
  27. }
  28. else
  29. {
  30. for (i = 1; i <= b; i ++)
  31. circle(n-1, i, num*10+i, ps + powD[i]);
  32. }
  33. }
  34. int binsearch(int key, int low, int hi)
  35. {
  36. int m;
  37. if (low > hi) return (-1);
  38. if (low == hi)
  39. if (key == B[low][0]) return low; else return -1;
  40. if (key == B[low][0]) return low;
  41. if (key == B[hi][0]) return hi;
  42. if (low + 1 == hi) return -1;
  43. m = (low + hi) >> 1;
  44. if (key == B[m][0])
  45. return m;
  46. else
  47. if (key < B[m][0])
  48. return binsearch(key, low, m);
  49. else
  50. return binsearch(key, m, hi);
  51. }
  52. int toSort(int n)
  53. {
  54. int D[10];
  55. int i, j;
  56. for (i = 1; i <= 9; i ++) D[i] = 0;
  57. while (n > 0)
  58. {
  59. D[n % 10]++;
  60. n /= 10;
  61. }
  62. D[0] = 0;
  63. for (i = 9; i >= 1; i --)
  64. if (D[i])
  65. for (j = 0; j < D[i]; j++)
  66. {
  67. D[0] *= 10;
  68. D[0] += i;
  69. }
  70. return D[0];
  71. }
  72. void mark(int pos)
  73. {
  74. int i, next, j, k;
  75. for (i = 0; i < pos; i ++)
  76. if (B[i][0] == B[i][1])
  77. B[i][2] = 1;
  78. else
  79. if (B[i][2] == 0)
  80. {
  81. next = binsearch(B[i][1], 0, pos-1);
  82. if (B[next][2] != 0)
  83. B[i][2] = -1;
  84. else
  85. {
  86. j = 0;
  87. Temp[j++] = i;
  88. Temp[j++] = next;
  89. B[i][2] = 2;
  90. while (B[next][2] == 0)
  91. {
  92. B[next][2] = 2;
  93. next = binsearch(B[next][1], 0, pos-1);
  94. Temp[j++] = next;
  95. }
  96. k = j;
  97. if ((B[next][2] == -1) || (B[next][2] == 1))
  98. for (j = 0; j < k - 1; j ++) B[Temp[j]][2] = -1;
  99. else
  100. {
  101. for (j = 0; j < k - 1; j ++)
  102. B[Temp[j]][2] = -1;
  103. B[next][2] = 1;
  104. }
  105. }
  106. }
  107. }
  108. int powerDigit(int n)
  109. {
  110. int r = 0, k = n;
  111. while (k > 0)
  112. {
  113. r += powD[k % 10];
  114. k /= 10;
  115. }
  116. return r;
  117. }
  118. void write(int n)
  119. {
  120. int first, next;
  121. first = powerDigit(n);
  122. printf("%d -> ", first);
  123. next = first;
  124. next = powerDigit(first);
  125. while (next != first)
  126. {
  127. printf("%d -> ", next);
  128. next = powerDigit(next);
  129. }
  130. printf("%d\n", next);
  131. }
  132. int main(void)
  133. {
  134. int i;
  135. printf("Input N: ");
  136. scanf("%d", &N);
  137. init();
  138. for (i = 1; i <= N + 1; i ++)
  139. circle(i, 9, 0, 0);
  140. for (i = 0; i < pos; i ++)
  141. B[i][1] = toSort(B[i][1]);
  142. mark(pos);
  143. // for (i = 0; i < pos; i ++) printf("(%d, %d, %d) ", B[i][0], B[i][1], B[i][2]);
  144. printf("\n");
  145. for (i = 0; i < pos; i ++)
  146. if (B[i][2] == 1)
  147. {
  148. printf("(%d, %d)\n ", B[i][0], B[i][1]);
  149. write(B[i][1]);
  150. }
  151. return 0;
  152. }
复制代码
终于正确了,都是瞬间完成 增加了输出 N > 8的只要修改使用大数运算和有足够的缓存,也是能求出的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 16:32:23 | 显示全部楼层
N = 2 (1, 1) 1 -> 1 (2, 4) 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 ============================================== N = 3 (1, 1) 1 -> 1 (52, 331) 55 -> 250 -> 133 -> 55 (61, 721) 352 -> 160 -> 217 -> 352 (73, 73) 370 -> 370 (74, 74) 407 -> 407 (442, 631) 244 -> 136 -> 244 (531, 531) 153 -> 153 (731, 731) 371 -> 371 (991, 9541) 919 -> 1459 -> 919 ======================================= N = 4 (1, 1) 1 -> 1 (882, 882) 8208 -> 8208 (6431, 6431) 1634 -> 1634 (8721, 6541) 2178 -> 6514 -> 2178 (9744, 9744) 9474 -> 9474 (9921, 93311) 6725 -> 4338 -> 4514 -> 1138 -> 4179 -> 9219 -> 13139 -> 6725
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 16:33:20 | 显示全部楼层
N = 5 (1, 1) 1 -> 1 (541, 541) 4150 -> 4150 (652, 9331) 59536 -> 73318 -> 50062 -> 10933 -> 59536 (761, 85442) 37973 -> 93149 -> 119366 -> 74846 -> 59399 -> 180515 -> 39020 -> 59324 -> 63473 -> 26093 -> 67100 -> 24584 -> 37973 (5411, 5411) 4151 -> 4151 (9761, 86333) 41273 -> 18107 -> 49577 -> 96812 -> 99626 -> 133682 -> 41063 -> 9044 -> 61097 -> 83633 -> 41273 (9842, 98732) 108899 -> 183635 -> 44156 -> 12950 -> 62207 -> 24647 -> 26663 -> 23603 -> 8294 -> 92873 -> 108899 (9843, 9843) 93084 -> 93084 (64311, 954) 63198 -> 99837 -> 167916 -> 91410 -> 60075 -> 27708 -> 66414 -> 17601 -> 24585 -> 40074 -> 18855 -> 71787 -> 83190 -> 92061 -> 66858 -> 84213 -> 34068 -> 41811 -> 33795 -> 79467 -> 101463 -> 9045 -> 63198 (86533, 55441) 8299 -> 150898 -> 127711 -> 33649 -> 68335 -> 44155 -> 8299 (87544, 87544) 54748 -> 54748 (88651, 87643) 58618 -> 76438 -> 58618 (96532, 7522) 19996 -> 184924 -> 93898 -> 183877 -> 99394 -> 178414 -> 51625 -> 14059-> 63199 -> 126118 -> 40579 -> 80005 -> 35893 -> 95428 -> 95998 -> 213040 -> 1300 -> 244 -> 2080 -> 32800 -> 33043 -> 1753 -> 20176 -> 24616 -> 16609 -> 74602 -> 25639 -> 70225 -> 19996 (97722, 97722) 92727 -> 92727 (98883, 976551) 89883 -> 157596 -> 89883 (999741, 999741) 194979 -> 194979
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 16:35:55 | 显示全部楼层
N = 6 (1, 1) 1 -> 1 (6555, 95331) 548525 -> 313179 -> 650550 -> 93531 -> 548525 (8643, 653321) 63804 -> 313625 -> 63804 (8741, 98833) 1057187 -> 513069 -> 594452 -> 570947 -> 786460 -> 477201 -> 239459 -> 1083396 -> 841700 -> 383890 -> 1057187 (85431, 985522) 824963 -> 845130 -> 282595 -> 824963 (776541, 76631) 211691 -> 578164 -> 446171 -> 172499 -> 1184692 -> 844403 -> 275161 -> 179996 -> 1758629 -> 973580 -> 927588 -> 1189067 -> 957892 -> 1458364 -> 333347 -> 124661 -> 97474 -> 774931 -> 771565 -> 313205 -> 17148 -> 383891 -> 1057188 -> 657564 -> 246307 -> 169194 -> 1113636 -> 94773 -> 771564 -> 301676 -> 211691 (885443, 885443) 548834 -> 548834
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-27 16:37:05 | 显示全部楼层
N = 7 (1, 1) 1 -> 1 (98763, 9887775) 11526027 -> 1181862 -> 4474371 -> 1698426 -> 7456506 -> 1556049 -> 5235540 -> 253074 -> 920367 -> 5888763 -> 7475247 -> 2581650 -> 2533467 -> 1202490 -> 4799610 -> 10685802 -> 4552494 -> 4988499 -> 18575979 -> 13466427 -> 1418499 -> 11695860 -> 7518120 -> 2998950 -> 16524312 -> 376890 -> 7985787 -> 11526027 (98821, 987742) 8543719 -> 7800361 -> 3202819 -> 6882565 -> 4910554 -> 4971988 -> 14600170 -> 1119865 -> 7238185 -> 5098288 -> 11152678 -> 3278887 -> 7940857 -> 8621716 -> 3480697 -> 8002171 -> 2920825 -> 6958630 -> 7520305 -> 982108 -> 8977402 -> 8543719 (98871, 98871) 9800817 -> 9800817 (884211, 884211) 4210818 -> 4210818 (965531, 5433221) 99140 -> 9582323 -> 6962876 -> 8543600 -> 2473784 -> 3779321 -> 6434558 -> 2568293 -> 7240625 -> 1198244 -> 6913019 -> 9848063 -> 9275780 -> 8605460 -> 2751533 -> 984296 -> 11959538 -> 11821529 -> 6958505 -> 7394432 -> 5643782 -> 3297455 -> 5781461 -> 3295142 -> 4879922 -> 12503273 -> 906299 -> 14628971 -> 8000114 -> 2113538 -> 2179781 -> 8527337 -> 3826865 -> 4834616 -> 2691980 -> 11943155 -> 4957793 -> 11309720 -> 5608829 -> 9335462 -> 5161916 -> 5420969 -> 9940511-> 9660449 -> 10158578 -> 5174099 -> 10483991 -> 11681663 -> 2939150 -> 9646379 -> 10967924 -> 10685930 -> 7240370 -> 1665785 -> 3636818 -> 4758551 -> 3171455 -> 998366 -> 12225149 -> 4877864 -> 6154094 -> 5173799 -> 11293337 -> 5613203 -> 362564 -> 656696 -> 5980838 -> 11154737 -> 1743785 -> 3840935 -> 6979004 -> 10685801 -> 4552367 -> 1278428 -> 5034488 -> 4307384 -> 2957837 -> 8607647 -> 4320494 -> 4834436 -> 2430614 -> 315020 -> 80441 -> 2129921 -> 9566324 -> 5439665 -> 5517662 -> 1539794 -> 10486178 -> 5314169 -> 5159603 -> 5221343 -> 99140 (976432, 975541) 5779147 -> 7348108 -> 5036419 -> 5159602 -> 5219284 -> 6974887 -> 10920679 -> 10669546 -> 5717287 -> 4646035 -> 672952 -> 5964829 -> 12037663 -> 1387918 -> 9803005 -> 6960433 -> 5363599 -> 10006498 -> 7176442 -> 1959919 -> 19210003-> 4785286 -> 5392420 -> 4879921 -> 12503146 -> 376762 -> 2209273 -> 5609083 ->7240369 -> 5905147 -> 5779147 (977552, 8665433) 2755907 -> 6586433 -> 2755907 (984222, 9988866) 16417266 -> 1679865 -> 8341662 -> 2675724 -> 2021787 -> 3744495 -> 5735976 -> 6868428 -> 6867840 -> 5594103 -> 4957791 -> 11307534 -> 922428 -> 6896889-> 16417266 (988531, 987655) 8139850 -> 9057586 -> 8139850 (7433211, 844431) 2148492 -> 6913146 -> 5361414 -> 393018 -> 6884496 -> 9569913 -> 14709156 -> 5980959 -> 16602309 -> 5345157 -> 1076490 -> 5902833 -> 6962748 -> 8280048-> 6307968 -> 8265723 -> 3281199 -> 11665407 -> 1477926 -> 6726504 -> 1478052 -> 3015333 -> 86874 -> 5314167 -> 1200177 -> 1647216 -> 1399929 -> 19134192 -> 9584640 -> 7270950 -> 6508308 -> 4554552 -> 345396 -> 5161788 -> 5375910 -> 5764950 -> 6059082 -> 7238310 -> 2925198 -> 11741472 -> 1679985 -> 12844695 -> 7271079-> 7253727 -> 2551197 -> 5762892 -> 8061981 -> 9257211 -> 5684895 -> 9429843 ->11698173 -> 7985790 -> 13388301 -> 4200867 -> 3217143 -> 844431 -> 2148492 (7754211, 7754211) 1741725 -> 1741725 (9663211, 8555431) 2350099 -> 9646378 -> 8282107 -> 5018104 -> 2191663 -> 5345158 -> 2350099 (9766421, 9887621) 10080881 -> 6291458 -> 7254695 -> 6059210 -> 5141159 -> 4955606 -> 5515475 -> 1152428 -> 2191919 -> 14349038 -> 6917264 -> 6182897 -> 10080881 (9877621, 887722) 5841646 -> 2767918 -> 8807272 -> 5841646 (9965321, 9965321) 9926315 -> 9926315 (99954421, 99954421) 14459929 -> 14459929
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-22 13:36 , Processed in 0.025666 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表