半幻方
Semimagic Square
我必须创建生成随机 NxN 幻方的函数,所有列和行的总和等于 S。变量 N 和 S 必须是用户输入。我已经创建了在满足给定条件时绘制正方形并中断循环的函数。它适用于 3x3 或 4x4 等小正方形,但对于较大的正方形则效率极低。矩阵内的所有数字都必须是整数,不需要对角线等于行和。
任何建议如何解决这个问题?
由于任何幻方也是半幻方(不必有对角线求和为幻方常数),要回答这个问题,提供一种有效的算法来生成真正的幻方就足够了。求解幻方的经典算法之一如下(Robin K. S. Hankin 引用):
In a square of order 4m, shade the long major diagonal. Then shade all
major diagonals distant by a multiple of 4 cells from the long
diagonal. Do the same with the minor diagonals. Then, starting with
“1” at the top left corner and proceeding from left to right and top
to bottom, count from 1 to n^2, filling in the shaded squares with the
appropriate number and omitting the unshaded ones. Fill in the
remaining (unshaded) squares in the same way, starting at the lower
right corner, moving leftwards and upward.
您可能会发现 R 包 magic 是研究高效幻方生成算法的有用资源。从包源中可以清楚地看出,问题可以分为三种不同的情况:
"magic" <-
function (n)
{
if(length(n)>1){
return(sapply(n,match.fun(sys.call()[[1]])))
}
n <- round(n)
if (n == 2) {
stop("Normal magic squares of order 2 do not exist")
}
if (n%%2 == 1) {
return(as.standard(magic.2np1(floor(n/2))))
}
if (n%%4 == 0) {
return(as.standard(magic.4n(round(n/4))))
}
if (n%%4 == 2) {
return(as.standard(magic.4np2(round((n - 2)/4))))
}
stop("This cannot happen")
}
magic
的执行时间出奇的短,即使对于大 n
:
> system.time(result <- magic(2017))
user system elapsed
1.256 0.316 1.573
最后,如果您真的只想要一个半幻方而不是真正的幻方,您可以随时交换所得方阵的任意两列。此操作不会影响行和列的总和,但肯定会破坏对角线的总和。
我必须创建生成随机 NxN 幻方的函数,所有列和行的总和等于 S。变量 N 和 S 必须是用户输入。我已经创建了在满足给定条件时绘制正方形并中断循环的函数。它适用于 3x3 或 4x4 等小正方形,但对于较大的正方形则效率极低。矩阵内的所有数字都必须是整数,不需要对角线等于行和。 任何建议如何解决这个问题?
由于任何幻方也是半幻方(不必有对角线求和为幻方常数),要回答这个问题,提供一种有效的算法来生成真正的幻方就足够了。求解幻方的经典算法之一如下(Robin K. S. Hankin 引用):
In a square of order 4m, shade the long major diagonal. Then shade all major diagonals distant by a multiple of 4 cells from the long diagonal. Do the same with the minor diagonals. Then, starting with “1” at the top left corner and proceeding from left to right and top to bottom, count from 1 to n^2, filling in the shaded squares with the appropriate number and omitting the unshaded ones. Fill in the remaining (unshaded) squares in the same way, starting at the lower right corner, moving leftwards and upward.
您可能会发现 R 包 magic 是研究高效幻方生成算法的有用资源。从包源中可以清楚地看出,问题可以分为三种不同的情况:
"magic" <-
function (n)
{
if(length(n)>1){
return(sapply(n,match.fun(sys.call()[[1]])))
}
n <- round(n)
if (n == 2) {
stop("Normal magic squares of order 2 do not exist")
}
if (n%%2 == 1) {
return(as.standard(magic.2np1(floor(n/2))))
}
if (n%%4 == 0) {
return(as.standard(magic.4n(round(n/4))))
}
if (n%%4 == 2) {
return(as.standard(magic.4np2(round((n - 2)/4))))
}
stop("This cannot happen")
}
magic
的执行时间出奇的短,即使对于大 n
:
> system.time(result <- magic(2017))
user system elapsed
1.256 0.316 1.573
最后,如果您真的只想要一个半幻方而不是真正的幻方,您可以随时交换所得方阵的任意两列。此操作不会影响行和列的总和,但肯定会破坏对角线的总和。