• 软件测试技术
  • 软件测试视频
  • 开源软件测试技术
  • 软件测试沙龙
  • 软件测试资料下载
  • 软件测试杂志
  • 软件测试人才招聘

字号: | 推荐给好友 上一篇 | 下一篇

如何使用组合改进软件测试用例的生成

发布: 2009-3-04 09:37 | 作者: 不详 | 来源: 领测软件测试网采编 | 查看: 2次 | 进入软件测试论坛讨论

领测软件测试网

:hyn A |1pQ y下面的输出将显示在屏幕上:
Combination c(5,3) is initially { 0 1 2 }软件测试技术门户nwOc?f6g
当组合类的构造函数进行如下调用时:
Combination c = new Combination(5,3);软件测试技术门户)R0q1`~3~
J*Xx}

F `7V.L?L:M/h  我在内存中获得一个对象,它表示五个条目中一次取三个的最初的词典排序的数学组合元素。内存中的对象可以被表示为如 Figure 4 所示。软件测试技术门户Ol(HbA
软件测试技术门户~O9{6Ac jx

7f2?&_B.`gyz.I
Pl']i} @Figure 4 内存中的对象

6m1v/N-A%D ] 软件测试技术门户@6A5o(B@ F}

  构造函数代码创建最初的组合元素时是相当简单的。两个代表条目总数和子集大小的参数被分别存储在数据成员 n 和 k 中。因为我处理的数值可能会很大, 所以我决定使用 C# 的 long 类型代替int 类型。如果我愿意的话,我可以用 ulong 类型(无符号 long)获得双倍的数值范围。我用子集的大小 k 来为一个 long 类型的命名数组分配空间,然后用 0 到 k-1 范围的整数填充每个数据单元。软件测试技术门户 \X,B[K4Gs^_

软件测试技术门户 jY N!IpRb

软件测试技术门户 qj*c oz

软件测试技术门户WR8ad4z*H2i2E;J C6?

计算组合元素的个数
5BHw7h.v3H'p*MQ
Qb"S*U'^  现在我已经确定了如何创建一个组合对象,让我们看看组合的三个基本操作的第二个——根据某个给定的条目总数 n 及子集大小 k 来计算组合元素的总数。举个例子,如果你处理一次从 n=5 条目中取 k=3,这里有10种可能的组合元素:软件测试技术门户9n!ikJ ~+Z.F QC p

        { 0, 1, 2 } { 0, 3, 4 }软件测试技术门户	B"F$`\_	Z_
{ 0, 1, 3 } { 1, 2, 3 }
;Rp&\b ~ zV { 0, 1, 4 } { 1, 2, 4 }软件测试技术门户e h6^p ?
{ 0, 2, 3 } { 1, 3, 4 }
fzY%?y0P!o { 0, 2, 4 } { 2, 3, 4 }

:kuR0w&y

A(`l'Q Df1En

'kelW0O-\*q*a  我想实现一个 Choose(n,k) 函数,它返回组合元素的个数;Choose(5,3) 返回10。查找现有的Choose 实现,我惊讶地发现 Internet 上的大多数算法都很不耐用。在我向你展示我的 Choose 实现之前,让我们简要地审视一下 Choose 函数的标准实现。
%\ yE;fK*`  编写 Choose(n,k) 函数的标准方法是直接使用其定义公式。这是一个明显的但是拙劣解决方案。这里是一个用 C# 编码的典型 Choose(n,k) 函数 :软件测试技术门户n;Z%nv-x%^CP

// poor implementation of Choose(n,k)static int Choose(int n, int k){  int numerator = Factorial(n);  int denominator = Factorial(k) * Factorial(n-k);  return ( numerator / denominator );}      
辅助函数 Factorial 的实现如下:
static int Factorial(int m){  int ans = 1;  for (int i = m; i >= 1; —i)  {    ans = ans * i;  }  return ans;}        
软件测试技术门户f(H5U kXL WO [

  这里的 Choose(n,k) 实现有几个问题:最严重的是它会因为当 n 和 k 的值十分小时而溢出。注意这个 Choose(n,k) 首先计算 Factorial(n), 即便 n 是一个很小的值,它也会迅速增大到一个非常大的数 ( 比如,21! 将溢出一个无符号的 64 位数)。其次 Choose(n,k) 的值由两个阶乘的乘积 来除,这也可能成为一个非常大的数,得出的结果可能非常小。关键是即使 Choose(n,k) 返回的结果很小,中间计算结果很容易溢出。软件测试技术门户V,QKJ+P4alMmH:]
  一个更好的 Choose(n,k) 实现使用一个不同的方法计算其答案。改版的 Choose(n,k) 使用以下不同的公式来计算:软件测试技术门户e OdPufZK

        Choose(n,k) = (n * (n-1) * (n-2) * ... * (n-k+1)) / ( 1 * 2 * ... * k) 
这个算法看起来很丑,但用一个例子来说明就知道,它更容易理解:
        Choose(7,3) = (7 * 6 * 5) / (1 * 2 * 3)软件测试技术门户@4N-]"u`&R{

D"k |+paT
软件测试技术门户[v3G Rd3y9G-`Ct

  这个算法取代了原来计算分子(一个大数),然后计算分母(一个大数),然后相除,你可以计算部分乘积法并随意进行除法运算。对于 Choose(7,3) 例子,你 先计算 7 * 6 并除以 2,得到 21(译注:原文为“getting 24”显然不对,7 * 6/2=21)(跳过此分数下面部分的第1项,因为被1除是没有作用的)。这时用5乘以部分乘积并用3除,你可以得到答案35, 和前面的结果一样。软件测试技术门户3i|[zf
   这里对 Choose(n,k) 的第二次优化是由以下特性产生的:软件测试技术门户3o9bi[O6kw

        Choose(n,k) = Choose(n, n-k).
:}aT/kq8ee{
  举个例子,Choose(10,8) = Choose(10,2)。这不是一个明显的关系,但是如果你用一些例子来试验的话,你将看到为什么这是对的。直接计算 Choose(10,8) 之间涉及到计算七个部分乘积和七个除法,但是计算等价的 Choose(10,2) 只要求一个乘法和一个除法操作。软件测试技术门户3i+Ii