|
Personal Software Process Stages |
时间百分比(%) |
实际花费的时间 (分钟) |
原来估计的时间 (分钟) |
|
计划 |
0 |
0 |
0 |
|
· 估计这个任务需要多少时间，把工作细化并大致排序 |
0 |
0 |
0 |
|
开发 |
|||
|
· 需求分析 (包括学习新技术) |
0 |
0 |
0 |
|
· 生成设计文档 |
0 |
0 |
0 |
|
· 设计复审 (和同事审核设计文档) |
0 |
0 |
0 |
|
· 代码规范 (制定合适的规范) |
0 |
0 |
0 |
|
· 具体设计 |
5 |
30min |
30min |
|
· 具体编码 |
60 |
3h |
4h |
|
· 代码复审 |
5 |
10min |
0 |
|
· 测试（自我测试，修改代码，提交修改） |
30 |
1h |
1h |
|
总结报告 |
|||
|
|||
|
|||
|
|||
|
总计 |
100% |
总用时 5H |
总估计的用时 6H |
总结：
感觉这次作业在算法方面难度过大，有点难以入手
对于第一个要求：每个单词仅出现一次。这个限制条件过于抽象，无法从这个角度去实现具体编码
我选择的是从【图形必须是正方形】出发
先将n的值设置位Max（WordLength）
然后在这个n*n的矩阵中以某种【特定的顺序】尝试填入所有单词
如果成功，则输出这个矩阵，else n++；
下面解释何为【特定的顺序】
首先从最具体的条件出发，即【每个角都必须有一个单词】
然后从【不能含有空行】这个条件出发，优先把四条边填满
然后将剩余的单词，填入这个矩阵中
具体做法是暴力枚举：即枚举矩阵中的每一个点，如果这个点可以放入某个单词，那么就将这个单词放入
最后将所有的空白，随机填入一个字母
此时检查【单词唯一性】问题，如果不满足，则改变单词的填入顺序
在进行测试
不得不说 这个算法思路实在是非常的烂
虽然能满足所有的限制条件
但是得到的矩阵可能非常大。。。。
因为对于【单词的交错相连】这个点
我暂时没有找到更好的方法去处理这个问题
所以得到的图可能是一个比较松散的图
这是一个测试数据的截图：
下面是用c写的源码：
（将测试数据复制入testdata文本中，将生成同目录下的一个wordoutput文本，用于显示结果）
#include <stdio.h>
#include<stdlib.h>
#include <string.h>
#define M 300 #define sinput "testdata.txt"
#define soutput "WordOutPut.txt"
FILE *file,*fileout; int used[M],i,j,k,x,maxl,l,y,n,u,t,an,ini[M],len[M],e,start,charused[M],ismin; char a[M][M],s[M],g[M][M],sum,c[M],dx[]={,,-,,-,,-,},dy[]={,,,-,-,,,-}; int ising(int x,int y)
{
return (x>=&&x<n&&y>=&&y<n);
} f(int dx,int dy,int x,int y,char* s)
{
int i;
for(i=;s[i];i++){
g[x][y]=s[i];
x+=dx;
y+=dy;
}
} int pd(int dx,int dy,int x,int y,char *s)
{
int i;
for(i=;s[i];i++){
if(!(g[x][y]==s[i]||!g[x][y])||!ising(x,y)) return ;
x+=dx;
y+=dy;
}
return ; } main()
{
file=fopen(sinput,"r");
fileout=fopen(soutput,"w"); while(fscanf(file,"%s",s)>){
t=strlen(s);
len[an]=t;
sum+=t; if(maxl<t) maxl=t; ini[s[]]++; strcpy(a[an++],s);
} for(i=;i<an;i++)
for(j=i+;j<an;j++) if(len[i]<len[j]){
strcpy(s,a[i]);
strcpy(a[i],a[j]);
strcpy(a[j],s);
t=len[i];
len[i]=len[j];
len[j]=t;
} x=;
u=; while(){
for(i='a';i<='z';i++) if(ini[i]>=u&&!charused[i]){
c[x++]=i;
charused[i]=;
} if(x<) u--;
else break;
} n=maxl; while(){ for(i=;i<n;i++)
for(j=;j<n;j++) g[i][j]=;
for(i=;i<an;i++) used[i]=; for(i=;i<;i++){
x=y=;
if(i==) y=n-;
else if(i==) x=n-;
else if(i==){
x=n-;
y=n-;
} j=i;
for(k=;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])&&a[k][]==c[i]){
used[k]=;
f(dx[j],dy[j],x,y,a[k]);
break;
}
} ///four courner
for(i=;i<;i++){
x=y=;
if(i==) y=n-;
else if(i==) x=n-;
else if(i==){
x=n-;
y=n-;
} for(j=;j<;j++)
for(k=;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])&&a[k][]==c[i]){
used[k]=;
f(dx[j],dy[j],x,y,a[k]);
break;
}
} /* //zhongjian x=0;
y=0;
for(i=0;i<n;i++){ x++;
y++; for(j=4;j<6;j++)
for(k=0;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])){
used[k]=1;
used[k]=1;
f(dx[j],dy[j],x,y,a[k]);
break;
}
}
*/ //sibian x=y=;
for(i=;i<n;i++){ y++; j=;
for(k=;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])){
used[k]=;
used[k]=;
f(dx[j],dy[j],x,y,a[k]);
break;
}
} x=;
y=n-;
for(i=;i<n;i++){ x++; j=;
for(k=;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])){
used[k]=;
used[k]=;
f(dx[j],dy[j],x,y,a[k]);
break;
}
} x=n-;
y=n-;
for(i=;i<n;i++){
y--; j=;
for(k=;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])){
used[k]=;
used[k]=;
f(dx[j],dy[j],x,y,a[k]);
break;
}
} x=n-;
y=;
for(i=;i<n;i++){ x--; j=;
for(k=;k<an;k++) if(!used[k]&&pd(dx[j],dy[j],x,y,a[k])){
used[k]=;
used[k]=;
f(dx[j],dy[j],x,y,a[k]);
break;
}
} for(i=;i<n;i++)
for(j=;j<n;j++)
for(l=;l>=;l--)
for(k=;k<an;k++) if(!used[k]&&pd(dx[l],dy[l],i,j,a[k])){
used[k]=;
f(dx[l],dy[l],i,j,a[k]);
break;
} ismin=; for(i=;i<an;i++) if(!used[i])
ismin=; if(ismin) n++; else{
srand();
for(i=;i<n;i++){
for(j=;j<n;j++) if(g[i][j]) fprintf(fileout,"%c",g[i][j]); else fprintf(fileout,"%c",rand()%+'a');
fputs("\n",fileout);
}
return ;
} }
}