[other] 6月21日的数学题的穷举算法
Tofloor
poster avatar
水月
deepin
2024-06-21 22:50
Author

原题:

小明五次输入四位数的手机密码均错误,但是每次输入的密码中有两位数字正确,位置都不对。现求小明正确的四位数手机密码?

五次手机密码分别是:

6087 5173 1358 3825 2531

代码使用C语言编写,写的很潦草,见笑了。

#include 
#include 

void paixu(int a[],int x[],int s[],int m[][4],int level);
bool Compare(int a[],int b[]);
bool Exit(int a,int b[]);

int main(){
	int m[5][4]={
		{6,0,8,7},
		{5,1,7,3},
		{1,3,5,8},
		{3,8,2,5},
		{2,5,3,1}
	};
	int A[4];
	int X[4]={0};
	int S[4];
	// 这里选出可能为密码的一组数字 然后进行验算
	// 通过验算就输出
	for(int i=0; i<3; ++i){
		for(int t=i+1; t<4; ++t){
			for(int j=0; j<3; ++j){
				for(int k=j+1; k<4; ++k){
					A[0]=m[0][i];
					A[1]=m[0][t];
					A[2]=m[4][j];
					A[3]=m[4][k];
					paixu(A,X,S,m,0);
				}
			}
		}
	}
}
// 对选出来的数进行排列组合,最后进行验算
void paixu(int a[],int x[],int s[],int m[][4],int level){
	if(level == 4){
		for(int i=0; i<5; ++i){
			if(Compare(m[i],s) == false)
				return;
		}
		printf("%d %d %d %d\n",s[0],s[1],s[2],s[3]);
		return;
	}
	for(int t=0; t<4; ++t){
		if(x[t] == 0){
			x[t] = 1;
			s[level]=a[t];
			paixu(a,x,s,m,level+1);
			x[t] = 0;
		}
	}
}
// a:输入的密码 b: 正确的密码
bool Compare(int a[],int b[]){
	int same=0;
	for(int i=0; i<4; ++i){
		if(a[i] == b[i])
			return false;
		if(Exit(a[i],b)){ // 正确的数字的个数
			same++;
		}
	}
	if(same == 2)
		return true;
	else
		return false;
}
bool Exit(int a,int b[]){ // b数组中是否存在a
	for(int i=0; i<4; ++i){
		if(a == b[i])
			return true;
	}
	return false;
}

众所周知,程序员不喜欢写注释【狗头】。

Reply Favorite View the author
All Replies
晚秋(lateautumn)
Moderator
2024-06-22 08:09
#1

太厉害了like

Reply View the author
hanzn-zzx
deepin
2024-06-22 09:25
#2

屏幕截图 2024-06-21 231000.png

运行实证:答案是对的

Reply View the author
tangp
deepin
2024-06-22 11:08
#3

穷举法时空复杂度太大了。而且你还用了递归。

Reply View the author
tangp
deepin
2024-06-22 11:10
#4

我打算给出新解法,说不定我也能获个奖

Reply View the author
水月
deepin
2024-06-22 11:46
#5
tangp

我打算给出新解法,说不定我也能获个奖

期待阁下的思路与算法。

Reply View the author
乾豫恒益
deepin
2024-06-22 16:03
#6

这个好,关注一下,刚好思考思考。。。

Reply View the author
deepin-superuser
deepin
2024-06-24 13:51
#7
var a = [0, 7, 8];
var b = [2, 6, 7];
var c = [0, 1, 6];
var d = [0, 2, 6];

var f = [1, 3, 2, 4, 0, 4, 1, 2, 3, 0]

for (var aa = 0; aa < a.length; aa++) {
    for (var bb = 0; bb < b.length; bb++) {
        for (var cc = 0; cc < c.length; cc++) {
            for (var dd = 0; dd < d.length; dd++) {
                if (a[aa] != b[bb] && a[aa] != b[bb] && a[aa] != c[cc] && a[aa] != d[dd] && b[bb] != c[cc] && b[bb] != d[dd] && c[cc] != d[dd]) {
                    if (f[a[aa]] + f[b[bb]] + f[c[cc]] + f[d[dd]] == 10) {
                        console.log(a[aa] + '' + b[bb] + '' + c[cc] + '' + d[dd])
                    }
                }
            }
        }
    }
}
Reply View the author