我和一个朋友正在考虑一个有趣的计算机科学问题。
你有一个简单的二维数组:
[ 1, 2, 3, 4 ]
[ 5, 6, 7, 8 ]
[ 9, 10, 11, 12 ]
[ 13, 14, 15, 16 ]
现在取这个数组并打乱数组中的所有元素:
[ 11, 5, 14, 10 ]
[ 8, 2, 4, 16 ]
[ 15, 1, 3, 13 ]
[ 6, 12, 9, 7 ]
一开始是一个相当简单的概念。但是,如果我们再迈出一步呢?现在,打乱原始数组,使新数组中的任何元素都不会与它们在原始数组中在基本方向上相邻的项相邻。
我们的第一次洗牌失败,因为 1 在 2 旁边,并且在原始数组中也在 2 旁边。
这是一个工作示例:
[ 7, 16, 13, 2 ]
[ 14, 3, 5, 8 ]
[ 9, 1, 4, 11 ]
[ 12, 10, 15, 6 ]
还不算太糟糕。现在到了真正的问题!
再次对原始数组进行洗牌,使数组中的任何元素都不会与它们在基数方向或对角线相邻的元素相邻。
我们的工作示例失败了,因为 1 对角线靠近 5,并且在原始数组中靠近 5。
一些想法:
- 甚至可以确定一个数组吗?
- 它取决于数组的大小吗?
- 阵列是否需要对称?
- 数组是否需要有偶数/奇数个元素?
- 解决方案是否适用于所有大小为M乘N的数组?
- 如果存在解决方案,找到新阵列的运行时间是多少?
你怎么看?
编辑
我很惊讶地发现我的问题被关闭为“离题”。根据常见问题解答,如果我的问题“......通常涵盖特定的编程问题......”那么它可以被问到并且不是“离题”。
我问的底线问题是:
“你能拿一个二维数组并打乱它,这样新数组中的成员就不会彼此相邻,包括对角线”。
这不是一个好的编程问题吗?我强烈认为我的问题不应该结束。