关于结点类论文例文,与最小长度加法生成序列算法相关mem硕士论文

本文是一篇结点论文范文,关于结点类自考毕业论文开题报告,关于最小长度加法生成序列算法相关毕业论文开题报告范文。适合结点及数据结构及什么是方面的的大学硕士和本科毕业论文以及结点相关开题报告范文和职称论文写作参考文献资料下载。

【 摘 要 】 由最小长度加法生成序列定义出发,结合树型结构的特点,探索其解决方案.并用Delphi语言实现了该算法.

【 关 键 词 】 最小长度加法生成序列；树；结点

Analyzing and Discussing of the shortest Adding production Series Algorithm

Liu Na Liu Gui-ping

（Department of Science Hetao College Inner Mongolia Bayannur 015000）

【 Abstract 】 In this paper, How to returning the shortest adding production series from its creating Tree is created , and give out a Delphi source code.

【 Keywords 】 the shortest adding production series； tree； node

1.引言

什么是加法生成序列?

对于给定的正整数n,一个具有如下性质：①a0等于1；②am等于n；③a0称为一个加法生成序列.

什么是最小长度加法生成序列?

对于给定正整数n,依据加法生成序列的原则所构造的整数序列长度最短,则称之为正整数n的最小加法生成序列.假如有两个或两个以上的这样的序列,任选其一即可.例如,<1,2,3,5>和<1,2,4,5>都是n等于5的解.

2.算法初探

对于给定的n,最直观的也是最长的加法生成序列是<1,2,3,4,…,n>.这个问题解决起来是很方便的,构造一个等差数列,首项a0等于1,公差d等于1,an等于n.但此时得到的显然不是最小加法生成序列.

接下来看个特例,如果n等于2m,也容易得到最小加法生成序列,即<1,2,4,8,…,2m>.这是一个等比数列,首项a0等于1,公比q等于2,am等于n.但如果n≠2m,就很难得到这样的结论了.由以上两个例子我们可以看出,这个序列并不是个简单的等差或是等比数列.

3.树型结构求解

树型结构是一类重要的非线性数据结构,直观看来,树是以分支关系定义的层次结构.树是n（n≥0）个结点的有限集.在任意一棵非空树中（1）有且仅有一个特定的称为根的结点；（2）当n >1时,其余结点可分为m（m >0）个互不相交的有限集T1,T2,等,Tm,其中每个集合本身又是一棵树,并且称为根的子树.结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲.例如,图1结点的层次从根开始定义起,根为第一层,根的孩子为第二层.若某结点在第l层,则其子树的根就在第l+1层.

结点的祖先是从跟到该节点所经分支上的所有结点.例如,G的祖先为A、D和F.

如果将树中结点的各子树看成从左至右是有次序的（即不能互换）,则称该树为有序树,否则称为无序树.在有序树最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子.

构建最小加法生成序列树型图,如图2所示.

最小加法序列树满足如下特性.

如果对一棵最小加法序列树分层进行连续编号,约定编号从每一层最左结点起,由左至右编号,并按照其编号将结点命名.例如编号为11的结点,表示的便是第一层的从左起的第一个结点,并将其命名为结点a11；编号为43的结点,表示的是第四层从左起的第三个结点,并将其命名为结点a43.如图3所示.

性质1： 除根结点外,其余结点的取值均为其父结点与祖先结点之和.例如a43等于a31+a11.

性质2：第m层的结点数最多是（m-1）!个.

设第m-1层有k个结点,由性质1可知,每个结点的子结点个数最多为（m-1）,可以推断出第m层的结点数最多是k×（m-1）个.由于第一层为根结点,结点数为1,所以第m层的结点数最多是（m-1）!个.

性质3：在第m层上最小加法序列树穷举了该层次上所有可能得到的结果,因为列举了上一个层次产生的每一个结果与其自身以及在同一个分支上的每一个祖先之和.

由性质3可以推断出,若要求得n的最小加法序列,只需要找到生成目标数n的最小层次即可,由n这个结点向上逆推到根结点,这个逆推的过程,便是得到序列的过程.

4.算法实现

本文用Delphi语言给出算法,采用存储结构为动态数组,具体代码如下：

var N：integer；//整型变量N最小加法生成序列的目标元素

A：array of array of integer；//动态二维数组A,用于存放树的结点

B：array of integer； //一维数组B,用于存放树每一层的结点数

I,I1,I2,J,J1,J2,P ,K：integer； //循环中用到的整型变量

F：integer；//标志变量,用于判定是否找到了N

C,L：integer；//存放N第一次出现所在的位置

begin

{ TODO -oUser -cConsole Main ： Insert code here }

N：等于0；

C：等于1；

L：等于1； while （N<=0） do

begin

writeln（'请输入整型变量N：'）；

readln（N）；

end；

setlength（A,11）；//设置树的深度,为10

setlength（B,11）；

B[1]：等于1；//第一层结点数为1

for I：等于2 to 10 do

B[I]：等于B[I-1]*（I-1）；//第I层上结点的个数为（I-1）!个

F：等于0；//初值为0

I：等于1；

J：等于1；

setlength（A[I],B[I]+1）； //设置第I层结点个数

A[I,J]：等于1；

I：等于2；

setlength（A[I],B[I]+1）；

A[I,J]：等于2；

while （I<=10） and （F=0）do //循环控制,不超过10行,F<>0

begin

I：等于I+1；

setlength（A[I],B[I&#