杭州交通信息网科研单位工作总结:画图问题
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/29 23:22:12
任意给出一个图形,如何判断最少要多少笔画出来?
很多关于数学趣味的书上都有.
我这里介绍一种我自己推出来的算法.(和我自己那本书里的不一样,如有雷同 纯属巧合)
公式:n=P(1)*L(1)+P(2)*L(2)+...+P(n)*L(n)-C+1
其中括弧里的是下标.
解释一下.(有很多是自己发明的名词)
P是同级结点的总数.
L是该类结点的级数.
C是图形中环的个数.
举个例子:"田"字形至少要多少划呢?
步骤:
1.田"字"形有2种结点.
即一个点引出4条线的(中间)和四个点引出3条线的(上下左右).(一个点引出2条的不算结点)
2.关于结点的级数计算
一个点引出3条或4条线的是1级结点.
一个点引出5条或6条线的是2级结点.
一个点引出7条或8条线的是3级结点.
......
一个点引出n条线的
如果N为奇数则为(N+1)/2-1级
如果N为偶数则为N/2-1级
"田"字一个点引出4条线和四个点引出3条线的都是1级.
3.关于C
"田"字有四个环.(外边的大环不算,即里面没有图形的环)
4.所以N=1*4+1*1-4+1=2,"田"字最少要2笔才能画出来.
看奇数条连线的端点的个数是多少
个数/2-1就是多少笔画了(若为0个,则是1笔)