算法问题（语言不限）

问题描述：

一个二维坐标系，从（0,0）点出发，每次只能上下左右任意方向移动1，例如移动一步可以移动到（1,0）（0,1）（-1,0）（0，-1），问k步之后可以移动到多少个不同的位置（给出通式）？输出出来

答

可以倒着思考：假设第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;
}

答

分析一下问题,起点是0.0 移动K步 ,最大范围就是 |x| + |y| <=k ;
如果k 是偶数 ,那么 |x| + |y| <=k 且 |x| + |y| 不能为奇数
如果k 是奇数 ,那么 |x| + |y| <=k 且 |x| + |y| 不能为偶数
然后输出所有符合 |x| + |y| <=k ; 且x,y属于整数的坐标点.符合上面几个条件
在这里分一下象限,只需要求出第一象限的所有坐标就行,由于置换到二,三,四象限只需要换x,y 的符号即可.
而第一象限的所有点是一个三角形
就是两个for 循环

for(i=0;i for(j=0;j if(i+j>k&&( 0&(i+j)!=(k&0) )break;

    console.log(i,j);
    console.log(i*-1,j);
    console.log(i,j*-1);
    console.log(i*-1,j*-1);
}

}

答

上面的有点问题,下面的ok了

 分析一下问题,起点是0.0 移动K步 ,最大范围就是 |x| + |y| <=k ;
如果k 是偶数 ,那么 |x| + |y| <=k 且 |x| + |y| 不能为奇数
如果k 是奇数 ,那么 |x| + |y| <=k 且 |x| + |y| 不能为偶数
然后输出所有符合 |x| + |y| <=k ; 且x,y属于整数的坐标点.符合上面几个条件
在这里分一下象限,只需要求出第一象限的所有坐标就行,由于置换到二,三,四象限只需要换x,y 的符号即可.
而第一象限的所有点是一个三角形
就是两个for 循环

for(i=0;i<=k;i++){
    for(j=0;j<=k;j++){
        if(i+j>k||( 0&(i+j)!=(k&0) )break;
    console.log(i,j);
    console.log(i*-1,j);
    console.log(i,j*-1);
    console.log(i*-1,j*-1);
}
}

答

假设二维坐标系为整数坐标系，因为题目限定了起点（0，0），而且还限定了是K步，那么就构造一个正方形与正菱形交错的递归式。

fun(k)
{
    if(0 != k)
    {
        输出半径为K的正菱形（◇）边角坐标
        if(0 == k % 2) 
        {
            输出边长为K的正方形（□）边角坐标
        }
        fun(k-1)
    }
}

答

public static void main(String[] args) {
Set re = find(2,0,0);
System.out.println(re);
}

public static Set<String> find(int k,int x, int y){
    Set<String> re = new HashSet<>();//java 中 set 会去掉重复的元素
    if(k ==0){
        re.add(x +","+y);
        return  re;
    }
    re.addAll(find(k-1,x+1,y));
    re.addAll(find(k-1,x-1,y));
    re.addAll(find(k-1,x,y+1));
    re.addAll(find(k-1,x,y-1));
    return re;
}

答

输出结果:
(奇葩语言负号在右边)

  2-    0      0 ,0  ->1-,0  ->2-,0

 1-  1-      0 ,0  ->1-,0  ->1-,1

 1- 1        0 ,0  ->1-,0  ->1-,1

 0   2-       0 ,0  ->0 ,1- ->0 ,2

 0    0        0 ,0  ->1 ,0  ->0 ,0

 0    2        0 ,0  ->0 ,1  ->0 ,2

 1    1-       0 ,0  ->1 ,0  ->1 ,1

 1    1      0 ,0  ->1 ,0  ->1 ,1

 2   0      0 ,0  ->1 ,0  ->2 ,0

答

大家一起来吐槽一下奇葩的ABAP语言：

 *在二维坐标系中某一点开始移动，每次只能横向或纵向移动1，求移动X 步之后的终点位置*

report aaa.

DATA: BEGIN OF STEPS OCCURS 0,
      X TYPE i,
      Y TYPE i,
      WAY TYPE STRING,
      END OF STEPS.

PERFORM GOSTEP USING 0 0 2  ''. " 初始坐标位置I ,初始坐标位置J，移动步数Z,初始路径STEP.

"输出终点位置
SORT STEPS BY X Y.
DELETE ADJACENT DUPLICATES FROM STEPS  COMPARING X Y. "去除重复
loop at STEPS.
  write: STEPS-X,steps-Y,  steps-waY.
    SKIP.
endloop.

FORM GOSTEP USING
                    value(X) type i
                    value(Y) type i
                    value(Z) TYPE N
                    value(STEP) TYPE STRING. "路径

  DATA: X1 type I, Y1 type I,
        S_X type string, S_Y type string.

    IF STEP <> ''.
       CONCATENATE STEP ' ->' INTO STEP.
    ENDIF.
    S_X = X.S_Y = Y.
    CONCATENATE STEP S_X ',' S_Y INTO STEP.

    IF Z = 0.
      STEPS-X = X.
      STEPS-Y = Y.
      STEPS-WAY = STEP.  "路径
      append STEPS. "记录终点位置
    ELSE.

    Z = Z - 1 .
    X1 = X + 1 .
         PERFORM GOSTEP USING X1 Y  Z  STEP.
    X1 = X - 1 .
         PERFORM GOSTEP USING X1 Y  Z  STEP.
    Y1 = Y + 1 .
         PERFORM GOSTEP USING X Y1  Z  STEP.
    Y1 = Y - 1 .
         PERFORM GOSTEP USING X Y1  Z  STEP.
  ENDIF.
endform.

算法问题（语言不限）

相关推荐