分类: 有趣的算法
发布20
有趣的算法-分治算法
什么是分治分而治之是一种很古老但很实用的策略，或者说战略，本意是将 一个较大的力量打碎分成小的力量，这样 每个小的力量都不足以对抗大的力量。在现实应用中，分而治之往往是将大片区域分成小块区域治理。战国时期，秦国破坏合纵连横即是一种分而治之的手段。我们经常听到一句话： “山高皇帝远”，意思是山高路远，皇帝管不了。实际上无论山多 高，... 阅读更多
评论: 0 分类: 有趣的算法有趣的算法-二分查找
先理解一下什么是二分（折半）算法？先来看个有趣的例子：一间很大的教室如果老师要点人数，有什么好方法吗？一个一个点，2个2个点其实这都是算法，如果这个教室有10000人，你怎么数呢，有一个很好的方法就是让所有同学都站起来，每个人代表数字1，然后两个人商量好一个人取得对方的数字相加，另外一个人就坐下去，以此类推，每一次都会有原来一半的人坐下去，这样不用几次剩下最后一个人他的数字就是总人数了。10000人理论上2的14次方就远远超过了，也就是14次就能数万了。不过这个让人实现起来比较困难，因为有的人会犯错... 阅读更多
评论: 0 分类: 有趣的算法有趣的算法-快速排序
冒泡排序可以说是我们学习的第一个真正的排序算法，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了 O(N2)。假如我们的计算机每秒钟可以运行 10 亿次，那么对 1 亿个数进行排序，冒泡排序则需要 1 千万秒，达到 115 天之久，是不是很吓人？那有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！光听这个名字是不是就觉得很高端呢？假设我们现在对“6 1 2 7 9 3 4 5 10 8”这 10... 阅读更多
评论: 0 分类: 有趣的算法有趣的算法-约瑟夫问题（队列的应用）
首先我们先来了解一种数据结构叫做队列。队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车。队列的工作原理与此相同。你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。如果你将两个元素加入队列，先加入的元素将在后加入的元素之前出队。因此，你可使用队列来表示查找名单！这样，先加入的人将先出队并先被检查。队列是一种先进先出（First In First... 阅读更多
评论: 0 分类: 有趣的算法有趣的算法-递归-分形树
点我查看Scratch实现 阅读更多
评论: 0 分类: 有趣的算法通过Scratch了解什么是递归
递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用非常简单直接的方式来解决。递归的问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。递归为我们提供了一种对复杂问题的优雅解决方案，精妙的递归算法常会出奇简单，令人赞叹。1.黄金分割在古希腊有有位叫欧多克索斯先哲，他在研究怎么把一个线段一分为二最好看，这个点究竟要分在哪才给它看上去最协调好看，他给出了个确切的答案0.618，那为什么必须是0.618呢？这其实来源于线段的自相似性。如下图... 阅读更多
评论: 0 分类: 有趣的算法有趣的算法-求最大公约数
枚举法求最大公约数枚举算法虽然比较简单，但是效率不高，下面再介绍一种求最大公约数的方法。辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。（78,14）78除以14余814除以8 余6 8除以6 余2 6除以2... 阅读更多
评论: 0 分类: 有趣的算法有趣的算法-冒泡排序
冒泡排序冒泡排序是一个简单的排序算法,它重复地遍历要排序的数列,依次比较两个元素,如果前者比后者大就进行交换操作.遍历数列的循环进行直到没有再需要交换,这数列已经排序完成.算法因为越小的元素会经过交换操作慢慢浮出到数列的顶端所以得名冒泡算法.点我看冒泡排序效果点我用Scratch实现冒泡排序Python求解def bubble_sort(arr): """冒泡排序""" # 第一层for表示循环的遍数 for i in range(len(arr) - 1):... 阅读更多
评论: 1 分类: 有趣的算法有趣的算法-鸡兔同笼-枚举法
1，枚举算法的定义：在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么该结论是可靠... 阅读更多
评论: 1 分类: 有趣的算法有趣的算法-二进制
十以外的进制无处不在特别是在时间单位的表达上尤为明显比如分秒时就是60进制，时和天之间是24进制，天和周之间是7进制，天到月是28/29/30/31进制不等，月到年是12进制，天到年是365.25进制，或者说是365/366进制，年和世纪是100进制二进制和十进制如何转换？" width="400" height="300" frameborder="0"... 阅读更多
评论: 1 分类: 有趣的算法