排列搜索

发布时间:2017-5-30 3:02:54 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"排列搜索",主要涉及到排列搜索方面的内容,对于排列搜索感兴趣的同学可以参考一下。

设数组a包含n个元素恰好是0..n - 1的一个排列,给定b[0],b[1],b[2],b[3]问有多少个0..n-1的排列a,满足(a[a[b[0]]]*b[0]+a[a[b[1]]]*b[1]+a[a[b[2]]]*b[2]+a[a[b[3]]]*b[3])%n==k ? 输入包含5个参数:N,K,B0,B1,B2,B3,其中 4<= N<12, 0 <= K,B0,B1,B2,B3 < N。 #include <stdio.h> #include <iostream> #include <string> using namespace std; class Test { public: static void parse(int &n, int &k, int pos, bool *flag, char *buf, long long int *factor, int &used, long long int &count, int &b0, int &b1, int &b2, int &b3) { if (pos == 8) { if ((buf[buf[b0]]*b0 + buf[buf[b1]]*b1 + buf[buf[b2]]*b2 + buf[buf[b3]]*b3) % n == k) { count += factor[n-used]; } return; } for (int i = 0; i < n; i++) { bool newAssigned = false; if (pos == 0) { buf[b0] = i; flag[i] = true; used = 1; parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); buf[b0] = -1; flag[i] = false; used--; } else if (pos == 1) { if (buf[buf[b0]] == -1) { if (flag[i]) { continue; } buf[buf[b0]] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[buf[b0]] = -1; flag[i] = false; used--; } else { break; } } else if (pos == 2) { if (buf[b1] == -1) { if (flag[i]) { continue; } buf[b1] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[b1] = -1; flag[i] = false; used--; } else { break; } } else if (pos == 3) { if (buf[buf[b1]] == -1) { if (flag[i]) { continue; } buf[buf[b1]] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[buf[b1]] = -1; flag[i] = false; used--; } else { break; } } else if (pos == 4) { if (buf[b2] == -1) { if (flag[i]) { continue; } buf[b2] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[b2] = -1; flag[i] = false; used--; } else { break; } } else if (pos == 5) { if (buf[buf[b2]] == -1) { if (flag[i]) { continue; } buf[buf[b2]] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[buf[b2]] = -1; flag[i] = false; used--; } else { break; } } else if (pos == 6) { if (buf[b3] == -1) { if (flag[i]) { continue; } buf[b3] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[b3] = -1; flag[i] = false; used--; } else { break; } } else if (pos == 7) { if (buf[buf[b3]] == -1) { if (flag[i]) { continue; } buf[buf[b3]] = i; flag[i] = true; used++; newAssigned = true; } parse(n, k, pos+1, flag, buf, factor, used, count, b0, b1, b2, b3); if (newAssigned) { buf[buf[b3]] = -1; flag[i] = false; used--; } else { break; } } } } static int howmany (int N,int K,int B0,int B1,int B2,int B3) { bool flag[11]; char buf[11]; for (int i = 0; i < N; i++) { flag[i] = false; buf[i] = -1; } long long int factor[12]; factor[0] = 1; for (int i = 1; i < 12; i++) { factor[i] = factor[i-1] * i; } int used = 0; long long int count = 0; parse(N, K, 0, flag, buf, factor, used, count, B0, B1, B2, B3); return count; } }; //start 提示:自动阅卷起始唯一标识,请勿删除或增加。 int main() { cout<<Test::howmany(11,6,5,9,8,7)<<endl; } //end //提示:自动阅卷结束唯一标识,请勿删除或增加。

上一篇:VC6修改注册表来改字体
下一篇:linux CentOS6 安装kchmviewer 6问题的解决方法

相关文章

关键词: 排列搜索

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。