题目：有 1、2、3、4 四个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？
程序分析：可填在百位、十位、个位的数字都是 1、2、3、4，组成所有的排列后再去掉不满足条件的排列。
实例：
#include<stdio.h> int main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) { // 以下为三重循环 for(j=1;j<5;j++) { for (k=1;k<5;k++) { // 确保i、j、k三位互不相同 if (i!=k&&i!=j&&j!=k) { printf("%d,%d,%d\n",i,j,k); } } } } }
以上实例输出结果为：
1,2,3 1,2,4 1,3,2 1,3,4 1,4,2 1,4,3 2,1,3 2,1,4 2,3,1 2,3,4 2,4,1 2,4,3 3,1,2 3,1,4 3,2,1 3,2,4 3,4,1 3,4,2 4,1,2 4,1,3 4,2,1 4,2,3 4,3,1 4,3,2
1、为了尽量减少不必要的循环，做了如下的小优化。
#include <stdio.h> #include <stdint.h> int main() { uint32_t i; // 百位 uint32_t j; // 十位 uint32_t k; // 个位 for (i=1; i<5; i++) { for (j=1; j<5; j++) { // 百位与十位重复 // 跳过当前十位 if (j==i) { continue; } for (k=1; k<5; k++) { // 个位与百位或十位重复 // 跳过当前个位 if (k==j || k==i) { continue; } printf("%u,%u,%u\n", i, j, k); } } } }
2、参考方法：
#include<stdio.h> int main(void) { int i,j,k; for(i = 1;i < 5;i++) { for(j = 1;j < 5;j++) { if(i == j) continue; for(k = 1;k < 5;k++) { if(i == k || j == k) continue; printf("%d,%d,%d\n",i,j,k); } } } return 0; }
3、深搜法(DFS)写此题:
#include <stdio.h> #include <stdlib.h> int b[4],arr[4];//定义两个数组用来类比 int Count=0;//计数器 void DFS(int step){ if(step==5){ if(arr[1]!=arr[2]&& arr[1]!=arr[3]&&arr[2]!=arr[3]){//判断哪些符合条件 Count++; printf("%d%d%d\n",arr[1],arr[2],arr[3]);//输出可用排列 } return ; } for(int i=1;i<=4;i++){ if(b[i]==0){ arr[step]=i; b[i]=1;//排除重复 DFS(step+1);//自己调用自己 b[i]=0; } } return ; } int main(void) { DFS(1); printf("共有%d种",Count); return 0; }
4、使用递归与链表：
#include <stdio.h> #define NUM 4 // 数字个数 #define LEN 3 // 排列出的数字的长度 struct number { int val; struct number *next; } list[NUM]; void permutation(struct number *list, int m) { static int array[LEN]; struct number *p, *piror, *head; if(m) // 如果此次还未排列好，则选择剩余数字继续排列 for(piror=NULL, p=list, head=list; p; piror=p, p=p->next) { array[LEN - m] = p->val; // 将排列结果临时存入数组 if(piror) // 如果本次选择的数字不在表头 { piror->next = p->next; // 重组链表进行下一位数的排列 permutation(head, m-1); piror->next = p; // 还原链表 } else permutation(p->next, m-1); } else // 否则打印出此次排列出的数字 { int i; for(i=0; i<LEN; i++) printf("%d%c", array[i], i==LEN-1? '\n': ','); } } int main() { int i; // 初始化链表 for(i=0; i<NUM; i++) { list[i].val = i + 1; list[i].next = list + i + 1; } list[NUM - 1].next = NULL; // 递归打印排列结果 permutation(list, LEN); return 0; }
递归排列的过程中逐一将选中的数字从链表中删除，直接避免组成的三位数中出现重复数字。
