cs106x-lecture11(Autumn 2017)-SPL实现

打卡cs106x(Autumn 2017)-lecture11

(以下皆使用SPL实现，非STL库，后续课程结束会使用STL实现)

1、diceRolls

Write a recursive function named diceRolls accepts an integer representing a number of 6-sided dice to roll, and output all possible combinations of values that could appear on the dice. For example, the call of diceRolls(3); should print:

{1, 1, 1}
{1, 1, 2}
{1, 1, 3}
{1, 1, 4}
{1, 1, 5}
{1, 1, 6}
{1, 2, 1}
{1, 2, 2}...
{6, 6, 4}
{6, 6, 5}
{6, 6, 6}

If the number of digits passed is 0 or negative, print no output. Your function must use recursion, but you can use a single for loop if necessary.

解答：

#include <iostream>
#include "console.h"
#include "vector.h"using namespace std;void diceRollsHelper(int n, Vector<int>& v) {if (n == 0) {cout << v << endl;} else {for (int i = 1; i <= 6; i++) {v.add(i);diceRollsHelper(n - 1, v);v.remove(v.size() - 1);}}
}void diceRolls(int n) {if (n >= 0) {Vector<int> v;diceRollsHelper(n, v);}
}int main() {diceRolls(3);return 0;
}

2、diceSum

Write a recursive function named diceSum that accepts two parameters: an integer representing a number of 6-sided dice to roll, and a desired sum, and output all possible combinations of values that could appear on the dice that would add up to exactly the given sum. For example, the call of diceSum(3, 7); should print all combinations of rolls of 3 dice that add up to 7:

{1, 1, 5}
{1, 2, 4}
{1, 3, 3}
{1, 4, 2}
{1, 5, 1}
{2, 1, 4}
{2, 2, 3}
{2, 3, 2}
{2, 4, 1}
{3, 1, 3}
{3, 2, 2}
{3, 3, 1}
{4, 1, 2}
{4, 2, 1}
{5, 1, 1}

If the number of digits passed is 0 or negative, or if the given number of dice cannot add up to exactly the given sum, print no output. Your function must use recursion, but you can use a single for loop if necessary.

解答：

#include <iostream>
#include "console.h"
#include "vector.h"using namespace std;void diceSumHelper(int n, int desired, int sum, Vector<int>& v) {if (n == 0 && sum == desired) {cout << v << endl;} else {for (int i = 1; i <= 6; i++) {int min = sum + i + 1 * (n - 1);int max = sum + i + 6 * (n - 1);if (desired >= min && desired <= max) {v.add(i);diceSumHelper(n - 1, desired, sum + i, v);v.remove(v.size() - 1);}}}
}void diceSum(int n, int desired) {if (n >= 0) {Vector<int> v;int sum = 0;diceSumHelper(n, desired, sum, v);}
}int main() {diceSum(3, 7);return 0;
}

3、printSubVectors 

Write a recursive function named printSubVectors that accepts a reference to a vector of integer values as a parameter and that prints console output (to cout) displaying all possible sub-vectors that can be created from some subset of the vector's elements. For example, if a vector variable v stores the elements {1, 2, 3}, the call of printSubVectors(v); should print the following output to the console:

{}
{3}
{2}
{2, 3}
{1}
{1, 3}
{1, 2}
{1, 2, 3}

Your function can print the sub-vectors in any order, but the sub-vectors you print should preserve the order of the values from the vector. For example, the sub-vectors of {42, 23} should be listed as:

{}
{23}
{42}
{42, 23}

You may assume the vector passed contains no duplicate values. If passed an empty vector, print only a single line containing the empty vector itself, {} .

Constraints: You may define helper functions if you like. You are allowed to construct exactly one auxiliary collection of your choice from the collections we have studied (one vector, set, map, stack, queue, array, etc.). That is, at most one collection can be constructed in total for each call a client makes on your function. Note that a compound collection, such as a Vector of Vectors, is considered to be more than one auxiliary collection in this context. Your function should not alter the contents of the vector that is passed as a parameter; declare your function's header in such a way to assure the client that you will not do so. You may not use any loops to solve this problem; you must use recursion.

解答：

#include <iostream>
#include "console.h"
#include "vector.h"using namespace std;void printSubVectorsHelper(Vector<int>& v, Vector<int>& chosen){if (v.isEmpty()) {cout << chosen << endl;} else {int n = v[0];v.remove(0);chosen.add(n);printSubVectorsHelper(v, chosen);chosen.remove(chosen.size() - 1);printSubVectorsHelper(v, chosen);v.insert(0, n);}
}void printSubVectors(Vector<int> v) {if (v.size() == 0) {cout << v << endl;} else {Vector<int> chosen;printSubVectorsHelper(v, chosen);}
}int main() {printSubVectors({1, 2, 3});return 0;
}