step4-算法设计技术

《step4-算法设计技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录算A05缺失的数据（按位排序）1算A06纪念品分组（贪心法）2算A07蛇行矩阵3算A08士兵队列训练问题4算A09绝对值排序5算B01kitty猫的基因编码（递归）6算B02数列（蛮力法）7算B03统计数字（按位排序）8算B04四塔问题（递归）9算B05逆序对个数（蛮力法è分治法）10注：算表示本题属于算法设计技术，A表示简单，B表示稍难。9算A05缺失的数据（按位排序）【问题描述】网络传输中由于受到链路层的最大传输单元(MaximumTransmissionUnit，MTU)的限制，在很多情况下需要对原始的数据报进行分片，使得每一分片可以顺利的传输。F公司的网络设备根据MTU

2、的限制将每个原始的数据划分成n片，用1~n这n个数字对每个分片进行编号，在目的主机上将这些分片重新组合成原始的数据。可是在测试中发现一个问题：经常出现缺失一个数据分片的情况。公司希望在将分片重新组合前就能知道缺失的数据分片编号。【数据输入】有多组输入数据，你必须处理到EOF为止。每组输入数据第一行就一个整数n(2<=n<=105),表示数据分成了n片。第二行有n-1个以空格隔开的整数，表示目的主机收到的数据分片的编号，由于网络传输的一些因素，数据分片到达的顺序是随机的。【数据输出】输出缺失的数据片编号。【样例输入】55321【样例输出】49算A06纪念品分组（贪心法）【问题描述】元

3、旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。【数据输入】输入包含多组测试数据，每个测试数据包含n+2行：第1行包括一个整数w，为每组纪念品价格之和的上限。第2行为一个整数n，表示购来的纪念品的总件数。第3~n+2行每行包含一个正整数pi(5<=pi<=w)，表示所对应纪念品

4、的价格。1<=n<=30000,80<=w<=200【数据输出】对每个测试数据，输出一行，包含一个整数，即最少的分组数目。相邻两个测试数据间用一个空行隔开。【样例输入】1009902020305060708090【样例输出】69算A07蛇行矩阵【问题描述】蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。【数据输入】本题有多组数据，每组数据由一个正整数N组成。（N不大于100）【数据输出】对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。【样例输入】5【样例输出】1361015259144813712

5、119算A08士兵队列训练问题【问题描述】某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。【数据输入】本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。【数据输出】共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。【样例输入】22040【样例输出】17

6、19119379算A09绝对值排序【问题描述】输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。【数据输入】输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。【数据输出】对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。【样例输入】33-424012-30【样例输出】-432-32109算B01kitty猫的基因编码（递归）【问题描述】kitty的基因编码如下定义：kitty的基因由一串长度2^k（k<=8)的01序列构成，为了方便研究

7、，需要把,01序列转换为ABC编码。用T（s)来表示01序列s的ABC编码T(s)＝‘A'（当S全由'0'组成）T(s)＝‘B'（当s全由'1'组成）T(s)＝‘C'+T（s1)+T（s2)s1,s2为把s等分为2个长度相等的子串比如T（'00')='A'T('00001111')='CAB'【数据输入】一行，长度为2^k，为kitty猫的01基因编码，有多个数据【数据输出】一行，由ABC构成的ABC编码【样例输出】01001011【样例输出】CCCABACCBAB9