在键盘上输入N个整数整数N( 1 <= N <= 10 )，生成从1~N所有整数的全排列。

来源：蜘蛛抓取(WebSpider) 时间：2018-12-01 17:02 标签： 在键盘上输入N个整数

这学期好忙整个人都变懒了。coursera上的课程作业只来得及更新到github上，希望自己以后看着注释还能记得怎么做。得空把上学期的一些作业放这里。

【在键盘上输入N个整數形式】在键盘上输入N个整数整数N

【输出形式】输出有N!行，每行都是从1~N所有整数的一个全排列各整数之间以空格分隔。各行上的全排列不重复输出各行遵循“小数优先”原则, 在各全排列中，较小的数尽量靠前输出如果将每行上的输出看成一个数字，则所有输出构成升序数列具体格式见输出样例。【样例在键盘上输入N个整数1】1【样例输出1】1 【样例说明1】在键盘上输入N个整数整数N=1其全排列只有一种。【样例在键盘上输入N个整数2】3  【样例输出2】1 共有N!=6行且先输出1开头的所有排列数，再输出2开头的所有排列数最后输出3开头的所有排列數。在以1开头的所有全排列中同样遵循此原则【样例在键盘上输入N个整数3】10 【样例输出3】1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 10

【运行时限】要求每次运行时间限制在20秒之内。超出该时间则认为程序错误提示：当N增大时，运行时间将急剧增加在编程时要注意尽量优化算法，提高运行效率

}perm在递归深度大于數组长度时认为一次重新排列完成，把这个数组输出到屏幕

而如果不是则将递归深度为界，重新排列数组对于全排列而言，这意味着將递归深度上的数与每个后面的数（包括它自身）都交换一次

包括与其自身交换是一个技巧，可以直接生成与目前排序相同的排列这樣就能涵盖所有的排列。而与每个数都交换递归下去就能保证每个数在每个位置上都出现过。

例如递归深度为一，目前数列为[1,2,3,4,5]那么夲次调用会产生五个新的下一级递归，分别将第一个元素"1"与"2" "3" "4" "5"交换

由于本题要求“小数优先”原则，在把第一个元素与后面交换时有一个技巧：我们发现这个元素后面的数是已经从小到大排好序的利用这个特点

在用于交换的函数rearr中，我们可以将那个数插在我们要交换的位置上而那个数到交换位置之间的所有数向前挪一位，这样就保证了小数依旧优先

交换完成后derearr是这个过程的逆过程，把数组还原以便于其他递归调用时后面的元素不变

请编写程序输出前n个正整数嘚全排列（n<10）并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。
在键盘上输入N个整数给出正整数n（<10）
输出1到n的全排列。烸种排列占一行数字间无空格。排列的输出顺序为字典序即序列a1,a2,?,an

代码：递归法（递归调用发生在for循环内）

/* 递归函数：前继段已完成，设定arr[curPos]设定后续段 递归出口：curPos=n，当前排列完成输出 因为改变了当层递归的变量值*/

我要回帖

更多关于 在键盘上输入N个整数 的文章

 

随机推荐