啊哈算法-坑爹的奥数

极致的暴力带来风扇渡劫般的咆哮

去掉了重复的式子

#include
int main(){
    //  xxx+xxx=xxx；
    int a[10],book[10],num1,num2,num3,total=0;
    for(a[0]=1;a[0]<=9;a[0]++){
        for(a[1]=1;a[1]<=9;a[1]++){
            for(a[2]=1;a[2]<=9;a[2]++){
                for(a[3]=1;a[3]<=9;a[3]++){
                    for(a[4]=1;a[4]<=9;a[4]++){
                        for(a[5]=1;a[5]<=9;a[5]++){
                            for(a[6]=1;a[6]<=9;a[6]++){
                                for(a[7]=1;a[7]<=9;a[7]++){
                                    for(a[8]=1;a[8]<=9;a[8]++){
                                        int flag=1;
                                        for(int tem=1;tem<10;tem++) book[tem]=0;
                                        for(int tem=0;tem<9;tem++) book[a[tem]]++;
                                        for(int tem=1;tem<10;tem++){
                                            if(book[tem]==0){
                                                flag=0;
                                                break;
                                            } 
                                        }
                                        if(flag==1){
                                            num1=a[0]*100+a[1]*10+a[2];
                                            num2=a[3]*100+a[4]*10+a[5];
                                            num3=a[6]*100+a[7]*10+a[8];
                                            if(num1==num2 && num1+num2==num3){
                                                total++;
                                                printf("%d%d%d+%d%d%d=%d%d%d ",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);
                                                if(total%5==0) printf("\n");//五个换行 
                                            }
                                            else if(num1num3){
                                                total++;
                                                printf("%d%d%d+%d%d%d=%d%d%d ",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);
                                                if(total%5==0) printf("\n");
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    printf("\ntotal : %d",total);
    return 0;
}

 2021.12.16 回来用递归写的时候发现上面写的代码有问题，改了一下。

#include
int book2[999][999];
int main(){
    //  xxx+xxx=xxx；
    int a[10],book[10],num1,num2,num3,total=0;
    for(a[0]=1;a[0]<=9;a[0]++){
        for(a[1]=1;a[1]<=9;a[1]++){
            for(a[2]=1;a[2]<=9;a[2]++){
                for(a[3]=1;a[3]<=9;a[3]++){
                    for(a[4]=1;a[4]<=9;a[4]++){
                        for(a[5]=1;a[5]<=9;a[5]++){
                            for(a[6]=1;a[6]<=9;a[6]++){
                                for(a[7]=1;a[7]<=9;a[7]++){
                                    for(a[8]=1;a[8]<=9;a[8]++){
                                        int flag=1;
                                        for(int tem=1;tem<10;tem++) book[tem]=0;
                                        for(int tem=0;tem<9;tem++) book[a[tem]]++;
                                        for(int tem=1;tem<10;tem++){
                                            if(book[tem]==0){
                                                flag=0;
                                                break;
                                            }
                                        }
                                        if(flag==1){
                                            num1=a[0]*100+a[1]*10+a[2];
                                            num2=a[3]*100+a[4]*10+a[5];
                                            num3=a[6]*100+a[7]*10+a[8];
                                            if(num1+num2==num3 && book2[num1][num2]==0){
                                                total++;
                                                printf("%d+%d=%d ",num1,num2,num3);
                                                book2[num1][num2]++;
                                                book2[num2][num1]++;
                                                if(total%5==0) printf("\n");//五个换行 
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    printf("\ntotal : %d",total);
    return 0;
}

然后下面是用第四章开头的递归写的，时间大幅度减少。

#include
void xxx(int n);
int book[10],a[10],tem[3],count=0,book2[1000][1000];

int main(){//xxx+xxx=xxx
    book[0]=1;
    xxx(1);
    printf("\ntotal:%d",count);
    return 0;
}
void xxx(int n){
    if(n==7){
        int num1=a[1]*100+a[2]*10+a[3],num2=a[4]*100+a[5]*10+a[6],num3=num1+num2,tem_num=num1+num2;
        do{
            if(book[num3%10]!=0){//数字字典查重 
                while(tem_num!=num3){
                    book[tem_num%10]--;
                    tem_num/=10;
                }
                return;
            }
            book[num3%10]++;
            num3/=10;
        }while(num3);
        
        if(book2[num1][num2]==0){//查重输出 
            printf("%d+%d=%d ",num1,num2,num1+num2);
            count++;
            book2[num1][num2]++;//输出字典 
            book2[num2][num1]++;
            if(count%5==0) printf("\n");
        }
        
        
        while(tem_num!=num3){//book复原 (因为上面查重改动了book) 
            book[tem_num%10]--;
            tem_num/=10;
        }
        return ;
    }
    else{
        for(int i=1;i<=9;i++){
            if(book[i]==0){
                a[n]=i;
                book[i]=1;//使用一个数字 
                xxx(n+1);
                book[i]=0;//放回一个数字 
            }
        }
        
    }
}