网站建设需要什么流程宁夏建设银行发行寄念币网站

网站建设需要什么流程,宁夏建设银行发行寄念币网站,电脑科技网站模板,wordpress博客简洁主题浅浅氵一篇特地写篇笔记假设手头有 n 个数字#xff0c;需要从中选出 k 个不同的数字相加。问题是#xff1a;有多少种选法#xff0c;能让这 k 个数字的和是质数#xff1f;举个简单的例子#xff1a; 有数字#xff1a;3, 7, 12, 19 要从中选 3 个数字相加 那么所有可能…浅浅氵一篇特地写篇笔记假设手头有 n 个数字需要从中选出 k 个不同的数字相加。问题是有多少种选法能让这 k 个数字的和是质数举个简单的例子有数字3, 7, 12, 19要从中选 3 个数字相加那么所有可能的组合是371222不是质数371929是质数3121934不是质数7121938不是质数所以答案是只有 1 种选法能得到质数和。核心思路分析这个问题看似简单但涉及到几个关键点1. 组合问题 vs 排列问题这是最开始容易混淆的地方组合{3,7,12} 和 {7,3,12} 是同一个组合顺序不重要排列{3,7,12} 和 {7,3,12} 是不同的排列顺序很重要这个问题显然是组合问题所以需要避免重复计数。2. 质数判断质数是只能被1和自身整除的大于1的自然数。比如2, 3, 5, 7, 11……判断一个数是不是质数最直接的方法就是检查它能不能被2到n-1之间的数整除。但是这样太慢了有个小技巧只需要检查到 √n 就可以了。为什么呢因为如果一个数 n 有大于√n的因子那它必然有小于√n的对应因子。代码实现过程我先把完整的代码展示一下然后详细解释#includeiostream using namespace std; int n, k, a[100010], b[100010], cnt 0; bool judge(int y)//判断质数 { if (y 2) return 0; for (int i 2; i * i y; i) { if (y % i 0)return 0; } return 1; } void dfs(int x) { if (x k 1) { int sum0; for (int i 1; i k; i) { sum b[a[i]]; } if (judge(sum)) cnt; return; } for (int i a[x - 1] 1; i n; i) { a[x] i; dfs(x 1); } } int main() { cin n k; for (int i 1; i n;i) { cin b[i]; } dfs(1); cout cnt; return 0; }代码逐行解析第一部分头文件和变量声明#includeiostream using namespace std; int n, k, a[100010], b[100010], cnt 0;#includeiostream引入输入输出流库相当于拿到控制台的遥控器using namespace std;打开标准命名空间这样写cout时就不用写成std::cout了变量声明n总共有多少个数字k要选几个数字a[100010]记录选择了哪些数字的位置索引b[100010]存储实际的数字cnt计数器记录符合条件的方案数初始化为0第二部分质数判断函数bool judge(int y)//判断质数 { if (y 2) return 0; // 小于2肯定不是质数 for (int i 2; i * i y; i) // 只检查到sqrt(y) { if (y % i 0)return 0; // 如果能整除不是质数 } return 1; // 通过了所有检查是质数 }这个函数很关键检查范围是i * i y而不是i y这就是刚才说的优化技巧。第三部分深度优先搜索DFSvoid dfs(int x) { if (x k 1) // 已经选了k个数字 { int sum0; for (int i 1; i k; i) // 计算选出的k个数字的和 { sum b[a[i]]; // a[i]记录的是位置b[a[i]]才是实际数字 } if (judge(sum)) cnt; // 如果是质数计数器加1 return; } for (int i a[x - 1] 1; i n; i) // 关键避免重复 { a[x] i; // 记录选择第i个数字 dfs(x 1); // 继续选择下一个数字 } }这是算法的核心用深度优先搜索来生成所有组合。解释一下关键点x参数表示当前正在选第几个数字当x k 1时说明已经选了k个数字可以计算和并判断了循环中的i a[x - 1] 1确保了每次选择的位置都比上一次大这样就避免了重复组合比如选择了位置2的数字后下一次就从位置3开始选不会回头选位置1这样就不会产生{1,2,3}和{2,1,3}这样的重复。第四部分主函数int main() { cin n k; // 读取n和k for (int i 1; i n;i) // 读取n个数字 { cin b[i]; // 存储到b数组中 } dfs(1); // 从选第1个数字开始 cout cnt; // 输出结果 return 0; }我踩过的坑坑1数组索引的选择一开始还挺纠结数组索引到底该从0开始还是从1开始最后我选择了从1开始因为这样更直观b[1]存储第1个数字b[2]存储第2个数字以此类推……但要注意循环条件也要相应调整比如for (int i 1; i n; i)而不是for (int i 0; i n; i)。坑2全局变量的初始化在代码中数组a[100010]是全局变量。这里有个小知识点全局变量会自动初始化为0所以当我第一次调用dfs(1)时for (int i a[x - 1] 1; i n; i) // 第一次i a[0] 1 0 1 1这样就正确地从第1个位置开始选择了。如果a是局部变量就需要手动初始化为0了。坑3和的计算时机我最初犯过一个错误在每次递归时都计算部分和。但其实等到选满k个数字后再一次性计算更简单。算法复杂度分析这个算法的时间复杂度主要取决于组合数C(n,k) 种选择方案每种方案需要O(√sum)的时间判断质数对于n≤20的情况完全在可接受范围内。总结DFS是解决组合问题的利器通过维护起始位置可以避免重复质数判断有优化技巧只需检查到√n全局变量会自动初始化这个细节很重要代码调试要耐心有时候小错误会导致大问题