余数 - 周期性与分组
余数 --周期性与分组
余数就是做除法运算时的剩下的数。
思考题1
100天以后是星期几？
一周有七天，每过7天，便循环到相同的星期数。如果今天星期日，则7天后，14天...这种7天倍数天后，都是星期日。98是7的倍数，则：
98天后 --- 星期天
99天后 --- 星期一
100天后 -- 星期二
答案便是星期二
上面的思考题就是下面这种方法计算的。
0 | 日
1 | 一
2 | 二
3 | 三
4 | 四
5 | 五
6 | 六
100 / 7 = 14 .. 2
因此星期二
余数的力量 -- 将较大的数除一次就能分组
在面对难以直接计算的庞大的数字时，只要发现它是如何循环的，就可以通过余数的力量将其降服。
思考题2
今天星期日，10^100天后星期几？
提示：
如果像求100天以后的星期数那样，我们可以用10^100 除以 7的余数来计算；但实际上由于数字太大了，计算起来相当费力。上题思考题使用星期的周期来解决问题，那么这题有没有其他的周期性呢？
思考
我们并不急于求出10^100，而是依次观察0的个数观察规律。
10^0 一
10^1 三
10^2 二
10^3 六
10^4 四
10^5 五
10^6 一
10^7 三
10^8 二
10^9 六
10^10 四
10^11 五
10^12 一
...
果然有规律
- 余数以1,3,2,6,4,5的顺序循环，星期数以一，三，二，六，四，五...的顺序循环；
- 通过观察发现，每增加6个0，星期数就相同，因此周期为6，将0的个数除以6，得到的余数为0,1,2,3,4,5的其中之一，它们分别对应星期一，星期三，星期二，星期六，星期四，星期五；
- 因此，10^100天以后的星期数，可以将天数中0的个数除以6，通过余数来判断，所以 100 /6 = 16 ...4
所以答案为星期四
思考题3
1234567^987654321的个位数是什么呢？
提示：找个位数的规律
规律和余数的关系
对于庞大的数值不能直接计算，所以先用较小的数字进行试算，找出规律，只要找出规律，就可以通过余数解决。运用余数，大数字的问题就能简化成小数字的问题。
奇偶校验
黑白棋通信
魔术师和他的徒弟在台上表演，下面有3个观众。魔术师蒙着眼睛
1）桌子随机排列着7个黑白棋，魔术师蒙着眼睛，看不到棋子。
2）魔术师的徒弟在看完这7枚棋子之后，又往右面添了一枚棋子，与其他棋子并排，这时有8枚棋子。
3）这时观众可将其中一枚棋子翻转，或不翻转任何棋子；此间，徒弟和观众不发一言，魔术师还是蒙着眼睛，并不知道观众没有翻转棋子。
4）魔术师摘下眼罩，观察8枚棋子，然后马上就能说出“观众翻转了棋子”或“没有翻转棋子”，识破观众的行为。
那魔术师是如何识破观众的行为呢？
提示：
徒弟只是放了一枚棋子，而且放棋子的动作在观众行动之“前”，那么，徒弟是如何向魔术师传递有没有翻转棋子的信息的呢？
答案：
徒弟在观众摆放的7枚棋子中，数出黑棋子个数，若为奇数，就添加黑旗。若为偶数，则添加白棋。不管哪种情况，在最终的8个棋子中，黑棋必为偶数个。
观众可以有1--3三种情况：
- 观众翻转白棋，那么黑棋就增加了一枚，即黑棋变为奇数个。
- 观众翻转黑棋，那么白棋就增加了一枚，即黑棋也变为奇数个。
- 观众不翻转棋子，黑棋仍然是偶数个。
魔术师摘下眼罩，马上数出黑棋的个数。如果黑棋为奇数个，就说“观众翻转了棋子”。如果是偶数个，就说“没有翻转棋子”。
这里，徒弟摆放棋子使黑棋个数为“偶数”；若使黑棋个数为奇数也可以，只要魔术师和徒弟商量好就行。
奇偶校验
我们将魔术师和徒弟表演的戏法想作白棋为2进制的0，黑棋为2进制的1，那么它就和计算机通信中奇偶校验的方法一样的。
- 徒弟是为发送方，魔术师是接收方。中途翻转黑白棋的观众为“干扰通信的噪音”。
- 徒弟作为发送方，放置的一个棋子，在通信领域中被称为奇偶校验位，魔术师作为接收方，通过检查摆放的棋子的奇偶性来判断是否因噪音发生了通信错误。
- 至于奇偶校验位是设为偶数还是奇数，那么在发送方和接收方之间的通信规定中所约定。
奇偶校验位将数字分为两个集合。
另外，也可以这么思考。7枚棋子的排列法总共2^7=128种，其中一半（64种）是黑棋为偶数个，另一半（64种）是黑棋为奇数个。128种组合被分为了2组。魔术师的徒弟添加的1枚棋子，起到了标识目前7枚棋子属于哪个组的作用。用摆放黑棋或摆放白棋两种情况，以此来区分两个组。
寻找恋人的思考题
在一个小王国中，有8个村子（A-H），如图所示，各个村之间有道路相连（黑点表示村子，线表示道路）。而你要寻找流浪在这个王国的你唯一的恋人。你的恋人住在这8个村子中的某一个里。 她每过1个月便顺着道路去另一个村子，每个月都一定会换村子，然而选择哪个村子是随机的，预测不了。例如，如果恋人这个月住在G村，那么下个月就住在“C,F,H”中的某个村子。
目前你手上掌握的信息只有，1年前（12个月前），恋人住在G村。请求出这个月恋人住在A村的概率。
image.png
提示：先试算较小的数
恋人12个月前住在G村。那就意味着，在这12个月中，恋人从G开始随机地移动了12次。这次的问题就是要求出移动12次后恋人在A处的概率。
我们先不考虑12次的移动，还是从较小的数着手。
12个月前（第0次移动），恋人在G;
11个月前（第1次移动），恋人在C,F,H其中之一
10个月前 (第2次移动)，恋人在B,D,E,G其中之一
9个月前（第3次移动），恋人在A,C,F,H其中之一
8个月前（第4次移动），恋人在B,D,E,G其中之一
从这之后，奇数次移动时，恋人在A,C,F,H其中之一；偶数次移动时，在B,D,E,G其中之一。因此我们得出，现在（第12次移动）恋人在B,D,E,G其中之一，并不在A村。即概率为0
回顾
这个问题的有趣之处在哪儿呢？
恋人游移不定地在各个村子之间碾转。如果考虑恋人所经过的路线的话，就必须研究很多种可能性。
而在刚才的答题过程中，我们并不着眼于路线，而是关注目的地。这样问题就迎刃而解了。
以G为起点，我们将恋人移动奇数次到达的目的地称为“奇数村”，移动偶数次到达的目的地称作“偶数村”
image.png
奇数村：A,C,F,H
偶数村：B,D,E,G
本题的解答要点是：不是分别考虑这8个村的情况，而是将8个村分为奇数村和偶数村2组来解答。因为就算不知道第12次移动具体到达了8个村里的哪个村，但能知道是在奇数村还是偶数村。
A-H这8个村没有一个是既属于奇数村又属于偶数村的。并且，所有这8个村必定属于奇数村或偶数村的其中之一。即，奇数村和偶数村的分类是“兼具排他性和完整性的分类”。并且，从奇数村移动1次就到了偶数村，从偶数村移动一次就到了奇数村。通过该规律，就能够解答这个问题。本题也是奇偶校验的一个例子。
本章小结
- 对于难以处理的庞大数值，只要发现其周期性并使用余数，就能简化问题。
- 还可以根据余数结果的差异，将许多事物进行分组。
- 当我们“想要详细地研究”事物时，往往容易陷入“想正确把握所有细节”的思维。但是，像奇偶性校验那般，较之“正确地把握”，有时“准确地分类”则更加有效
