数据结构、算法与应用——C++语言描述 课后习题答案

发布于 2021-02-06  15 次阅读



   此页面的内容及资料需要长期更新,现存页面中资料未必是最新。  ==>  展开 / 收缩

Chapter 1

Exercise 1

The function swap fails to swap the values of the actual parameters because x and y are value parameters. The invocation swap(a, b) results in the values of the actual parameters a and b being copied into the formal parameters x and y, respectively. Then, within the body of swap, the values of x and y are interchanged, and the function terminates. Upon termination, the new values of x and y are not copied back into the actual parameters. Consequently, the values of the actual parameters are unaffected by the function.
To get the function to work properly we should change the header to

void swap(int& x, int& y);

函数 swap 无法交换实际参数的值,因为 xy 是形参。调用 swap(a, b)导致实际参数a和b的值分别复制到形式参数 xy 中。然后,在交换体内,xy 的值互换,并且函数终止。 终止后,不会将 xy 的新值复制回实际参数中。 因此,实际参数的值不受该功能的影响。
为了使功能正常工作,我们应该将标头更改为

void swap(int& x, int& y);

Exercise 2

template <class T>
int count(T a[], int n, const T& value)
{// 返回数组 a[0:n-1] 中 value 出现的次数.
   int theCount = 0;
   for (int i = 0; i < n; i++)
      if (a[i] == value)
         theCount++;
   return theCount;
}

Exercise 3

template <class T>
void fill(T* a, int start, int end, const T& value)
{// 建立数组 a[start:end-1].
   for (int i = start; i < end; i++)
      a[i] = value;
}

Exercise 4

template <class T> 
T inner_product(T a[], T b[], int n)
{// 返回 sum_(0  < = i  <  n) a[i] * b[i].
   T ip = 0;
   for (int i = 0; i  <  n; i++)
      ip += a[i] * b[i];
   return ip;
}

Exercise 5

template <class T>
void iota(T* a, int n, const T& value)
{// 建立 a[i] = a[i] + value, 0 <= i < n.
   for (int i = 0; i < n; i++)
      a[i] += value;
}

Exercise 6

template <class T>
bool is_sorted(T a[], int n)
{// 当且仅当 a[0:n-1] 有序时,返回 true.
   for (int i = 0; i < n - 1; i++)
      if (a[i] > a[i + 1])
         return false;
   return true;
}

Exercise 7

template <class T>
int mismatch(T* a, T* b, int n)
{// 返回使不等式 a[i] != b[i] 成立的最小索引 i.
 // Return n if no such i.
   for (int i = 0; i < n; i++)
      if (a[i] != b[i])
         return i;

   // no mismatch
   return n;
}

Exercise 8

The signature of a function is given by the number and data types of its actual parameters. Both functions have the same signature (int, int, int).

函数的签名由其实际参数的数量和数据类型给出。 这两个函数具有相同的签名 (int,int,int)

Exercise 5

  1. The signature of the function invocation agrees with that of the abc function of Program 1.1. Therefore, the abc function of Program 1.1 is invoked.

  2. The signature of the function invocation agrees with that of the abc function of Program 1.2. Therefore, the abc function of Program 1.2 is invoked.

  3. vThe signature of the function invocation does not agree with that of either of the abc functions. Since type conversions from both float to int and int to float are possible, C++ cannot resolve which function to use and gives a compile-time error.

  4. The actual parameters are of type double. C++ cannot resolve which function to use and gives a compile-time error as type conversions from double to both int and float are possible.

  • 函数调用的签名与程序 1.1 的 abc 函数的签名一致。 因此,将调用程序 1.1 的 abc 函数。

  • 函数调用的签名与程序 1.2 的 abc 函数的签名一致。 因此,将调用程序 1.2 的 abc 函数。

  • 函数调用的签名与任何一个 abc 函数的签名不一致。 由于可以进行从 floatint 以及从 intfloat 的类型转换,因此 C++ 无法解析要使用的函数,并且会给出编译时错误。

  • 实参的类型为 double。 C ++无法解析要使用的函数,并且会给出编译时错误,因为可能会将类型从double 转换为 intfloat


Exercise 10

int abc(int a, int b, int c)
{
   if (a < 0 && b < 0 && c < 0)
          throw 1;
   if (a == 0 && b == 0 && c == 0)
          throw 2;
   return a + b * c;
}

int main()
{
  int a = -1, b = -2, c= -3;
  cout << "The parameters to abc were " << a << ", "
       << b << ", " << c << endl;
  try {cout << abc(a,b,c) << endl;}
  catch (int e)
      {
         if (e == 1)
            cout << "All are < 0" << endl;
         else
            cout << "All are = 0" << endl;
      }
  a = b = c= 0;
  cout << "The parameters to abc were " << a << ", "
       << b << ", " << c << endl;
  try {cout << abc(a,b,c) << endl;}
  catch (int e)
      {
         if (e == 1)
            cout << "All are < 0" << endl;
         else
            cout << "All are = 0" << endl;
      }
  a = 1; b = 2; c= 0;
  cout << "The parameters to abc were " << a << ", "
       << b << ", " << c << endl;
  try {cout << abc(a,b,c) << endl;}
  catch (int e)
      {
         if (e == 1)
            cout << "All are < 0" << endl;
         else
            cout << "All are = 0" << endl;
         return 1;
      }
   cout << "No Exception" << endl;
   return 0;
}

Exercise 11

template <class T>
int count(T a[], int n, const T& value)
{// 返回数组 a[0:n-1] 中 value 出现的次数.
   if (n < 1)
      throw "n must be >= 1";

   int theCount = 0;
   for (int i = 0; i < n; i++)
      if (a[i] == value)
         theCount++;
   return theCount;
}

Exercise 12

template <class T>
void make2dArray(T ** &x, int numberOfRows, int* rowSize)
{// 创建一个二维数组

   // 创建行指针
   x = new T * [numberOfRows];

   // 为每一行分配空间
   for (int i = 0; i < numberOfRows; i++)
      x[i] = new T [rowSize[i]];
}

Exercise 13

template<class T>
void changeLength1D(T*& a, int oldLength, int newLength)
{
   if (newLength < 0)
      throw illegalParameterValue("new length must be >= 0");

   T* temp = new T[newLength];              // 分配新数组
   int number = min(oldLength, newLength);  // 复制 number
   copy(a, a + number, temp);
   delete [] a;                             // 释放旧空间
   a = temp;
}

Exercise 14

template<class T>
void changeLength2D(T**& a, int oldRows, int oldColumns, int newRows, int newColumns)
{
   if (newRows < 0 || newColumns < 0)
      throw illegalParameterValue("# of rows and columns must be >= 0");

   T** temp;
   make2dArray(temp, newRows, newColumns);
   int rowsToCopy = min(oldRows, newRows);
   int columnsToCopy = min(oldColumns, newColumns);
   for (int i = 0; i < rowsToCopy; i++)
      copy(a[i], a[i] + columnsToCopy, temp[i]);
   delete2dArray(a, oldRows);    // 释放旧空间
   a = temp;
}

Exercise 15

  • The data member dollar is of type long. The maximum value assignable to a variable of type unsigned long is 2^{32}-1. The maximum allowable value forcents` is 99. Therefore, when the representation of Program 1.13 is used, the maximum permissible currency value is 2^{32} - 1 dollars and 99 cents.
    Since we store the sign seprately, the minimum currency value is just the negative of the maximum value.

  • The maximum value assignable to a variable of type int is 2^{31} - 1. The maximum allowable value for cents is 99. When the data type of dollars and cents is changed to int, the maximum permissible currency value is 2^{31} - 1 dollars and 99 cents.
    Since we store the sign seprately, the minimum currency value is just the negative of the maximum value.

  • To avoid an error in the conversion, the result (a1 and a2) should not exceed MAX_VALUE = 2^{32}-1. Therefore, the dollar amount should not exceed MAX_VALUE / 100. Even though the dollar amount may not exceed MAX_VALUE / 100, the method may not give the correct result. To assure a correct result, the sum of the dollar amounts should not exceed MAX_VALUE / 100.

  • 数据成员 dollar 的类型为 long 。可分配给 unsigned long 类型的变量的最大值为 2 ^ {32}-1cent 的最大允许值为 99。因此,当使用程序 1.13 的表示形式时,允许的最大货币值为 2 ^ {32 }-1 dollar 和99 cent
    由于我们将符号分开存储,因此最小货币值就是最大值的负数。

  • 可分配给 int 类型的变量的最大值为 2 ^ {31}-1cent 的最大允许值为 99。当 dollarcent 的数据类型更改为 int 时,最大允许的货币值为 2 ^ { 31}-1 dollar 和 99 cent
    由于我们分开存储符号,因此最小货币价值就是最大值的负数。

  • 为避免转换错误,结果(a1a2)不应超过 MAX_VALUE = 2 ^ {32} -1。因此,dollar金额不应超过 MAX_VALUE /100。即使 dollar 金额可能不超过 MAX_VALUE / 100,该方法也可能无法给出正确的结果。为了确保结果正确,dollar 的总和不应超过 MAX_VALUE / 100

Exercise 16

We have at least two options on how to proceed. The new functions can be placed directly into the class currency or we can place the new functions in a class enhancedCurrency which is derived from currency. We shall take the latter approach. Even here, we have the option of either changing the visibility modifer for the data members of currency from private to protected so that our new class can directly access these data members, or we can leave things the way they are and use the get and set functions of currency. We shall take the latter option. Our choices leave the original class currency unmodified.

关于如何进行,我们至少有两个选择。 可以将新功能直接放置在 currency 类中,也可以将新功能放置在从 currency 派生的类 EnhancedCurrency 中。 我们将采用后一种方法。 即使在这里,我们也可以选择将 currency 数据成员的可见性修改器从 private 更改为 protected ,以便我们的新类可以直接访问这些数据成员,或者可以按原样保留一切并使用 getset currency功能。 我们将采用后一种选择。 我们的选择使原始类别的 currency 保持不变。

class enhancedCurrency : public currency
{
   public:
      // 与super class相同的构造函数
      enhancedCurrency(signType theSign = plus,
                       unsigned long theDollars = 0,
                       unsigned int theCents = 0) :
         currency(theSign, theDollars, theCents) {}

      // new instance methods
      void input()
      {
         // 输入 double 类型的金额
         cout << "Enter the currency amount as a real number" << endl;
         double theValue;
         cin >> theValue;

         // 设定 value
         setValue(theValue);
      }

      enhancedCurrency subtract(const enhancedCurrency& x)
      {// 返回 *this - x.
         // 将* this转换为 a long
         long a1 = getDollars() * 100 + getCents();
         if (getSign() == minus) a1 = -a1;

         // 将 x 转换为a long
         long a2 = x.getDollars() * 100 + x.getCents();
         if (x.getSign() == minus) a2 = -a2;

         long a3 = a1 - a2;

         // 将结果转换为 EnhancedCurrency 对象
         enhancedCurrency result;
         signType theSign = plus;
         if (a3 < 0)
         {
            theSign = minus;
            a3 = -a3;
         }
         result.setValue(theSign, a3 / 100, a3 - a3 / 100 * 100);

         return result;
      }

      enhancedCurrency percent(float x)
      {// 返回 * this的 x 百分比。
         long a1, a2;
         // convert this to a long
         a1 = getDollars() * 100 + getCents();
         if (getSign() == minus) a1 = -a1;

         a2 = (long) (a1 * x / 100);

         // 将结果转换为 EnhancedCurrency 对象
         enhancedCurrency result;
         signType theSign = plus;
         if (a2 < 0)
         {
            theSign = minus;
            a2 = -a2;
         }
         result.setValue(theSign, a2 / 100, a2 - a2 / 100 * 100);

         return result;
      }

      enhancedCurrency multiply(float x)
      {// 返回 this * x.
         long a1, a2;
         // convert this to a long
         a1 = getDollars() * 100 + getCents();
         if (getSign() == minus) a1 = -a1;

         a2 = (long) (a1 * x);

         // 将结果转换为 EnhancedCurrency 对象
         enhancedCurrency result;
         signType theSign = plus;
         if (a2 < 0)
         {
            theSign = minus;
            a2 = -a2;
         }
         result.setValue(theSign, a2 / 100, a2 - a2 / 100 * 100);

         return result;
      }

      enhancedCurrency divide(float x)
      {// 返回 this / x.
         long a1, a2;
         // 将 x 转换为 a long
         a1 = getDollars() * 100 + getCents();
         if (getSign() == minus) a1 = -a1;

         a2 = (long) (a1 / x);

         // 将结果转换为 EnhancedCurrency 对象
         enhancedCurrency result;
         signType theSign = plus;
         if (a2 < 0)
         {
            theSign = minus;
            a2 = -a2;
         }
         result.setValue(theSign, a2 / 100, a2 - a2 / 100 * 100);

         return result;
      }
};

Exercise 17

We have at least two options on how to proceed. The new functions can be placed directly into the class currency or we can place the new functions in a class enhancedCurrency which is derived from currency. We shall take the former approach.

关于如何进行,我们至少有两个选择。 可以将新功能直接放置在 currency 类中,也可以将新功能放置在从 currency 派生的类 EnhancedCurrency 中。 我们将采用前一种方法。

void input()
{
   //  //输入金额为 double
   cout << "Enter the currency amount as a real number" << endl;
   double theValue;
   cin >> theValue;

   // set the value
   setValue(theValue);
}

currency subtract(const currency& x)
{// 返回 *this - x.
   currency result;
   result.amount = amount - x.amount;
   return result;
}

currency percent(float x)
{// 返回 *this 的 x 百分比.
   currency result;
   result.amount = (long) (amount * x / 100);
   return result;
}

currency multiply(float x)
{// 返回 this * x.
   currency result;
   result.amount = (long) (amount * x);
   return result;
}

currency divide(float x)
{// 返回 this / x.
   currency result;
   result.amount = (long) (amount / x);
   return result;
}

Exercise 18

We have at least two options on how to proceed. The new functions can be placed directly into the class currency or we can place the new functions in a class enhancedCurrency which is derived from currency. We shall take the former approach.

关于如何进行,我们至少有两个选择。 可以将新函数直接放置在 currency类中,也可以将新函数放置在 currency 类的 enhancedCurrency 类中。 我们将采用前一种方法。

class currency 
{
   friend istream& operator>>(istream&, currency&);
   public:
      // 构造函数
      currency(signType theSign = plus,
               unsigned long theDollars = 0,
               unsigned int theCents = 0);
      // 析构函数
      ~currency() {}
      currency operator=(int theAmount)
      {
         amount = theAmount;
         return *this;
      }
      currency operator=(float theAmount)
      {
         if (theAmount < 0)
            amount = (long) ((theAmount - 0.001) * 100);
         else
            amount = (long) ((theAmount + 0.001) * 100);
         return *this;
      }
      signType getSign() const
        {if (amount < 0) return minus;
         else return plus;}
      unsigned long getDollars() const
        {if (amount < 0) return (-amount) / 100;
         else return amount / 100;}
      unsigned int getCents() const
        {if (amount < 0) return -amount - getDollars() * 100;
         else return amount - getDollars() * 100;}
      currency operator+(const currency&) const;
      currency operator-(const currency&) const;
      currency operator%(float) const;
      currency operator*(float) const;
      currency operator/(float) const;
      currency& operator+=(const currency& x)
        {amount += x.amount; return *this;}
      void output(ostream&) const;
   private:
      long amount;
};

currency::currency(signType theSign, unsigned long theDollars,
                                     unsigned int theCents)
{// 创建对象 currency.
   if (theCents > 99)
      // 美分太多
      throw illegalParameterValue("Cents should be < 100");

   amount = theDollars * 100 + theCents;
   if (theSign == minus) amount = -amount;
}

currency currency::operator+(const currency& x) const
{// 加 x 和 *this.
   currency result;
   result.amount = amount + x.amount;
   return result;
}

currency currency::operator-(const currency& x) const
{// 从 *this 添加 x.
   currency y;
   y.amount = amount - x.amount;
   return y;
}

currency currency::operator%(float x) const
{// 返回 *this 的 x %.
   currency y;
   y.amount = (long) (amount * x) / 100;
   return y;
}

currency currency::operator*(float x) const
{// 返回 x * (*this).
   currency y;
   y.amount = (long) (amount * x);
   return y;
}

currency currency::operator/(float x) const
{// 返回 (*this) / x.
   currency y;
   y.amount = (long) (amount / x);
   return y;
}

void currency::output(ostream& out) const
{// 将 value 值插入流中.
   long theAmount = amount;
   if (theAmount < 0) {out << '-';
                       theAmount = -theAmount;}
   long dollars = theAmount / 100; // dollars
   out << '$' << dollars << '.';
   int cents = theAmount - dollars * 100; // cents
   if (cents < 10) out << '0';
   out << cents;
}

// 重载 <<
ostream& operator<<(ostream& out, const currency& x)
   {x.output(out); return out;}

// 重载 >>
istream& operator>>(istream& in, currency& x)
{// 输入货币金额

   float y;
   cout << "Enter the currency amount as "
        << "a floating point number as in dd.cc or -dd.cc"
        << endl;

   in >> y;
   x = y;
   return in;
}

Exercise 19

int factorial (int n)
{// 返回 n!.
   if (n <= 1)
      return 1;
   int fact = 2;
   for (int i = 3; i <= n; i++)
      fact *= i;
   return fact;
}

Exercise 20

  1. public static int recursiveFibonacci(int n)
    {
      if (n == 0)
         return 0;
      if (n == 1)
         return 1;
         return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
    }
    
  2. When computing F_3, for example, F_2 is computed twice. Notice that F_3 is computed as F2 + F_1.

    例如,在计算F_3时,两次计算F_2。 请注意,F_3计算为F_2 + F_1$。

  3. To compute the nth Fibonacci number nonrecursively, we compute the numbers in the order F_0, F_1, F_2, F_3, ...; F_2, F_3, ... may each be computed by summing the two preceding numbers in the sequence.

    为了非递归地计算第n个斐波那契数,我们按 F_0,F_1,F_2,F_3,... 的顺序计算数字; F_2,F_3,...可以通过将序列中的两个前面的数字相加来计算。

    public static int fibonacci(int n)
    {
      if (n == 0)
         return 0;
      if (n == 1)
         return 1;
      int secondLast = 0;  // 倒数第二个斐波那契数
                           // 到目前为止计算
      int last = 1;        // 最后的斐波那契数
                           // 到目前为止计算
      // 计算新数字
      for (int i = 2; i <= n; i++)
      {
         // 计算第 i 个斐波那契数
         int next = last + secondLast;
         // 更新 last 和 secondLast
         secondLast = last;
         last = next;
      }
    
      return last;
    }
    

Exercise 21

f(5) = f(3 \times 5 + 1) = f(16) = 16 / 2 = 8.

f(7) = f(3 \times 7 + 1) = f(22) = 22 / 2 = 11.

The base component is f(n) = n/2, n is even and the recursive component is f(n) = f(3n + 1), n is odd.

When n is odd, one application of the recursive component transforms the occurrence of n on the right hand side to the base component because 3n + 1 is even whenever n is odd.

基础部分为f(n)= n / 2,n为偶数,递归成分为f(n)= f(3n + 1),n为奇数

n为奇数时,递归组件的一个应用程序会将右侧的 n 的出现转换为基本组件,因为 3n + 1 在 任意 n 时都为奇数。

public static int recursiveF(int n)
{
   return (n % 2 == 0) ? n / 2 : recursiveF(3 * n + 1);
}
public static int iterativeF(int n)
{
   return (n % 2 == 0) ? n / 2 : (3 * n + 1) / 2;
}

Exercise 22

A(1,2) = 2^2 = 4.

A(2,1) = A(1,2) = 4.

A(2,2) = A(1, A(2,1)) = A(1, 4) = 2^4 = 16.
The base component is A(i,j) = 2j for i = 1 and j = 1 and the recursive components are A(i,j) = A(i-1,2) for i >= 2 and j = 1 and A(i,j) = A(i-1,A(i, j-1)) for i,j>= 2.

对于 i = 1j = 1,基本分量为 A(i,j)= 2j;对于 i> = 2 且 j = 1,递归分量为 A(i,j)= A(i-1,2)。 对于 i,j> = 2,A(i,j)= A(i-1,A(i,j-1))

```cpp
/** 计算阿克曼函数
* @当 i 或 j <1时抛出 IllegalArgumentException */
public static int ackermann(int i, int j)
{
if (i < 1 || j < 1)
throw new IllegalArgumentException("i and j must be >= 1, they are "+ "i = " + i + " j = " + j);

<pre><code> return a(i, j);
</code></pre>

}

/** 计算阿克曼函数
*假设 i,j> = 1 */
private static int a(int i, int j)
{
if (i <span class="text-highlighted-inline" style="background-color: #fffd38;"> 1)
{// 计算 2^j
int ans = 2;
for (int k = 1; k < j; k++)
ans *= 2;
return ans;
}</span>

<pre><code> if (j == 1)
return a(i - 1, 2);

// i 和 j >= 2
return a(i - 1, a(i, j - 1));
</code></pre>

}

```

Exercise 23

\gcd(20, 30) = \gcd(30, 20 \mod 30) = \gcd(30, 20) = \gcd(20, 30 \mod 20) = \gcd(20, 10) = \gcd(10, 20 \mod 10) = \gcd(10, 0) = 10.

\gcd(112, 42) = gcd(42, 112 \mod 42) = \gcd(42, 28) = \gcd(28, 42 \mod 28) = gcd(28, 14) = \gcd(14, 28\mod 14) = \gcd(14,0) = 0.

The base component is gcd(x, y) = x when y = 0 and the recursive component is gcd(x, y) = gcd(y, x mod y), y > 0.

A formal proof can be provided using induction. We provide an informal proof. When x < y, the first application of the definition gives us gcd(x, y) = gcd(y, x mod y) = gcd(y, x). Following this, the first parameter is > the second. So, we may consider only the case when x >= y.

When x = y, an application of the definition results in gcd(x,y) = gcd(y, x mod y) = gcd(y,0) which is an occurrence of gcd in the base component.

When x > y, an application of the definition results in gcd(x,y) = gcd(y, x mod y) = gcd(y,z), where 0 <= z < y. Each application of the recursive component decreases the second parameter. Therefore, after a sufficient number of applications (at most y), the second parameter will become 0 and we will have an occurrence of gcd which is in the base component.

基础部分是当y = 0时,gcd(x,y) = x,递归部分是gcd(x,y)= gcd(y,x mod y),y> 0

可以使用归纳法提供正式证明。 我们提供非正式证明。 当 x < y``` 时,定义的第一个应用为我们提供gcd(x, y)= gcd(y, x mod y)= gcd(y, x)。在此之后,第一个参数>第二个参数。 因此,我们可能只考虑x >= y` 的情况。

x = y 时,定义的应用导致 gcd(x,y)= gcd(y,x mod y)= gcd(y,0) 。这是在基础组件中出现的 gcd

x > y时,定义的应用将导致gcd(x,y)= gcd(y,x mod y)= gcd(y,z),其中0 <= z < y 递归组件的每次应用都会减少第二个参数。 因此,在足够数量的应用程序之后(最多为 y),第二个参数将变为 0 ,并且在基本组件中将出现 gcd

```cpp
/** @返回 x 和 y 的 gcd
* @当 x 或 y < 0 时抛出 IllegalArgumentException
public static int gcd(int x, int y)
{
if (x < 0 || y < 0)
throw new IllegalArgumentException("x and y must be >= 0, " + "x = " + x + " y = " + y);

<pre><code> return rgcd(x, y);
</code></pre>

}

/** @return the gcd of x and y
* assumes x,y >= 0 */
private static int rgcd(int x, int y)
{
return (y <span class="text-highlighted-inline" style="background-color: #fffd38;"> 0) ? x : rgcd(y, x % y);
}

```

Exercise 24

The code is given below. This code first compares a[n-1] and x. If they are equal, we are done. If they are not equal, the problem becomes one of determining whether x is one of a[0:n-2]. The recursion terminates when n is smaller than 1.

代码如下。 该代码首先比较 a [n-1]x。 如果它们相等,我们就完成了。 如果它们不相等,则问题成为确定 x 是否为 a[0:n-2] 之一。 当 n 小于 1 时,递归终止。

package applications;

import wrappers.*;
import utilities.*;

public class Exists
{
   /** @ 如果 x 属于 a[0:n-1] ,返回 true */
   public static boolean exists(Comparable [] a, Comparable x, int n)
   {
      if (n < 1)
         return false;
      if (a[n - 1].equals(x))
         return true;
      return exists(a, x, n - 1);
   }
}

Exercise 25

We may represent a subset of n elements by the one-dimensional array x[1:n], where x[j] is one if element j is included in the subset and x[j] is zero if element j is not included in the subset.

To output the subsets recursively, we define a method subsets(int i) which outputs all x[1:n] with preset values for x[1:i-1] and x[i:n] taking on all possible 0 and 1 values. The invocation subsets(1) will output all subsets.

我们可以用一维数组 x [1:n] 表示n个元素的子集,其中如果元素 j 被包含在子集中,则x[j] 为1,如果元素 j 不包含在子集中,则 x[j] 为零。

为了递归地输出子集,我们定义了一个方法 subsets(int i),该方法输出所有带有预定值 x [1:i-1]x[i:n]x[1:n],并取所有可能的 0 和 1 的值。 调用 subsets(1) 将输出所有子集。

/** 生成n个元素的所有子集 */

package applications;

public class AllSubsets
{
   // 类数据成员
   static int [] x;  // subset vector

   /** 定义数组 x 并调用私有方法子集*/
   public static void allSubsets(int n)
   {
      x = new int [n + 1];
      // output all subsets of x[1:n]
      subsets(1);
   }

   /** 输出 x[1:i-1],后跟 x[i:x.length-1] 的所有子集 */
   private static void subsets(int i)
   {
      if (i == x.length - 1)
      {// x[x.length-1]可以为 0 或 1
         // 输出没有最后一个元素的子集
         x[x.length - 1] = 0;
         for (int j = 1; j <= x.length - 1; j++)
            System.out.print(x[j] + " ");
         System.out.println();

         // 输出带有最后一个元素的子集
         x[x.length - 1] = 1;
         for (int j = 1; j <= x.length - 1; j++)
            System.out.print(x[j] + " ");
         System.out.println();
         return;
      }

      // 忽略元素 i
      x[i] = 0;
      // 生成所有排除 i 的子集
      subsets(i + 1);

       // 生成包含 i 的所有子集
       x[i] = 1;
       // generate all subsets with i included
       subsets(i + 1);
   }

   /** 测试程序 */
   public static void main(String [] args)
   {
      allSubsets(4);
   }
}

Exercise 26

g(4) = g(3), 4, g(3) = g(2), 3, g(2), 4, g(2), 3, g(2)
= g(1), 2, g(1), 3, g(1), 2, g(1), 4, g(1), 2, g(1), 3, g(1), 2, g(1)
= 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1.

The base component is g(n) = 1, for n = 1 and the recursive component is g(n) = g(n-1), n, g(n-1) for n >= 1.

A formal proof can be provided using induction. We provide an informal proof. When n = 1, we have an occurrence of the base component. When n > 1, one application of the recursive component yields two occurrences of g(n-1). Two additional applications of the recursive component will replace the two occurrences of g(n-1) by four occurrences of g(n-2), and so on. So, after 1 + 2 + 4 + 8 + ... + 2^n-2 applications of the recursive component, all remaining occurrences of g are base component occurrences.

基础部分是g(n)= 1,对于n = 1,递归分量是g(n)= g(n-1),n,g (n-1)对于n> = 1

可以使用归纳法提供正式证明。 我们提供非正式证明。 当n = 1时,我们有一个基本成分出现。 当n > 1时,递归组件的一种应用将产生两次g(n-1)。 递归组件的另外两个应用程序将用四个出现的 g(n-2) 替换两个出现的 g(n-1),依此类推。 因此,在递归组件的 1 + 2 + 4 + 8 + ... + 2 ^ n-2应用之后,所有剩余的 g 的出现都是基本分量的出现。

/** @返回 n 位格雷码的位转换顺序
  * @ n < 1 时抛出IllegalArgumentException */
private static String grayCode(int n)
{
   if (n < 1)
      throw new IllegalArgumentException(" n must be >= 1, it is "+ n);
   return g(n);
}

/** @返回 n 位格雷码的位转换顺序 */
private static String g(int n)
{
   if (n == 1)
      return "1";

   String left = g(n - 1);
   return left + ", " + n + ", " + left;
}

Exercise 27 ~ Exercise 44

404 Not Found.

Exercise 45

The program has 4 execution paths and each execution path has at least one statement that is not on any other execution path. Therefore, any test set that provides statement coverage must follow all execution paths, and hence must provide execution path coverage coverage.

The program has 3 decisions. By examining the decisions needed to execute each of the 4 execution paths, we see that over these 4 execution paths, each of the 3 decisions takes on the truth values true and false. Hence execution path coverage implies decision coverage. Since we have already shown that statement coverage implies execution path coverage, it follows that any test set that provides statement coverage must also provide decision coverage.

该程序有 4 个执行路径,每个执行路径都有至少一个不在任何其他执行路径上的语句。 因此,任何提供语句覆盖范围的测试集都必须遵循所有执行路径,因此必须提供执行路径覆盖范围。

该程序有 3 个分支。 通过检查执行 4 条执行路径中的每条所需的分支,我们看到在这4条执行路径中,这3条决策中的每条都采用真值true和false。 因此,执行路径覆盖意味着决策分支。 由于我们已经表明语句覆盖率意味着执行路径覆盖率,因此,提供语句覆盖率的任何测试集也必须提供分支覆盖率。

Exercise 46

When n = 3, the for loop is entered three times and there can be 2^3 = 8sequences of outcomes for the decision (a[pos].lessThan(a[i])). So there are 8 execution paths and 8 data sets are required for execution path coverage. Each execution path can be described by the truth value sequence for the decision. For example, FFF describes the path when (a[pos].lessThan(a[i])) is false on all three iterations of the for loop, and TFF describes the execution path when (a[pos].lessThan(a[i])) is true on the first iteration and false on the remaining two iterations of the for loop.

A sample array a[0:3] for each execution path is given below.

n = 3时,for循环被输入 3 次,并且可能有 2 ^ 3= 8 决策的结果序列(a[pos].lessThan(a[i]))。 因此,执行路径覆盖需要 8 条执行路径和 8 个数据集。 每个执行路径都可以由决策的真值序列描述。 例如,当 a[pos].lessThan(a[i]))for 循环的所有三个迭代中为 false 时,FFF 描述路径,而 TFF 描述执行 当 (a[pos].lessThan(a[i])) 在 for 循环的第一次迭代中为 true 且在其余两次迭代中为 false 时的路径。

下面给出了每个执行路径的示例数组 a[0:3]

Path Test set
FFF [6, 2, 3, 1]
TFF [2, 6, 3, 1]
FTF [6, 2, 8, 1]
TTF [2, 6, 8, 1]
FFT [6, 2, 3, 8]
TFT [2, 6, 3, 8]
FTT [6, 2, 8, 9]
TTT [2, 6, 8, 9]

Exercise 47

For each value of n, Program 1.30 has exactly one execution path.

对于每个 n 值,程序 1.30 仅有一个执行路径。

Exercise 48

For each value of n, method rSum of Program 1.31 has exactly one execution path.

对于每个 n 值,程序 1.31 的 rSum 函数具有一个执行路径。


大变に气分がいい