类别-编号

题目

遁去的1

来源

1

N阶楼梯上楼问题

N阶楼梯上楼问题:一次可以走两阶或者一阶，问有多少种上楼方式(要求采用非递归)

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186333

2

不容易系列之一

给N个网友写信，所有信全部装错信封有多少种可能的错误方式

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186349

3

最长递增子序列问题

在一个已知的序列{a1,a2,...,an}中，取出若干数组组成的序列{ai1,ai2,..,aim},其中下标i1,i2,...,im保持递增，即新增数列中的各个数之间依旧保持原数列中的先后顺序，那么称新的序列为原序列的一个子序列。若在序列中，下标ix > iy时，aix > aiy，称这个子序列为原序列的一个递增子序列。

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186395

4

拦截导弹

导弹系统有缺陷，后面炮弹高度<=前一发高度。计算系统能拦截多少导弹。拦截时，必须按照时间顺序，不允许先拦截后面的导弹再拦截前面的导弹。

输入:每组输入两行。第一行:导弹数量k(k<=25)。第二行:k个整数，表示第k枚导弹的高度，按时间顺序，空格分隔

输出:每组输出一行，包含一个整数，表示能拦截多少导弹。

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186409

5

最长公共子序列

字符串S中按照先后顺序依次取出若干字符，并将它们排列成一个新的字符串，这个字符串就称为原字符串的子串。有2个字符串S1和S2，求字符串S3同时为S1和S2的子串，且要求它的长度最长，确定这个长度。

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186443

6

搬寝室

n件物品，n<2000.准备搬2*k(<=n)件物品。每搬一次的疲劳度和左右手之间的重量差的平方成正比。请求出办完这2*k件物品后的最低疲劳度是多少

输入:每组输入数据有2行，第一行有2个数n,k(2<=2*k<=n<2000),第二行有n个整数，分别表示n件物品的重量(<2的15次方)

输出:对应每组输入数据，输出数据只有一个表示他的最少的疲劳度，每个一行.

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186477

7

Greedy Tino

有一堆柑橘，重量为0到2000，总重量不大于2000。从中取出两堆放在扁担两头，且两头重量相等，问符合条件的的每堆重量最大是多少。没有符合条件的分堆方式则输出-1

输入:第一行时t,表示t个测试用例，对每个测试用例，包含一个数字n,表名橘子数。第二行有n个数字，表明每个橘子的重量，1<=n<=100.如果是因为存在重量为0的橘子，导致扁担两边重量为0，那么应该输出0,否则输出-1

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186505

8

采药

不同草药，采每一株需要一些时间，每一株有自己价值，如何让采到的价值最大。

输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)，T代表总共能够用来采药的时间，M代表山洞里的草药数目。

接下来的M行，每行包括两个在1到100之间(包括1和100)的整数，分别表示采摘某株草药的时间和这株草药的价值

输出:在规定时间内，可以猜到的草药的最大总价值

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186535

9

Piggy-Bank

有一个储蓄罐，告知空的质量和当前重量，并给定一些钱币的价值和相应的重量，求储蓄罐中最少有多少现金。

输入:包含T组测试用例。第一行。每一个测试用例包含2个整数E和F，表明空储蓄罐的重量和装满钱的重量。<=10,000g，第二行是每个测试用例，包含一个整数N(1<=N<=500)，

     给出了各种硬币的数量。接下来是N行，每行表示一种硬币类型，每行包括2个整数，P,W(1<=p<=50000,1<=W<=10000)，p是价值，W是重量

输出:

储蓄罐中最少有多少钱

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/97750459

10

珍惜现在，感恩生活

支援灾区。你有n元，市场有m种大米，每种打磨都是袋装产品，价格不等，并且只能整袋购买。你最多能采购多少公斤粮食

输入:第一行1个正整数C(表示有C组测试用例)，每组测试用例的第一行时两个整数n和m(1<=n<=100,1<=m<=100)，分别表示经费的金额和大米的种类，然后是m行数据。

每行包括3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

输出:输出能够购买大米最多重量，经费可以不用完

计算机考研—机试指南

https://blog.csdn.net/qingyuanluofeng/article/details/47186603

11

连续子数组的最大和:

输入一个整形数组，数组里有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的

最大值。要求时间复杂度为O(n)

剑指offer

https://blog.csdn.net/qingyuanluofeng/article/details/39186633

12

数塔问题

有形如右图的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大

算法设计与分析

https://blog.csdn.net/qingyuanluofeng/article/details/47189313

13

TSP之货郎担问题

如果对于任意数目的n个城市，分别用1~n编

号，则这个问题归结为在有向带权图中，寻找一

条路径最短的哈密尔顿回路问题。

这里，V表示城市顶点，（i,j) ∈E 表示城市之

间的距离，用邻接矩阵C表示城市之间的距离。

算法设计与分析

https://blog.csdn.net/qingyuanluofeng/article/details/47189319

14

多段图的最短路径问题

定义： 给定有向带权图G(V,E,W)，如果把顶点集合V划分成k个不相交的子集V i ，1≤i ≤k，k≥2，使得E中的任何一条边

(u,v)，必有uЄ V i， v ∈ V i+m  ，m≥1，则称这样的图为多段图。

算法设计与分析

https://blog.csdn.net/qingyuanluofeng/article/details/47189329

15

资源分配问题

资源分配问题:是考虑如何把有限的资源分配给

若干个工程问题。假设资源总数为 r，工程个数为n，给每个工程投入的资源不同，所得的利润也不同，要求把总数为 r 的资源分配给n个工程，以获得最大利润的分配方案

算法设计与分析

https://blog.csdn.net/qingyuanluofeng/article/details/47189335

16

最长公共子序列

假定，A=a 1 a 2 …a n 是字母表∑上的一个字符序列，如果存在

∑上的另外一个字符序列S=c 1 c 2 …c j ，使得对所有的k,

k=1,2,…,j，有c k =a ik （其中，1≤ik≤n），是字符序列A的一个下标递增序列，则称字符序列S是A的子序列。

如果∑={x,y,x}， ∑上的字符序列是A=xyzyxzxz，则xxx是A的

一个长度为3的子序列。该子序列中的字符，对应于A的下

标是1,5,7。而xzyzx是A的长度为5的子序列，对应于A的下

标是1,3,4,6,7.

算法设计与分析

https://blog.csdn.net/qingyuanluofeng/article/details/47189343

17

仪器维修时间表问题

一台精密仪器的工作时间为 n 个时间单位, 与仪器工作时间同步进行若干仪器维修程序. 一旦启动维修程序, 仪器必须进入维修程序. 如果只有一个维修程序启动, 则必须进入该维修程序. 如果在同一时刻有多个维修程序, 可任选进入其中的一个维修程序. 维修程序必须从头开始,不能从中间插入. 一个维修程序从第 s 个时间单位开始, 持续 t 个时间单位, 则该维修程序在第 s+t-1 个时间单位结束. 为了提高仪器使用率, 希望安排尽可能少的维修时间. 

对于给定的维修程序时间表, 计算最优时间表下的维修时间.

输入数据的第 1 行有 2 个小于 10000 的正整数 n 和 k, n 表示仪器的工作时间单位, k 是维修程序数. 接下来的 k 行中, 每行有 2 个表示维修程序的整数 s 和 t, 该维修程序从第 s 个时间单位开始, 持续 t 个时间单位.

算法设计与分析

https://blog.csdn.net/qingyuanluofeng/article/details/47189359