摘要
本文讨论了关于正整数 n的最短加法链问题 .利用已取得的关于正整数 n的最短加法链长度 l(n)的上、下界的理论成果 ,构造了在回溯法中对状态空间树进行剪枝的精细的剪枝函数 ,从而设计出产生任意正整数
This paper is concerned with the computational aspects of gererating the shortest addition chains for an integer n. Theoretically developed lower and upper bounds for the minimal length of the addition chains for an integer n are exploited to construct a subtle pruning function used in the backtracking algorithm. Finally an efficient algorithm for generating the shortest addition chains for an integer n is presented.
出处
《小型微型计算机系统》
CSCD
北大核心
2001年第10期1250-1253,共4页
Journal of Chinese Computer Systems
基金
福建省科学技术厅项目 (2 0 0 0 Z14 8)
国家 973项目 (G19980 3 0 60 0 T)资助
关键词
最短加法链
状态空间树
回溯法
剪枝技术
算法
数据结构
Shortest addition chains
State space trees
Backtracking algorithms
Pruning techniques