聪明的暴力枚举求abcde/fghij=n

• 2022 年 11 月 3 日
• 筆記
• C/C++, 学习笔记, 算法竞赛

前言

枚举如何聪明的枚举？那就是优化啦！下面梳理之前做过的一个暴力枚举的题，想了蛮久最后把它优化了感觉还不错，算是比较聪明的枚举了。

一、题目

输入正整数n，输出所有如abcde/fghij=n的表达式，其中a-j为数字0-9的不重复的排列，这里的除为整除，请统计这样的组合一共有多少个？例如：

输入：62
输出：
79546/01283=62
94736/01528=62

二、暴力初解

初解思路：
直接调的全排列函数，枚举所有的可能然后判断所有的结果，可以就输出

#include <bits/stdc++.h> 
using namespace std; 
int main(){ 
	int a[10]={0,1,2,3,4,5,6,7,8,9}; 
	int n; cin>>n; int num=0; 
	do{ 
		int x =a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4]; 
		int y =a[5]*10000+a[6]*1000+a[7]*100+a[8]*10+a[9]; 
		if(x==y*n){ 
			cout<<a[0]<<a[1]<<a[2]<<a[3]<<a[4]<<"/"<<a[5]<<a[6]<<a[7]<<a[8]<<a[9]<<"="<<n<<endl; 
		} 
	}while(next_permutation(a,a+10)); 
	return 0; 
}

三、优化再解（借鉴bitmap）

bitmap简介：//www.cnblogs.com/cjsblog/p/11613708.html

再解思路：
欲求abcde / fghij = n的表达式，
从1234枚举到98765即可，设i 为 abcde，那么fghij = n * i，
这样问题就转化成了判断 i 和 n * i 一起是否数字为0-9的组合，
然后借鉴bitmap的思路用10位二进制数表示0-9这10个数字，遍历 i 和 n * i 的位数，如果存在0-9就把对应位的1转为0，最后计算完后如果是所有数字都不相同的话就是0；

#include<bits/stdc++.h>
using namespace std;

int judge(int a , int b)//判断a,b所有数字是否都不相同，且为0-9
{
	int allNum=1023;//所有二进制数为1，一共10个1，也就是1024-1；
	string str = to_string(a)+to_string(b);//合在一起运算
	if(a<10000 || b<10000) str+='0';//避免缺少了一个0的计算
	for(char i : str){
		int tmp=1;		
		for(int j = (i-'0');j>0;j--)//把1移到对应的位 
			tmp=tmp<<1;
		allNum&=(~tmp);//这里allNum-=tmp;也可以
	}
	return allNum;//如果a,b所有数字都不相同且为0-9那么返回0，否则返回非0;
}

int main() {
	int n=0;
    scanf("%d" , & n);
    for(int i = 1234 ; i * n < 98766 ; i ++) {
        if(!judge(i, i * n))//如果非0则不能输出所以取反跳过，如果是0那么可以输出所以取反输出可行解	
            printf("%05d / %05d = %d\n",i*n,i,n);
    }
    return 0;
}

总结

如果枚举0~9的所有排列，需要10！=3628800次！，可以接受，但是没有必要；聪明的枚举比如输入62只需要359次即可！这算是比较聪明的枚举了吧，如果有问题欢迎评论指出，本人也是算法菜鸡一枚。