我的博客貌似总是有点碎碎念。唉，为了克服自己的碎碎念的欲望，逼迫自己在这里写些读书笔记。
读书笔记第一站：计算机程序设计与算法分析：递归
计算机程序设计与算法分析 》读书笔记1：递归
第一题：整数划分问题：
将正整数n表示成n1+n2+...+nk(n1>=n2>=...nk>=1),称为正整数的一种划分。
正整数n的不同的划分个数成为正整数n的划分数，记为p(n),譬如正整数6的划分数
p(6)=11,不同的划分分别为：
1+1+1+1+1+1;
2+1+1+1+1;
2+2+1+1;
2+2+2;
3+1+1+1;
3+2+1;
3+3;
4+1+1;
4+2;
5+1;
6;
那么写一个程序计算给定的正整数n的划分数
解答：记n1不大于m的划分个数为：q(n,m),那么有如下的递推关系式
q(n,m)=1 (if m==1);//基础情况
q(n,m)=q(n,n) (if m>n);//m>n
q(n,n)=q(n,n-1)+1; (最大整数不大于n时，其划分分为两种：最大数不大于n-1和最大数等于n)//m==n
q(n,m)=q(n,m-1)+q(n-m,m)(正整数n的最加数不大于m的划分，由最大加数不大于m-1的划
分和最大加数等于m的划分组成)//m<n
于是有下面的程序
int q(int n,int m)
{
if((n<1||(m<1))
return 0;
if((n==1)&&(m==1))
return 1;
if(m>n) return q(n,n);
if(m==n) return 1+q(n,n-1);
return q(n,m-1)+q(n-m,m);
}
那么如何记录下并且显示出这些具体划分呢？
1，递归法：
#include<stdio.h>
int a[1000];
void q(int n,int step)
{
if(n==0)
{
for(int i=0;i<step;i++)
printf("%d ",a[i]);
printf("\n");
return ;
}
for(int k=n;k>0;k--)
{
if(step>0)
{
if(k>a[step-1])
continue;
}
a[step]=k;
q(n-k,step+1);
}
}
int main()
{
int n;
printf("Please input n:\n");
printf("\n");
while((scanf("%d",&n))!=EOF)
{
printf("\n");
q(n,0);
printf("Please input the number n:\n");
}
return 0;
}
------------------------------------
雅虎中国研究院的一道笔试题：
在平面直角坐标系的第一象限，有一个点物质的移动只能有三种方向：
1）右移单位1长度，
2）上移单位1长度
3）单位正方形的左下角移动到右上角
如图所示：
那么问：从(x1,y1)走向(x2,y2)（x1,y1,x2,y2都是正整数）有几种走法？分别是什么？
解答如下：
#include<stdio.h>
int a[3][2]={{1,0},{0,1},{1,1}};//0,1,2，
//0对应的是右移时的坐标变化，1对应的是上移，2对应的是斜上移
char direc[3]={'-','|','/'};//分别对应的是右移 上移 斜上移的示意图
char route[1000]; //用来标记路程
void findroute(int step,int x1,int y1,int x2,int y2)
{
//static int cnt=0;
if((x1>x2)||(y1>y2))
return;
if((x1==x2)&&(y1==y2))
{
//printf("%d: ",cnt);
for(int i=0;i<step;i++)
{
printf("%c ",route[i]);
//route[i]=0;
}
printf("\n");
//cnt++;
return ;
}
for(int k=0;k<=2;k++)
{
route[step]=direc[k];
findroute(step+1,x1+a[k][0],y1+a[k][1],x2,y2);
}
}
int main()
{
int x1,y1;
int x2,y2;
while(1)
{
printf("Please input the first pair of coor\n");
if(scanf("%d %d",&x1,&y1)==EOF) break;
printf("Please input the second pair of coor\n");
if(scanf("%d %d",&x2,&y2)==EOF) break;
findroute(0,x1,y1,x2,y2);
}
return 0;
}
|
加为好友
送他礼物
发送消息
