题目描述:
有一个100*1000矩形,要在这个矩形框中种树,要求每颗树之间的距离不得小于1米,问最多可以种多少树?
题目分析:
每两个树之间的距离必须大于等于1米,那么直觉上会想到等边三角形,这样就可以满足任意两个点之间的距离为1米,那么我们的想法就是用1米长的等边三角形去填充那个矩形。
我们以100为宽,1000为高,那么第一行可以种101颗,以正三角形来安放,那么第二行就是中100颗,如图所示:
1 2 3 4 。。。。
1 2 3
那么可以算出,每两行之间的 高度为 sqrt(3) / 2 = 0.866...,然后通过计算 1000 / 0.866 = 1154 ,那么一共就可以种1155行,所以最多可以种的树的数量为 101 * (1155/2+1) + 100 * 1155/2 = 116078。
算到这个地方,问题似乎解决了,但是细心一点可以发现,当你种到1155行后,一共只是用掉了 1154*0.866 = 999.39 ,还有 0.61的地方没有用,但是还种一排显然是不合格的。
可是如果我们最后几排不遵守正三角形规则的话,每行高度不是相差0.866么 ,只是差 0.134,所以一旦我们将上下高度调整为1米,那么偶数排可以多种一颗树,那么现在如果我们按三角形法则种树,种到第1151行,这时候一共占据高度1150*0.866=995.9,以下的种树我们按着排的1米宽度种一行,那么 995.9 + 1 + 1 + 1 + 1 = 999.9 ,加起来刚好也是1155行,两行偶数,两行奇数,只是偶数行比以前多了1颗树,所以一共多了两颗,所以最后的答案便是116080颗!
还有一种思路是,用半径为1的圆填充,看填不能相交的圆一共有多少个,矩形区域变成102*1002的大小,其实质也是等边三角形填充!
从这个可以看出,用等边三角形填充往往对这样的问题比较实用 ,但最后一定要想清楚,如果不是刚好够,最后处理的时候要适当的不按规则图形来填充!
发表评论
-
QQ中杂七杂八的调用点
2016-03-28 20:52 0QQ中的API调用太多了,在这里做一个记录,方便以 ... -
各类公司2014笔试题
2013-09-17 09:33 654美团: http://www.itmian4.com/f ... -
面试题汇总
2013-08-30 00:53 7391.题目:给定数组A,大小为n,数组元素为0到n-1的数字 ... -
非递归、仅用一个栈、不加标记数组实现二叉树的后序遍历算法
2013-08-18 23:55 0http://www.cnblogs.com/fin ... -
球称重问题
2013-07-28 22:47 0一般的问题是,如果明确次品球是重或轻,可以直接利用公式 ... -
随机概率相关面试题详解
2013-05-15 10:46 01. 已知有个rand7()的函数,返回1到7随机 ... -
csdn------屌丝们的欢乐算法题
2013-03-08 21:34 01. 1 2 3 ... -
贪心算法---基础篇
2012-08-26 13:20 0理论部分 贪 ... -
计算几何-----判断一个点是否在多边形内
2012-08-20 15:01 0如何判断点在多 ... -
大整数相关运算
2012-08-20 13:52 0既然这是我的暑假任务,那么不管怎样一定要按计划完成了! ... -
编程之美---寻找发帖水王(含扩展问题)
2012-08-19 10:11 0题目:Tango是微软亚洲 ... -
编程之美-----2.21只考加法的面试题
2012-08-12 19:59 0http://www.cnblogs.com/flyinghe ... -
前序+中序==>后序 && 后序+中序==>前序
2012-08-12 09:49 0一. 前序 + 中序 -> 后序 分析: ... -
DE算法学习
2012-08-07 12:38 0DE(差分演化算法) 理论: 这部分内容直接参 ... -
字符串的hash
2011-08-23 00:58 0这段时间一直学习hash,总结的片片断断,今天就比较重要的 ... -
qsort总结大全(转)
2011-08-23 00:36 0qsort()排序函数的使用qsort函数应用大全 ... -
树的同构问题
2011-08-22 14:56 0前几天看一个hash问题,结果涉及到了树的同构 ... -
树的同构
2011-08-22 10:49 0前几天看一个hash问 ... -
hash的相关应用
2011-08-19 00:45 0hash函数如果设计合理,理想情况下查询的时间花费仅仅为 ... -
排序算法--桶排序(基数排序)
2011-08-15 10:55 17401.基数排序 基数排序的思想是针对整数的每一位进行 ...
相关推荐
常见算法笔试或面试题,有些题目还挺有趣.
python算法趣味题目.doc
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个...
大二上的算法课,经典的算法.例如分治问题,归纳问题和动态规划类的问题。也有助于考试。
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个...
12个有趣的C语言面试题-
我们力求使书中给出的每一个算法都易于理解和有趣。为了在同学们遇到不熟悉或比较困难的算法时提供帮助,我们逐个步骤地描述每一个算法。此外,为了便于大家理解书中对算法的分析,对于其中所需的数学知识,我们给出...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个...
几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有排列可能性 三维图形的消隐...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个...
几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有排列可能性 三维图形的消隐...
《算法导论思考题》!呵呵,懂行的人都知道这是好东西!这本书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。
其实可以不必这么担心,因为并不是一个随便的信用卡号码都是合法的,它必须通过Luhn算法来验证通过。 该校验的过程: 1、从卡号最后一位数字开始,逆向将奇数位(1、3、5等等)相加。 2、从卡号最后一位数字开始,逆向...
全书分为2个部分共10章,内容涵盖了编程必备的基础知识(如数据结构、常用算法等),编程实例介绍,常见算法和数据结构面试题等。《妙趣横生的算法(C语言实现)》最大的特色在于实例丰富,题材新颖有趣,实用性强,...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。书中专门讨论了线性规划,介绍了动态规划的两个...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个...
该分类法站在通用问题求解策略的高度,对现有大多数算法准确分类,从而引领读者沿着一条清晰、一致、连贯的思路来探索算法设计与分析这一迷人领域。《算法设计与分析基础(第3版)》作为第3版,相对前版调整了多个章节...
对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个...