所谓夹数，可以理解成1到n各一对共2n个数字。存在一个序列，使得对于每个数字m，两个m之间存在m个数字。 比如1，2，3各两对共六个数字。存在一个序列3 1 2 1 3 2，使得对于任何数字m（1-3），两个m之间存在m各数字。 这个命题不是对每个自然数都成立。比如4存在5就不存在这样的序列。 4 1 3 1 2 4 3 2。5 1 4 1 2 3 5 2 4 3（这个序列中4之间夹了5个数字）。 写一个比较好的算法（复杂度小）判断自然数m是否为夹数。 我的思路如下： 对于2m个数字（1-m各两对）来说，数字排列格式为… m a1 … am m … （a1到am为m个任意数），即数字个数大于m+2个。 夹数满足条件2m > m + 2，即m > 2. 但这个条件不充分，仅必要。(我把这个必要条件当答案给考官，考官说出了5不满足否定我的结论）。 后来考官让我用遍历所有排列并判断m是否为夹数的方法。 复杂度为n^2,性能比较差。先记录下，未来回顾。 优化后代码使用了递归调用。第一份代码递归生成1－m两对共2m个数字的全排列，而且有很多重复元素。 第二份优化代码生成1－m共m个数字的全排列，并遍历每个元素，间隔元素值后插入相同元素。 如4,2,3,1. 第一次插入 4 2 3 1 0 4 第二次 4 2 3 1 2 4 第三次4 2 3 1 2 4 3 第四次4 2 3 1 2 1 4 3 最后检查生成序列是否满足夹数性质，显然上数列不满足夹数性质，继续下一个排列，直到所有可能排列，找到 4 1 3 1 2 4 3 2。 易算出7,4,3都是夹数，2,5,6不是。 <无> .CodeEntity .code_pieces ul.piece_anchor{width:25px;position:absolute;top:25px;left:-30px;z-index:1000;}.CodeEntity .code_pieces ul.piece_anchor li{width:25px;background: #efe;margin-bottom:2px;}.CodeEntity .code_pieces ul.piece_anchor li{border-left:3px #40AA63 solid;border-right:3px #efe solid;}.CodeEntity .code_pieces ul.piece_anchor li:hover{border-right:3px #40AA63 solid;border-left:3px #efe solid;}.CodeEntity .code_pieces ul.piece_anchor li a{color: #333;padding: 3px 10px;}.CodeEntity .code_pieces .jump_to_code{visibility:hidden;position:relative;}.CodeEntity .code_pieces .code_piece:hover .jump_to_code{visibility:visible;}.CodeEntity .code_pieces .code_piece:hover .jump_to_code a{text-decoration:none;}.CodeEntity .code_pieces h2 i{float:right;font-style:normal;font-weight:normal;}.CodeEntity .code_pieces h2 i a{font-size:9pt;background: #FFFFFF;color:#00A;padding: 2px 5px;text-decoration:none;}
微软面试题：判断10是否为夹数，并判断n是否为夹数。
