- 博客(30)
- 收藏
- 关注
RSS订阅原创 蓝桥杯题目 过桥问题
题目： 在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。输入：两行数据：第一行为小朋友个数n第二行有n个数，用空格隔开，分别是每个小朋友过桥的时间。...
2020-05-07 08:36:12
989
1
原创 蓝桥杯题目《39级阶梯》
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!站在台阶前，他突然又想着一个问题：如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？这个问题的突破口就是找到是怎么产生的这个结果，什么结果？就是这个最后一步是右脚是怎么产生的，经由这样的产生我们可以通过动...
2020-05-07 08:31:33
921
原创 游戏与AI基础算法——寻踪觅迹：A*算法
人工智能是近几年的热门专业，国家也在大力发展人工智能这方面的人才游戏领域从18年再次达到一个高度，有许许多多的独立游戏开发人励志做游戏，做好游戏人工智能与游戏领域结合可以说是未来的主潮流。今天要介绍的A星算法是在这两个领域都可以说是很有用的算法。A星算法是导航寻路系统中的一个算法，在2D游戏涉及很多。比如说：自动寻路、怪物追踪你等。在人工智能寻路中也起了不少作用。本篇介绍曼哈顿距离、A...
2020-05-07 08:26:01
752
原创 五大算法的总结及浅谈对算法的感受
这一篇是算法的总结，但不是说算法就学会了。就没有问题了。毕竟算法设计与分析一直是当今研究的问题。学了算法更应该在以后编程去运用，去做更好的优化最后，算法真的很有用！本篇是对我们前面介绍的分治法、动态规划算法、贪心算法、回溯法、分支限界法的总结，以及我的一些在学完算法的想法。1、分治算法的总结分治算法的适用条件：1.该问题的规模缩小到一定的程度就可以容易地解决;2.该问题可以分解为若...
2020-04-29 22:22:35
864
原创 探讨与研究——动态规划算法、回溯法、分支限界法解0-1背包问题
一个人终归是要成长的，是要不断历练的，没有人可以安安稳稳一辈子。就算是最有地位最有钱的人也要不断追求、不断历练、不断提升自己。人的学问少时在不断学习，青年时期不断实践。随着时间推移，到了老年终有所成，就是人口中的前辈、艺术家等等。这也是社会的普遍定律。还是一样，年少时学问再高，也高不过你年老时的学问。不断历练，才能百炼成钢；必要的弯路绕也绕不过去，正视自我，正视现实，不断历练。必要的路该走就得...
2020-04-29 22:20:06
1857
原创 回溯法与分支限界法的总结
本篇是对回溯法与分支限界法的总结回溯法与分支限界法总结1、适用于解决组合搜索问题及优化问题2、求解条件：满足多米诺性质3、回溯法的解空间应至少包含问题的一个最优解，通常将解空间组织成树或图的形式，从树根到叶子结点的任意一条路径可表示解空间中的一个解4、回溯法一般是采用三种树结构：n叉树、子集树、排列树n叉树n个结点分出了n个叉产生了n个子节点的一棵树。那么探寻时，是从某一结点开始逐步...
2020-04-29 22:16:24
7060
1
原创 依靠队列搜索——分支限界法及其应用：最大团问题、货郎问题
人生是需要做好规划的，就算是混这人生也要混出个名堂出来。全国有大部分人知道考研，但是考出来干什么，走什么的路是真的没有想法。计算机行业涉及到许许多多的领域，所以，大学期间要学计算机专业，一定要做好规划，想做什么才能去学什么。囫囵吞枣只会让你啥也没有学到，说明白点就只是让你明白个大概，而不能明白所以然。所以要定好方向，，将来想干什么，然后在这条路上学懂专业，这样到了社会，才能给你这一席之地。...
2020-04-29 22:12:07
7522
1
原创 剪枝操作——回溯法的限界思想及其应用：圆排列问题
我相信人都有自尊，而尊重别人的自尊是一种及其高尚的精神。社会中有很多想不到的惨绝人寰的事情，有时候发生到了自己身上、有时候发生在自己最亲密的人身上、有时候发生在自己周围人的身上等。这些无不露出一些类似于心理变态vs心灵脆弱。“不尊重别人”在社会中出现了太多太多了。习以为常的人笑而不谈；不习以为常的人又觉得太恐怖了。把人当“玩物”，就是一种典型的不尊重别人的例子。在这个浮夸、嘈杂的社会中如何去...
2020-04-28 14:47:12
1680
原创 回溯法的一个应用：最优装载问题
上一篇我们介绍了回溯法。了解了回溯法的空间状态是树形结构。本篇介绍一个回溯法的一个应用：最优装载问题。最优装载问题我们在贪心法中介绍过最优装载问题，本篇是说它的加强版本。由于是加强版本，自然问题也变了，比原先的最优装载问题复杂了一些。原先问题是1艘轮船。而加强版的是2艘轮船什么是加强版的最优装载问题有n个集装箱，需要装上两艘载重为c1和c2的轮船。wi为第i个集装箱的重量，且w1+w2+…...
2020-04-28 14:38:45
4254
4
原创 带预判的穷举法——回溯法及其应用：n皇后问题
回溯法也是算法中比较重要的，是一种试探法，和蛮力法差不多。回溯法与蛮力法的区别就是，回溯法有预判功能，一旦前方经过计算不满足约束条件或者前方不可能再具有最优解，则回头从另一方向进行搜索。回溯法一般的解空间是用一棵树表示的。我们再上一篇稍稍提到了回溯法的这个词汇，本篇来介绍回溯法的概念。回溯法和蛮力法（穷举法）是差不多的算法。回溯法也是一个一个试探，然后找到一个最优解的算法。但是它们的最大...
2020-04-27 10:11:15
1537
原创 一个看似简单实则很难的算法——字符串匹配问题：KMP算法
人的影响力是很大的，人产生的导向型也是很强的。当我们有想法想拥有什么、想改变什么的时候。有可能一个人的舆论可能会把你导向另一边当我们有心事的时候，可能有人把你导向好的一面；也有可能抓住你的心理，把你导向阴暗面。讲道理，人心理是复杂度。所以不存在一种极端的评价去评论啥，更要考虑的是折中观念说实话，还是让自己内心保持镇静，不被别人带跑。这才是一个看似不错的理性人。本篇我想介绍一个有意思的算...
2020-04-27 10:04:54
1252
1
原创 贪心算法与数据结构结合4——最优前缀码及哈夫曼算法
我曾经和不少做独立游戏的人交流过。讲实话18年是国产游戏的兴盛期，这就激励了一大批想做游戏的人，和一大批独立游戏开发者的人开始不惜金钱、时间等代价开发游戏。当然他们也做出了很大的成功。这一行大部分都是数媒专业，或者不断自学研究出来的东西。现在的国家形式，当游戏开发人，做独立游戏真的是一种莫大的勇气。游戏人去做游戏，为游戏产业做贡献。不单单是为了自己，还是为了国家，就是想拿出来一款可以称得上、...
2020-04-27 09:21:49
3067
2
原创 贪心算法与数据结构结合3——最小生成树问题：Kruskal算法
本篇介绍解决最小生成树问题的另一个贪心算法：Kruskal算法Kruskal算法什么是Kruskal算法输入：图G=(V,E,W)输出：G的最小生成树T1、按照长度从小到大排序2、以此考察当前最短边e，如果e与T的边不构成回路，则把e加入树T，否则跳过e，直到选择了n-1条边为止下面我们看个例子：还是以上一篇那个实例进行说明首先对边进行从小到大排序，然后考虑当前最短边。从图中看...
2020-04-23 08:21:29
517
原创 贪心算法与数据结构结合2——最小生成树问题：Prim算法
我曾经听说过很多人的梦想，但由于时间的消磨。这些梦想也就慢慢消退了；我也听说过很多人侃侃而谈，最后却只是谈了谈而已。人基本都是这样的，肯定都有梦想，但就是碍于时间和精力以及周遭变化原因未能继续追寻，继续前进了。所以，如果你还想奋斗，还想追寻那种美好的憧憬。请一定要坚持下去，不要放弃！本篇是贪心算法与数据结构结合的第二篇，本篇主要介绍最小生成树问题和以及解最小生成树问题的贪心算法——Pri...
2020-04-23 08:15:23
693
原创 贪心算法与数据结构结合1——单源最短路径问题：Dijkstra算法
万众一心，共同抗击灾难。这是我们国家自古以来的美德国家遭受重大灾情，每个中国人都是有义务去解决这样的重大问题。国家紧紧和老百姓拴在一起，凝聚着中国魂，中国力量，中国精神！数据结构中的有一个图论问题——单源最短路径问题，而解决这一问题的算法是Dijkstra算法。而本篇主要介绍单源最短路径问题和Dijkstra算法1、单源最短路径问题什么是单源最短路径问题给定带权有向网络G=(V,E,...
2020-04-22 08:30:08
783
原创 贪心算法下的两大经典问题：最优装载问题、最小延迟调度问题
上一篇主要介绍了贪心算法的内容和活动选择问题。本篇主要介绍最优装载问题和最小延迟调度问题1、最优装载问题什么是最优装载问题类似于0-1背包问题那样，有n个集装箱1,2,…,n装上轮船，集装箱i的质量wi，轮船装载重量限制为C，无体积限制。问如何装使得上船的集装箱最多？这个和前面介绍的完全背包和0-1背包问题差不多一样。然而那些问题是有重量和价值的。这个最优装载问题是只关乎于重量对价值没有要...
2020-04-22 08:24:06
6257
原创 一个凭借直觉的算法——贪心算法及其应用：活动选择问题
贪心法是比较实用的算法，因为它是由局部考虑从而达到整个最优。贪心策略就是人在面对一个问题时候的一种直观想法的策略，不断地利用这个策略可以让我们得到想要的结果当然，贪心策略并不一定是正确的，也并不一定适用于整体。贪心法是优先考虑的算法，因为算法考虑起来简单；而且代码的复杂性不这么高；时间和空间复杂性能够达到最优。所以在某些算法问题中，贪心法是一个先考虑的算法。本篇主要介绍什么是贪心法，贪心...
2020-04-21 08:24:53
1421
原创 一个特别有意思的算法——多边形游戏
世界上有许许多多的不可能,但是即使再不可能。合全人类的力量还能做不成吗地球本身就是一个大的自然圈。而这些用具、房屋、衣物不都是人类一点点装饰起来的我认为从无到有是最困难的事情。然而文明、科技、器械等一代代创建和传承。所以我们面对困难不要轻言放弃，哪怕用自己的想法证明这是一件我做不到、就是一件困难的事情，也要按照这个想法做一遍。本篇介绍一个多边形游戏算法，它也是一个动态规划的经典算法。1...
2020-04-21 08:21:02
2543
1
原创 一个动态规划算法的应用——图像压缩
青少年总是会有许许多多的梦想，我们也永远是在实现梦想的道路上去勇敢奋斗。当然，我们也有遇到过打击或者说是不在意你这么梦想的人或事情。为什么？因为他们认为你想的这个东西基于你目前状况根本没法实现，而且他们认为你也不能会实现。因为我都实现不了，你怎么会实现。但是，我想说梦想是你一个人，也有可能是你这一个圈子或者一个团队的。关别人什么事。所以想清楚怎么实现才是要做的事情，如果陷入怀疑之中，那永远也做...
2020-04-20 10:00:59
2434
原创 动态规划算法下的序列问题：最长公共子序列问题和最大子段和问题
本篇主要介绍最长公共子序列问题和最大子段和问题1、最长公共子序列问题什么是最长公共子序列给定一个序列X=<x1,x2,x3,x4…,xm>，另一个序列Z=<z1,z2,z3,z4…,zk>，若存在一个严格递增的X的下标序列<i1,i2,i3,…,ik>对所有的1,2,3,…,k，都满足x(ik)=zk，则称Z是X的子序列比如说：比如Z=<B,C,D...
2020-04-20 09:54:11
2052
原创 动态规划算法下的两个经典问题：投资问题和完全背包问题
中国蓬勃发展，国家日益昌盛。我们无不惊叹于变化之快。纵观五千年，又怎么想到现在的科技、饮食、房屋、衣裳发生了翻天覆地的变化。千秋万代，并未虚掷。我们是新青年，国家的指挥棒交到了我们这一代。我们应该主动承担国家力量，民族力量。将祖国继续发扬光大。千载之后又会是一个不同的景色。愿人族星火相传，奋飞不辍！上一篇我们介绍了动态规划算法，我们直到动态规划是将原问题划分成有依赖关系的子问题，最后通过追...
2020-04-20 09:40:08
4850
原创 以空间换时间——动态规划算法及其应用：矩阵链相乘
动态规划算法是5大算法基础中最重要的一个，它专门用来解决平面世界下的应用，即会多次使用二维数组。当然动态规划算法是空间换时间的算法，也就是说：我们可以利用空间资源来使某算法问题的时间复杂度降到最低。当然算法题中，动态规划也是占了一大部分说到以空间换时间，上一篇中的锦标赛算法就是一个以空间换时间的算法。锦标赛算法创建了一个2倍的原始数组的临时数组，是用来保存原始数组中的数，和相互比较的结果；...
2020-04-16 08:28:49
2427
2
原创 一个特别有意思的算法——锦标赛算法
我们应该多去研究我们学的专业，并在前辈所总结的知识道理上挖掘出更深的知识。超越前辈是一种社会主潮流。如果我们这一代比起前辈没有进步，那社会怎么发展。本篇介绍一个特别有趣的算法——锦标赛算法，运用锦标赛算法可以更好的去找最大和第二大的数。1、蛮力法找最大和第二大我们在上一篇已经知道找最大和最小的算法，用蛮力法找最大和最小的T(n)是2n-3。同样的，用蛮力法找最大和第二大也是T(n)=2n...
2020-04-16 08:16:21
9658
5
原创 分治算法的简单应用——选最大和最小
分治法在实际应用中是很常用的，分治算法一般会有两种情况：第一种情况就是将值返回回来使用；第二种就是重点在过程，出口仅仅可能就是一个return;本篇是介绍一个分治算法的简单应用：选最大和最小1、选最大算法这个算法，也是在接触编程语言的时候敲过的最多的算法。选最大算法就是循环遍历一遍数组，然后将数组中的值和max进行比较。最后输出max，即是原问题的解。具体代码分析就不再详细介绍了。...
2020-04-15 10:25:19
2456
原创 Graham扫描法解凸包问题
本篇是继续上篇的凸包问题的解法——将采用Graham扫描法来解凸包问题我们再上一篇说到用分治法去解决凸包问题的最坏时间复杂度是O(n^2)。那么利用Graham扫描法解决凸包问题可以降到O(nlogn)的量Graham扫描法我们可以采用一个贪心法的策略来解凸包问题什么是贪心算法我们区别于动态规划算法的那种从整体考虑部分，加以选择，而是从某种意义或者一些普遍真理的一种量度去达到局部的最优...
2020-04-15 10:22:38
432
原创 平面下的分治算法（平面点对问题和凸包问题）及其分治算法的改进（下）
如果说吃一个包子不饱，两个包子不饱，到第五个才能饱。这是量变引起的质变。如果说一个原始文明到一个古代文明再到一个近代文明到现代再到未来。这就是文明的传承。这两个都是前面的铺垫给了现在的辉煌文明从来都没有灭亡。我们看不到不代表不存在，不仅存在还有可能是我们今朝的缩影。我们不是替换了它，而是一步步传承下去，想了好的方向发展。我们祖宗一辈辈的摸索到了现在中国乃至世界的辉煌。星火相传，奋飞不辍！这...
2020-04-14 09:04:23
1757
1
原创 矩阵（斐波那契数列和Strassen矩阵）下的分治算法及其分治算法的改进（上）
我昨天在想，应试教育真的会把知识学死吗。我认为这只是一个借口，教育本来就不是活的，如果我们不主动去思考，去应用。而只是一味的为了考试而去学习，当然会把知识学的没有用处。所以说不是应试教育把知识学死了，而是你把知识学死了。《增广贤文》里面有一句老话是：师傅领进门，修行在个人。前辈将知识传给我们，我们是要在其上进行再提炼，发展到我们的当代生活中。所以才有我们现在的美好生活。文化这个东西是不断再传承的...
2020-04-14 08:48:59
1195
原创 分治算法的解和幂乘算法及其优化以及汉诺塔算法的介绍
分治算法就是分成若干个和原问题一样性质的子问题，然后逐步递归这些子问题，直到遇到规模很小的子问题，求出子问题的解，归结成原问题的解的算法就是分治算法分治算法为递归问题，可以用来解决快排、二分归并、斐波那契数列、锦标赛问题、凸包问题等 递归方程主要分为两类：（1）（2）f(n)=af(n/b)+d(n) &nbs...
2020-04-13 10:49:45
2535
原创 分而治之——分治算法下快排和二分归并排序
算法一直是程序员必备的东西，了解算法在将来会对你求职和编程有很大帮助。当然算法很难，它综合了数学、数据结构等一些知识。尤其是算法设计，为了设计出更有效，更节约时间的算法，必定要做大量演算。算法很难，所以面试会通过算法来刷人（无论你是研究生面试，还是工作面试） 算法为什么这么重要，因为算法是程序的灵魂，是编程的工具。这么说吧，你在玩游戏的时候，你希望你的打斗场...
2020-04-13 10:23:24
1010
原创 几个简单排序算法的总结
大学里面的接触的排序的理论大部分不是冒泡就是选择，实际上啊，排序算法有很多，然而接触的冒泡和选择是简单的，但不是最简单的，也不是运行效率最高的。排序算法网上说的有9种。这篇我们只介绍冒泡排序，选择排序，插入排序这些最基本的排序。还是一样的，学习排序算法得从最简单最基础的学习。1.冒泡排序什么是冒泡排序？我们通过遍历数组，将相邻的元素拿来比较，然后根据升序或者降序的原则彼此进行交换。最后将...
2020-04-13 09:54:18
241
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人