| 最短加法链算法 |
| |
| 引用本文： | 王晓东. 最短加法链算法[J]. 小型微型计算机系统, 2001, 22(10): 1250-1253 |
| |
| 作者姓名： | 王晓东 |
| |
| 作者单位： | 福州大学计算机科学与技术系 |
| |
| 基金项目： | 福建省科学技术厅项目(2000Z148),国家973项目(G1998030600T)资?种 |
| |
| 摘 要： | 本文讨论了关于正整数n的最短加法链总理问题。利用已取得的关于正整数n的最短加法链长度1(n）的上、下界的理论成果，构造了在回溯法中状态空间树进行剪枝的精细的剪枝丞数，从而设计出产生任意正整数n的最短加法链的高效算法。
|
| 关 键 词： | 最短加法链 状态空间树 回溯法 剪枝技术 算法 数据结构 |
| 文章编号： | 1000-1220(2001)10-1250-04 |
AN ALGORITHM FOR GENERATING THE SHORTEST ADDITION CHAINS |
| |
| WANG Xiao dong. AN ALGORITHM FOR GENERATING THE SHORTEST ADDITION CHAINS[J]. Mini-micro Systems, 2001, 22(10): 1250-1253 |
| |
| Authors: | WANG Xiao dong |
| |
| Abstract: | 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. |
| |
| Keywords: | Shortest addition chains State space trees Backtracking algorithms Pruning techniques |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
