c++ - 选举投票递归函数 - Stanford CS106B issue

Question

我在理解/执行这个问题时遇到了一些问题。基本上，这是 self 导向的，如果有人能够阐明递归的结构(某种伪代码将不胜感激)，我们将不胜感激。

我遇到的问题是问题 3 - 搜索“Every Vote Counts”。

http://see.stanford.edu/materials/icspacs106b/H18-Assign3RecPS.pdf

我试图理解它是你可以生成投票结果的数量而无需在索引处指定的 block 。如果该区 block 将这个数字压倒了大多数选票，那么它就很关键了。但是我如何将这个想法转化为代码呢？

澄清 这是他们所指的热身问题，它有效，需要更改以回答上述问题:

bool CanMakeSum(Vector<int> & nums, int targetSum) {

if (targetSum == 0) { 

    counter++;
    cout << listSubset(partial_solution) << endl;

} else {

    for (int i = 0; i < nums.size(); i++) {

        int element = nums[i];

        Vector<int> rest = nums;
        rest.removeAt(i);
        partial_solution.add(element);

        int newTargetSum = targetSum - element;

            if (CanMakeSum(rest, newTargetSum)) {

                return true;

            }

        int remove_place = partial_solution.size() - 1;
        partial_solution.removeAt(remove_place);

    }
}


if (counter > 0) {

    cout << "The number of subsets that exist are: " << counter << endl;
    return true;

}

return false;
}

string listSubset(Vector<int> &partial_solution) {

string solution = "These total up to the sum: ";

for (int i = 0; i < partial_solution.size(); i++) {
    solution += IntegerToString(partial_solution[i]) + " ";
}

return solution;

}

Answer 1

你有一些投票区 block ，

std::vector<int> v = { 4, 2, 7, 4 }

总共有 17 票，多数 floor((17 + 1)/2) 或需要 9 票才能扭转选举。

假设集合是从零开始索引的(毕竟它将在一个 vector 中)，并且您想找到区 block 3 的关键投票(有 4 票)。

首先，构建剩余 block 的集合:

std::vector<int> r = { 4, 2, 7 }

现在找到 powerset 该集合。该练习引用了您之前可能使用过的“ListSubsets”函数；这将是相关的。使用 std::set 和一些递归很容易重新实现。如果您想专门使用 std::vector 来执行此操作，则必须自己进行唯一性测试。

void find_powerset(std::set<std::set<int>> &powerset, std::set<int> initial)
{
  powerset.insert(initial);

  for (auto i = initial.begin(); i != initial.end(); i++)
  {
    std::set<int> new_set(initial);
    new_set.erase(new_set.find(*i));
    find_powerset(powerset, new_set);
  }
}

你可以很简单地调用它，

std::set<std::set<int>> powerset;
find_powerset(powerset, std::set<int>(r.begin(), r.end()));

这最终会生成这样的东西(当然 std::set 不会按这个顺序保存东西)。

{ }
{ 4 }
{ 2 }
{ 7 }
{ 4, 2 }
{ 4, 7 }
{ 2, 7 }
{ 4, 2, 7 }

现在只需将每个子集中的总票数相加即可:

0, 4, 2, 7, 6, 11, 9, 13

这些尚未超过多数票的投票结果中有多少会在与当前区 block 的投票相结合时超过多数票？您可能会发现练习中的“热身 B”任务很相关。

这一步可以与上一步结合，通过修改上面的 powerset 函数只返回总和在适当范围内的子集。这是留给读者的练习。

无论如何，答案是“只是 2”，{ 7 } 和 { 4, 2 }。在所有其他结果中，最后一个区 block 的投票不会改变任何东西。简单!