数学研发论坛

 找回密码
 欢迎注册
楼主: mathematica

[提问] 紫罗兰算式(数学代数方面的)

[复制链接]
发表于 2010-8-19 15:44:10 | 显示全部楼层
20# 没——问题

运行时错误,
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 16:22:20 | 显示全部楼层
本帖最后由 没——问题 于 2010-8-19 16:24 编辑
20# 没——问题

运行时错误,
wayne 发表于 2010-8-19 15:44


我这里正常啊(我刚才编辑帖子是改那个时间复杂度,后来发现没错,又改回去了)

难道你那里错误是因为内存消耗太大?
其时还可以优化一个数量级,当时只是顺手那么写的
这个是优化过的,并且输出全部解(上一个输出的不是全部解)
  1. /**************************************************************************
  2. * 题目:紫罗兰算式
  3. *      设第一个数是“CLOVER”;
  4. *      第二个数是“CROCUS”;
  5. *      第三个数是“VIOLET”;
  6. *      其中第一个数与第二个数的和是第三个数,
  7. *      注意:相同的字母表示同一个数字,不同的字母
  8. *      表示不同的数字。每个字母的取值是从0到9的整数。
  9. *      /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>

  21. typedef struct {int value,id;} group;//value为等式一侧的值,id为一侧变量的值依次排列在一起组成的十进制数字的值
  22. int cmp(const void *a, const void *b){return ((group *)a)->value - ((group *)b)->value;}//从小到大排序

  23. int main()
  24. {
  25.     int o,l,i,c,r;//生成数据时vutsr和olic中只使用了5个
  26.     group left[100000],*pl=left,right[10000],*pr=right;
  27.     for(o=0;o<10;o++)for(l=0;l<10;l++)for(i=0;i<10;i++)for(c=0;c<10;c++)
  28.     {
  29.         pr->value=-1000*o-9900*l+10000*i-200100*c;
  30.         pr->id=1000*o+100*l+10*i+c;
  31.         pr++;
  32.      for(r=0;r<10;r++)   
  33.         {
  34.             pl->value=-99900*o+10*l-i+c+10001*r;
  35.             pl->id=o*10000+l*1000+i*100+c*10+r;
  36.             pl++;
  37.         }
  38.     }

  39.     qsort(left, 100000, sizeof(group), cmp);
  40.     qsort(right, 10000, sizeof(group), cmp);

  41.     printf("%d,%d\n",left[0].value,right[0].value);
  42.     printf("vutsr,olic\n----------\n");
  43.     for(pl--,pr--;pl!=left&&pr!=right;)
  44.     {
  45.         if(pl->value==pr->value)
  46.         {
  47.             //输出变元的值,此处没有排除使得X,Y,Z中出现前导零的答案.
  48.             printf("%05d,%04d\n",pl->id,pr->id);
  49.             while((pl-1)->value==pl->value)pl--,printf("%05d,%04d\n",pl->id,pr->id);
  50.             while((pr-1)->value==pr->value)pr--,printf("%05d,%04d\n",pl->id,pr->id);
  51.             pl--,pr--;
  52.         }
  53.         if(pl->value > pr->value)pl--;else pr--;
  54.     }

  55.     return 0;
  56. }
复制代码
我这里:
real        0m0.038s
user        0m0.028s
sys        0m0.004s
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 16:47:28 | 显示全部楼层
real        0m0.038s
user        0m0.028s
sys        0m0.004s

莫非是在linux下用了time命令?

俺是在windows下用GCC编译的。
为啥第一个是运行时错误,第二个是输出一堆的结果呢,按道理只有一个答案的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 17:17:49 | 显示全部楼层
他没有检查两边id中使用了重复数据的情况,稍微修改即可:

  1. /**************************************************************************
  2. * ..:.....
  3. *      ......聯CLOVER聰.
  4. *      .....聯CROCUS聰.
  5. *      .....聯VIOLET聰.
  6. *      ...................
  7. *      .....................
  8. *      .................0.9....
  9. *      /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>

  21. typedef struct {int value,id;} group;//value.......,id........................
  22. int cmp(const void *a, const void *b){return ((group *)a)->value - ((group *)b)->value;}//......
  23. int testid(int id1, int id2)
  24. {
  25.     char b[10];
  26.     int i;
  27.     for(i=0;i<10;i++)b[i]=0;
  28.     for(i=0;i<5;i++){
  29.         b[id1%10]++;
  30.         id1/=10;
  31.     }
  32.     for(i=0;i<4;i++){
  33.        b[id2%10]++;
  34.        id2/=10;
  35.     }
  36.     for(i=0;i<10;i++)if(b[i]>1)return 0;
  37.     return 1;
  38. }

  39. int main()
  40. {
  41.     int o,l,i,c,r;//.....vutsr.olic.....5.
  42.     group left[100000],*pl=left,right[10000],*pr=right;
  43.     for(o=0;o<10;o++)for(l=0;l<10;l++)for(i=0;i<10;i++)for(c=0;c<10;c++)
  44.     {
  45.         pr->value=-1000*o-9900*l+10000*i-200100*c;
  46.         pr->id=1000*o+100*l+10*i+c;
  47.         pr++;
  48.      for(r=0;r<10;r++)   
  49.         {
  50.             pl->value=-99900*o+10*l-i+c+10001*r;
  51.             pl->id=o*10000+l*1000+i*100+c*10+r;
  52.             pl++;
  53.         }
  54.     }

  55.     qsort(left, 100000, sizeof(group), cmp);
  56.     qsort(right, 10000, sizeof(group), cmp);

  57.     printf("%d,%d\n",left[0].value,right[0].value);
  58.     printf("vutsr,olic\n----------\n");
  59.     for(pl--,pr--;pl!=left&&pr!=right;)
  60.     {
  61.         if(pl->value==pr->value)
  62.         {
  63.             //......,........X,Y,Z..........
  64.             if(testid(pl->id,pr->id))
  65.             printf("%05d,%04d\n",pl->id,pr->id);
  66.             while((pl-1)->value==pl->value){
  67.               pl--;
  68.               if(testid(pl->id,pr->id))
  69.                  printf("%05d,%04d\n",pl->id,pr->id);
  70.             }
  71.             while((pr-1)->value==pr->value){
  72.                   pr--;
  73.                  if(testid(pl->id,pr->id))
  74.                   printf("%05d,%04d\n",pl->id,pr->id);
  75.             }
  76.             pl--,pr--;
  77.         }
  78.         if(pl->value > pr->value)pl--;else pr--;
  79.     }

  80.     return 0;
  81. }
复制代码
输出:
-899109,-1899000
vutsr,olic
----------
59376,0842
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 17:33:59 | 显示全部楼层
这个程序很简单,我给一个C++版本的:

  1. #include <stdio.h>
  2. #include <algorithm>
  3. using namespace std;
  4. #define C a[0]
  5. #define L a[1]
  6. #define O a[2]
  7. #define V a[3]
  8. #define E a[4]
  9. #define R a[5]
  10. #define U a[6]
  11. #define S a[7]
  12. #define I a[8]
  13. #define T a[9]
  14. #define NUM(x1,x2,x3,x4,x5,x6) ((x1)*100000+(x2)*10000+(x3)*1000+(x4)*100+(x5)*10+(x6))
  15. int a[10]={0,1,2,3,4,5,6,7,8,9};
  16. int main()
  17. {
  18.     do{
  19.          int x=NUM(C,L,O,V,E,R);
  20.          int y=NUM(C,R,O,C,U,S);
  21.          int z=NUM(V,I,O,L,E,T);
  22.          if(x+y==z){
  23.             printf(" %d\n+%d\n-------\n %d\n",x,y,z);
  24.          }
  25.     }while(next_permutation(a,a+10));
  26.     return 0;
  27. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 17:54:16 | 显示全部楼层
全排列函数next_permutation,真巧妙。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 18:03:27 | 显示全部楼层
他没有检查两边id中使用了重复数据的情况,稍微修改即可:
mathe 发表于 2010-8-19 17:17


是的~,注释里的题目是复制上去的~,看来当时应该读一下~
而且(假如注意到这个限制...囧),E不是任意的,只能是1
从开始我就无视了这条件...囧

显然的:
mathe的代码也是秒以下
real        0m0.345s
user        0m0.308s
sys        0m0.004s
而且省空间
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 18:19:05 | 显示全部楼层
你的机器挺慢的。
不过这个题目,由于非常简单,我觉得代码的可读性比效率更加重要
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-19 18:54:30 | 显示全部楼层
恩,老机器了,所以装的linux
为了学习东方的算法才写这个的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-21 15:08:22 | 显示全部楼层
25# mathe

没想到algorithm里面竟然还有  next_permutation 这个函数!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-2-17 17:38 , Processed in 0.178548 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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