【读书笔记】趣味数学及编程拓展(第2版) 第5章
第5章精巧求解剖析
精巧求解，是指，巧解、精解，巧和精结合求解，凝聚数学的精华，彰显出编程的卓越。
5.1和与积巧算
5.1.1互积和
【编程题】
给定n个整数，对这n个整数求任意2个数之积，任意3个数之积，......，直至所有n个整数之积。把所有这些积求和称为这些整数的互积和m。
【妙思巧解】
巧妙构造多项式化互积为多项式积。
n个整数记为a1、a2、a3、......、an
m = (1+a1)(1+a2)...(1+an) - (a1+a2+...+an) - 1
这样，用循环就一个积，就可以巧妙的求解整数的互积和。
5.1.2嵌套根式和
设计要点：处理根号嵌套，要逆向处理循环，从最内层根号开始，直至最外层根号。
5.2同码数汇趣
由同一个数码组成的数称为同码数。如5555是同码整数；0.77777是同码小数。
5.2.1同码数整除
【编程题】探求同码数能被p整除。
采用模拟竖式除法。
5.2.2同码数求和
【编程题】求同码整数和。S(d, n) = d + dd + ddd + dddd + ... + dd...d(n个d)
s用数组存储，数组每个单元存储一位数字。
从个位开始，相加和进位。
5.3统计的智慧
5.3.1巧妙建模
【编程题】
对于给定的正整数和s，对于3个变量x, y, z的不定方程x+y+z = s，试统计x, y, z取自区间[c, d](0 ≤ c < d, 3c ≤ s)整数解的组数。
设计要点：循环，依次探求即可
5.3.2三角网格统计
把一个正三角形的三边分成n等份，分别与各边平行连接各分点，得n-三角网格。
【编程题】
对于指定正整数n，试求n-三角形网格中所有不同三角形（大小不同或方位不同）的个数，以及所有这些三角形的面积之和（约定网格中最小的单位三角形的面积为1）
设计要点：从最上层得单位三角形开始，推导计算公式。
5.3.3交通方格网
用典型的矩形方格网表示交通网。
【编程题】
给定一个交通方格网，其中有路障禁止通行，（路线中各段只能从左至右，从下至上），求从起始点（0，0）到终点（m，n）的最短路线的条数。
设计要点，用递推求得点(x, y)和前点(x-1, y)与(x, y-1)的关系
5.4游戏中的素数概率
5.4.1从摇骰子到抽数牌
【编程题】抽数牌之和为素数的概率。
有n张数字牌，数字牌上分别标有整数1，2，3，……，n。
输入牌的张数n（10<n<1000），分别计算抽取2张与抽取3张牌，这两种抽牌整数之和为素数的概率，并分别指出出现概率最高的素数（精确到小数点后3位）。
设计要点：注意循环枚举时设置正确，以免出现遗漏或重复；用试商判别法判别素数。
涉及概率计算，必须统计事件的总体数与满足指定条件事件个数，这是概率计算的基础。
5.4.2抽扑克牌
【编程题】扑克牌，除取大小王，有四种花色牌，每种花色有A，2，3，4，...，10，J，Q，K（约定A为数码为1，J，Q，K分别为11，12，13），即每种花色有13个数码牌。
分别计算抽取2张与抽取3张牌，这两种抽牌整数之和为素数的概率。
设计要点，用数组依次存储四种花色的牌，其他同5.4.1
5.5梅齐里亚克砝码问题
梅齐里亚克砝码问题
一位商人有一个40磅的砝码，由于跌落在地而碎成4块.后来，称得每块碎片的重量都是整磅数，而且可以用这4块来称从1至40磅之间的任意整数磅的重物.问这4块砝码碎片各重多少？
此类问题后来拓展成数学中一类“称重问题”，引起人们广泛关注。
5.5.1单砝码盘称重
单砝码天平，规定只能在砝码盘放砝码，而称重盘只能放物品不能放砝码。
【编程题】
一人要用整数m克材料制作n个砝码，可以用这n个砝码在单码盘天平上称1~m克的任意整数克质量。
输入整数m及指定整数质量t（m≤1000，t≤m），输出砝码至少个数n及这n个砝码的质量，并输出在天平商称重t的砝码配置方案。
设计要点，当n块砝码质量分别为1，2，2^2，... ，2^(n-1)时，
m = 1+2+2^2+... +2^(n-1) = 2^n - 1
可在单码盘天平上实现称1~m的任意整数质量。
5.5.2双砝码盘称重
双砝码盘，天平的两个盘都能放砝码。
【编程题】
一人要用整数m克材料制作n个砝码，可以用这n个砝码在双码盘天平上称1~m克的任意整数克质量。
输入整数m及指定整数质量t（1<t<m），输出砝码至少个数n及这n个砝码的质量。
设计要点，当n块砝码质量分别为1，3，3^2，... ，3^(n-1)时，
m = 1+3+3^2+... +3^(n-1) = (3^n - 1)/2
可在双码盘天平上实现称1~m的任意整数质量。
5.60-1串积与多码串积
5.6.1探求0-1串积
【编程题】
输入整数b，试寻找最小的整数a，使得a x b为0-1串积。
设计要点，不要枚举整数a来探求，工作量非常大，而通过枚举串积来探求，工作量相对要小得多。从小到大搜索0-1串积（要看作十进制数），从中找出最小的能被b整除的0-1串积。
5.6.2指定多码串积
【编程题】
输入两个数码v, u（约定0 ≤ v < u ≤ 9），对指定的正整数b，试探求最小的正整数a，使得a x b全由数字v与u组成。
设计要点：应用求余数判别指定n码串积。
5.7精妙的尾数前移
【编程题】
整数n的尾数q（可为多位）移到n的前面所得的数为n的p倍，记为n(q, p)。这里正整数p不大于前移尾数q的首位。对于指定的尾数q与倍数p，求解n(q, p)。
设计要点：用数组存储整数的各位数字，应用模拟竖式除法计算。
5.8伯努利装错信封问题
排列的定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m)。
组合的定义：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。
5.8.1实现排列组合
【编程题】
输入正整数n，m，实现排列A(n,m)与组合C(n,m)，并输出。
设计要点：应用回溯法设计
5.8.2全错位排列
某人想邀请朋友来家中聚会，写好了n封请柬，需要装入n个信封，结果因为粗心把请柬全部装错了信封。请问：装错的可能会有多少种呢？
设计要点，可以用枚举法，或者用递推数列法
5.9两个“幽灵”e和π
e和π都是无限不循环小数，试超越数，在数学上称为幽灵。
5.9.1自然对数的底e
【编程题】
试设计程序计算自然对数的底e，精确到小数点后指定的x位。
设计要点：选择计算自然对数的底e的公式，确定计算项数，模拟竖式除法
5.9.2圆周率π
【编程题】
试设计程序计算圆周率π，精确到小数点后指定的x位。
【读者体会】
这一章介绍了一些精巧求解例题。
编程设计要点。找到巧妙的求解公式。
