pascal中级教程第九章数学问题Word下载.docx
《pascal中级教程第九章数学问题Word下载.docx》由会员分享，可在线阅读，更多相关《pascal中级教程第九章数学问题Word下载.docx（21页珍藏版）》请在冰点文库上搜索。
整理得到：
①
所以要想求（x1+x2+…+xt）n的任意一项
的系数只要将①式中令x1=x2=…=xt=1，得到
（2）因为
……
所以
（3）由分析
（1）、
（2）求
的系数化为求上述的除法运算：
①先计算n!
；
②将n!
逐一去除n1,n2,…,nt；
③最后的商为所求结果。
由于题目所给n≤12，计算n!
可在长整型范围内，无需采用高精度运算。
设数组no:
array[1..t]为nt；
total为n!
。
主要算法描述如下
total:
=1;
fori:
=1tondototal:
=total+i;
{求n!
}
=1totdo
forj:
=1tono[i]do
total:
=totaldivj;
{整除n!
9.2两数之和
源程序名pair.?
可执行文件名pair.exe
输入文件名pair.in
输出文件名pair.out
我们知道从n个非负整数中任取两个相加共有n*（n-1）/2个和，现在已知这n*（n-1）/2个和值，要求n个非负整数。
输入文件仅有一行，包含n*（n-1）/2+1个空格隔开的非负整数，其中第一个数表示n（2<
n<
10），其余n*（n-1）/2个数表示和值，每个数不超过100000。
输出文件仅一行，按从小到大的次序依次输出一组满足要求的n个非负整数，相邻两个整数之间用一个空格隔开；
若问题无解则输出“Impossible”。
pair.inpair.out
3126911601663383777886
本题的规模只有10，看似一道搜索题。
其实不然，搜索固然有可能出解，但是本题是有多项式级算法的。
本题的难点就在于要理清这看似混乱的n（n-1）/2个“和”的关系，从中寻找突破口。
那么，突破口在哪里呢?
n（n-1）/2个“和”是任意给出的，并未按照什么指定的顺序，所以从表面上看这些数（和）之间似乎没有什么区别。
当然，我们必须在这些数（和）中制造出一些区别来，因为没有区别我们也就无从下手。
对什么信息也没有的一些数，惟一可以制造出的区别就是它们之间的大小关系。
根据数的大小关系，我们可以对这n（n-1）/2个数排序。
排完序后，可以成为突破口的无非就是那么几个，最小的数（和）、最大的数（和）、中位数……我们不可能随便找一个数出来作为突破口，因为随便找一个数的话，大小关系就失去意义了。
所以，这时我们需要注意的只有这么几个数了：
最小的数（和）、最大的数（和）和中位数。
中位数看上去似乎也很难成为突破口，因为我们无法预知中位数是哪两个数的和。
而最小、最大的两个数（“最小的和”与“最大的和”）则不同，最小的和必然是最小的两个数之和，最大的和必然是最大的两个数之和。
由问题对称性，最小与最大其实是等价的，所以我们可以只考虑最小的情况，解决了最小，最大也就相应解决了。
最小的和是最小的两个数之和，这是一条已经确定的与最小的两个数相关的信息。
当然，就凭这些信息，我们还是无法知道最小的两个数究竟是多少，这是我们目前面临的一个障碍。
我们不妨先跳过这个障碍，考虑以后的问题。
我们可以假设已经知道最小的数的大小，这样我们又可以很顺利的知道次小的数是多少了（最小的和-最小的数）。
知道最小的两个数的大小对我们有什么好处呢？
其实关键是知道最小的数是多少，这是至关重要的，因为很多特殊的和都与最小的数有关。
试想，我们知道了最小的两个数，也就确定了一个和（最小的和）。
把这个“和”从n（n-1）/2个和中去掉，剩下的n（n-1）/2-1个和中又会产生新的最小的和。
这个新的最小的和是哪两个数的和呢?
应该是最小的数与第三小的数的和。
由于我们假设已经知道最小的数，我们自然就可以通过作差得到第三小的数了。
得到前三小的数后，我们就确定了3个“和”了。
籽这三个“和”从n（n-1）/2个和中去掉，剩下的n（n-1）/2-3个和中又会产生新的最小的和。
这个新的最小的和必然是最小的数与第四小的数的和。
由于最小的数已知，第四小的数就可以算出了。
更一般的情况，知道了前k小的数，那么我们就确定了k（k-1）/2个和了。
将这k（k-1）/2个和从n（n-1）/2个和中去掉，剩下的n（n-1）/2-k（k-1）/2个和中又会产生新的最小的和。
这个新的最小的和必然是最小的数与第k+1小的数的和。
由于最小的数已知，第k+1小的数就可以通过作差得到。
如此，在知道了最小的数的情况下，不断的从当前最小的和入手，就可以从小到大依次把所有的数都推算出来了。
不过，有一点还是需要注意的，前面所有的推导都是建立在最小的数已知的情况下的，但实际情况是最小的数未知。
所以，我们还需要创造条件，使最小的数由未知变为已知。
一个简单而可行的方法就是枚举最小的数。
简单就不必说了，为什么说枚举是可行的呢?
因为题目规定所有的数都不超过100000，因此总共需要枚举的方案数最多只有100000。
而在知道最小的数的情况下，推算出其他数的代价是O（n2），n≤10。
100000*102的计算代价是可以承受的。
最后，我们总结一下前面得到的算法。
（1）枚举最小的数；
（2）根据最小的数和最小的和，得到次小的数；
（3）由前k小的数推出第k+1小的数。
算法的时间复杂度是O（Cn2），其中C表示数值的大小。
从本题的解题过程中，我们看到其中最关键的一步就是以最小的和作为突破口。
在解决数学问题的时候，很多情况下从为数不多的信息中寻找突破口是至关重要的。
找到了突破口，问题本身也就迎刃而解了。
9.3盒子与球
源程序名box.?
可执行文件名box.exe
输入文件名box.in
输出文件名box.out
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子。
问有多少种方法？
例如：
有2个不同的盒子（分别编为1号和2号）和3个不同的球（分别编为1、2、3号），则有6种不同的方法：
1号盒子
1号球
1、2号球
1、3号球
2号球
2、3号球
3号球
2号盒子
两个整数，n和r，中间用空格分隔。
（0≤n,r≤10）
表示n个球放入r个盒子的方法。
box.in
32
box.out
6
第二类Stirling数。
先考虑三种情况：
（1）若盒子数r大于球数n，根据题意不允许有空盒的要求，放置的方法数为零；
（2）若r＝1，则只有一种放法；
（3）若r＝n，相当于将n个不同的球进行排列，故有n！
种。
下面考虑1<
r<
n的情况。
n个不同的球放入r个不同的盒子中，可以先把r个盒子视为相同的，即先求出n个不同的球放入r个相同的盒子中，且不允许有空盒子的不同方案数，设为S（n,r）；
再将r个盒子进行全排列，共有r!
记号f（n,r）为n个不同的球放入r个不同盒子中，且不允许有空盒子的不同放法，根据乘法原理，有f（n,r）=S（n,r）·
r!
如何求S（n,r）?
请看如下定义：
定义n个有区别的球放入r个相同的盒子中，要求无一空盒，其不同的方案数s（n,r）称为第二类Stirling数。
红（k）、黄（y）、蓝（b）、白（w）四种颜色的球，放入两个无区别的盒子里，不允许空盒，其方案数共有如下7种：
方案
1
2
3
4
5
6
7
第1盒子
r
y
b
w
ry
rb
rw
第2盒子
ybw
rbw
ryw
ryb
bw
yw
yb
所以S（4,2）=7
下面就1≤n≤5，1≤r≤n列出各个S（n,r）的植如下
n
15
25
10
定理第二类Stirling数满足下面的递推关系
S（n,r）=r·
S（n-1,r）+S（n-1,r-1）（n>
1,r≥1）
证明：
设n个不同的球为b1,b2,…,bn，从中取一个球设为b1。
把这n个球放入r个盒子无一空盒的方案全体可分为两类：
（1）b1独占一盒，其余n-1个球放入r-1个盒子无一空盒的方案数为S（n-1，r-1）
（2）b1不独占一盒，这相当于先将b2,b3,…,bn。
这n-1个球放入r个盒子，不允许有空盒的方案数共有S（n-1,r），然后将b1放入其中一盒，这一盒子有r种可挑选，故b1不独占一盒的方案数为r·
S（n-1,r）。
根据加法原理，则有：
S（n,r）＝r·
S（n-1,r）+S（n-1,r-1）（n>
1，r≥1）
对于n＝r，或r＝1，显然有S（n,n）＝1，S（n,1）＝1。
综上所述，本题的算法可用第二类Stirling数的递推关系先求出S（n,r），再乘上r!
，即得所求方案数。
主要算法描述如下：
（1）数据结构
constmaxn=10{球的最大数目}
vars:
array[0..maxn,0..maxn]oflongint;
{存放第二类数}
（2）用下列二重循环求S（n,r）
①置S[0,0]=1;
②fori:
=1tondo
forj:
=1tordo
S（i,j）=i*S（i-1,j）+S（i-1,j-1）
③计算方案数S
S:
=S[n,r]
Fori:
=1tordoS:
=S*I;
9.4取数游戏
源程序名cycle.?
可执行文件名cycle.exe
输入文件名cycle.in
输出文件名cycle.out
有一个取数的游戏。
初始时，给出一个环，环上的每条边上都有一个非负整数。
这些整数中至少有一个0。
然后，将一枚硬币放在环上的一个节点上。
两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下：
（1）选择硬币左边或者右边的一条边，并且边上的数非0；
（2）将这条边上的数减至任意一个非负整数（至少要有所减小）；
（3）将硬币移至边的另一端。
如果轮到一个玩家走，这时硬币左右两边的边上的数值都是0，那么这个玩家就输了。
如下图，描述的是Alice和Bob两人的对弈过程，其中黑色节点表示硬币所在节点。
结果图（d）中，轮到Bob走时，硬币两边的边上都是0，所以Alcie获胜。
（a）Alice（b）Bob（c）Alice（d）Bob
现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。
第一行一个整数N（N≤20），表示环上的节点数。
第二行N个数，数值不超过30，依次表示N条边上的数值。
硬币的起始位置在第一条边与最后一条边之间的节点上。
仅一行。
若存在必胜策略，则输出“YES”，否则输出“NO”。
cycle.incycle.out
4YES
2530
3NO
000
【问题分析】
本题的数据规模（N≤20，边上的数值不超过30）实际上是一个幌子，是想误导我们走向搜索的道路。
考虑一个简化的问题。
如果硬币的一边的数值为0，那么惟一可能取胜的走法就是向另一边移动，并且把边上的数减到0。
因为如果不把边上的数减到0，那么下一步对方会将硬币移动到原来的位置，并且将边上的数减到0，这样硬币两边的数值就都为0了。
所以，对于一边有0的情况，双方惟一的走法就是不停的向另一边移动，并取完边上的数值。
因此，判断是否有必胜策略，就是看另一个方向上连续的非零边是否为奇数条。
那么两边都非零的情况呢?
如果有一个方向上连续的非零边为奇数条，那么显然是有必胜策略的，因为只需往这个方向走并取完边上的数即可。
如果两个方向上连续的非零边都是偶数条，则没有必胜策略。
因为不管往哪个方向走，必然不能取完边上的数，否则必败。
如果不取完，则下一步对方可以将硬币移动回原来的位置并取完边上的数，这样就变成了一边为0、另一边有偶数条连续的非零边的情况，还是必败。
所以，对于一般的情况，只需判断硬币的两边是否至少有一边存在奇数条连续的非零边。
如果存在，则有必胜策略；
否则无必胜策略。
算法的时间复杂度为O（N）。
9.5磁盘碎片整理
源程序名defrag.?
可执行文件名defrag.exe
输入文件名defrag.in
输出文件名defrag.out
出于最高安全性考虑，司令部采用了特殊的安全操作系统，该系统采用一个特殊的文件系统。
在这个文件系统中所有磁盘空间都被分成了相同尺寸的N块，用整数1到N标识。
每个文件占用磁盘上任意区域的一块或多块存储区，未被文件占用的存储块被认为是可是用的。
如果文件存储在磁盘上自然连续的存储块中，则能被以最快的速度读出。
因为磁盘是匀速转动的，所以存取上面不同的存储块需要的时间也不同。
读取磁盘开头处的存储块比读取磁盘尾处的存储块快。
根据以上现象，我们事先将文件按其存取频率的大小用整数1到K标识。
按文件在磁盘上的最佳存储方法，1号文件将占用1,2,…,S1的存储块，2号文件将占用S1+1,S1+2,…，S1+S2的存储块，以此类推（Si是被第i个文件占用的存储块的个数）。
为了将文件以最佳形式存储在磁盘上，需要执行存储块移动操作。
一个存储块移动操作包括从磁盘上读取一个被占用的存储块至内存并将它写入其他空的存储块，然后宣称前一个存储块被释放，后一个存储块被占用。
本程序的目的是通过执行最少次数的存储块移动操作，将文件安最佳方式存储到磁盘上，注意同一个文件的存储块在移动之后其相对次序不可改变。
每个磁盘说明的第一行包含两个用空格隔开的整数N和K（1≤K≤N≤100000），接下来的K行每行说明一个文件，对第i个文件的说明是这样的：
首先以整数Si开头，表示第i个文件的存储块数量，1<
=Si<
=N-K，然后跟Si个整数，每个整数之间用空格隔开，表示该文件按自然顺序在磁盘上占用的存储块的标识。
所有这些数都介于1和N之间，包括1和N。
一个磁盘说明中所有存储块的标识都是不同的，并且该盘至少有一个空的存储块。
对于每一个磁盘说明，只需输出一行句子“WeneedMmoveoperations”，M表示将文件按最佳方式存储到磁盘上所需进行的最少存储块移动操作次数。
如果文件已按最佳方式存储，仅需输出“Nooptimizationneeded.”。
defrag.indefrag.out
203Weneed9moveoperations
4231112
17
318510
本题可以看作是一个置换的调整问题。
按文件块的目标位置对文件块编号后，调整文件块位置的问题就转化为调整置换的问题了。
不过，本题还有一点特殊之处，就是存在一些数，它们不要求归位，这些数可作为交换空间。
找出所有的循环节，分情况讨论。
如果一个循环节上所有的数都是要求归位的，那么必须先利用交换空间将一个数先交换出去，然后其他数都归位，最后再把交换出去的数换回来。
如果这个循环节上有不需要归位的数，则可直接贪心，将可以归位的尽量归位即可。
9.6欧几里德的游戏
源程序名game.?
可执行文件名game.exe
输入文件名game.in
输出文件名game.out
欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。
给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。
然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。
下面是他们用（25，7）两个数游戏的过程：
Start：
257
Stan：
117
Ollie：
47
43
13
10
Stan赢得了游戏的胜利。
现在，假设他们完美地操作，谁会取得胜利呢？
第一行为测试数据的组数C。
下面有C行，每行为一组数据，包含两个正整数M,N。
（M,N不超过长整型。
）
对每组输入数据输出一行，如果Stan胜利，则输出“Stanwins”；
否则输出“Olliewins”
game.ingame.out
2Stanwins
257Olliewins
2415
这是一道博弈题。
解题的关键在于把握胜负状态的关系。
任意的状态只有两种可能：
一种可能是胜状态——即有必胜策略，另一种可能是负状态——即没有必胜策略。
对于任意的胜状态，无论如何走，都不可能走到另一个胜状态；
而任意的负状态，至少存在一种走法可以走到胜状态。
（0,0）是初始的胜状态。
考察任意的状态（a,b），不妨假设a≥b。
如果
<
2，则只有一种走法，即将（a,b）变为（a-b,b）。
那么，（a,b）是何种状态就取决于（a-b,b）是何种状态：
根据前面胜负状态的定义可知，（a-b,b）为胜状态时，（a,b）为负状态；
（a-b,b）为负状态时，（a,b）为胜状态。
如果
≥2，则至少存在两种走法：
将（a,b）变为（c,b）或（c+b,b），这里c＝amodb。
如果这两个状态中至少有一个是负状态，则根据定义（a,b）是胜状态。
如果两个状态都是胜状态，由于（c+b,b）可以变为（c,b），这就与“胜状态只能走到负状态”产生了矛盾，所以两个状态都是胜状态的情况是不存在的。
因此，
≥2时，（a,b）必为胜状态。
总结一下前面的结论，设f（a,b）为状态（a,b）的胜负情况（1表示胜状态，0表示负状态），a≥b，则：
1、
2、
9.7百事世界杯之旅
源程序名pepsl.?
可执行文件名pepsl.exe
输入文件名pepsl.in
输出文件名pepsl.out
“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。
只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。
还不赶快行动！
”
你关上电视，心想：
假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？
整数n（2≤n≤33），表示不同球星名字的个数。
输出凑齐所有的名字平均需要买的饮料瓶数。
如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为：
3
5--
20
第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。
减号的个数应等于分母的为数。
分子和分母的首位都与第一个减号对齐。
分数必须是不可约的。
pepsi.inpepsi.out
23
【提示】
“平均”的定义：
如果在任意多次随机实验中，需要购买k1,k2,k3,…瓶饮料才能凑齐，而k1,k2,k3,…出现的频率分别是p1,p2,p3,…，那么，平均需要购买的饮料瓶数应为：
k1*p1+k2*p2+k3*p3+…
这道题目主要考察的是数学的推导能力。
假设f[n,k]为一共有n个球星，现在还剩k个未收集到，还需购买饮料的平均次数。
则有：
经移项整理，可得：
我们所要求的实际上应该是f（n,n），根据f（n,k）的递推式，可得
其中，H（n）表示HarmonicNumber。
9.8倒酒
源程序名pour.?
可执行文件名pour.exe
输入文件名pour.in
输出文件名pour.out
Winy是一家酒吧的老板，他的酒吧提供两种体积的啤酒，aml和bml，分别使用容积为aml和bml的酒杯来装载。
酒吧的生意并不好。
Winy发现酒鬼们都非常穷。
有时，他们会因为负担不起aml或者bml啤酒的消费，而不得不离去。
因此，Winy决定出售第三种体积的啤酒（较小体积的啤酒）。
Winy只有两种杯子，容积分别为aml和bml，而且啤酒杯是没有刻度的。
他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。
为了简化倒酒的步骤，Winy规定：
（1）a≥b；
（2）酒桶容积无限大，酒桶中酒的体积也是无限大（但远小于桶的容积）；
（3）只包含三种可能的倒酒操作：
①将酒桶中的酒倒入容积为bml的酒杯中；
②将容积为aml的酒杯中的酒倒入酒桶；
③将容积为bml的酒杯中的酒倒入容积为aml的酒杯中。
（4）每次倒酒必须把杯子倒满或把被倾倒的杯子倒空。
Winy希望通过若干次倾倒得到容积为aml酒杯中剩下的酒的体积尽可能小，他请求你帮助他设计倾
升级会员 