聰明的暴力枚舉求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次即可！這算是比較聰明的枚舉了吧，如果有問題歡迎評論指出，本人也是演算法菜雞一枚。