Algorithm 版 (精华区)
发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: [合集]帮我，help!急~~
发信站: 哈工大紫丁香 (2002年07月26日23:33:28 星期五), 站内信件
────────────────────────────────────────
samuel (孔雀翎) 于 2002年07月19日17:39:16 星期五 说道:
██ ██ 可以拼成3X4的 ████
█ █ █ ████
█ █ ████
███
设计一个算法能够求出全部的的拼法。
请大家帮忙，提出一种算法，我给出的算法老师说不行。
明天晚六点之前就要，我要疯了 :(
────────────────────────────────────────
GREnTOFEL (Crazy Plucking) 于 2002年07月19日21:02:12 星期五 说道:
设定一个数组，规定一个元素为原点，则先把四快板其中一块放在原点
上，然后依次在这快板的其中一块小板上放上第二块板，直到把四块板都
放完，最后检查所得图形是否为所需图形。回溯，旋转放置的板，或换另
一块小板放置，如下图：
11
1
1111
1 1
1
1111
1 1
1 1
11
1
1111
1 1
1 1
11
11
到此所得图形不正确则回溯
1111
1 1
1 1
111
1
仍然不正确，回溯
......
......
最后肯定能把所有结果求出来。中间可以做些优化，比如所得图形的长
以超过4，则肯定要回溯。等等。
────────────────────────────────────────
Lerry (想不开·撞树) 于 2002年07月20日08:39:12 星期六 说道:
幸亏是拼接矩形,上次讨论的三角形的还没有什么可行的方案呢
三角形很少还可以,但数目增多的时候,这样穷举和简单的剪枝就没有意义了
────────────────────────────────────────
samuel (孔雀翎) 于 2002年07月20日11:30:58 星期六 说道:
下面是我已经实现的算法，已经交上去了，老师还算满意
██ ██ 可以拼成3X4的 ████
█ █ █ ████
█ █ ████
███
设计一个算法能够求出全部的的拼法。
题目相当于对目标的12个格子用四种颜色进行着色，第一、二种颜色着4个格子，第三种
颜色着3个格子，第四种颜色着一个格子，而且要求同色的格子构成固定的图形，求全部
可能的方案数。
那么不妨分两步进行，第一步，首先求出对目标图形的各种着色方案；第二步，对每一
种着色方案，判断其是否能合理的解决目标问题的规划。
二步求精，在算法注释和文档中会详细解释算法：
#include<stdio.h>
/*首先构造一个求阶乘的函数，根据《组合数学》原理，求n种颜色对目标着色，每种颜
色分别着k1、k2……kn个的方案数，其中k1+k2+……+kn=k，相当于可重组合的问题，着
色方案应为k!/(k1!k2!……kn!)
本题中k=12,k1=4,k2=4,k3=3,k4=1,总方案数为138600种*/
int factorial(int n)
{
int i,n;
if (n==0)
return(1)
else {
i=n*factorial(n-1)
return (i)
}
}
/*生成着色方案数组，存储全部合理着色方案数*/
int bepaint(i,j,m,n,o,p)
{
int i,j,m,n,o,p;
extern int S[138600][12];//用于存放着色方案结果的数组，全局数组
int k,l;
k=m+n+o+p;//存放当前剩余待着色的目标数，就是还剩几个格子没有着色
l=factorial(k)/(factorial(m)*factorial(n)*factorial(o)*factorial(p))//着
色方
案总数
int e,f,g
e=l*m/k;
f=e+l*n/k;
g=f+l*o/k;
int i=1;//着色方案序号
int j;
j=12-k+1;//当前着色目标序号，即给第几个格子着色
if (i<=e)
{
S[i][j]='a';i++;bepaint(i,j,m-1,n,o,p)//相应格子着色a，共a、b、c、d四
种颜
色，递归调用
}
else if (i<=f)
{
S[i][j]='b';i++;bepaint(i,j,m,n-1,o,p)
}
else if (i<=g)
{
S[i][j]='c';i++;bepaint(i,j,m,n,o-1,p)
}
else
{
S[i][j]='d';i++;bepaint(i,j,m,n,o,p-1)
}
}
/*构造一个转换函数，用来将1-12的二维数组转换成题目要求的3*4的三维数组*/
int conversion(i,j,l,m,n)
{
int i,j,l,m,n;
extern int T[138600][4][3];//转化后的数组，全局数组
for (l=1;l<=138600;l++)
{
for (m=1;m<=3;m++)
{
for (n=1;n<=4;n++)
{
int e=m*4+n;
if ((j==e)and(l==i))
{
T[l][m][n]=S[i][j]
}
}
}
}
}
/*下面是算法的主程序，将给出题目要求的全部拼法*/
int patchwork(k,e,f,g,h)
{
int i,m,n,e,f,g,h;counter;
m=1;n=1;e=0;f=0;g=0;h=0;i=1;
counter=0;//计数器，用于存放符合要求的方案数
while (i<=138600) do
{ if (T[i][m][n]='a')//判断着色a的形状是否符合要求
{
if (((T[i][m+1][n-1]='a')and(T[i][m+1][n+1]='a')and(T[i][m+1][n+
1]='a'))
or((T[i][m-1][n+1]='a')and(T[i][m][n]='a')and(T[i][m][n+1]='a
'))
or((T[i][m-1][n]='a')and(T[i][m][n-1]='a')and(T[i][m][n+1]='a
'))
or((T[i][m-1][n-1]='a')and(T[i][m][n-2]='a')and(T[i][m][n-1]=
'a'))
//每一种图形可以旋转90度、180度、270度，有四种形态
//每一种形态又根据格与格的相邻关系有构成方块数-1个相邻块
//加以判断，就可得每一个方块和相邻格是否可以构成合理的构件
or((T[i][m+1][n]='a')and(T[i][m+1][n+1]='a')and(T[i][m+2][n]=
'a'))
or((T[i][m-1][n]='a')and(T[i][m][n+1]='a')and(T[i][m+1][n]='a
'))
or((T[i][m-1][n-1]='a')and(T[i][m][n-1]='a')and(T[i][m-1][n-1
]='a'))
or((T[i][m-2][n]='a')and(T[i][m-1][n]='a')and(T[i][m-1][n+1]=
'a'))
or((T[i][m][n+1]='a')and(T[i][m][n+2]='a')and(T[i][m+1][n+1]=
'a'))
or((T[i][m][n-1]='a')and(T[i][m][n+1]='a')and(T[i][m+1][n]='a
'))
or((T[i][m][n-2]='a')and(T[i][m][n-1]='a')and(T[i][m+1][n-1]=
'a'))
or((T[i][m+1][n-11]='a')and(T[i][m+1][n]='a')and(T[i][m+1][n+
1]='a'))
or((T[i][m+11][n-1]='a')and(T[i][m+1][n]='a')and(T[i][m+2][n]
='a'))
or((T[i][m-1][n+1]='a')and(T[i][m][n+1]='a')and(T[i][m+1][n+1
]='a'))
or((T[i][m-1][n]='a')and(T[i][m][n-1]='a')and(T[i][m+1][n+1]=
'a'))
or((T[i][m-2][n]='a')and(T[i][m-1][n-1]='a')and(T[i][m-1][n]=
'a')))
{
e++;
if ((m==3)and(n==4))
{
i++;m=1;n=1;
if ((e>0)and(f>0)and(g>0)and(h>0)) counter=couter+1;
//如果每个形状的图形都存在，自然这是所求问题的一个解
}
else if (n==4) {m++;n=1}
else n++;
}
else if (T[i][m][n]='b')////判断着色b的形状是否符合要求
{
if (((T[i][m][n+1]='b')and(T[i][m][n+2]='b')and(T[i][m+1][n]
='b'))
or((T[i][m][n-1]='b')and(T[i][m][n+1]='b')and(T[i][m+1][n
-1]='b'))
or((T[i][m][n-2]='b')and(T[i][m][n-1]='b')and(T[i][m+1][n
-2]='b'))
or((T[i][m-1][n]='b')and(T[i][m-1][n+1]='b')and(T[i][m-1]
[n+2]='b'))
or((T[i][m][n+1]='b')and(T[i][m+1][n+1]='b')and(T[i][m+2]
[n+1]='b'))
or((T[i][m][n-1]='b')and(T[i][m+1][n]='b')and(T[i][m+2][n
]='b'))
or((T[i][m-1][n-1]='b')and(T[i][m-1][n]='b')and(T[i][m+1]
[n]='b'))
or((T[i][m-2][n-1]='b')and(T[i][m-2][n]='b')and(T[i][m-1]
[n]='b'))
or((T[i][m+1][n-2]='b')and(T[i][m+1][n-1]='b')and(T[i][m+
1][n]='b'))
or((T[i][m-1][n+2]='b')and(T[i][m][n+1]='b')and(T[i][m][n
+2]='b'))
or((T[i][m-1][n+1]='b')and(T[i][m][n-1]='b')and(T[i][m][n
+1]='b'))
or((T[i][m-1][n]='b')and(T[i][m][n-2]='b')and(T[i][m][n-1
]='b'))
or((T[i][m+1][n]='b')and(T[i][m+2][n]='b')and(T[i][m+2][n
+1]='b'))
or((T[i][m-1][n]='b')and(T[i][m+1][n]='b')and(T[i][m+1][n
+1]='b'))
or((T[i][m-2][n]='b')and(T[i][m-1][n]='b')and(T[i][m][n+1
]='b'))
or((T[i][m-2][n-1]='b')and(T[i][m-1][n-1]='b')and(T[i][m]
[n-1]='b')))
{
f++;
if ((m==3)and(n==4))
{
i++;m=1;n=1;
if ((e>0)and(f>0)and(g>0)and(h>0)) counter=couter+
1;
}
else if (n==4) {m++;n=1}
else n++;
}
else if (T[i][m][n]='c')//判断着色c的形状是否符合要求
{
if (((T[i][m][n+1]='c')and(T[i][m+1][n]='c'))
or((T[i][m][n-1]='c')and(T[i][m+1][n-1]='c'))
or((T[i][m-1][n]='c')and(T[i][m-1][n+1]='c'))
or((T[i][m][n+1]='c')and(T[i][m+1][n+1]='c'))
or((T[i][m][n-1]='c')and(T[i][m+1][n]='c'))
or((T[i][m-1][n-1]='c')and(T[i][m-1][n]='c'))
or((T[i][m+1][n-1]='c')and(T[i][m+1][n]='c'))
or((T[i][m-1][n+1]='c')and(T[i][m][n+1]='c'))
or((T[i][m-1][n]='c')and(T[i][m][n-1]='c'))
or((T[i][m+1][n]='c')and(T[i][m]+1[n+1]='c'))
or((T[i][m-1][n]='c')and(T[i][m][n+1]='c'))
or((T[i][m-1][n-1]='c')and(T[i][m][n-1]='c')))
{
g++;
if ((m==3)and(n==4))
{
i++;m=1;n=1;
if ((e>0)and(f>0)and(g>0)and(h>0)) counter=couter
+1;
}
else if (n==4) {m++;n=1}
else n++;
}
else {h++;//着色d只有一个格子，必定符合要求，无需判断
if ((m==3)and(n==4))
{
i++;m=1;n=1;
if ((e>0)and(f>0)and(g>0)and(h>0)) counter=cout
er+1;
}
else if (n==4) {m++;n=1}
else n++;}
}
}
}
}
return(counter)//返回题解
}
//以上程序在Visual Studio.NET环境中调试通过，结果为6。
【 在 Lerry ( 想不开·
撞
树) 的大作中提到: 】: 幸亏是拼接矩形,上次讨论的三角形的还没有什么可行的方案呢
────────────────────────────────────────
Lerry (想不开·撞树) 于 2002年07月20日14:11:16 星期六 说道:
这样考察所有的是否合适,还不如把你的那几个简单的图形拼起来快呢
────────────────────────────────────────
ssos (存在与虚无·了却尘缘) 于 2002年07月20日14:17:58 星期六 说道:
en,你没看到他们老师要求算法么
────────────────────────────────────────
samuel (孔雀翎) 于 2002年07月20日18:17:22 星期六 说道:
唯一的好处是一个通用的算法，可以稍加修改求解另一个相似的问题
最大的缺点是算法的时间复杂度还是嫌大了一点
────────────────────────────────────────
samuel (孔雀翎) 于 2002年07月20日18:18:30 星期六 说道:
是啊，那种相对简单的算法已经实现了
但是老师说：“根本就不对！”
不知道根据是什么，没办法，只好另起炉灶了。
────────────────────────────────────────
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：203.124毫秒