一个困了我好久的算法问题 — 编程爱好者社区

主题：一个困了我好久的算法问题

jessezu [专家分：0] 发布于 2006-05-12 14:14:00

设有n种不同的颜色，同一种形状的n颗宝石分别具有这n种不同的颜色。现有n种不同形状的宝石共n*n颗，欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个程序计算出对于给定的n有多少种不同的宝石排列方案。

本帖地址： http://bbs.pfan.cn/post/165216.html

回复列表（共6个回复）

沙发

euc [专家分：4310] 发布于 2006-05-15 20:27:00

不太确定: 只考虑颜色的话,有n!种,由于旋转90度的4种情况算一种,所以是n!/4,然后加上形状这第2维因素,跟颜色一样考虑,总共是(n!/4)^2种.

板凳

boxertony [专家分：23030] 发布于 2006-05-16 09:11:00

euc的公式肯定不对。
首先n=2是无解的。
n=3时，我找到3个解（3!/4)^2 = 2.25

a1 b2 c3
c2 a3 b1
b3 c1 a2

b1 c2 a3
a2 b3 c1
c3 a1 b2

c1 a2 b3
b2 c3 a1
a3 b1 c2

我在一本数学上看见过这道题的论述，我回去查查。

3 楼

euc [专家分：4310] 发布于 2006-05-17 20:25:00

今天又想了一会儿，发现挺难的，只好用回溯了。

4 楼

boxertony [专家分：23030] 发布于 2006-05-18 08:34:00

我查了一下书，这个东西叫正交拉丁方。欧拉曾经研究过，给出过一个猜想，后来被推翻了。现在还有一个猜想，号称另一个费尔曼小定理，即设N(n)＝n-1（当n为素数幂时） N(n)即正交拉丁方的个数

5 楼

jessezu [专家分：0] 发布于 2006-05-28 16:36:00

就是用回溯算法啊

6 楼

36336985 [专家分：0] 发布于 2006-07-14 10:53:00

就是一个拉丁方阵的问题啊
应该简单啊

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：一个困了我好久的算法问题

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：一个困了我好久的算法问题

回复列表 （共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共6个回复）