我需要写一个算法如何解决这个练习,有什么建议吗?
练习:
我们有一个矩形,分成n x m个正方形,有自然数。写一个计算这个矩形内有多少个幻方的函数。
幻方是方格中k x k(k>=2)个数(通常是整数)的排列,其中每行、每列中的数以及主对角线和次对角线中的数都相加为同一个数。
最佳答案
构造4个数组:
1:每个元素都是原始数组中的元素+左一个。
2:每个元素都是从原始数组+1到顶部的元素。
3:每个元素都是从原始数组+左上角的元素。
4:每个元素都是从原始数组+1到右上角的元素。
你的阵列会得到这样的东西。
现在你必须检查数组中所有可能的正方形拟合(可能有更好的解决方案,但我想不出任何)在其他四个中寻找类似的东西。
因为我们在数组中保留和,所以我们可以清楚地看到,当检查数组3x3(从左上角开始)时,所有和都是15意思是这是一个魔方。
如果不是从左上角开始,就不那么明显了,但仍然很容易请看下面突出显示第二个幻方的示例。
你可以看到evey深色元素减去相应的浅色元素是常量(在本例中是12)
它对第一个魔方的作用是一样的,但是会有0,所以我们可以跳过它。
关于algorithm - 函数找出由n * m组成的矩形中有多少个魔方,其中n,m-自然数,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27019710/