软件工程第3次作业——Visual Studio 2017下针对代码覆盖率的C/C++单元测试
本项目Github地址(同时包括两个作业项目):
Assignment03 -- https://github.com/Oberon-Zheng/SoftwareEngineeringAssignments
st=>start: Start
e=>end: End
cond=>condition: Option
op1=>operation: solution_1
op2=>operation: solution_2
st->cond
cond(yes)->op1->e
cond(no)->op2->e
测试案例
A - 最大子列和(Sum of the maximum subarray)问题
问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时,最大子段和为20。
- Baidu Baike
关于我个人对于此问题的算法考虑我将另起一个博文(会吾倚马万言,易此帜以外链)发布,这里直接使用Kadane算法(使用Python完成的一个子程序,这里改写为C++的)加以实现,关于这个算法的具体实现细节将同样在那篇博客连同我自己的想法一同发布,这里先给出这个程序的流程图(根据mermaid语法绘出):
I'll be your mermaid, caught on your rod
- Memorized Mermaid
- Scott Skott
注意,由于cnblogs的mermaid组件需要经过google的code analytics服务器,因此在转换为正确的流程图之前需要花费一段时间
So, stay tuned, plz!
我有雅各布的天梯,我天下无敌,我藐视银河系
ESO黑洞警告
start(开始)-->inputarry>"传入arry"]
inputarry-->domakeres["(rb:RangeBlock):={sum:=0,start:=-1,end:=-1}"]
domakeres-->tryempty{"arry.size()=0?"}
tryempty-->|true|return>"返回rb"]
return-->e("结束")
tryempty-->|false|init["maxsum=0<br />sum=0<br />kickoff=0<br />i=0"]
init-->tryloop{"i>arry.size()"}
tryloop-->|true|accumulate["sum:=arry<br />若sum<0则sum:=0"]
accumulate-->max["maxsum:=max{sum,maxsum}"]
max-->tryneg{"arry[i]是负的同时arry[i]的绝对值大于原来sum<br />(sum=0且arry[i]<0)"}
tryneg-->|true|rststart["kickoff:=i+1"]
tryneg-->|false|inhale["rb.start:=kickoff<br />rb.end:=i"]
sendmax["rb.sum:=maxsum"]
inhale-->sendmax
rststart-->sendmax
sendmax-->return
上述程序能够求得关于传入序列arry
的一个最大子列和(下文简称最大和),并且能够得到这个最大子列在arry中的位置。
案例实现
本案例以C++语言加以实现,代码如下:
///File : MaxSubarray.h
#pragma once
#include <vector>
using namespace std;
struct RangeBlock
{
int sum;
int start;
int end;
};
/// File : MaxSubarray.c
#include "MaxSubarray.h"
#define POSCLIP(X) (X>0)?X:0
#define MAX(X,Y) (X>Y)?X:Y
using namespace std;
RangeBlock MaxSubArray(vector<int> arry)
{
RangeBlock rb = { 0,-1,-1 };
if (arry.size() == 0)
{
return rb;
}
int maxsum = 0;
int sum = 0;
int kickoff = 0;
for (int i = 0; i < arry.size(); i++)
{
sum = POSCLIP(sum + arry[i]);
maxsum = MAX(sum, maxsum);
if (sum == 0 && arry[i] < 0)
{
kickoff = i + 1;
//rb.end = rb.start;
}
else if(sum == maxsum)
{
rb.start = kickoff;
rb.end = i;
}
}
rb.sum = maxsum;
return rb;
}
这个程序传入一个标准库vector<int>
容器作为输入(之所以使用vector
是因为vector
的长度可变),然后通过一个RangeBlock
型对象返回最大子列的和与区间。
根据上面的流程图,这里面存在一个长度不定的循环,并且在循环内仍然有一个分支,因此这里面想要对循环内的所有可能情况做出测试是不可能的,因此for
内的测试仅对若干种条件组合(每个数据会分别将覆盖内部的三个分支)。
单元测试
本单元测试将满足判定-条件覆盖(所有的判定都走一次,所有的条件分两个分支都满足一次)
归纳上述代码可以得到如下的条件判定列表:
arry.size()==0 <---> arry.size()!=0 --[1]
i < arry.size() <---> i >= arry.size() --[2]
sum==0 <--->sum!=0 --[3]
arry[i]<0 <---> arry[i] >=0 --[4]
sum == maxsum <---> sum != maxsum --[5]
根据代码的执行情况来看,其中[3]和[4]存在条件组合,实际上当[3]的左命题成立时,[4]的右命题一定不成立,同时若[2]右、[3]右、[4]左成立则[5]左一定不成立(arry[i]<0,maxsum>=sum ==>> sum+arry[i]<maxsum
),而[2]的命题在执行一句for循环的时候总会有成立和不成立(维持循环和跳出循环),对于上述推断为一定不成立的关系下,无法找出具体的测试用例(因为是逻辑关系制约的不可能发生,比如我无法找到sum==0 && arry[i]>0
的测试数据,因为根本写不出来,除非遭到某种硬件错误导致arry[i]
或者sum
发生翻转,但这不是单元测试能够解决的),对于for的测试主要聚焦于OBOE问题(一步之差),而当[1]的前命题成立时,实际上之后的条件实际上都走不到,但如果必要考虑后面的条件的话,实际上只能讨论i>=arry.size()
,for循环实际上也执行不了,因此我们归纳出如下的条件组合:
arry.size() == 0 --[S1]
arry.size() != 0 && sum == 0 && arry[i]<0 && sum == maxsum --[S2]
arry.size() != 0 && sum == 0 && arry[i]<0 && sum != maxsum --[S3]
array.size() != 0 && sum != 0 && arry[i] < 0 && sum != maxsum --[S4]
array.size() != 0 && sum != 0 && arry[i] >= 0 && sum == maxsum --[S5]
array.size() != 0 && sum != 0 && arry[i] >= 0 && sum != maxsum --[S6]
单元测试将围绕[S1]到[S6]产生测试数据如下:
S1 | S2 | S3 | S4 | S5 | S6 |
---|---|---|---|---|---|
空数组 | 全负数组 | 第一个负数 | 有正数的时候加入负数 | 加入非负数(开始) | 加入非负数(继续加入) |
根据上述归纳,编订了如下的测试数据:
#include "stdafx.h"
#include "CppUnitTest.h"
#include "..\Assignment03\MaxSubarray.h"
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace UnitTestA03
{
TEST_CLASS(UnitTest1)
{
public:
TEST_METHOD(TestEmpty) //S1
{
std::vector<int> a;
RangeBlock rb = MaxSubArray(a);
Assert::AreEqual(rb.sum, 0);
Assert::AreEqual(rb.start, -1);
Assert::AreEqual(rb.end, -1);
}
TEST_METHOD(TestAllNegative) //S2
{
std::vector<int> a = { -1,-5,-8,-10,-6,-40,-1630,-5 };
RangeBlock rb = MaxSubArray(a);
Assert::AreEqual(rb.sum, 0);
Assert::AreEqual(rb.start, -1);
Assert::AreEqual(rb.end, -1);
}
TEST_METHOD(TestAllZero) //S4
{
std::vector<int> a(10, 0);
RangeBlock rb = MaxSubArray(a);
Assert::AreEqual(rb.sum, 0);
Assert::AreEqual(rb.start, 0);
Assert::AreEqual(rb.end, 9);
}
TEST_METHOD(TestOscillating) // S3和S5
{
std::vector<int> a = {0, 1,-2,3,-4,5,-6,7 };
RangeBlock rb = MaxSubArray(a);
Assert::AreEqual(rb.sum, 7);
Assert::AreEqual(rb.start, 7);
Assert::AreEqual(rb.end, 7);
}
TEST_METHOD(TestInhaling) // S4和S5
{
std::vector<int> a = {1, 3,-2,-3,0,0,-6,-10 };
RangeBlock rb = MaxSubArray(a);
Assert::AreEqual(rb.sum, 4);
Assert::AreEqual(rb.start, 0);
Assert::AreEqual(rb.end, 1);
}
TEST_METHOD(TestNormal) //综合测试
{
std::vector<int> a = { 1,3,2,-4,0,5,8,-1,-10 };
RangeBlock rb = MaxSubArray(a);
Assert::AreEqual(rb.sum, 15);
Assert::AreEqual(rb.start, 0);
Assert::AreEqual(rb.end, 6);
}
};
}
最终各测试均通过:
Kadane算法在\(\omicron(n+k)\)的复杂度下得到了正确的结果。
B - 阶梯营业税问题
下表为某商场每日营业额与应收税率的对照表,请编写一小程序根据该商场每日营业额计算其实际应缴纳税费。
营业额X/¥|税率
:---最新文章
- R中list对象属性以及具有list性质的对象
- Kingdom of Obsession---hdu5943(二分匹配)
- [数据库]SQL Server 用户NT AUTHORITY\IUSR 登录失败
- 伸展树(三)之 Java的实现
- httpModules与httpHandlers之httpModules(转载)
- github里的gist是什么意思
- CSS概述<;选择器总结>;
- hi,mongo!(1)
- 转:LayoutInflater作用及使用
- SSL与TLS的区别以及介绍(转)
- jquery考试纠错笔记.
- Qt+VS2015应用程序发布
- Django权限机制的实现
- 2017-06-20 (pwd ls cd)
- myeclipse使用步骤总结
- 字符串之StringBuffer 与 StringBuilder的对比
- Linux交换空间(swap space)
- Oracle多关键字模糊查询
- 给div加滚动条
- [label][JavaScript][The Defined Guide of JavaScript] 如何声明变量
热门文章