GUI、模块化与结对编程(homework-03)

摘要:

  在本次作业博客里,我将主要阐述作业3的收获。作业3表面是将之前的程序转换为图形界面(之前程序见http://www.cnblogs.com/shone/p/3348372.html),然而本质是:

1. 熟悉模块化、重构、重写

2. 体验结对编程。

  作业以上一次的优秀代码为基础,我们首先敲定了/h, /v, /h /v, /a几个模块的算法,然后进行模块化,成为独立的.dll文件,最后使用PYQT写UI并调用前述dll文件,实现原始需求。博客中老师要求提到的内容,以加粗表示。

GUI、模块化与结对编程(homework-03)

上图为我们的成果,并以此作为测试通过的象征,其他功能已经通过测试,不在此赘述。

1. 算法相关

  算法部分:http://www.cnblogs.com/shone/p/3348372.html 这篇博客里,我不断地使用归结法,解决了 /h, /v, /h /v问题,但是在/a中败下阵来,苦思冥想而不得解。在本期结对编程中,我请教了大神熊英夫,在他老人家的点化下,我们为 /a 问题找到了一个相对满意的算法:
  SAA退火算法。退火算法用来提供近似最优解:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。下面代码中,MaxS表示当前状态下选择的最优化状态,RanS表示一个随意拓展的状态:

  void SAA(int v,float T,float r,float Tmin)
{
int i,max,maxS=,ranS,tmp,SMR,sum,ri,j;//State
struct link * p;
srand(time());
sum=value[v];
for(i=;i<;i++){visited[i]=;available[i]=;}
topq=;p=g[v];visited[v]=;
while (p!=NULL)
{
if (!visited[p->t]){available[p->t]=;}
p=p->next;
}
while()
{
max=-;
ri=;
for (i=;i<num;i++)
{
if (visited[i]) {continue;}
if (available[i])
{
tmp=estimate(i);
if (tmp>max)
{
max=tmp;
maxS=i;
}
ri++;
}
}
if (ri==) {break;}
ranS=rand()%ri+;
for (i=;i<num;i++)
{
if (available[i]&&!visited[i])
{
ranS--;
if (ranS==)
{
ranS=i;
break;
}
}
}
if (visited[ranS]||!available[ranS]) {return ;}
SMR=;
tmp=estimate(maxS);
if (sum+tmp>totalmax) {totalmax=sum+tmp;pseudoexpand(maxS);}
if (tmp>){SMR=;}
else
{
if (exp(tmp/T)>(rand()%)/10000.0){SMR=;}
}
T*=r;
tmp=SMR==?estimate(maxS)-estimate(ranS):estimate(ranS);
if (sum+estimate(ranS)>totalmax) {totalmax=sum+estimate(ranS);pseudoexpand(ranS);}
if (exp(tmp/T)>(rand()%)/10000.0){SMR=;}
T*=r;
switch(SMR)
{
case :sum+=expand(maxS);break;
case :sum+=expand(ranS);break;
}
if (T<Tmin){break;}
if (sum>totalmax) {totalmax=sum;printf("%d\n",totalmax);for (j=;j<;j++){chosen[j]=visited[j];}}
}
}

  上面的代码使用了5次相同的退火过程,每个过程1000*点数V次初始温度。退火算法并不能保证是最优解。下面的patch()函数从较优解提升为最优解。patch()函数将正值的点打包,得到局部不可扩充最优解,代码:

  void patch()
{
int i,j,sum,yes;
struct link * p,*q;
while()
{
yes = ;
for (i=;i<num;i++)
{
if (value[i]>&&!chosen[i])
{
for (j=;j<;j++) {visited[j]=;}
q = DFS(i);
p = q;
if (p==NULL)
{
continue;
}
sum = p->s;
if (sum>=)
{
yes = ;
while (q!=NULL)
{
chosen[q->t] = ;
q = q->next;
}
}
}
}
if (yes==) {break;}
}
} struct link * DFS(int v)
{
struct link * p;
struct link * q;
struct link * tmp;
int result=-;
p = g[v];
visited[v] = ;
q = (struct link *)malloc(sizeof(struct link));
q->next = NULL;q->s = value[v];q->t = v;
while (p!=NULL)
{
//printf("%d %d %d\n",p->t,visited[p->t],chosen[p->t]);
if (chosen[p->t])
{
visited[v] = ;
q->next = NULL;q->s = value[v];q->t = v;
return q;
}
if (visited[p->t]||value[p->t]>)
{
p=p->next;
continue;
}
if (value[p->t]<&&!chosen[p->t])
{
tmp = DFS(p->t);
if (tmp!=NULL&&result<tmp->s+value[v])
{
result = tmp->s+value[v];
q->next = tmp;
q->s=tmp->s+value[v];
}
}
p = p->next;
}
visited[v] = ;
if (q->next!=NULL) return q;
return NULL;
}

  当patch()可用,我们可以直接得到状态MaxS和RanS。patch()无用时,最优解已经可以在退火过程被选取。又因为/v, /h只是图形对称的问题,到此与/a有关的问题便得到解决。

2. 模块化与重构

  模块化的意义:我们希望将作业2实现的代码独立出来。模块化能够使得之前的命令行与现在的GUI使用同一份代码,这将提高代码的重用性,提高程序开发的效率,让我们少写一点代码,多一点时间打游戏。同时,专事专做,正确率高,在一定程度上也保障了相关代码的安全。

  模块化的方式:代码模块化,可以使用class library,dll等方式。这里面,我们选择后者。

我的代码变化在哪里呢?

  主要是两方面:

1. 补充\a的算法(见前文)

2. 补充图形用户界面。因为我们的代码都是正确的,考虑到一致性的需要,当我们坐在一起编程时,便选择一人的代码为基础,共同进行改进。总体上来说,各个模块化的函数按需进行重构,涉及到文件读取、控制的代码需要重写,并与GUI结合。

3. 增加对动态链接库的调用。

重构与重写:

    这里面,原始的命令行代码分为被调用函数和main函数两部分。前者是模块化的函数,处理\a, \h等等情况,是可共用部分,进行重构,导出到dll中。而main中进行文件读取、对调用函数进行调用的与控制流程相关的代码,则需要根据GUI重写。这里面使用python实现。

3. 我使用的代码规范

  我(们)再编程中特意注意了代码规范,尽力写出可读性强、风格良好的代码。代码风格是内在问题,变化最大的是代码外观:排版与格式。

  第一方面,我全面阅读了《C语言代码规范》和老师给的博客,并按照其处理缩进、下划线,/类/函数名都用Pascal形式,所有的变量都用Camel形式。

  第二方面,由于使用Visual Assist插件,基本的代码缩进、字体、颜色等方面已经可以自动保证。
  

  近期学习到的是老师的博客,在这篇博客中,说明{}各占一行是一个更加清晰的方法,而且不论是VS还是VA插件都默认如此。我之前的习惯是{不独立占行,而}独立占行。我之前认为这样能保证代码的简洁明了。但是博客中提出了“ }else{”这样的例子,这样就不再清晰,因此,我优化了{}的使用。

  另外,注释是我忽略的地方,我明确了了什么是有用的注释,以及注释恰当的位置。

4. 结对编程

  我们实践了结对编程,结对编程中队员可以不断地彼此提醒、鼓励并进行代码复查,提高代码正确性和编程效率,从开发层次、心理感受、管理上都是很好的方法。

  我最开始的小伙伴叫熊英夫,男,我航计院人氏。后来在助教大人的允许下,我们收留了因同伴退课而无家可归的小伙伴柴泽华。柴泽华,男,我航计院人氏,人称柴哥。

  我的小伙伴们十分优秀。

优点:

熊英夫是编程的大牛,除了小地方由我们提示外,熊英夫对于算法和Python都是我们中最出色的。除此之外,他还很谦虚,很接受我们的建议,丝毫不因为技术水平高而拒绝交流。最后,他很肯干,写了大比例的代码。

柴哥是个比较搞笑的人,这算一个优点吧。除此之外,他经常提醒我们的进度,并且经常和我交流博客的写法问题。

小伙伴们需要改进的地方:

我们不得不承认谁都有可以改进的地方。首先,我们三人的编程水平都是可以增强的,尤其是\a问题上也是费了很大劲才得到结论。其次,我们对于代码重构的知识了解甚少,做得时候并不十分专业和流畅。第三,我们都有拖延症,不到deadline不提交...

整个过程中,我从小伙伴们学到的最大的收获是退火算法,当然我也发挥了我的价值,比如使用两种语言分别处理算法部分和UI部分。

你的设计是如何保证 不同的 maxsum.exe 命令行最后在一个GUI 的界面显示的? (C++ 的设计模式中有 singleton 的概念, 说明一个类的实例如何在一个进程中保持单例, 我们这里谈的是软件如何在操作系统中保持 singleton)

这样的功能,可以通过建立管道来实现,程序端监听,命令行向程序发送消息,若程序无标签,则新建并显示;若已经有标签,则在其右侧显示出一个标签出来。

但是我们在学习导出dll,调用dll,以及退火算法上耗费了大量的时间,上述的思想已经不再有时间实现..于是我们直接显示了file1和file2两个标签,抛弃命令行,直接在GUI编辑和运行。这里的实现方式是:在UI部分相对简单的前提下(运行效率要求不高),使用PYQT,先使用ERIC4提供的QTdesigner绘制框架再通过ERIC4向python编译,再用自己写的窗口类继承setui。

5.表格

Personal Software Process Stages

时间百分比(%)

实际花费的时间 (分钟)

原来估计的时间 (分钟)

Planning

计划

·         Estimate

·         估计这个任务需要多少时间,把工作细化并大致排序

100

30

30

Development

开发

80

·         Analysis

·         需求分析 (包括学习新技术)

200

120

60

·         Design Spec

·         生成设计文档

0

0

·         Design Review

·         设计复审 (和同事审核设计文档)

同时进行

·         Coding Standard

·         代码规范 (制定合适的规范)

同时进行

·         Design

·         具体设计

·         Coding

·         具体编码

100

180

180

·         Code Review

·         代码复审

同时进行

·         Test

·         测试(自我测试,修改代码,提交修改)

100

30

30

Reporting

总结报告

·         Test Report

·         测试报告

·         Size Measurement

·         计算工作量

100

20

20

·         Postmortem & Improvement Plan

·         事后总结, 并提出改进

100

60

60

Total

总计

 

总用时 440

总估计的用时 500

上一篇:wangEditor——轻量化web富文本框


下一篇:CodeForces 505B Mr. Kitayuta's Colorful Graph