正方形网格里的最长路

aimisiyou

F（N）=N^2/2+N-3/4-(-1)^N/4

王守恩

aimisiyou 发表于 2022-8-23 12:06
F（N）=N^2/2+N-3/4-(-1)^N/4

F（N）=N^2/2+N-3/4-(-1)^N/4 是这串数：

1, 3, 7, 11, 17, 23, 31, 39, 49, 59, 71, 83, 97,

这串数可以：\(\D F(N)=\frac{N(N + 2) - GCD(N,N+2)\ \ \ \ \ \ \ \ \ \ \ \ \ \ }{2}\)

风云剑

上界是(n+1)^2/2？

mathe

n=4k+1时，结果应该很规律

王守恩

aimisiyou 发表于 2022-8-23 12:06
F（N）=N^2/2+N-3/4-(-1)^N/4

F（N）=N^2/2+N-3/4-(-1)^N/4 是这串数：

1, 3, 7, 11, 17, 23, 31, 39, 49, 59, 71, 83, 97,

这串也可以：

\(\D F_{N}=2F_{N-1}-F_{N-2}+1-\cos(N\pi),F_{1}=1,F_{2}=3\)

\(\D F_{N}=F_{N-1}+2\lfloor N/2\rfloor,F_{2}=1\)

mathe

https://oeis.org/A000532 Fans可以计算到18项，这个问题应该可以差不多

https://bbs.emath.ac.cn/thread-16151-1-1.html

aimisiyou

mathe 发表于 2022-8-25 09:33
https://oeis.org/A000532 Fans可以计算到18项，这个问题应该可以差不多

https://bbs.emath.ac.cn/threa ...

还是有些区别，有且仅有一条路径到达，限制条件更强。
当然从所有路径里筛选出符合条件的最长路径是可以，但运算量是否太大了。

ejsoon

王守恩 发表于 2022-8-23 14:52
F（N）=N^2/2+N-3/4-(-1)^N/4 是这串数：

1, 3, 7, 11, 17, 23, 31, 39, 49, 59, 71, 83, 97,

gcd是甚麼？
明白了，最大公約數。

aimisiyou

KeyTo9_Fans 发表于 2022-8-22 06:40
问题1：

如何在某些格子里设置障碍，

编了下程序，计算n=6时用时5秒，n=7时用时6分钟。

aimisiyou

n=8运行耗时太长了，估计得一周。看来得想办法优化下。