算法之枚举及其优化(1) |
您所在的位置:网站首页 › 解决某问题的算法可能有多种 › 算法之枚举及其优化(1) |
目录 写在前面: 从百钱百鸡问题说起 直接枚举(暴力破解) 开始优化(缩小枚举范围) 继续优化(二重循环) 最终优化(一重循环) 总结 写在后面 写在前面:本文适合初学者学习,鉴于本人能力有限以及希望读者可以在最短的时间内获得最高的收益的原则,本人不阐述过多的专业术语以及底层知识,简明扼要,精简文字,避免文章晦涩冗长。 考虑到学习枚举的同学可能没有学过C++,本文代码完全使用C来实现。有的初学者可能是为了学习“百钱百鸡问题”而来,所以笔者不讲述时间复杂度的概念,而是以clock()函数直接显示程序计算时间,虽然略有不妥,却也能在一定程度上反映算法的优劣。(您大可不必在意这个clock函数,它只是一个显示时间的函数而已) 从百钱百鸡问题说起关于枚举,我们从一个经典的百钱百鸡问题说起: 题目:我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题,该问题叙述如下:鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一;百钱买百鸡,则翁、母、雏各几何? 翻译过来,意思是公鸡一个五块钱,母鸡一个三块钱,小鸡三个一块钱,现在要用一百块钱买一百只鸡,问公鸡、母鸡、小鸡各多少只? 直接枚举(暴力破解)对于此题,我们有一种无脑思路,就是将每一种买鸡的情况罗列出来,由计算机来检查是否符合题目的要求,我们很容易通过程序来解决这个问题,如下: # include int main() { int x,y,z;//x为公鸡,y为母鸡,z为小鸡 for(x=0;x |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |