一、选择的题目
题目(1):最大连续子数组和(最大子段和)
问题: 给定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。
-- 引用自《百度百科》
这个题目可以参考< 这篇博客>
二、问题的分析
输入一组数据,个数为n个,首先定义sum代表最大字段和并且赋初值为0,用thissum来保存当前数列的和并赋初值0。对thissum和sum的值进行比较,当thissum的值大于sum,将thissum的值赋给sum,如果小于,则舍弃当前的数值返回继续进行。
注意的是:这个程序进行时最开始已经对sum赋初值为0,虽然thissum的值在求和的过程中可能为负,但由于编写的这个程序对thissum进行判断时,就已经包括对当所给的整数均为负数时定义子段和为0的这种情况,因为当thissum小于0时并没有将他的值赋给sum,所以当数列所给的整数均为负数时,sum的就是为0,所以最后不需要对sum的值进行对0的判断。
三、编程
代码清单
#include<iostream>
using namespace std;
int sum = 0;
int qiusum(int n, int a[])
{
for (int i = 0; i < n; i++)
{
int thissum = 0;
for (int j = i; j < n; j++)
{
thissum += a[j];
if (thissum > sum)
{
sum = thissum;
}
}
}
return sum;
}
int main()
{
int n, a[300];
int qiusum(int n, int a[]);
cout << "给定整数的个数:" << endl;
cin >> n;
cout << "输入数列" << endl;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout<<"序列子段和的最大值:"<<endl;
sum = qiusum(n, a);
cout << sum << endl;
system("pause");
return 0;
}
题中测试用例
程序代码链接:coding.net
四、程序的流程图
五、覆盖方法的比较与选择
(1)语句覆盖:使得程序中每个语句至少都能被执行一次。
(2)判定覆盖:使得程序中每个判定至少为T和F各一次。
(3)条件覆盖:使得判定中的每个条件获得各种可能的结果。
(4)判定/条件覆盖:同时满足判定覆盖和条件覆盖。
(5)条件组合覆盖:使得每个判定中条件的各种可能组合都至少出现一次。
我选择的是条件组合覆盖:
由流程图可知,组合覆盖为2种情况,分别是:
1、路径AC:thissum>sum。
2、路径BC:thisum<=sum。
测试用例:
样例1{-1,-3,-5,-7,-9,-11},样例2{8,-3,6,-7,10,16},二组测试用例。其中测试用例1是都为负数的情况,用来证明sum不需要判断是否小于0,实现当字段和为负数时,最大字段和为0的情况。
六、样例测试以及结果
2组测试用例同时进行测试,结果如下:
单元测试代码
#include "stdafx.h"
#include "CppUnitTest.h"
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
int sum = 0;
int qiusum(int n, int a[])
{
for (int i = 0; i < n; i++)
{
int thissum = 0;
for (int j = i; j < n; j++)
{
thissum += a[j];
if (thissum > sum)
{
sum = thissum;
}
}
}
return sum;
}
namespace UnitTest1
{
TEST_CLASS(UnitTest1)
{
public:
TEST_METHOD(TestMethod1)
{
// TODO: 在此输入测试代码
int a[6] = { -1,-3,-5,-7,-9,-11 };
int sum = qiusum(6, a);
Assert::AreEqual(0, sum);
}
TEST_METHOD(TestMethod2)
{
// TODO: 在此输入测试代码
int a[6] = { 8,-3,6,-7,10,16 };
int sum = qiusum(6, a);
Assert::AreEqual(30, sum);
}
};
}
单元测试代码链接:danyuanceshi
七、总结
这次作业我选择的是VS2017以及自带的测试工具,通过本次作业,自己又有了一些提高,又学会了一种软件的应用。虽然过程有些困难,但是结果还是挺令人开心的。