包含标签 算法 的文章

等物体填充问题

那天在群里,rich大牛提了一个问题,一个直径为10cm的球内最多能够填充直径为1cm的球多少个. 之前看到过一个类似的简单说明,就像是在一个盒子里装乒乓球,如果装满了,想继续装,如何办?经验告诉我们,摇一摇盒子。。这个问题看上去简单,其实是个NP难问题…于是,查找了一些资料,比较有意思,分享一下。  首先是stetson大学efriedma教授的网页,收集了各类填充(英文是packing)问题的图示,欢迎移步:packing center ,不过这里面恰好没有球体填充(SpherePacking)的问题,然后继续查找,进入了一个可以演示球体填充问题的页面:sphere packing demo 感谢网站作者Hugo Pfoertner,这里作者解出了1-72个球的问题,但是,作者说对于n>10的情况无法证明最优化.不过这个页面的演示太帅了,推荐看看。  可以鼠标拖动旋转3D视角。 然后在数学世界看到了一球体填充问题的证明结果,见:SpherePacking,当然,下面一大堆引用我都没看..看文章里的意思是说这个填充问题填充率已经被证明最大是77.9%,但是这个上限可能还能提高,因为貌似根据这个情况,rich大牛提出的这个问题应该数量在779左右..  ……

阅读全文

阿里巴巴5月5日综合算法题详解

之前参加了阿里的笔试和电面,让后天那个敏感的日子去参加现场面,就去看了一下那天笔试的最后一道综合题,看着网上清一色最后一道题不知道从哪转的答案,不忍直视,一看代码就是错的,最直接的就是求中位数连奇偶性都不判断,直接处以2..这,另外当在无法整除的情况下,数据结果错误。  这道题的大意是:有一个淘宝商户,在某城市有n个仓库,每个仓库的储货量不同,现在要通过货物运输,将每次仓库的储货量变成一致的,n个仓库之间的运输线路围城一个圈,即1->2->3->4->…->n->1->…,货物只能通过连接的仓库运输,设计最小的运送成本(运货量*路程)达到淘宝商户的要求,并写出代码。 解题思路: 假设n个仓库的初始储货量分别为warehouse[1],warehouse[2],…,warehouse[n] 计算平均储货量 就算出来了最终的结果中,每个仓库应该有的存量 首先,从仓库1向仓库n运送k; 然后,从1到n-1,依次向下运送某一特定值,使得每一个仓库的余量都为average,剩下的问题就是求总代价的最小值了。 设第0步从1仓库向n仓库(注意因为是圆圈,所以路径长度是1)运出k存量,k可以为负,如果为负数,意味着从n向1运输|k|存量,然后从循环,从(1到n-1),从i仓库向i+1仓库运输,运输的量需要保证i仓库在运输完毕后等于average 第0步(从仓库1向仓库n运送k):花费代价为 |k|, 第1步(确保仓库1的余量为average):需要花费代价为 也就是从1向2伙从2向1运输 3. 第2步(确保仓库2的余量为average):代价为 … n-1.第n-1步:代价为 此时,仓库n剩下的货物量: 刚好也满足,其实这里不用推导,因为平均值是算好的,所以最胡一定是刚好完成的。 总的代价为: 不妨令sum[i] = warehouse[1]+warehouse[2]+…+warehouse[i]-i*average 则,总代价可表示为:|k|+|sum[1]-k|+|sum[2]-k|+…+|sum[n-1]-k| 这个式子可以看成在水平数轴上寻找一个点k,使得点k到点0,sum[1],sum[2],sum[3],…,sum[n-1]的距离之和最小,显然k应该取这n个数的中位数。至此问题解决。 给出详细注释代码:  思路借鉴了:http://hi.baidu.com/hujunjiehit/item/54204f01931ee6c49157184c 错误之处欢迎留言指出..……

阅读全文

邻接表实现无向图(C++)

很早以前写的代码了,贴出来做个备份吧。用向量来存储一条邻接链表,存储可连通值。实现了判断是否连通,添加边,添加顶点的功能。 UnDirectGraph.h UnDirectGraph.cpp 代码还算清晰,就不解释了,有问题留言反馈。谢谢。……

阅读全文

求整数1-N范围和为N的所有组合

看到的一道题,给出答案 问题:找出整数1~N范围和为N的所有集合,集合里的数不允许重复。 解答:递归吧 代码如下: 要是允许重复,也简单,将递归中的这句话改为: 同理,还可以解决类似给定一个数组,让求和为N的元素组合,只需要现将元素排个序,然后思路相同。  ……

阅读全文

倒水问题求解(C++)

明天要去参加微软面试,不求顺利,但求体验。 这个题目答题的意思是: 给你一个容量为A升的桶和一个容量为B升的桶,水不限使用,要求精确得到Q升水.请说明步骤 当数字比较小的时候,我们可以通过大脑穷举来得到结果,但这里有两个问题,当数字很大的时候怎么解?题目给定的数据是否有解? 首先判断是否有解? 题目可以理解为,x为用A的次数,y为用B的次数,Q为目标值 Q = A * x + B * y Q =目标值. Q必须是 Gcd(A,B)(也就是A,B的最大公约数)的倍数,否则无解,如果 Gcd(A,B) == 1, 任何Q都是可解的 最简单的方法就是把A的水不断的向B中倒(B向A中倒也行),知道得到最终结果,如果桶满了,就清空该桶.举个例子 A = 3, B = 4 并且 Q = 2 重复得从 A->B A B 0 0 4 0 1 3 1 0 0 1 4 1 2 3 <-A桶中得到2了 试试从 B->A A B 0 0 0 3 3 0 3 3 4 2 <- B中也得到了2 但是注意,从 B->A 比从 A->B快哦 然后我贴出代码 运行结果如下: 关于如何求最少的步数来求解这个问题,希望有朋友能够留言指教。……

阅读全文

模板优先级队列及堆排序(C++实现)

模板优先级队列,数组实现,再熟悉一下常用算法,同时简单的堆排序应用 写了一个是队列自增长,另一个为了演示我还添加了一个叫做FillPq的方法,这个方法可以使用一个数组直接填充到优先级队列里,此时,优先级队列并不优先,然后进行下滤调整,之后建堆完成,输出即可 然后是堆排序  ……

阅读全文

模板栈以及中缀表达式求值(C++实现)

栈直接用链表实现,这个比较简单,不多说,不过C++写程序,IDE的错误检测不是很给力。 至于给定一个中缀表达式,如何不转换成后缀表达式,直接求值,方法就是使用两个栈,一个操作符栈,一个操作数栈,然后从左到右扫描表达式,我这里中缀表达式计算实现的很简单,不完整,大家可以扩展。栈的实现是我想写的,思路如下: 1.如何是操作数,压入操作数栈 2.如果是操作符,压入操作符栈 3.如果是左括号,直接忽略 4.如果是有括号,弹出操作符栈栈顶元素,然后弹出操作数栈两个元素,进行操作以后结果压入操作数栈  看个图就好了  最后给出栈顶实现代码 然后是main函数代码 另外,今天是博客建站一周年.加油!……

阅读全文

[藏]关于B树的一篇文章

很多人对B树的理解有很多错误,我看的最多的就是有人混淆二叉树(Binary Tree)和B树(B-Tree),二叉树是不用简称,也就是BT的,而特殊一点的二叉搜索树才会用BST(Binary Search Tree),至于B-树和B树,这两个其实一样的,英文都是(B-Tree),注意看中间的-号,这个是国内翻译的问题.所以大家不要被误导. Rudolf Bayer 和 Ed McCreight 于1972年,在Boeing Research Labs 工作时发明了B 树,但是他们没有解释B 代表什么意义(如果有的话).Douglas Comer 解释说: 两位作者从来都没解释过B树的原始意义。我个人觉得很有可能是他的名字,程序员对其作品的一种情结吧. 这篇文章来自国外,是某大学的CS课程在线的,由于有时候无法访问,我直接提供PDF版,对其构造过程非常清晰.非常非常好的B树教程,图示很多,就不翻译了,强烈推荐阅读!  下载:B树讲解  ……

阅读全文