Q 02　山手线的印章比赛

IQ　70
目标时间：15 分钟

我们来看一下山手线的印章比赛。假设所有车站都有印章，参与者必须在进站的车站和出站的车站盖章。印章在检票口里面，进站后可以在不出站的情况下收集印章。

山手线是东京都内的一条环状地铁线，一共有 29 个车站。这里假设不能通过山手线换乘其他路线，并且只能在山手线单向通行。参与者购买单程车票，从一个车站到另一个车站，每个车站只能通过一次（中途逆行就算违反规则）。

假设印章卡上能够盖所有车站的印章，且山手线上的各站用 1 ～ 29 按顺序编了号。

问题

如果从 1 号车站进入，从 17 号车站出站，则一共有多少种盖章方式（图 1.3）？

¹山手线是环形运行的，靠内侧运行的叫作内环，在其外侧反向运行的叫作外环。我国是右侧通行，所以内环是顺时针，外环是逆时针，而日本是左侧通行，所以内外环运行的方向与我国的情况恰好相反。——编者注

思路

为了简化问题，我们可以把车站想象成笔直的一列，而不是一个圆环。由于不能逆行，所以我们只要考虑参与者在各站是否下车即可，由此便能求出组合数。

比如，在有 1、2、3、4、5 这 5 个车站的情况下，组合方式一共有 8 种，具体如图 1.4 所示。

因为我们一定会在进站和出站的两个车站盖章，所以只要思考是否在 2 号、3 号和 4 号车站下车即可。用就能求出结果。也就是说，如果“中间的车站数”有个，组合方式就有种。

代码清单 02.01（q02.rb）

N = 29

# 设置进站和出站的车站号
a, b = 1, 17

# 求中间经过的车站数
n = (a - b).abs

# 将内环和外环的情况相加后，去掉重复的部分
puts (1 << (n - 1)) + (1 << (N - n - 1)) - 1

代码清单 02.02（q02.js）

N = 29;

var a = 1;
var b = 17;
var n = Math.abs(a - b);

console.log((1 << (n - 1)) + (1 << (N - n - 1)) - 1);

关键点

在求时，用到了移位运算符“<<”。“<<”是左移运算符，1<<3 表示将二进制数 1 左移 3 位，右侧的空位补零（图 1.5）。

图 1.5　左移运算符

左移 1 位，表示的数就会变成原数的 2 倍，右移 1 位，则会缩小为原数的 1/2，所以要计算 2 的次方，只要将二进制数 1 往左移次就可以了。

在计算的次方时，在使用 Ruby 的情况下可以写成 a ** b，在使用 JavaScript 的情况下可以写成 Math.pow(a, b)，但如果底数是 2，即如果求的是 2 的乘方，那么使用移位运算符的处理速度会更快。

※根据 ES2016，在使用 JavaScript 的情况下也能写成 a ** b 的形式。

答案　36 863 种

前辈的小讲堂　实用的位运算

除了在本题中用到的移位运算，AND、OR、XOR 等位运算（逻辑运算）也很常用。位运算不仅能让代码变得简洁，提高处理速度，还能在一份数据中融入多条信息。

使用位运算容易给人一种“技术狂”的印象，但其实在实际工作中我们经常会用到它。例如，在开发 Windows 应用程序时，我们经常用位运算判断文件和文件夹的属性。

已经保存的文件会被赋予“只读”“隐藏”等各种属性。这部分是通过 FileAttributes 枚举来管理的。各类属性使用 1, 2, 4, 8, 16,…这种 2 的乘方的枚举常量来定义。表 1.4 中列出了这些属性，各个属性按比特位赋特定的值。

表 1.4　FileAttributes 的属性

例如，我们可以按照下面的方式使用 AND 来判断文件是否设置了只读位。

attr = File.GetAttributes("文件名")
if (attr & FileAttributes.ReadOnly) == FileAttributes.ReadOnly