C语言之递归经典问题 |
您所在的位置：网站首页 › c语言经典问题 › C语言之递归经典问题 |
|
目录 一、十进制转换 二、前中序遍历确定后序遍历 三、汉诺塔 四、八皇后问题 五、细胞分裂 分治法将原问题划分为若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并问题的解即为原问题的解。 递归很适合实现分治思想，递归的逻辑中有两个重要概念：递归边界和递归式。 一、十进制转换 //十进制数递归转换为小于10的进制数 #include #define radix 2 void convert(int n, int x) { if(n == 0) return; else { convert(n/x, x); printf("%d", n%x); } } int main() { int n; while(scanf("%d", &n) != EOF) { convert(n, radix); printf("\n"); } return 0; } 二、前中序遍历确定后序遍历 #include #include #include typedef struct BiNode { char data; struct BiNode *lchild, *rchild; }BiNode, *BTree; //前中序确定后序 BTree preInTree(char preOrder[], int pl, int pr, char inOrder[], int il, int ir) { //以{FDXEAG}和{XDEFAG}为例 int i = 0； int len_p = pr-pl+1, len_i = ir-il+1; if(len_p lchild = preInTree(preOrder, pl+1, pl+i, inOrder, il, il+i-1); //{AG}和{AG} p->rchild = preInTree(preOrder, pl+i+1, pr, inOrder, il+i+1, ir); printf("%c", preOrder[pl]); return p; } int main() { char a[30], b[30]; while(scanf("%s%s", a, b) != EOF) { BTree BT = preInTree(a, 0, strlen(a)-1, b, 0, strlen(b)-1); printf("\n"); } return 0; } 三、汉诺塔 #include int main() { void hanoi(int n, char one, char two, char three); int N; printf("input the number of disks:"); scanf("%d", &N); printf("output the step to move:\n"); hanoi(N, 'A', 'B', 'C'); return 0; } void hanoi(int n, char one, char two, char three) //将n个盘从one座借助two座，移到three座 { void move(char x, char y); if(n == 1) move(one, three); else { hanoi(n-1, one, three, two); move(one, three); hanoi(n-1, two, one, three); } } void move(char x, char y) { printf("%c-->%c\n", x, y); } 四、八皇后问题题目描述：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 假设每行放皇后，则只需要考虑列情况，即数组下标表示行，数组元素表示列。 #include #include #define n 8 int array[10]; int sum=0; int judge(int k) {//判断当前位置是否能够满足斜线和列限制 for(int j = 1; j < k; j++) if(abs(k-j) == abs(array[k] - array[j]) || array[k] == array[j]) return 0; return 1; } int queen(int k) {//k代表行，i进行列循环 int i; if(k > n) sum++; else { for(i = 1; i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |