输出：
顺序列出s个被删去的数字
算法分析
由于正整数n的有效数位为240位，因此采用string类型存贮n。为了尽可能逼近目标，我们每一步总是选择一个使剩下的数最小的数删去：
按高位→低位的顺序搜索，若各位数字递增，则删最大的尾数符；否则删第一个递减区间的首字符，这样便形成了一个新数串。然后回到串首，按上述规则删下一个数符。依次类推，直至删除s个数符为止。例如 n=‘1 7 8 5 4 3’ s=4 删数过程如下
n=‘1 7 8 5 4 3’ 删‘8’ ‘1 7 5 4 3’ 删‘7’ ‘1 5 4 3’ 删‘5’ ‘1 4 3’ 删‘4’ ‘1 3’
这样删数问题与如何寻找递减区间首字符这样一个简单的问题对应起来：
while s>0 do {按贪心策略删s个数}
begin i←1；
while (i while (length(n)>1)and (n[1]=‘0’) do delete(n，1，1)； {删去串首的无用零} 输出n； 【例题廿三】取数游戏 给出2*n个自然数。游戏双方分别为A方（计算机方）和B方（对奕的人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大为取胜方；双方和相等，属于A胜。试问A方可否有必胜的策略 输入： 2*n个自然数 输出： 前2*n行为游戏经过。每两行分别为A方所取的数和B方所取的数，其中B方取数时应给予提示，让游戏者选择取哪一头的数（L/R—左端或右端）。最后一行分别为A方取得的数和和B方取得的数和。 算法分析 设自然数列 7 9 3 6 4 2 5 3 我们设计一种方案，从数大的一头让A、B轮流取两个连续数： 由此得出 A方取得的数和为7+3+4+5=19 B方取得的数和为9+6+2+3=20 按照规则，判定A方输。虽然A方败给B方，但是我们却发现了一个有趣的事实： A方取走偶位置的数后，剩下两端数都处于奇位置；反之，若A方取走奇位置的数后，剩下两端数都处于偶位置。即无论B方如何取法，A方即可以取走奇位置的所有数，亦可以取走偶位置的所有数。由此萌发一种策略：让A方取走数和较大的奇（或偶）位置上的所有数，则A方必胜。这样，取数问题便对应于一个简单问题—让A方取奇偶位置中数和较大的一半数。 设 j—A取数的奇偶位置标志 j???0?1偶位置数和较大,A取偶位置的所有;数奇位置数和较大,A取奇位置的所有;数 SA，SB—A方取数和，B方取数和（SA≥SB） a—2*n个自然数序列； lp，rp—序列的左端位置和右端位置； ch—B方取数的位置信息（’L’或’R’）； SA，SB←0； {计算A方取数和、B方取数和，A方取数的位置标志} for i：=1 to n do begin SA←SA+a[2*i-1]； SB←SB+a[2*i]； end；{for} if SA≥SB then j←1 else begin j←0； SA?SB； end；{else} lp←1； rp←2*n； for i：=1 to n do {A方和B方依次进行n次对奕} begin if ((j=1) and (lp mod 2=1)) or ((j=0)and (lp mod 2=0)) {若A方应取奇位置数且左端位置为奇，或者A方应取偶位置数且左端位置为偶，则A方取走左端位置的数} then begin 输出A方取a[lp]； lp←lp+1； end {then} else begin {否则A方取走右端位置的数} 输出A方取a[rp]； rp←rp-1； end；{else} 输出提示信息：B方的取数位置（L/R）； repeat 读ch； if ch=‘L’ then begin 输出B方取a[lp]； lp←lp+1；end；{then} if ch=‘R’ then begin 输出B方取a[rp]； rp←rp-1；end；{then} until ch ?{‘L’，’R’}； end；{for} 输出A方取数的和SA和B方取数的和SB； 三、对应数学问题 运用已学到的数学知识，对试题给出的各个对象及其关系进行分析、演绎、归纳，从而建立一个清晰简练的解析式，使得试题与某个数学问题对应。当然，这个数学问题的计算量非人工演算所能及，必须译成算法语言，通过计算机运算方可完成。 【例题廿四】极值问题 m、n为整数，且满足下列两个条件： ①m、n∈{１，２，?，k} ②（n2－m*n－m2）2＝1 编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2＋n2的值最大。例 22 如，若K＝1995，则m＝987，n＝1597，则m、n满足条件，且可使m＋n 的值最大。 输入： 9 键盘输入正整数K（1≤k≤10）。 输出： m n 算法分析 这是一门典型的数学题。如果读者仅从初等数学的角度考虑，通常会得出这样一种算法： 由条件②（n2－m*n－m2）2＝1得出 22 n－m*n－m＋1＝０ 22 n－m*n－m－1＝０ 根据求根公式 n1＝（m＋△1）/2 n2＝（m+△2）/2 n3＝（m-△1）/2 n4＝（m-△2）/2 其中：△1＝5*m2?4；△2＝5*m2?4； 下面再来考虑条件①。由于n>1，因此排除了n3 和n4 存在的可能性，即 n＝n1＝(m＋△1）/２或者n＝n2＝(m＋△2）/２ 又由于n和m是整数，因此△1和△2应为整数。同样，（m＋△1）/２和（m＋△2）/２也应为整数。 22 有了上述条件限制和m与n的函数关系式，使得求m＋n值最大的一组m和n就比较方 22 便了。由于m＋n单调递增，因此我们从m＝k出发，按递减方向将m值代入n的求根公式。 22 只要△1(或△2）为整数、n1(或n2）为整数且小于k，则得出的一组m和n一定使m ＋n的 值最大。算法如下： m←k； while m≥1 do begin △1←5*m2?4； if △1 为整数then begin n1←(m＋△1）/２ ； if(n1为整数)and(n1≤k)then begin 输出m和n1 ；halt；end；{then} end；｛then｝ △2←5*m2?4； if △2为整数then begin n2←(m＋△2）/２； if（n2为整数）and（n2≤k）then begin输出m和n2 ；halt；end；{then} end；{then} m←m－l； end；{while} 上述算法从数学意义上讲是一定可以出得出正确解的。但是采用该算法的读者疏漏了一 95 个重要条件──１≤k≤10 。一般说，如果K值超过10 ，上述算法决计不可能在竞赛限定的１５秒内出解。要提高算法效率，不能不借助一些组合数学的知识和组合分析的方法解题： 222 首先，我们对表达式（n－m*n－m）＝1作一些数学变换 222 （n－m*n－m） 222 ＝(m ＋n*m－n〕 222 ＝((n＋m)－n*（n＋m）－n〕 222 ＝〔（n＇）－m＇*n＇－（m＇）〕 其中n＇＝m＋n，m＇＝n 由上述数学变换式可以得出，如果m和n为一组满足条件①和条件②的解，那么m＇和n＇也是一组满足条件①和条件②的解。另外 m＝１ n＝１ 满足条件①和条件②，因此，我们可以将所有满足条件①和条件②的m和n按递增顺序排成一个Fibomacci数列｛1，1，2，3，5，8，??｝，数列中小于k的最大两个相邻数即为试题所要求的一组m和n。计算过程如下： m←1； n←1； {确定Fibonacci数列的头两项数} Repeat {顺推数列中小于K的最大两个相邻数} t←m + n； if t≤k Then Begin m←n；n←t；End；{then}