紫罗兰算式（数学代数方面的）

wayne

20# 没——问题 运行时错误，

没——问题

20# 没——问题 运行时错误， wayne 发表于 2010-8-19 15:44

我这里正常啊(我刚才编辑帖子是改那个时间复杂度,后来发现没错,又改回去了) 难道你那里错误是因为内存消耗太大? 其时还可以优化一个数量级,当时只是顺手那么写的 这个是优化过的,并且输出全部解(上一个输出的不是全部解)

1. /**************************************************************************
2. * 题目:紫罗兰算式
3. * 设第一个数是“CLOVER”；
4. * 第二个数是“CROCUS”；
5. * 第三个数是“VIOLET”；
6. * 其中第一个数与第二个数的和是第三个数，
7. * 注意：相同的字母表示同一个数字，不同的字母
8. * 表示不同的数字。每个字母的取值是从0到9的整数。
9. * http://bbs.emath.ac.cn/viewthread.php?tid=2606&extra=&page=1
10. * 分析:
11. * 设所求的三个数为X,Y,Z,通过写做10的幂的和的形式可得到方程:
12. * -99900*V+10*U-T+S+10001*R+1000*O+9900*L-10000*I+200100*C==0
13. * 分为两组:
14. * -99900*V+10*U-T+S+10001*R == -1000*O-9900*L+10000*I-200100*C
15. * 对等式两边分别将所有可能的值写入数组left和right,并分别排序
16. * 数组的每个元素除存储等式一侧的值外还需存储生成此值的变元的值
17. * 寻找两组中相等的数,时间复杂度: 10^5+10^4
18. *************************************************************************/
19. #include <stdlib.h>
20. #include <stdio.h>
22. typedef struct {int value,id;} group;//value为等式一侧的值,id为一侧变量的值依次排列在一起组成的十进制数字的值
23. int cmp(const void *a, const void *b){return ((group *)a)->value - ((group *)b)->value;}//从小到大排序
25. int main()
26. {
27. int o,l,i,c,r;//生成数据时vutsr和olic中只使用了5个
28. group left[100000],*pl=left,right[10000],*pr=right;
29. for(o=0;o<10;o++)for(l=0;l<10;l++)for(i=0;i<10;i++)for(c=0;c<10;c++)
30. {
31. pr->value=-1000*o-9900*l+10000*i-200100*c;
32. pr->id=1000*o+100*l+10*i+c;
33. pr++;
34. for(r=0;r<10;r++)
35. {
36. pl->value=-99900*o+10*l-i+c+10001*r;
37. pl->id=o*10000+l*1000+i*100+c*10+r;
38. pl++;
39. }
40. }
42. qsort(left, 100000, sizeof(group), cmp);
43. qsort(right, 10000, sizeof(group), cmp);
45. printf("%d,%d\n",left[0].value,right[0].value);
46. printf("vutsr,olic\n----------\n");
47. for(pl--,pr--;pl!=left&&pr!=right;)
48. {
49. if(pl->value==pr->value)
50. {
51. //输出变元的值,此处没有排除使得X,Y,Z中出现前导零的答案.
52. printf("%05d,%04d\n",pl->id,pr->id);
53. while((pl-1)->value==pl->value)pl--,printf("%05d,%04d\n",pl->id,pr->id);
54. while((pr-1)->value==pr->value)pr--,printf("%05d,%04d\n",pl->id,pr->id);
55. pl--,pr--;
56. }
57. if(pl->value > pr->value)pl--;else pr--;
58. }
60. return 0;
61. }

复制代码

我这里: real 0m0.038s user 0m0.028s sys 0m0.004s

wayne

real 0m0.038s user 0m0.028s sys 0m0.004s

莫非是在linux下用了time命令？ 俺是在windows下用GCC编译的。 为啥第一个是运行时错误，第二个是输出一堆的结果呢，按道理只有一个答案的

mathe

他没有检查两边id中使用了重复数据的情况,稍微修改即可:

2. /**************************************************************************
3. * ..:.....
4. * ......聯CLOVER聰.
5. * .....聯CROCUS聰.
6. * .....聯VIOLET聰.
7. * ...................
8. * .....................
9. * .................0.9....
10. * http://bbs.emath.ac.cn/viewthread.php?tid=2606&extra=&page=1
11. * ..:
12. * ........X,Y,Z,....10............:
13. * -99900*V+10*U-T+S+10001*R+1000*O+9900*L-10000*I+200100*C==0
14. * ....:
15. * -99900*V+10*U-T+S+10001*R == -1000*O-9900*L+10000*I-200100*C
16. * ..................left.right,.....
17. * ..............................
18. * .........,.....: 10^5+10^4
19. *************************************************************************/
20. #include <stdlib.h>
21. #include <stdio.h>
23. typedef struct {int value,id;} group;//value.......,id........................
24. int cmp(const void *a, const void *b){return ((group *)a)->value - ((group *)b)->value;}//......
25. int testid(int id1, int id2)
26. {
27. char b[10];
28. int i;
29. for(i=0;i<10;i++)b[i]=0;
30. for(i=0;i<5;i++){
31. b[id1%10]++;
32. id1/=10;
33. }
34. for(i=0;i<4;i++){
35. b[id2%10]++;
36. id2/=10;
37. }
38. for(i=0;i<10;i++)if(b[i]>1)return 0;
39. return 1;
40. }
42. int main()
43. {
44. int o,l,i,c,r;//.....vutsr.olic.....5.
45. group left[100000],*pl=left,right[10000],*pr=right;
46. for(o=0;o<10;o++)for(l=0;l<10;l++)for(i=0;i<10;i++)for(c=0;c<10;c++)
47. {
48. pr->value=-1000*o-9900*l+10000*i-200100*c;
49. pr->id=1000*o+100*l+10*i+c;
50. pr++;
51. for(r=0;r<10;r++)
52. {
53. pl->value=-99900*o+10*l-i+c+10001*r;
54. pl->id=o*10000+l*1000+i*100+c*10+r;
55. pl++;
56. }
57. }
59. qsort(left, 100000, sizeof(group), cmp);
60. qsort(right, 10000, sizeof(group), cmp);
62. printf("%d,%d\n",left[0].value,right[0].value);
63. printf("vutsr,olic\n----------\n");
64. for(pl--,pr--;pl!=left&&pr!=right;)
65. {
66. if(pl->value==pr->value)
67. {
68. //......,........X,Y,Z..........
69. if(testid(pl->id,pr->id))
70. printf("%05d,%04d\n",pl->id,pr->id);
71. while((pl-1)->value==pl->value){
72. pl--;
73. if(testid(pl->id,pr->id))
74. printf("%05d,%04d\n",pl->id,pr->id);
75. }
76. while((pr-1)->value==pr->value){
77. pr--;
78. if(testid(pl->id,pr->id))
79. printf("%05d,%04d\n",pl->id,pr->id);
80. }
81. pl--,pr--;
82. }
83. if(pl->value > pr->value)pl--;else pr--;
84. }
86. return 0;
87. }

复制代码

输出: -899109,-1899000 vutsr,olic ---------- 59376,0842

mathe

这个程序很简单，我给一个C++版本的:

2. #include <stdio.h>
3. #include <algorithm>
4. using namespace std;
5. #define C a[0]
6. #define L a[1]
7. #define O a[2]
8. #define V a[3]
9. #define E a[4]
10. #define R a[5]
11. #define U a[6]
12. #define S a[7]
13. #define I a[8]
14. #define T a[9]
15. #define NUM(x1,x2,x3,x4,x5,x6) ((x1)*100000+(x2)*10000+(x3)*1000+(x4)*100+(x5)*10+(x6))
16. int a[10]={0,1,2,3,4,5,6,7,8,9};
17. int main()
18. {
19. do{
20. int x=NUM(C,L,O,V,E,R);
21. int y=NUM(C,R,O,C,U,S);
22. int z=NUM(V,I,O,L,E,T);
23. if(x+y==z){
24. printf(" %d\n+%d\n-------\n %d\n",x,y,z);
25. }
26. }while(next_permutation(a,a+10));
27. return 0;
28. }

复制代码

风云剑

全排列函数next_permutation，真巧妙。

没——问题

他没有检查两边id中使用了重复数据的情况,稍微修改即可: mathe 发表于 2010-8-19 17:17

是的~,注释里的题目是复制上去的~,看来当时应该读一下~ 而且(假如注意到这个限制...囧),E不是任意的,只能是1 从开始我就无视了这条件...囧 显然的: mathe的代码也是秒以下 real 0m0.345s user 0m0.308s sys 0m0.004s 而且省空间

mathe

你的机器挺慢的。 不过这个题目，由于非常简单，我觉得代码的可读性比效率更加重要

没——问题

恩,老机器了,所以装的linux 为了学习东方的算法才写这个的

wayne

25# mathe 没想到algorithm里面竟然还有 next_permutation 这个函数！！！