一些程序设计训练相关的题目，及其报告

题 1：数码管

一、问题描述

【问题描述】

液晶数码管用七笔阿拉数字表示的十个数字，把横和竖的一 个短划

都称为一笔，即７有３笔，８有７笔等。对于十个数字一种排列，要

做到两相邻数字都可以由另一个数字加上几笔或减去几笔组成，但不

能又加又减。比如 ７→３是允许的，７→２不允许。任意输入一组

数，判断是否符合上述规则，注意，1 在右边。

【输入形式】

3 5 1 6 2 7 9 0 4 8

-1

【样例输出】

YES

NO

二、问题分析及边界条件

要处理的问题就是如何判断相邻的两个数字是否可以相互转变，只

要这个问题解决了，本题就迎刃而解了。

YES。

四、详细设计（从算法到程序）

1.用字符串 s 来存储可以相互转换的数字，如 01、07……注意每个

字符串要以逗号分隔开。

2.在输入的时候将数字转化成字符存储进字符串 str 中，str.push_

b ack ((a+'0'))。

3.for()循环遍历字符串 str，截取相邻的两个字符，

str.substr(i,2)。

4.如果 s.find(ss)!=s.npos，说明这两个数字可以转化，sum++。

5.循环结束后，if(sum==9)，输出 YES。

4 1 0 7 3 9 5 6 8 2

YES

3 5 1 6 2 7 9 0 4 8

NO

-1

Process exited after 7.651 seconds with return value 0

请按任意键继续. . .

-1

Process exited after 46.37 seconds with return value 0

请按任意键继续. . .

六、分析与总结

如果想不出其他方法，有时候像这个题一样先把所有情况（前提是不

复杂）列举出来也不失为一个好方法；单个数字转换成字符，+ ‘0’

即可；字符截取函数 substr（）的用法；字符串中 find（）函数的

用法，如果找到字符串，表达式为 s.find(ss)!=s.npos。

题 2：最大报销额

一、问题描述

含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N<=30）是发票

张数。随后是 N 行输入，每行的格式为：

m Type_1:price_1 Type_2:price_2 … Type_m:price_m

其中正整数 m 是这张发票上所开物品的件数，Type_i

和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文

字母表示。当 N 为 0 时，全部输入结束，相应的结果不要输出。

【输出形式】对每个测试用例输出 1 行，即可以报销的最大数额，精

确到小数点后 2 位。

【样例输入】

200.00 3

1200.00 2

2 B:600.00 A:400.00

100.00 0

【样例输出】

123.50

1000.00

1200.50

二、问题分析及边界条件

本题主要就是对数据的处理，如果成功的得到数据，那么剩下的就只

是普通的 0-1 背包问题。

三、算法设计

每张发票上的物品数为 m，然后输入 m 个字符串，接下来就是对这些

字符串进行处理，每个字符串的前两个字符是固定的，只需要删除，

剩下的就是数字字符串了，只需要将其转化成数字即可，同时对照题

目要求，将最终满足题意可以报销的发票上的钱数依次存储进 vector

容器中，0-1 背包问题，可以把给定的报销额度*100（因为是小数）

看作背包容量，可以报销的钱数*100（对照上面的报销额）看作每个