发新话题
打印【有0个人次参与评价】

[数学] 2010-8-10 初二

2010-8-10 初二

一个圆上有12个点A1,A2,A3,.....,A11,A12.以它们为顶点连三角形,使每个点恰好是一个三角形的顶点,且各个三角形的边都不相交.问共有多少种不同的连法?

.

TOP

49种不同连法

易知
3个不同点为顶点连三角形,1种连法
6个不同点为顶点连三角形,3种连法

9个不同点为顶点连三角形,
不妨首先以点A1开始连
1、A1左右的3个连续点连三角形,有3种,剩下的6个点连三角形,各3种,总计9种
2、A1左右的2个连续点,再加隔开3个点的1个点连三角形,有2种,剩下6个点被分割为2个3个点,各1种,总计2种
3、A1与隔开3个点的2个连续点连三角形,有1种,剩下6个点被分割为2个3个点,有1种,总计1种
4、综合上述,9个不同点为顶点连三角形,12种不同连法

12个不同点为顶点连三角形,
不妨首先以点A1开始连
1、A1左右的3个连续点连三角形,有3种,剩下的9个点连三角形,各12种,总计36种
2、A1左右的2个连续点,再加隔开3个点的1个点连三角形,有2种,剩下9个点被分割为1个3个点,1个6个点,各3种,总计6种
3、A1与隔开3个点的2个连续点连三角形,有2种,剩下9个点被分割为1个3个点,1个6个点,各3种,总计6种
4、A1与均隔开3个点的2个点连三角形,有1种,剩下9个点被分割为3个3个点,有1种,总计1种
5、综合上述,12个不同点为顶点连三角形,49种不同连法

数了半天,也不知道对不对?呵呵.

TOP

复杂度呈指数级增长问题的递归求解方法

该题看似简单,其实复杂度是指数级增长的。
这类问题,适合用递归方法求解。见我的另一个帖子,也是适合用递归方法求解的。http://ww123.net/baby/thread-4702329-1-1.html

结论1, 三个点,显然只有一种连法。
结论2, 六个点,只有三种连法。很意外吧,它们分别对应A1A2A3,A1A5A6,A1A2A6。(在问题变得复杂以前,这点务必理解!只要抓住A1点来看,并且三角形互不相交使得问题的复杂度大大降低。当A1所在的三角形确定,另外三点,很据结论1,只有1中连法了。 )

现在讨论九个点,开始复杂起来。以A1为观察对象,只要找出它有几种组合,这个问题就解决了。为叙述方便起见,设A1在最上方,九个点按顺时针方向排列。
余下六点在A1所在三角形一侧的,分三种情况A1A2A3,A1A8A9,A1A2A9
余下六点在A1所在三角形两侧的,分两种情况 A1A2A6,A1A5A6
在上面两个结论的基础上,上述5种情况分别对应3+3+3+1+1连法,故
结论3, 九个点有12种连法。

现在开始解题目要求的12个点的情况。
余下9个点在A1所在三角形1侧的(9+0),分三种情况A1A2A3,A1A2A12,A1A11A12
余下9个点在A1所在三角形2侧的(3+6),分六种情况A1A2A6,A1A2A9,A1A5A6,A1A8A9,A1A5A12,A1A8A12
余下9个点在A1所在三角形3侧的(3+3+3),仅A1A5A9一种情况。
于是,根据结论123, 12个点的连法有3*12+6*3*1+1*1*1*1=55种
12个点的问题,递推归结为圆上9个点,6个点,3个点的连法问题,谓之递归。
这类问题在低年级初中数学竞赛中属于偏难的问题,但如果学生能掌握“由简入难”的递归思想,则问题可迎刃而解。
猫老师仁慈,归为初二的题目,其实这种解法一旦掌握,初一的孩子解出这题也不是不可能。
比较经典的递归问题有hanoi塔问题,递归问题比较容易出现的题型有本题的圆上点连线问题,细胞(多边形)生长问题,堆积木问题,抽牌问题(即我上面提到的另一个帖子).

TOP

哦呃
俺果然数错了

更正:
12个不同点为顶点连三角形,
不妨首先以点A1开始连
1、A1左右的3个连续点连三角形,有3种,剩下的9个点连三角形,各12种,总计36种
2、A1左右的2个连续点,再加隔开3个点的1个点连三角形,有4种,剩下9个点被分割为1个3个点,1个6个点,各3种,总计12
3、A1与隔开3个点的2个连续点连三角形,有2种,剩下9个点被分割为1个3个点,1个6个点,各3种,总计6种
4、A1与均隔开3个点的2个点连三角形,有1种,剩下9个点被分割为3个3个点,有1种,总计1种
5、综合上述,12个不同点为顶点连三角形,55种不同连法.

TOP

发新话题