首页 > 试题广场 >

下列代码试图打印数字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
```

推荐

zcj5918

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

编辑于 2016-03-24 15:24:05 回复(7)

中汇信息技术最牛逼

不是我吐槽，题目中的run函数只有2个空。

发表于 2016-08-08 01:56:05 回复(2)

cd小鬼哥

先看代码

     for(i = ___; i < N; i++) {  

        swap(___, i);  

        run(n + 1);  

        swap(___, i);  

      }

为了防止内存溢出，我直接排除法选择了c。只是个做题技巧，程序没多看

发表于 2015-08-27 16:38:06 回复(14)

wangtingkui

记录一下错误：

我是第一个空错了，之前没有想到自己和自己交换有什么意义，所以选了n+1

这样的话就少了不交换的那种情况

发表于 2015-08-28 09:47:35 回复(7)

guanjian

  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)

GodfreyHarold

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)