一个二维坐标系,从(0,0)点出发,每次只能上下左右任意方向移动1,例如移动一步可以移动到(1,0)(0,1)(-1,0)(0,-1),问k步之后可以移动到多少个不同的位置(给出通式)?输出出来
7条回答 默认 最新
- Yi骑绝尘 2017-05-22 08:28关注
可以倒着思考:假设第k步之后的不同位置为 f(k),f(k)是在f(k-1)基础上得到的,即f(k)最外层点是在f(k-1)最外层的点基础上出来的。那么可以得到一个关系式:f(k) = a(*)f(k-1)+b
(为什么是一次函数关系,很容易理解,拿第一步和第二步分析一下就看出来了,(*表示相乘的意思,不转义字符串就是斜体显示。看着别扭))。得到f(0)=1,f(k) = f(k-1)+b,下面解决b:
每走一步,就有4个方向,所以是b = 4(*)k,所以最后的表达式为:f(k) = f(k-1)+4(*)k,f(0) = 1,代码实现:public static int function(int k){
if(k<0) {
System.out.println("k must be bigger than 0");
return -1;
}
if(k==0) return 1;
//非递归方法
int fk = 0;
for(int i=1;i<=k;i++){
fk = fk + 4*i;
}
return fk+1;
}本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报