贪心上机练习1

《贪心上机练习1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贪心上机练习11.删数问题（delete.Pas）【问题描述】键盘输入一个高精度的正整数n(≤240位)，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。Delete.in[输入格式]ns[输出格式]delete.out最后剩下的最小数。[样例输入]1785434[样例输出]132.取数游戏(qushu.pas)[问题描述]给出2*n(n<=100)个自然数（数小于等于30000）。游戏双方分别为A方（计算机方）和B

2、方（对奕的人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大为取胜方；双方和相等，属于A胜。试问A方可否有必胜的策略？[输入格式]qushu.inn及2*n个自然数。[输出格式]qushu.out共3*n+2行，其中前3*n行为游戏经过。每3行分别为A方所取的数和B方所取的数，及B方取数前应给予的适当提示，让游戏者选择取哪一头的数（L/R—左端或右端）。最后2行分别为A方取得的数和和B方取得的数和。3.0/1背包问题[问题描述]有一容量为weight的背包。现在

3、要从n件物品中选取若干装入背包中，每件物品i的重量为w[i]，价值为p[i]。定义一种可行的背包装载为：背包中物品的总重量不能超过背包的容量，并且一个物品要么全部选取，要么不选取。定义最佳装载是指所装入的物品价值最高，并且是可行的背包装载。[样例输入]11{weight}4{n}2467{w[i]}6101213{p[i]}[样例输出]0101234.取火柴游戏（match.pas）有k堆火柴棒，第i堆火柴棒的根数为ni，1<=i<=n，你和计算机取火柴游戏，取的规则为：每次可以从一堆中取走若干根

4、火柴，也可以一堆都取走，但不许跨堆取，也不许不取。谁取走最后一根火柴为胜利者。谁没有火柴棒可取，就算输。例如：k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取：A：(2,2)→(1,2){从一堆中取一根}P：(1,2)→(1,1){从另一堆中取一根}A：(1,1)→(1,0)P：(1,0)→(0,0){P胜利}如果决定A后取：P：(2,2)→(2,0)A：(2,0)→0,0){A胜利}又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：P：(1,2,3)→(0,2,3)A：(0,2,

5、3)→(0,2,2)编写一个程序，在给出初始状态后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取，如果是先取必败，则输出“lose”。[输入]match.In第一行一个整数n，表示堆数。第二行，n个数表示每堆火柴数。3369【输出】match.Out43{表示第一次从第3堆取4个出来，必胜}365{第一次取后的状态}样例1：3369样例2：输入415221910输出Lose5.均分纸牌（a.pas）[问题描述]　　有N堆纸牌，编号分别为1，2，…,N。每堆上有若干张，但纸牌总数

6、必为N的倍数。可以在任一堆上取若于张纸牌，然后移动。　　移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。　　例如N=4，4堆纸牌数分别为：　　①　9　②　8　③　17　④　6　　移动3次可达到目的：　　从③取4张牌放到④（981310）->从③取3张牌放到②（9111010）->从②取1张牌放到①（10101010）

7、。[输入]：a.in　　文件格式：　　N（N堆纸牌，1<=N<=100）　　A1A2…An（N堆纸牌，每堆纸牌初始数，l<=Ai<=10000）[输出]：输出至屏幕。格式为：　　所有堆均达到相等时的最少移动次数。‘[输入输出样例]a.in：　4　98176屏慕显示：　3