首页 > 试题广场 >

下列代码试图打印数字1-9的全排列组合

[单选题]
下列代码试图打印数字1-9的全排列组合。
#include "stdio.h"
#define N 9
int x[N];
int count = 0;

void dump() {
  int i = 0;
  for (i = 0; i < N; i++) {
    printf("%d", x[i]);
  }
  printf("\n");
}

void swap(int a, int b) {
  int t = x[a];
  x[a] = x[b];
  x[b] = t;
}

void run(int n) {
  int i;
  if (N - 1 == n) {
    dump();
    count ++;
    return;
  }
  for (i = ___; i < N; i++) {
    swap(___, i);
    run(n + 1);
    swap(___, i);
  }
}

int main() {
  int i;
  for (i = 0; i < N; i++) {
    x[i] = i + 1;
  }
  run(0);
  printf("* Total: %d\n", count);
}
其中run函数中缺失的部分应该依次为:
  • n+1, n, n+1
  • n+1, n, n
  • n, n, n
  • n, n+1, n+1
  • n+1, n+1, n+1
  • n, n, n+1
推荐

这是一道分治算法题。这种循环套递归的题目是很难一下子理解的,因此可以把问题的规模减小。先试 3 个元素,然后我们发现,在循环里面第一句话是那当前的某个数和后面的某个数交换(包括和自己交换,也就是不交换),交换完了之后,后面那个递归就是分治了,也就是从待交换的数的下一个开始直到末尾的一段调用递归用分治搞定。分治一直调用到最后无法交换的时候,也就是末尾两个指针相遇的时候程序就输出一种排列。所以在递归退出之后,根据程序的逻辑,在当前层循环里面应该只负责当前数和后面的数的交换,而当前数不能变,所以要把现场恢复,因此还需要调用一次 swap 再交换回来就可以了。所以根据程序逻辑,应该选择 C 。自己画一个三个数的排列就可以看明白了, 9 个数太复杂,搞明白关系就可以了。

编辑于 2016-03-24 15:24:05 回复(7)
不是我吐槽,题目中的run函数只有2个空。
发表于 2016-08-08 01:56:05 回复(2)
先看代码
 for(i = ___; i < N; i++) {
    swap(___, i);
    run(n + 1);
    swap(___, i);
  }
为了防止内存溢出,我直接排除法选择了c。只是个做题技巧,程序没多看
发表于 2015-08-27 16:38:06 回复(14)
记录一下错误:
我是第一个空错了,之前没有想到自己和自己交换有什么意义,所以选了n+1
这样的话就少了不交换的那种情况
发表于 2015-08-28 09:47:35 回复(7)
voidrun(intn) {//处理[n,N-1]的元素排列
  inti;
  if(N - 1 == n) {
    打印结果;
    return;
  }
  for(i = n; i < N; i++) {
    swap(n, i);// 从第n个元素依次和后面的元素进行交换.,i=n,表示不交换,原序打印
    run(n + 1);//处理[n+1,N-1]的元素排列
    swap(n, i);//交换回原样,以便再递归处理后面的元素
  }
}
发表于 2015-09-12 14:50:29 回复(2)
void run(int n) {
    // 递归调用
    int i;
    
    // 终止条件: 当当前操作元素是最后数组一个元素时结束递归;
    if (N - 1 == n) {
        dump();  // 输出结果;
        count ++;  // 更新统计个数;
        return;  // 结束递归;
    }
    // 递归方向: 每层递归的当前元素都可以和其后的元素进行交换;
    for (i = n; i < N; i++) {  // 每层递归将遍历余下数组元素(包含自身)并以此将当前元素与其后的元素交换;
        swap(n, i);
        run(n + 1);  // 递归方向: 进入下一层的递归;
        swap(n, i);  // 递归返回时恢复本层递归的现场(因下一层递归会更改当前工作数组x[N]);
    }
}

发表于 2022-01-20 19:10:36 回复(0)
发表于 2019-02-16 18:42:16 回复(0)
说内存溢出的人还有这么多赞,皮得很。
发表于 2018-09-18 00:08:48 回复(0)
以3的全排列为例。注意只有运行到run(N-1)时才会输出一个排列组合。求解run 0,当i=0,递归调用的话会有两次run 2,分别输出123和 132。同理i =1,输出213 231。i =2,输出321 312。所以i等于多少时说明该数的位置不变,输出后面几个数的全排列。
发表于 2016-10-06 17:39:27 回复(1)
可以用最简单的123举例,先保证1不变,后面两个是一种,然后交换,又是一种,递归一下就可以了!
发表于 2015-08-28 22:17:27 回复(0)
可以看成两步,首先求可能出现在第一个位置上的字符,即把第一个字符和后面所有的字符交换。第二步固定一个字符,求后面所有字符的全排列。
发表于 2017-10-06 20:26:27 回复(0)
用一句话解释:交换后,要交换回来才行,所以有两个swap。
发表于 2015-09-21 17:15:00 回复(0)
选D,运行结果也是对的
发表于 2015-09-05 21:50:38 回复(1)
for (i = n; i < N; i++) {
    //i从n开始主要是要包含不交换这种情况
    swap(n, i);
    run(n + 1);
    swap(n, i);
}
发表于 2015-08-28 11:25:47 回复(0)
这种递归求解的方法,最简单的理解方法是,假设run是一个求全排列的算法,所以run(1)必然能得出从1到N-1的全排列。那么我们a【0】处有多少种情况?不就是N种嘛?1到N嘛。所以才要和后面的所以有的数字进行一次交换然后递归求解。不多说直接上图吧
发表于 2019-09-26 10:02:29 回复(0)
1-9全排列
从首位开始(run(0)),每次从剩余数字中选择一个放在这一位,包括当前在第n位的数字。选完恢复,使下一个选法正常进行。
编辑于 2019-06-03 16:20:49 回复(0)
递归算法求全排列
基本思想就是轮流做第一个,然后进入下一轮
发表于 2018-05-16 20:53:56 回复(0)
当输入太多难辨认程序逻辑的时候就自己输入个小的同奇偶的。
发表于 2018-04-05 11:06:06 回复(0)
我就想问一下 swap函数是对的吗?能完成交换功能吗?
发表于 2017-07-10 23:11:30 回复(2)
run(n+1);此处运行完n已经加一,故最后一个空是n;而不是n+1;
发表于 2017-05-22 00:52:21 回复(0)
我用linux跑出来结果是C
发表于 2017-03-09 13:27:46 回复(0)