华师一附中OI组

标题: 数字游戏中的判断重复问题 [打印本页]
作者: diggersun    时间: 2014-11-22 14:24
标题: 数字游戏中的判断重复问题
本帖最后由 diggersun 于 2014-11-22 14:40 编辑

数学中常见这样的智力题：
ONE+ONE=TWO
AHHAAH/JOKE=HA
等等，其中每个字母表示一个数字，不同的字母呢，他还表示不同的数字，请问，分别是多少呢？
作者: diggersun    时间: 2014-11-22 14:39
本帖最后由 diggersun 于 2015-10-31 23:48 编辑

标准的做法是用a(0)-a(9)来记录每个数字出现的次数，若设初值为1，每出现一起次数减1，那么查找十个数字中谁小于0就说明谁出现了不止一次。
枚举时候也充分考虑到了数字的特殊性，比如hahaah的枚举生成。
  1. for (i=0; i<=9; i++) aa[i]=1;
  2. 假设每个数字只能出现1次
  3. aa[h]--;aa[a]--;aa[j]--;aa[o]--;aa[k]--;     aa[e]--;
  4. b=true;     i=0;  类似判断质数时的初值设置
  5. while (b && i<=9)
  6.                 {
  7.                     if (aa[i]<0) b=false ;
  8.                     else i++;
  9.                 }
  10. b=false出现了重复 完全类似经典的质数判断
复制代码


  1. # include <iostream>
  2. int aa[10]; //表示这个数字被用了多少次，注意0..9共有10个数字，10个可能！！！！
  3. int a,h,ha,ahhaah,joke,j,o,k,e;
  4. bool b;
  5. int i;
  6. using namespace std;
  7. int main()
  8. {
  9.     for (ha=10; ha<=99; ha++)
  10.         for (joke=1000; joke<=9999; joke++)
  11.         {
  12.             ahhaah=joke*ha;
  13.             h=ha/10;      a=ha%10;
  14.             j=joke/1000;        o=joke/100%10;         k=joke/10%10;         e=joke%10;
  15.             if (ahhaah==11001*h+100110*a)
  16.             {
  17.                 b=true;     for (i=0; i<=9; i++) aa[i]=1;
  18.                 aa[h]--;              aa[a]--;
  19.                 aa[j]--;                aa[o]--;                aa[k]--;                aa[e]--;
  20.                 i=0;                while (b && i<=9)
  21.                 {
  22.                     if (aa[i]<0) b=false ;
  23.                     else i++;
  24.                 }
  25.                 if (b) cout <<ahhaah<<'/'<<joke<<'='<<ha<<endl;
  26.             }
  27.         }
  28. }

复制代码
作者: diggersun    时间: 2014-11-22 15:12
例题2  将1到9 九个数字围成一个边长为4 的正三角形，让每条边上的数字和都等于P，输入P，问有多少种摆法呢？

好理解 但是效率不高的解法
  1. # include <iostream>
  2. int a,b,c,d,e,f,g,h,i,p;//表示这9 个数字
  3. int aa[10];//a[0]被浪费了；
  4. bool bb;
  5. int ii;
  6. using namespace std;
  7. int main()
  8. {
  9.    cin>>p;
  10.    for (a=1;a<=9;a++)
  11.    for (b=1;b<=9;b++)
  12.    for (c=1;c<=9;c++)
  13.    for (d=1;d<=9;d++)
  14.    for (e=1;e<=9;e++)
  15.    for (f=1;f<=9;f++)
  16.    for (g=1;g<=9;g++)
  17.    for (h=1;h<=9;h++)
  18.    for (i=1;i<=9;i++)
  19.      if ((a+b+c+d==p) &&(d+e+f+g==p) &&(g+h+i+a==p) )
  20.    {
  21.        bb=true;
  22.        for (ii=1;ii<=9;ii++) aa[ii]=1;
  23.        aa[a]--;aa[b]--;aa[c]--;aa[d]--;aa[e]--;
  24.        aa[f]--;aa[g]--;aa[h]--;aa[i]--;
  25.        ii=1;while ((ii<=9) && bb) {if (aa[ii]<0) bb=false; else ii++;}
  26.        if (bb)
  27.          {  cout <<a<<'+'<<b<<'+'<<c<<'+'<<d<<'=';
  28.             cout <<d<<'+'<<e<<'+'<<f<<'+'<<g<<'=';
  29.             cout <<g<<'+'<<h<<'+'<<i<<'+'<<a<<endl;
  30.          }
  31.    }

  33. }
复制代码
作者: /wjr/    时间: 2014-11-22 21:48
例二的奇葩解法。。。
  1. #include<iostream>
  2. using namespace std;
  3. int p,a[10],p0;
  4. long long tot;
  5. bool b[10],t;
  6. void print()
  7. {
  8.         for(int i=1;i<=9;i++)
  9.         {       
  10.                 if(!b[i]&&!t)a[8]=i,t=1;
  11.                 else if(!b[i]&&t)a[9]=i;
  12.         }
  13.         cout<<tot++<<":"<<a[1]<<"+"<<a[2]<<"+"<<a[3]<<"+"<<a[4]<<"="<<a[4]<<"+"<<a[5]<<"+"<<a[6]<<"+"<<a[7]<<"="<<a[7]<<"+"<<a[8]<<"+"<<a[9]<<"+"<<a[1]<<endl;
  14.         cout<<tot++<<":"<<a[1]<<"+"<<a[2]<<"+"<<a[3]<<"+"<<a[4]<<"="<<a[4]<<"+"<<a[5]<<"+"<<a[6]<<"+"<<a[7]<<"="<<a[7]<<"+"<<a[9]<<"+"<<a[8]<<"+"<<a[1]<<endl;//没办法啊，只能输出这么长了
  15. }
  16. void search(int i)
  17. {
  18.         for(int j=1;j<=9;j++)
  19.         if(!b[j]&&!b[p-a[i-1]-a[i+2]-j]&&p-a[i-1]-a[i+2]-j<=9&&p-a[i-1]-a[i+2]-j>=1&&p-a[i-1]-a[i+2]-j!=j)
  20.         {
  21.                 a[i]=j;a[i+1]=p-a[i-1]-a[i+2]-j;
  22.                 b[a[i]]=b[a[i+1]]=1;
  23.                 if(i==5)print();
  24.                 else search(i+3);
  25.                 b[a[i]]=b[a[i+1]]=0;
  26.         }
  27. }
  28. int main()
  29. {
  30.         cin>>p;
  31.         p0=p*3-45;
  32.         for(a[1]=1;a[1]<=9;a[1]++)
  33.         for(a[4]=1;a[4]<=9;a[4]++)
  34.         if(a[1]!=a[4]&&p0-a[1]-a[4]<=9&&p0-a[1]-a[4]>0&&p0-a[1]-a[4]!=a[1]&&p0-a[1]-a[4]!=a[4])
  35.         {a[7]=p0-a[1]-a[4];b[a[1]]=b[a[4]]=b[a[7]]=1;search(2);b[a[1]]=b[a[4]]=b[a[7]]=0;}
  36.         return 0;
  37. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2