首页 > 代码库 > 第四篇 枚举思想
第四篇 枚举思想
一: 思想
有时我们解决某个问题时找不到一点规律,此时我们很迷茫,很痛苦,很蛋疼,突然我们灵光一现,发现候选答案的问题规模在百万之内,
此时我们就想到了从候选答案中逐一比较,一直找到正确解为止。
二: 条件
前面也说了,枚举是我们在无奈之后的最后一击,那么使用枚举时我们应该尽量遵守下面的两个条件。
① 地球人都不能给我找出此问题的潜在规律。
② 候选答案的集合是一个计算机必须能够承受的。
三:举例
下面是一个填写数字的模板,其中每个字都代表数字中的”0~9“,那么要求我们输入的数字能够满足此模板。
思路1):对“算”“法”“洗”“脑”“题”分别进行枚举,复杂度达到了O(n5)。
//“算”字的取值范围 for (int i1 = 1; i1 < 10; i1++) { //“法”字的取值范围 for (int i2 = 0; i2 < 10; i2++) { //“洗”字的取值范围 for (int i3 = 0; i3 < 10; i3++) { //"脑"字的取值范围 for (int i4 = 0; i4 < 10; i4++) { //"题"字的取值范围 for (int i5 = 1; i5 < 10; i5++) { count++; //一个猜想值 var guess = (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) * i1; //最终结果值 var result = i5 * 100000 + i5 * 10000 + i5 * 1000 + i5 * 100 + i5 * 10 + i5; if (guess == result)
思路2):对乘积“算算算算算算”和被乘数“算”进行枚举,复杂度达到了O(n2)。
//商 int[] resultArr = { 111111, 222222, 333333, 444444, 555555, 666666, 777777, 888888, 999999 }; //除数 int[] numArr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int count = 0; for (int i = 0; i < resultArr.Count(); i++) { for (int j = 0; j < numArr.Count(); j++) { count++; var result = resultArr[i].ToString(); var num = numArr[j].ToString(); var origin = (resultArr[i] / numArr[j]).ToString(); if (origin.LastOrDefault() == result.FirstOrDefault() && origin.FirstOrDefault() == num.FirstOrDefault() && result.Length - 1 == origin.Length)
第四篇 枚举思想
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。