work2

回答问题:

描述在这么多相似的需求面前, 你怎么维护你的设计 (父类/子类/基类, UML, 设计模式,  或者其它方法) 让整个程序的架构不至于崩溃的?

答:诚然,问题给出了很多选项如-a,-v,-h。但我觉得其架构并不复杂,-v,-h以及它们的组合其实是基于普通的最大权矩阵问题的,因而我认为这三类可分在一起作为一个original.h文件,然后带有-a的单独分类。

给出你做单元测试/代码覆盖率的最终覆盖率的报告, 用截屏显示你的代码覆盖率

答:见GITHUB附件。

你在这个作业中学到了什么?  有什么好的设计值得分享?  感想如何 (太容易 / 太难 / 太无趣)?

答:学到了如何合理架构带有命令行参数的C程序,如何计算覆盖率。

问题分析

在一维情况下我们已经分析得到了基于长度n的O(n)时间复杂度的算法。那么我们可以先考虑在二维情况下是否可以得到基于长度n宽度m的O(m)时间复杂度的算法。如我在作业1里分析。设s[x][y]为以坐标(0,0)为,(x,y)为的点所形成的的矩形的加和。以(a,b)(x,y)构成的矩形的值为,(s[x][y] - s[a-1][y])-(s[x][b-1] - s[a-1][b-1]),不具备一维时的单调性,只能通过在此枚举一行。时间复杂度为O(m*n*n),无法达到最好的O(m*n)。

也就是说对于普通的问题,我们只需要枚举2行的组合即先枚举i再枚举小于等于i的j,加和j-i的区间,1维处理就可以了。

而对于-v的垂直相连参数,是很容易转化为普通问题的,普通问题中只考虑j-i的区间,而这里再考虑下i-n与0-j的区间就可以了,时间复杂度也为O(m*n*n)。

而对于-h的水平相连参数,我们可以从转化出的一维问题中考虑。对于1维情况下如果收尾相连应该如何处理。一开始我考虑的是一遍贴在右边,但其实实现起来限制过于复杂。如果选择了超越经线0的矩形其实就是踢掉了中间的一块矩形,于是只需要找到最小的矩形,然后用正行的权减去它,与普通解想比较即可。

而对于-a参数,一开始由于我自己给它定义了宽度不超过16,我寻思可以用连通性状态压缩动态规划做,但由于之后改成了32,只能使用搜索加剪枝。经过并查集缩点之后(将正权点加合在一起作为一个点,并认为它的负权为0),其实相当于是求一个图的最大权联通子图。由于时间不够,-a参数的1我还没有完成,我的思路是这样的,先算出每个点两两之间距离,对于每个正点维护一棵以负权点到该正节点距离为重量以节点编号为编号的treap,在深度优先搜素的状态空间中,当前状态已经选好的点在每颗treap中,然后对于接下来考虑的点,先比较是否能刷新其中的任意一个treap,如果不能刷新代表本质上无法得到更优解,否则入堆,计算此时加上最小距离点之外所有权值和是否能达到已经算出的较优不行则剪枝。

original.h

#ifndef ORIGINAL_H_INCLUDED

#define ORIGINAL_H_INCLUDED

int maxsumline(int *p,int size)

{

    int i;

    int sum,ans;

    sum=0;

    ans=-1;

    for(i=0;i<size;i++)

    {

        if(sum<0)

            sum=0;

        sum+=p[i];

        if(ans<sum)

            ans=sum;

    }

    return ans;

}

int maxsumcycle(int *p,int size)

{

    int i;

    int sum,ans;

    sum=0;

    ans=maxsumline(p,size);

    for (i=0;i<size;i++)

    {

        sum+=p[i];

        p[i] = -p[i];

    }

    if ((sum+maxsumline(p,size))>ans)

    {

        return (sum+maxsumline(p,size));

    }

    else return ans;

}

int maxsumblock(int a[],int n,int m,int cycle,int expand)

{

    int i,j,k,tmp,totalmax=0,start;

    int sum[32][32];

    int t[32];

    for (i=0;i<n;i++)

    {

        for (j=0;j<m;j++)

        {

            if (i!=0)

            {

                sum[i][j]=sum[i-1][j]+a[i*m+j];

            }

            else

            {

                sum[i][j]=a[i*m+j];

            }

        }

    }

    for (i=0;i<n;i++)

    {

        for (j=0;j<=i;j++)

        {

            for (k=0;k<m;k++)

            {

                t[k] = (j==0)?0:-sum[j-1][k];

                t[k] +=sum[i][k];

            }

            tmp = cycle?maxsumcycle(t,m):maxsumline(t,m);

            if (tmp>totalmax)

            {

                totalmax= tmp;

            }

            if (expand)

            {

                for (k=0;k<m;k++)

                {

                    t[k]=sum[n-1][k]-sum[i][k]+sum[j][k];

                   // printf("%d ",t[k]);

                }

                //printf("\n");

                tmp = cycle?maxsumcycle(t,m):maxsumline(t,m);

                if (tmp>totalmax)

                {

                    totalmax= tmp;

                }

            }

        }

    }

    return totalmax;

}

#endif // ORIGINAL_H_INCLUDED

main.c:

#include "original.h"

#include <stdio.h>

int m,n,a[1024];

void init(int p)

{

    int i,j;

    FILE * fin;

    char t[10];

    t[0]=p+48;

    t[1]=0;

    strcat(t,"input.txt");

    fin = fopen(t,"r");

    fscanf(fin,"%d%d",&n,&m);

    for (i=0;i<n;i++)

    {

        for (j=0;j<m;j++)

        {

            fscanf(fin,"%d",&a[i*m+j]);

        }

    }

}

int main(int argc,char * argv[])

{

    int i,p,j,cycle=0,expand=0,amorphous=0;

    for (i=1;i<argc;i++)

    {

        printf("%s\n",argv[i]);

        if (argv[i][1]=='v')

        {

            expand=1;

        }

        if (argv[i][1]=='h')

        {

            cycle=1;

        }

        if (argv[i][1]='a')

        {

            amorphous=1;

        }

    }

    printf("%d\n",expand);

    for (p=0;p<10;p++)

    {

 

        init(p);

        printf("%d\n",maxsumblock(a,n,m,cycle,expand));

    }

    return 0;

}

test.c:

#include <stdio.h>

#include <string.h>

int main()

{

    FILE * fout;

    char s[10];

    int i,j,k,t=21318,m=233;

    for (i=0;i<10;i++)

    {

        sprintf(s,"%d",i);

        strcat(s,"input.txt");

        printf("%s",s);

        fout=fopen(s,"w");

        fprintf(fout,"32 32\n");

        for (j=0;j<32;j++)

        {

            for (k=0;k<32;k++)

            {

                m=(m*m)%t;

                if (m%10<5)

                {

                    fprintf(fout,"-");

                }

                fprintf(fout,"%d ",m);

            }

            fprintf(fout,"\n");

        }

 

    }

}

#ifndef TREAP_H_INCLUDED
#define TREAP_H_INCLUDED
typedef struct Node {
int data;
long k;
struct Node *left,*right,*parent;
} NODE ;
typedef struct {
NODE *head;
} BST;
NODE * Search(NODE *root, int x)
{
while (root && root->data!=x)
{
if (root->data>x)
root = root->left;
else
root = root->right;
}
return root;
}

void Insert(BST *t, int x ,int w)
{
NODE *node,*child,*parent,*root;
root = t->head;
node = root;
child = root;
while (node && child)
{
if (node->data==x)
child = NULL;
else
{
parent = node;
if (node->data>x)
node = node->left;
else
node = node->right;
}
}
if (child)
{
child = (NODE *)malloc(sizeof(NODE));
child->left = child->right = NULL;
child->k = w;
child->data = x;
child->parent = parent;
if (parent->data>x)
parent->left = child;
else
parent->right = child;
node = child;
while (node->parent->parent && node->k<node->parent->k)
{
parent = node->parent;
if (node->data<parent->data)
{
parent->left = node->right;
if (node->right)
{
parent->left->parent = parent;
}
node->right = parent;
if (parent->data<parent->parent->data)
parent->parent->left = node;
else
parent->parent->right = node;
}
else
{
parent->right = node->left;
if (node->left)
{
parent->right->parent = parent;
}
node->left = parent;
if (parent->data<parent->parent->data)
{
parent->parent->left = node;
}
else
{
parent->parent->right = node;
}
}
node->parent = parent->parent;
parent->parent = node;
}
if (node->parent==root && node->k<root->k)
{
if (node->data<root->data)
{
root->left = node->right;
if (node->right)
root->left->parent = root;
node->right = root;
}
else
{
root->right = node->left;
if (node->left)
root->right->parent = root;
node->left = root;
}
root->parent = node;
node->parent = NULL;
t->head = node;
}
}
return ;
}
void Delete(BST *t,int x)
{
NODE *node,*parent,*node1,*parent1,*root;
int temp;
root = t->head;
node = root;
while (node && node->data!=x)
{
parent = node;
if (node->data>x)
node = node->left;
else
node = node->right;
}
if (!node)
return;
if (node!=root)
{
node->k = 1;
while (node->left node->right)
{
if (node->left)
{
node1 = node->left;
node->left = node1->right;
if (node1->right)
node1->right->parent = node;
}
else
{
node1 = node->right;
node->right = node1->left;
if (node1->left)
node1->left->parent = node;
}
if (node->parent->data>node->data)
node->parent->left = node1;
else
node->parent->right = node1;
node1->parent = node->parent;
node->parent = node1;
}
if (node->data<node->parent->data)
node->parent->left = NULL;
else
node->parent->right = NULL;
free(node);
}
return ;
}
void Init(BST *t, int x ,int w)
{
t->head = (NODE *)malloc(sizeof(NODE));
t->head->left = t->head->right = NULL;
t->head->data = x;
t->head->k = w;
t->head->parent = NULL;
return ;
}
void dfs(NODE *root)
{
if (root)
{
dfs(root->left);
printf("%d ",root->data);
dfs(root->right);
}
return ;
}


#endif // TREAP_H_INCLUDED

更多相关文章
  • .NET基礎拾遺(5)多線程開發基礎
     Index :  (1)类型语法.内存管理和垃圾回收基础  (2)面向对象的实现和异常的处理基础  (3)字符串.集合与流  (4)委托.事件.反射与特性  (5)多线程开发基础  (6)ADO.NET与数据库开发基础  (7)WebService的开发与应用基础 一.多线程编程的基本概念 下面的
  • .NET基礎 (19)多線程
    多线程编程的基本概念1 请解释操作系统层面上的线程和进程2 多线程程序在操作系统里是并行执行的吗3 什么是纤程.NET中的多线程1 如何在.NET程序中手动控制多个线程2 如何使用.NET的线程池3 如何查看和设置线程池的上下文4 如何定义线程独享的全局数据5 如何使用异步模式读取一个文件6 如何阻
  •  随便瞎写,其实没做出多少题: Chef and Cake  题目大概是用输入的数生成 一个数组并且生成出q个[X,Y]的询问, 数组长度N<=1,q<=10^7; 开始用线段树,RMQ,分块能切过去,但是线段树RE
  • 前言 此文并不是说要完全放弃使用Thread.Sleep,而是要说明在符合哪些情况下使用! 场景 很多时候,我们会需要一个定时服务来处理业务. 但并不是死死的每隔N分钟执行一次那种,而是在一次处理完后,算好下一次处理的时间点. 当到达此时间点,触发程序重新开始执行代码.   普遍做法 普遍的情况下,
一周排行
  • Android 基于Message的進程間通信 Messenger完全解析
    一.概述 说到Android进程间通信,大家肯定能想到的是编写aidl文件,然后通过aap ...
  • XP下IIS无法解释ASP等动态页主要是由微软的一个BUG造成的.由于系统原因使IWAM帐号的密码错误,致使出现IIS500内部错误. IWAM 帐号简介: IWAM 账号是安装 IIS5 时系统自动建立的一个内置账
  • SWFUpload v2.5.0 Documentation SWFUpload 2.5.0版 官方说明文档 中文翻译版 Table of Contents 内容列表 详情请点击翻译:yukon12345 2010. ...
  • 2010.11.13项管论文关注点 对于使用<信息系统项目管理师考试考前冲刺预测卷及考点解析>的读者,在备考2010.11.13信息系统项目管理师考试之下午II论文考试时,以下一些论文试题及其写作思路值得 ...
  • Problem Description The so-called best problem solver can easily solve this problem, with his/her childhood ...
  • 自己写了一个py脚本用来备份mysql日志.手动可以正常执行,后来放到crontab中无法执行,无反应,也就是/var/logs/cron中有执行的记录,但没反应,该创建的日志也没创建.也就是没执行.网上查了半天也没
  • 今天在給一个朋友安装vcenter server的时候出现域控上解析完全限定域名问题.摸索了半天终于搞定了,原来需要在DNS 中为之添加一台反向查找的指向.解决辦法如下: 1:从"管理工具"中打开 ...
  • 之所以要在软件技术中用到动态连接库技术,目的是为了压缩软件成本,说通俗点,就是多个程序公用一个程序模块,从而减少代码的书写量,更可以起到使程序尽 可能占用最少资源的目的,有助于促进代码重用和内存的有效使用.此外他还有
  •          今天搜php socket,发现了一个给力的php写socket的框架workman,有机会要用用.          好给力,原来那个小蝌蚪聊天室就是用这个开发的.          仿佛发现了新
  • 16. (Fan-Hoffman) 设 $A\in M_n$, $A=UP$ 为极分解, $U$ 为酉矩阵, $P$ 为半正定矩阵. 若 $W\in M_n$ 为酉矩阵, 则 $$\bex \sen{A-U}\leq