body, table{font-family: 微软雅黑; font-size: 10pt} table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;} th{border: 1px solid gray; padding: 4px; background-color: #DDD;} td{border: 1px solid gray; padding: 4px;} tr:nth-child(2n){background-color: #f8f8f8;}
递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。
从（0,0）到（m,n),每次走一步，只能向上或者向右走，有多少种路径走到(m,n) (0,0) ->(2,2) 0.0- >1.0 ->2.0 ->2,1 ->2,2 1 0,0->1.0->1,1 ->2.1->2.2 2 0.0 -> 1.0 ->.1,1->1,2->2,2 3 0.0 -> 0.1- >0.2- >1.2 ->2.2 4 0.0 ->0.1 ->1.1->1.2->2.2 5 0.0 ->0.1 ->1.1->2.1->2.2 6 f(m,n) | #include <stdio.h> #include<stdlib.h> #include<time.h> #define MAX 1000 int m, n; int count = 0; int path[MAX][2]; //2表示对应要记录的横坐标和纵坐标 void fun(int x, int y,int index); void print_path(int index); clock_t beg,end; int main() { scanf("%d%d", &m, &n); beg=clock(); fun(0, 0, 0); end=clock(); printf("count = %d\n", count); printf("time = %d\n", end-beg); system("pause"); return 0; } //搜索算法 void fun(int x, int y,int index) { path[index][0] = x; path[index][1] = y; if (x == m && y == n) { count++; print_path(index); return; } else if (x > m || y > n) return; fun(x + 1, y,index + 1); fun(x, y + 1,index + 1); } void print_path(int index) { int i; for (i = 0; i < index; i++) printf("(%d,%d) -> ", path[i][0], path[i][1]); printf("(%d,%d)\n", path[i][0], path[i][1]); } |
#include<stdio.h> #include<stdlib.h> int fun(int m,int n) { if(m==0&&n==0) { return 0; } else if(m==0||n==0) return 1; else return (fun(m-1,n)+fun(m,n-1)); } void main() { int m,n,sum; while( printf("请输入m,n:"), scanf("%d %d",&m,&n)!=EOF) { sum=fun(m,n); printf("一共%d种走法\n",sum); } system("pause"); } |