国际象棋-算法，指定跳跃

Question

我有一个问题。

我们有无限的棋盘，如何计算n跳后你可能发现自己跳的一半的数量？

例如：

一次跳跃后我们有 8 个盒子

经过两次跳跃后我们有 33 个盒子

#include<bits/stdc++.h>
using namespace std;

int sign(int n)
{
  if(n > 0 )return 1;
  else if(n == 0) return 0;
  else return -1;
}


int main()
{
  int t, n;
  cin >> t;
  for(int i = 0; i < t; i++)
  {
    cin >> n;
    cout << 7*n*n + 4*n - 3*sign(n-2)*sign(n-1) << endl;

  }
}


//f(n) = 7*n^2 + 4*n - 3*Sign[(n - 2)(n - 1)]

怎么了？

我的代码return11，对于n=1，应该return8

好的，工作中！

Answer 1

通过编写一个简单的 python 程序：

dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]

def calc(level):
    cell_list = set([(0,0)])
    for _ in range(level):
        new_cell_list = set()
        for x, y in cell_list:
            for k in range(len(dx)):
                new_cell_list.add((x+dx[k], y+dy[k]))
        cell_list = new_cell_list

    return len(cell_list)


for level in range(1, 10):
    print(calc(level), end=', ')

我们得到

8, 33, 76, 129, 196, 277, 372, 481, 604

即 A118312。公式为：

f(n) = 7*n^2 + 4*n - 3 + 4*Sign[(n - 2)(n - 1)]

哪里

           1   n > 0
Sign(n) =  0   n == 0
          -1   n < 0

这等同于：

f(0) = 1
f(1) = 8
f(2) = 33
f(n) = 7*n^2 + 4*n + 1, n >= 3

国际象棋-算法，指定跳跃

Chess - algorithm, designate jumps

algorithm

combinatorics