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");
}
|
 |