文思海辉编程大赛的初体验

墨蓝 2022-09-19 08:05 26阅读 0赞

作为一个所学专业和计算机相去十万八千里的人，我对编程题目的印象还基本上停留在十几年前大学里教的Fortran和自己考计算机二级时学的C语言教科书上的习题。归纳起来大致有这么三种。一是做计算机被发明出来做的事——计算，譬如求一个矩阵的逆矩阵。二是和字符串打交道，在屏幕上做符号游戏，比如打印出一个由星形组成的金字塔。三就是考察编程语言本身的概念，如数组和指针。这几类问题对我来说都有些乏味，比不上量子力学和相对论那么奇妙。一个问题若是在我看来是有趣的，至少具备下面两个条件之一。要么有数学或逻辑上的趣味，比如一个函数竟然可以用表面上毫不相关的三角函数的级数形式表示，又或者海盗分财宝的问题（当然我算不上在数学上有天赋，不少领域比如数论的问题也觉得很枯燥）。或者问题和物理世界的本质规律有关，扩展一点说和这个现实世界有关，也就是具有实际的意义。例如对薛定谔方程解的波函数的概率密度的解释，以及用这个方程就能够计算基本原子光谱，当年都令我上瘾和兴奋。虽然天分也够不上作理想中的物理学家，而且阴差阳错地成为一名程序员，但是对问题趣味的口味还一直保持着。所以当我随意点进博客上方的文思海辉第一届在线编程大赛的链接，看见单词博弈的题目，和奖品的吸引力相比问题本身的趣味更胜一筹。

这样一个博弈的游戏，和记忆中做过取豆子的游戏有些相似（两人轮流从一堆两种颜色的豆子中按规则取走若干看谁能使得剩下的豆子符合特定的结果）。分析了一下甲乙的取胜策略，方案可以化归成一个简洁的递归。轮到任何一方删字母时，如果当前的序列取走某个字母能变为单调递增，那么他就获胜；如果不能，问题就转化为他删去一个字母后对手面对新的序列能否获胜，双方能获胜的布尔值正好是互否的关系。于是用编程语言之需写明这种递归关系和判断当前字母序列是否单调递增的函数。在可选的四种语言中，我用了语法相对熟悉的C\#。

using System;
    
    public class Test 
    {
       public static  int who(string word)
        {
            if (Win(word)){
                return 1;
            }else{
                return 0;
            }
        }
            static bool Win(string word)
            {
                for (int i=0; i
       
        =letters[i+1]){
                        return false;
                    }
                }
                return true;
            }                
        //start 提示：自动阅卷起始唯一标识，请勿删除或增加。 
        public static void Main()
        {
           Console.WriteLine(who("Test"));
        }
        //end //提示：自动阅卷结束唯一标识，请勿删除或增加。
    }

打开Visual C\#Express，完成代码，测试了四五个字母的序列都正确，便在网页上提交了。结果有些意外：程序没能在三秒之内运行完成，挑战失败了。

我再回头去看题目，没有任何一个地方提到有运行时间的限制。另一个疑问就是，真的要运行那么久吗？在本机测试的时候不是都即刻可得出结果吗。仔细看题目，单词长度不超过十五个字母。评卷系统应该用的就是最长的可能。再在本机上测试一个无规律的十五个字母的序列，竟然真的等了几秒钟才出结果。看来我的程序在效率上确实有待提高。但是我对自己的解决思路的简洁挺满意，没有实际的需求和刺激，也就不愿再去思考怎样提高速度了。

因为这里给出的答案不合格，我贴此文对还在进行的文思海辉第一届在线编程大赛也没有任何影响：）