`
lcy0202
  • 浏览: 178577 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

递推求解

 
阅读更多

去参加UC的笔试出现了一道题目,没有做出来,郁闷就跟朋友聊聊,没想到最后还是跑回到算法那里去~~~+_+

问题:10个平面最多可以将空间分割几部分

 

 

解法一:递推思想
设用n个平面去切割空间的时候是f(n)块。
 首先,理解一下,当变为二维的时候,也就是一个平面被N条边最多可以分为几部分:p(n)=1/2[n*(n+1)]+1,这个比较好理解,原理:第N条边可以将p(n)中的n-1条直线相交,从而增加了n部分,于是可推到而出。
现在,当变为三维时,n-1个平面后,放上第n个平面,那么第n个平面上最多有n-1条线,这n-1条线能把第n个平面分为多少部分,那么空间就多了多少部分。
于是,可得推导式:
f(n)=f(n-1)+1/2[n*(n+1)]+1,于是可得f(n)=(n^3+5n+6)/2

 

 

 

解法二:数学方程求解
由上面所知,一个平面被N条边最多可以分为几部分:p(n)=1/2[n*(n+1)]+1,可以推测出二维的分割n的最高次幂为2,当为一维的时候,也就是点分割线的时候,n的最高次幂为1,由此可以推测,当为三维的时候,n的次幂是3;
于是可以设n个平面可以将空间分割为f(n)部分,f(n)=a*n^3+b*n^2+c*n+d,
而且知f(0)=1; f(1)=2; f(2)=4; f(3)=8代入,
可求得:f(n)=(n^3+5n+6)/2
 

 

 

分享到:
评论

相关推荐

    ACM递推求解求解算法

    【标题】:“ACM递推求解求解算法” 在计算机科学领域,特别是算法竞赛(如ACM/ICPC)中,递推求解是一种常用的技术。递推法是通过已知的简单情况来推导出复杂情况的解,通常用于解决具有明显规律性的数学问题。...

    递推求解----递推公式的伟大意义

    递推求解是一种在计算机科学和数学中广泛使用的解决问题的方法,尤其在算法设计和理论分析中扮演着重要的角色。递推公式是递推求解的核心工具,它通过定义当前值与前一个或多个值的关系来表示序列或序列的元素。递推...

    递推求解.ppt

    递推求解.ppt -武汉科技大学课件;

    (课件3)递推求解new

    递推求解是算法设计中的一种常见策略,特别是在 ACM(国际大学生程序设计竞赛)中,递推经常被用来解决复杂的问题。递推法通常适用于那些可以通过较小规模的解决方案推导出较大规模问题答案的题目。在本课件中,我们...

    递推求解 集合了递推的一些题目

    递推求解是一种在计算机科学和数学中广泛使用的解决问题的方法,尤其在算法设计和优化中。这种方法通过将复杂问题分解为更小规模的子问题来求解,通常涉及定义一个递推公式,从已知的基础情况出发逐步推导出整个序列...

    (lecture_03)递推求解090302.ppt

    【递推求解】在计算机科学,特别是ACM(国际大学生程序设计竞赛)领域,递推是一种解决问题的有效方法,尤其适用于解决与序列、序列生成和动态规划相关的问题。递推通常涉及通过已知的较小规模问题来推导较大规模...

    (HDUACM201403版_04)递推求解

    杭电ACM课件2014版之 (HDUACM201403版_04)递推求解

    HDUACM2010版03递推求解.ppt

    HDUACM2010版03递推求解.ppt

    随机结构有限元分析的递推求解方法的改进 (2010年)

    将随机结构有限元分析的递推求解方法和伽辽金投影方法相结合,提出了求解随机静力响应的改进的递推求解方法。利用随机收敛的非正交多项式展开表示由于材料、外部荷载或构件几何尺寸的随机性导致的结构随机响应。采用...

    acm课件 HDU 算法大全

    (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_7)特殊的数 (lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture...

    递推求解ACM试题和答案库.ppt

    挑战程序设计竞赛,ACM试题大全和结果,题目非常全面,欢迎大家分享。

    递推求解资源

    这是ACM中也比较重要的一个知识点,其中的资源包含文档和PPT,递推在生活中也是有许多应用,所以也是很有意义的,在现在的程序题目中,有许多这类的题目,有些简单点的做起来比较简单,但有些难一点的你真心推不出来...

    递推公式

    用于求解递推公式的matlab程序,自己编的,不错

    背包问题的递推解决

    一种贪心法解决背包问题的方式,通过递推并节点分述查找最优解

    杭州电子科技大学 acm 答案 代码

    这里我们关注的焦点是“递推求解”这一标签,它涉及到一系列利用递归或动态规划方法来解决数学问题的技术。在描述中提到了几个具体的题目,包括“不容易系列之1,2,3”,“超级楼梯”,“骨牌铺方格”,“母牛的...

    hdu acm教案2

    本教程主要围绕ACM程序设计竞赛的相关内容展开,主要讲解了递推求解的方法和实际应用。以下是对教程中涉及知识点的详细解释: 1. **递推求解**:递推是一种解决问题的方法,它通过已知较小规模问题的解来推导出较大...

    acm课件3 递归求解

    递推求解的一般步骤包括:首先确定基础情况(通常是规模较小的情况),然后假设规模较小的问题已经解决,接着分析规模扩大时的情况,并确保所有子情况都可以用已知数据来处理。在编程实现时,有时需要牺牲空间来换取...

    【老生谈算法】matlab的LMS算法.doc

    因此,LMS算法通常使用递推求解的方法,例如最陡下降法。 在matlab中实现LMS算法需要以下步骤: 1. 设计一个均衡系统,包括待均衡的信道、均衡器和判决器。 2. 定义滤波器的输入矢量、加权矢量和输出。 3. 根据...

Global site tag (gtag.js) - Google Analytics