基础算法(一)穷举法

计算机算法穷举法《探索神奇的计算机算法——穷举法》嘿，同学们！你们知道吗？在计算机的世界里，有一种超级有趣的算法，叫做穷举法！这名字听起来是不是有点怪？别着急，让我来给你们好好讲讲。

就好像我们在一个超级大的宝箱里找宝贝，但是我们不知道宝贝具体长啥样。

那怎么办呢？我们只能一个一个地把箱子里的东西拿出来看，直到找到我们想要的那个宝贝为止。

这穷举法呀，就跟这个差不多！比如说，我们要找一个密码。

假设这个密码是由数字0 到9 组成的，而且只有4 位。

那我们怎么办呢？穷举法就登场啦！从0000 开始，一个一个试，0001、0002、0003……一直试到9999 ，总会找到正确的那个密码。

我之前就和我的小伙伴们一起做过这样类似的小游戏。

我们把一个小礼物藏在了教室里，然后给了一些提示，让大家通过穷举的方法来找。

有的同学从第一排的桌子开始找，有的从后面的柜子开始，大家忙得不亦乐乎。

“哎呀，我找了这么多地方都没找到，难道在这个角落？”小明一边嘟囔着，一边翻着角落里的书包。

“哈哈，我肯定能比你们先找到！”小红自信满满地说。

我也不闲着，到处翻翻看看。

这过程可真是又紧张又刺激！最后还是我幸运地先找到了礼物。

再比如说，我们要解决一个数学问题，比如找出满足某个条件的所有整数组合。

这时候，穷举法就能派上用场啦。

虽然可能会有点麻烦，要一个一个去试，但只要我们有耐心，总能找到答案。

这穷举法就像是个勤劳的小蜜蜂，虽然方法笨了点，但一直不停地努力，总会有收获的。

你们想想，如果没有穷举法，好多问题我们还真不好解决呢！它虽然不是最聪明的办法，但在很多时候，却是最实在、最可靠的。

所以呀，同学们，穷举法虽然看起来简单粗暴，但在计算机的世界里，可是有着它独特的用处呢！总之，穷举法就是这样一种虽然有点费力，但有时候却能帮我们解决大问题的算法！你们觉得有趣吗？。

求最小值的方法一、穷举法。

穷举法是最直观、最简单的一种方法，它通过遍历所有可能的取值来找到最小值。

在一些情况下，穷举法是非常有效的，尤其是当问题规模较小、搜索空间较小的时候。

但是，穷举法的时间复杂度通常较高，当问题规模较大时，它的效率会变得很低。

二、贪心算法。

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望最终能够达到全局最优的算法。

在某些问题中，贪心算法可以很快地找到最小值，但是在一些情况下，贪心算法得到的结果并不一定是最优的。

三、动态规划。

动态规划是一种将原问题分解为若干个子问题，通过求解子问题的最优解来求得原问题的最优解的方法。

动态规划通常适用于具有重叠子问题和最优子结构性质的问题。

通过存储子问题的解，动态规划可以避免重复计算，从而提高求解效率。

四、二分法。

二分法是一种非常高效的求最小值的方法，它通常适用于在有序数组中查找特定元素的问题。

通过比较中间元素和目标值的大小关系，二分法可以将搜索空间缩小一半，从而快速地找到最小值。

二分法的时间复杂度为O(logn)，因此在大规模问题中具有较高的效率。

五、数学优化方法。

在一些数学问题中，我们可以通过对函数进行求导，找到函数的极值点来求得最小值。

数学优化方法通常需要一定的数学知识和技巧，但是它可以提供精确的最小值结果。

总结。

在实际问题中，我们可以根据具体情况选择合适的方法来求最小值。

穷举法适用于规模较小的问题；贪心算法适用于一些特定的问题；动态规划适用于具有重叠子问题和最优子结构性质的问题；二分法适用于有序数组中的查找问题；数学优化方法适用于一些数学问题。

希望本文介绍的方法能够帮助读者更好地理解和应用求最小值的方法。

注意：切勿先计算 xn 及 n!，然后计算 它们的商。因为它们均可能是非常大的 数，尤其是整数n!可能溢出；再做除法， 又可能出现更大的误差。
14
符号变量的设计与应用
例1-3 编程实现输入一个整数，判断
其是否能被 3, 5或7整除，并输出以下
信息之一
1.能同时被3, 5, 7整除。
2.能被两个数（要指出哪两个数）整除。
6
程序编译、连接生成可执行文件 可执行文件的运行结果
7
练习
题目描述：假设a、b、c均为整数，且满足a，b， c 大于1，并且小于等于100，找出所有符合条件： “a的平方 + b的平方 = c的平方”的整数组。 输出描述：按a从小到大的顺序输出所有满足条件 的整数组（若a相同，则按b从小到大的顺序输出）， 每行一组，每一组数据的输出样式为：3*3 + 4*4 = 5*5 注意：
方法2：将计算与输出相分离
先完成所有的判断然后输出，使计算与输出两 个环节相分离
设计一个标志量与整数n对应，记录n被3, 5, 7整除的
情况。我们约定标志量的
二进制最低位：1表示n能被3整除，0表示n不能被3整除
二进制第2位：1表示n能被5整除，0表示n不能被5整除 二进制第3位：1表示n能被7整除，0表示n不能被7整除
19
int main() { int n; while(1) { cout << ”\n请输入一个整数（负数退出）: ”; cin >> n;
if(n<0) break; show_result(n);
} return 0;
}
20
逻辑判断类题型解法
例1-4 夏日炎炎，空调机走俏。5家空调机厂的产 品在一次质量评比活动中分获前5名。评前大家就 已知道E厂的肯定不是第2名和第3名，B厂不是第2 名就是第3名。 A厂的代表猜：E厂的产品稳获第1名。 B厂的代表猜：我厂可能获得第2名。 C厂的代表猜：A厂的质量最差。 D厂的代表猜：C厂的产品不是最好的。 E厂的代表猜：D厂会获得第1名。 评比结果公布后发现，只有获得第1名和第2名的两 个厂的代表猜对了。请编程给出A，B，C，D，E 各是多少名？

鸡兔同笼问题的算法分析与优化研究引言：鸡兔同笼问题是数学中的经典问题之一，首次出现在中国古代数学著作《孙子算经》中。

该问题提供了一个有趣的应用场景，即在给定鸡兔的总数量以及它们的总腿数的条件下，求解鸡和兔的数量。

本文将对该问题的求解方法进行算法分析与优化研究，旨在提高解决该问题的效率。

问题描述：已知鸡和兔的总数量为n，它们的总腿数为m，请计算鸡和兔的数量。

算法一：穷举法最直观的解法是穷举法，即遍历所有可能的鸡和兔的数量组合，从中筛选满足条件的解。

具体步骤如下：1. 初始化鸡和兔的数量均为0。

2. 循环遍历所有可能的鸡和兔的数量组合，直到满足鸡和兔的总数量为n，且总腿数等于m为止。

3. 通过判断鸡和兔的数量是否满足给定的条件来筛选解，记录满足条件的解。

4. 返回记录的满足条件的解。

该方法的时间复杂度为O(n^2)，因为需要两层循环遍历所有可能的鸡和兔的数量组合。

在n较大时，该方法效率较低。

算法二：数学解法实际上，鸡兔同笼问题有一个简单的数学解法。

我们可以用以下公式得到鸡和兔的数量：鸡的数量 = (2n - m) / 2兔的数量 = (m - n) / 2该方法的时间复杂度为O(1)，由于只需进行简单的数学运算，因此在解决该问题时效率较高。

算法三：二分查找对于一个给定的鸡的数量x，可以通过二分查找的方式来确定相应的兔的数量。

具体步骤如下：1. 初始化鸡和兔的数量的取值范围为[0, n]。

2. 在取值范围内，取一个中间值mid，并计算对应的鸡和兔的数量。

3. 如果鸡和兔的总腿数等于m，则找到了一个解，返回结果。

4. 如果鸡和兔的总腿数小于m，说明鸡的数量太小，将鸡的数量的取值范围调整为[mid+1, n]，再次进行二分查找。

5. 如果鸡和兔的总腿数大于m，说明鸡的数量太大，将鸡的数量的取值范围调整为[0, mid-1]，再次进行二分查找。

6. 重复步骤2至5，直到找到满足条件的解或无解。

该方法的时间复杂度为O(logn)，通过二分查找的方式来缩小鸡和兔的数量的取值范围，从而快速找到解。