该题看似简单,其实复杂度是指数级增长的。
这类问题,适合用递归方法求解。见我的另一个帖子,也是适合用递归方法求解的。
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塔问题,递归问题比较容易出现的题型有本题的圆上点连线问题,细胞(多边形)生长问题,堆积木问题,抽牌问题(即我上面提到的另一个帖子).