算法实训
2011-软件091-092-实验一 .............................................................................................................. 3
最大子段和问题一 ................................................................................................................... 3 最大子段和问题二 ................................................................................................................... 3 最大子段和问题三 ................................................................................................................... 4 2011-软件091-092-实验二 .............................................................................................................. 5
找新朋友 ................................................................................................................................... 5 三个师妹之出题 ....................................................................................................................... 5 Sample Input ....................................................................................................................... 6 Sample Output .................................................................................................................... 6 提示: ......................................................................................................................................... 6 整数分解 ................................................................................................................................... 6 2011-软件091-092-实验三 .............................................................................................................. 7
找新朋友 ................................................................................................................................... 7 三个师妹之出题 ....................................................................................................................... 7 Sample Input ....................................................................................................................... 8 Sample Output .................................................................................................................... 8 提示: ......................................................................................................................................... 8 整数分解 ................................................................................................................................... 8 小学生都会算的A+B问题 ..................................................................................................... 9 幂运算精确值计算问题 ........................................................................................................... 9 字母序列 ................................................................................................................................. 10 2011-软件091-092-实验四 ............................................................................................................ 10
最大子段和问题三 ................................................................................................................. 10 2011-软件091-092-实验五 ............................................................................................................ 11
输油管道问题 ......................................................................................................................... 11 众数问题 ................................................................................................................................. 12 邮局选址问题 ......................................................................................................................... 13 半数集问题 ............................................................................................................................. 14 士兵站队问题 ......................................................................................................................... 14 2011-软件091-092-实验六 ............................................................................................................ 15
输油管道问题 ......................................................................................................................... 15 众数问题 ................................................................................................................................. 16 邮局选址问题 ......................................................................................................................... 17 半数集问题 ............................................................................................................................. 18 士兵站队问题 ......................................................................................................................... 19 有重复元素的排列问题 ......................................................................................................... 20 排列的字典序问题 ................................................................................................................. 21 集合划分问题I ...................................................................................................................... 22 集合划分问题II ..................................................................................................................... 23 半数单集问题 ......................................................................................................................... 24 双色Hanoi塔问题 ................................................................................................................. 25 标准2维表问题 ..................................................................................................................... 26
整数因子分解问题 ................................................................................................................. 27 有向直线2中值问题 ............................................................................................................. 28 数字游戏 ................................................................................................................................. 29 2011-软件091-092-实验七 ............................................................................................................ 30
零件加工问题1 ...................................................................................................................... 30
Sample Input ............................................................................................................. 30 Sample Output .......................................................................................................... 30 零件加工问题2 ...................................................................................................................... 31 2011-软件091-092-实验八 ............................................................................................................ 32
和MM去上课........................................................................................................................ 32 看亚运..................................................................................................................................... 33 零件加工问题2 ...................................................................................................................... 34 2011-软件091-092-实验九 ............................................................................................................ 35
打包......................................................................................................................................... 35 基站安装 ................................................................................................................................. 35 和MM去上课........................................................................................................................ 36 2011-软件091-092-实验十 ............................................................................................................ 37
Huffman Coding ..................................................................................................................... 37 2011-软件091-092-实验十一 ........................................................................................................ 38
部分背包问题 ......................................................................................................................... 38 2011-软件091-092-实验十二 ........................................................................................................ 39
最小生成树 ............................................................................................................................. 39 2011-软件091-092-实验十三 ........................................................................................................ 40
最小生成树 ............................................................................................................................. 40 2011-软件091-092-实验十四 ........................................................................................................ 41
拍照......................................................................................................................................... 41 最大子段和 ............................................................................................................................. 42 最长不下降子序列 ................................................................................................................. 43 2011-软件091-092-实验十五 ........................................................................................................ 44
拍照......................................................................................................................................... 44 数字三角形问题 ..................................................................................................................... 45 最长不下降子序列 ................................................................................................................. 46 2011-软件091-092-实验十六 ........................................................................................................ 47
神农架野人问题 ..................................................................................................................... 47
2011-软件091-092-实验一
最大子段和问题一
Time limit: 1000MS Memory limit: 32768K
Total Submit: 107 Accepted: 56
给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<=1000）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。
输入：输入为两行，第一行为整数n，第二行为n个整数。
输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；
Sample Input：
6
2 -5 11 -4 13 -2
Sample Output： From=3,To=5
MaxSum=20
最大子段和问题二
Time limit: 1000MS Memory limit: 32768K
Total Submit: 49 Accepted: 34
给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<=10000）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。
输入：输入为两行，第一行为整数n，第二行为n个整数。
输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；
Sample Input：
6
2 -5 11 -4 13 -2
Sample Output： From=3,To=5
MaxSum=20
最大子段和问题三
Time limit: 1000MS Memory limit: 32768K
Total Submit: 12 Accepted: 3
给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<= 100000 ）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。
输入：输入为两行，第一行为整数n，第二行为n个整数。
输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；
Sample Input：
6
2 -5 11 -4 13 -2
Sample Output： From=3,To=5
MaxSum=20
2011-软件091-092-实验二
找新朋友
Time limit: 1000MS Memory limit: 32768K
Total Submit: 11 Accepted: 5
新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。
输入：第一行是测试数据的组数CN（Case number，1），接着有CN行正整数N（1），表示会员人数。
输出：对于每一个N，输出一行新朋友的人数，这样共有CN行输出。
Sample input:
2 25608 24027
Sample output:
7680 16016
三个师妹之出题
Time limit: 1000MS Memory limit: 32768K
Total Submit: 49 Accepted: 31
这一次,那几个师妹给sharp出了一个题目:给定一个正整数N,求1/X+1/Y= 1/N的所有正整数解.sharp哈哈笑了两声,很简单的题目嘛....但是他一听数据范围就傻眼了,N最大可能是999999999!!!聪明的你能帮帮可怜的sharp吗?好让他不那么丢脸.
第一行输入一个正整数M,下面有M行,每一行都是一个正整数N.