等物体填充问题

那天在群里,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] 计算平均储货量 average = (warehouse[1]+warehouse[2]+…+warehouse[n])/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):需要花费代价为 |warehouse[1]-average-k| 也就是从1向2伙从2向1运输 第2步(确保仓库2的余量为average):代价为 |warehouse[2]+warehouse[1]-average-k-average|=|warehouse[1]+warehouse[2]-2*average-k| … n-1.第n-1步:代价为 |warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k| 此时,仓库n剩下的货物量: (warehouse[n]+k)+warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k=(warehouse[1]+warehouse[2]+…+warehouse[n])-(n-1)*average=average 刚好也满足,其实这里不用推导,因为平均值是算好的,所以最胡一定是刚好完成的。 总的代价为: |k|+|warehouse[1]-average-k|+|warehouse[1]+a[2]-2*average-k|+…+|warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k| 不妨令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个数的中位数。至此问题解决。 给出详细注释代码:   #include “stdafx.h” #include <iostream> #include <algorithm> #include<string> using namespace std; const int X = 100000; double sum[X],warehouse[X]; int n; double Abs(double x) { return max(x,-x); } int _tmain(int argc, _TCHAR* argv[]) { while(true) { double total = 0; double mid=0; cout<<“请输入仓库数目:”; cin>>n; //读入n个仓库的值,并计算总数 for(int i=1;i<=n;i++) { cout<<“请输入第”<<i<<“个仓库的存量:”; cin>>warehouse[i]; total += warehouse[i]; } //计算每个仓库应该最终存储的值 double average = total/n; //计算sum数组 for(int i=1;i<n;i++) sum[i] = warehouse[i]+sum[i-1]-average; //排序后打算去中位数 //sort采用半开半闭区间,所以排序为0~n-1 sort(sum,sum+n); //这个可以自己举个数字就知道了 if(n%2! [Read More]

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

很早以前写的代码了,贴出来做个备份吧。用向量来存储一条邻接链表,存储可连通值。实现了判断是否连通,添加边,添加顶点的功能。 UnDirectGraph.h #pragma once #include “stdafx.h” #include <vector> using namespace std; class UnDirectGraph { private: int vCount; vector<int> *adj; public: int GetVCount(); UnDirectGraph(int vCount); void AddEdge(int v,int w); vector<int> &Vadj(int v); bool IsConnected(int v,int w); }; UnDirectGraph.cpp #pragma once #include “stdafx.h” #include “UnDirectGraph.h” using namespace std; UnDirectGraph::UnDirectGraph(int _vCount) { this->vCount=_vCount; adj=new vector<int>[vCount]; for (int i=0;i&lt;vCount;i++) { adj[i].clear(); } } void UnDirectGraph::AddEdge(int v,int w) { adj[v].push_back(w); adj[w].push_back(v); } vector<int>& UnDirectGraph::Vadj(int v) { return adj[v]; } [Read More]

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

看到的一道题,给出答案 问题:找出整数1~N范围和为N的所有集合,集合里的数不允许重复。 解答:递归吧 代码如下: #include “stdafx.h” #include <iostream> using namespace std; void PrintResult(int *log,int index) { for (int i = 0; i <index; ++i) { cout<<log[i]<<” “; } cout<<endl; } void CalCombination(int* log,int startNum,int N,int &index) { if (N==0) { PrintResult(log,index); } else { for (int i = startNum; i &lt;= N; ++i) { log[index++]=i; CalCombination(log,i+1,N-i,index); } } index--; } int _tmain(int argc, _TCHAR* argv[]) { cout<<“请输入N:“; int N=20; cin>>N; int *log=new int[N]; int index=0; CalCombination(log,1,N,index); } 要是允许重复,也简单,将递归中的这句话改为: CalCombination(log,i,N-i,index); 同理,还可以解决类似给定一个数组,让求和为N的元素组合,只需要现将元素排个序,然后思路相同。 [Read More]

倒水问题求解(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快哦 [Read More]

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

模板优先级队列,数组实现,再熟悉一下常用算法,同时简单的堆排序应用 写了一个是队列自增长,另一个为了演示我还添加了一个叫做FillPq的方法,这个方法可以使用一个数组直接填充到优先级队列里,此时,优先级队列并不优先,然后进行下滤调整,之后建堆完成,输出即可 #include “stdafx.h” template< class T> class PriorityQueue { private: T *pq; int N; int capacity; public: PriorityQueue(void); ~PriorityQueue(void); void Insert(T x); T DelTop(); void Swim(int k); void Sink(int k); bool Less(int i,int j); void Swap(int i,int j); bool Resize(); void FillPq(T arr[],int size); }; template< class T> void PriorityQueue<T>::FillPq( T arr[],int size ) { N=size; capacity=2*size; for (int i=0;i<size;i++) { pq[i+1]=arr[i]; } } template< class T> PriorityQueue<T>::PriorityQueue(void) { pq=new T[10]; N=0; capacity=10; } [Read More]

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

栈直接用链表实现,这个比较简单,不多说,不过C++写程序,IDE的错误检测不是很给力。 至于给定一个中缀表达式,如何不转换成后缀表达式,直接求值,方法就是使用两个栈,一个操作符栈,一个操作数栈,然后从左到右扫描表达式,我这里中缀表达式计算实现的很简单,不完整,大家可以扩展。栈的实现是我想写的,思路如下: 1.如何是操作数,压入操作数栈 2.如果是操作符,压入操作符栈 3.如果是左括号,直接忽略 4.如果是有括号,弹出操作符栈栈顶元素,然后弹出操作数栈两个元素,进行操作以后结果压入操作数栈   看个图就好了   最后给出栈顶实现代码 #include “stdafx.h” #pragma region Node定义 template <class T> class Node { template<class T> friend class Stack; private: T m_data; Node *pNextNode; public: Node(); Node(T d); }; template <class T> Node<T>::Node() { m_data=default(T); pNextNode=NULL; } template <class T> Node<T>::Node(T d) { m_data=d; pNextNode=NULL; } #pragma endregion #pragma region Stack定义 template <class T> class Stack { private: Node<T> *m_pTopNode; int m_nNodeCount; public: Stack(); ~Stack(); bool IsEmpty(); bool Push(T e); T Pop(); int Size(); }; [Read More]

[藏]关于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树讲解