Q 01　少数服从多数

IQ　70
目标时间：20 分钟

少数服从多数的方式常在人们意见不一致时使用。该方式简单明了，所 以除了政界，学校和公司也常通过它来表决。这里，我们来思考一个使用了猜拳的少数服从多数的方式，具体规则如下。

每个人只能出“石头”“剪刀”“布”中的 1 种手势，出哪一种的人数最多，则哪些人获胜。比如，当参加者有 6 人时，既可能出现表 1.1 那种一次定胜负的情况，也可能出现表 1.2 那种胜负未决的情况。

当一定数量的人猜拳时，一次就能定胜负的人数组合方式有多少种呢？以 4 人为例，表 1.3 列出了所有可能的组合方式，一共有 12 种。

问题

当 100 人猜拳时，一次就能定胜负的人数组合方式有多少种呢？

思路

猜拳的手势有石头、剪刀、布这 3 种，我们可以数一下出各种手势的人数。一次定胜负指的就是，出的人数最多的手势只有 1 种的情况。

代码清单 01.01（q01_1.rb）

N = 100

cnt = 0
0.upto(N) do |rock|               # 出“石头”的人数
  0.upto(N - rock) do |scissors|  # 出“剪刀”的人数
    paper = N - rock - scissors   # 出“布”的人数
    all = [rock, scissors, paper]
    cnt += 1 if all.count(all.max) == 1
  end
end
puts cnt

代码清单 01.02（q01_1.js）

N = 100;

var cnt = 0;
for (var rock = 0; rock <= N; rock++){ // 出“石头”的人数
  for (var scissors = 0; scissors <= N - rock; scissors++){
    // 出“剪刀”的人数
    var paper = N - rock - scissors; // 出“布”的人数
    if (rock > scissors){
      if (rock != paper)
        cnt++;
    } else if (rock < scissors) {
      if (scissors != paper)
        cnt++;
    } else {
      if (rock < paper)
        cnt++;
    }
  }
}
console.log(cnt);

关键点

以 4 人为例，我们可以在石头、剪刀、布之间放置分隔符来表示各种组合。假设用“○”表示人，第 1 个“｜”之前是出“石头”的人，第 1 个“｜”和第 2 个“｜”之间是出“剪刀”的人，这之后是出“布”的人。于是，这个问题就可以转换成“求 4 个 ○ 和 2 个｜有多少种组合方式”的问题（图 1.2）。

在研究组合方式时经常会用到这种方法，大家要学会这种解题思路。

图 1.2 　用分隔符来思考组合方式

我们用 l（left）表示左边放分隔符的地方，用 r（right）表示右边放分隔符的地方（代码清单 01.03 和代码清单 01.04）。

代码清单 01.03（q01_2.rb）

N = 100

cnt = 0
0.upto(N) do |l|    # 左边的分隔符的位置
  l.upto(N) do |r|  # 右边的分隔符的位置
    all = [l, r - l, N - r] # 分别表示出石头、剪刀、布的人数
    cnt += 1 if all.count(all.max) == 1
  end
end
puts cnt

代码清单 01.04（q01_2.js）

N = 100;

var cnt = 0;
for (l = 0; l <= N; l++){   // 左边的分隔符的位置
  for (r = l; r <= N; r++){ // 右边的分隔符的位置
    if (l > r - l){         // 当出“石头”的人数多于出“剪刀”的人数时
      if (l != N - r)       // 当出“石头”的人数和出“布”的人数不同时
        cnt++;
    } else if (l < r - l){  // 当出“剪刀”的人数多于出“石头”的人数时
      if (r - l != N - r)   // 当出“剪刀”的人数和出“布”的人数不同时
        cnt++;
    } else {                // 当出“石头”的人数和出“剪刀”的人数一样时
      if (l < N - r)        // 当出“布”的人数最多时
        cnt++;
    }
  }
}
console.log(cnt);

答案　5100 种