啊哈算法-火柴棍等式
在枚举时,如果有枚举对象可以通过计算替代,那么直接用计算替代即可,可以大大减少枚举带来的时间。
#include#include<string.h> int main(){ int a[10]={6,2,5,5,4,5,6,3,7,6},n,book[100][100]; memset(book,0,sizeof(book)); scanf("%d",&n); n-=4; for(int i=0;i<=11111;i++){ for(int j=0;j<=11111;j++){ int sum=0,tem_i=i,tem_j=j,k=i+j,tem_k=k;//k=i+j省去了对k的枚举,大幅度减少时间 do{ sum+=a[tem_i%10]; tem_i/=10; }while(tem_i); if(sum>n) continue;//小优化,判断当前用的火柴有没有超过,超过直接下一次 do{ sum+=a[tem_j%10]; tem_j/=10; }while(tem_j); if(sum>n) continue; do{ sum+=a[tem_k%10]; tem_k/=10; }while(tem_k); if(sum==n && i+j==k){ if(i==j && book[i][j]==0){ book[i][j]=1; printf("%d+%d=%d\n",i,j,k); } else printf("%d+%d=%d\n",i,j,k); } } } printf("结束"); return 0; }