《全国青少年信息学 计算机 竞赛例题解析》

第一部分　基础部分3

第一章　PASCAL程序设计基本方法一3

1.1　ASCII码字符串输出3

1.2　求自然数n的不同因数的个数6

1.3　已知因数个数，求n11

1.4　求一元多项式在Xo处的值22

1.5　NOI'95第三题25

1.6　统计输入的字符串中的字母频率28

1.7　NOI'95第一题31

1.8　链表排序问答36

第二章　PASCAL程序设计基本方法二42

2.1　线性表基本操作单元42

2.2　合并线性表46

2.3　以基准数重排顺序51

2.4　带头结点的线性链表基本操作单元56

2.5　逆序合并链表63

2.6　数组元素逆时针方向赋值69

2.7　求幂集79

2.8 自然数n的拆分表达式82

2.9　求n的拆分数目92

第二部分　提高部分101

第三章 自顶向下逐步求精101

3.1　求最大数、最小数和平均值101

3.2　Faibonacci数列102

3.3　求2个数的最大公因子105

3.4　换钱问题107

3.5　求素数109

3.6　求完全数111

3.7　Nicomachus定理及应用113

3.8　字符串统计问题114

3.9　字符串加密116

3.10　统计字符串中字符出现的频率118

3.11　数的排列120

3.12　求出数列的前n项122

3.13　奇数幻方124

3.14　全排列问题126

第四章　回溯算法130

4.1　骑士的游历1130

4.2　骑士的游历2134

4.3　迷宫问题140

4.4　砝码称重144

4.5　钱币问题146

4.6　四色问题148

4.7　无根树的编码151

4.8　背包问题（1）155

第五章　动态规划158

5.1　最短路径问题158

5.2　求最长不下降序列162

5.3　最小代价子母树165

5.4　背包问题（2）171

5.5　四塔问题175

5.6　最小代价178

5.7　挖地雷182

第六章　多精度计算187

6.1　多精度加法187

6.2　多精度减法190

6.3　多精度与单精度乘法194

6.4　多精度与多精度乘法196

6.5　多精度与单精度除法200

6.6　多精度与多精度除法（1）202

6.7　多精度与多精度除法（2）206

6.8　数塔问题210

6.9　计算e220

第七章　递归方法225

7.1　钢板分割成小正方形问题225

7.2　用递归方法求解8皇后问题226

7.3　平面直线交点问题228

7.4　推广的哈夫曼编码230

7.5　表达式去括号238

第八章　其他问题247

8.1　过河问题247

8.2　行程问题（1）256

8.3　行程问题（2）260

8.4　求出方程xn+yn=sn+tn的最小整数解263

8.5　最少转弯问题267

8.6　士兵排队问题270

8.7　逻辑集成电路276

8.8　平面地砖曲线问题281

8.9　1×2的骨牌问题290

8.10　钢板切割零件问题304

8.11　工厂零件生产问题310

8.12　取数问题（1）312

8.13　称球问题313

8.14　堆塔问题315

8.15　取数问题（2）318