中值定理竞赛题目(NOIP信奥赛算法之加减算式)

昨天晚上儿子说要考考我,让我做一道题,输入是一行一句只有加减运算的算式,譬如1 5-7,让我写一个程序来计算出结果。

C 里没有原生支持以字符串形式导入一个表达式,并直接计算出结果的能力,可能有一些第三方的库支持。正常做法,如果表达式里有加减乘除四则运算,还有小括号来强制指定优先级,则先把表达式转换成逆波兰表达式,再计算之。未来我会给出具体解法,难度属于“普及 /提高-”。

而这一题,只有加减两种运算,那就只能算入门难度了。因为加减运算的优先级相同,都按从左至右的结合律依次两两计算。

表达式中有数字,有 和-两种运算符,混合在了一起,显然,用string类型来保存整个表达式最方便。

表达式可能会非常长,譬如下面是一个例子:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(1)

每个数字可能都不止一位,因此,要用一个int类型的变量来逐位提取每个参与运算的数字。

自从2021年9月后,C 14新特性终于可以用于NOIP了,语法糖(syntactic sugar,是指编程语言中可以更容易表达一个操作的语法,它可以使程序员更加容易去使用这门语言,操作可以变得更加清晰、方便,或者更加符合程序员的编程习惯)又有增加,对于一个字符串,可以用以下方式来遍历字符串s:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(2)

而在这之前,只能用下面的语句来遍历:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(3)

而且这种用法还会触发编译器告警,因为如果i为int类型,i的最大上限值是2,147,483,648,如果字符串的长度超过这个值,多余的部分就无法遍历到,正确的写法如下:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(4)

这种写法更为冗长,好在有了C 14,不用再那么麻烦了。

除了以上三种之外,还有第四种遍历string的方法,一起来看一下:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(5)

以上这种是采用迭代器iterator遍历string的方法。

第一种方法最简洁,但是也有缺陷,譬如无法从右往左遍历字符串,也无法在一次循环中同时获得字符串的多个字符。所以其它几种方法也并不能被方法一完全取代。在某些场合还是得使用如上这些看起来比较复杂的遍历方法。

在循环体内,需要对string中的每一个元素做判断,如果是数字,一种处理方式,否则,就是 或者-,那就是另外一种处理方式。程序结构如下:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(6)

在处理字符串中的数字之前,首先要搞清一件事, 形如"12345"和12345,在计算机内是完全不同的两种值,前者是一串字符串,并不能进行数学运算,只能打印出来。而后者是真实的数字,可进行数学运算。同样,字符'3'和数字3也完全是两码事。在C 里,字符串用双引号括起来,字符用单引号括起来。

表达式中夹杂着数字和 和-的运算符。我们只能把表达式当作一串字符来处理。因此我们要想个办法,把表达式中的数字字符串,譬如"12345"转变成12345,好让它进行数学运算。

我用前面的方案一,把表达式字符串s中的每一个字符依次放入字符变量ch里。如果ch连续的得到数字字符,则需要把它们合并成一个int类型的整数,方法是用一个初始值为0的变量,不断的乘以10,再加上这个数字。譬如字符串"123",从左往右,先把1拿出来,放在某个变量num中,然后乘以10再加上2,得到12放入num中,然后把num再乘以10得到120再加上3,就得到了123。

由于ch虽然看上去是数字,其实本质是一个char类型的字符,要通过减去字符'0',得到一个真正的数字。字符0~9在ASCII表中是连续排列的,如果我们得到或者保存一个字符'3',其实它在计算机内真正的值是十进制的51,是该字符的ASCII码值。显然我们不能用51去直接运算。那怎么让51变成数字3呢?只要让它减去'0'的ASCII码值即可。'0'的ASCII码值为十进制48, '3' - '0' = 51 - 48 = 3。这就完成了从'3'到3的转换。

因此对于一连串的数字形式的字符,要转成int类型的整数,可用如下的方式:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(7)

接下来,该处理运算符了,如果变量ch遇到一个运算符,该怎么处理?首先,我们可以意识到,遇到运算符就意味着变量num的数字合并工作暂时告一段落,变量num中的数字可以参于运算了,可以用来和上一次运算的结果进行 或者-的运算。那到底是 还是-呢?这可不是由当前的ch中的运算符来决定的,而是由上一次得到的运算符来决定的。因此,要有一个变量,来保存上一次的运算符。给它取个名字叫last_op吧,给其一个初始值 。并用另一个变量ans来保存上一次运算的结果,给一个初始值0。

试想,当遇到表达式中第一个运算符的时候(无论它是 还是-),num中保存的数字立即就会与初始值为0的ans做 的操作,并把结果保存在ans里。这就是我们想要的结果。等运算完成,last_op的使命完成,我们就可以把当前ch中保存的运算符,放入last_op中,用于下一次的计算。同时,还要把num置为0,因为num的当前计算已经完成,它要变成0,以迎接下一批连续的数字。代码可扩展如下:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(8)

我们快完成了,但这样的程序还是不太正确,试想一下,所有的表达式是以数字结尾的,并非以 或者-结尾。譬如表达式1 - 3 5, 最后,有一个数字5,最后不可能是一个 或者一个-。 而我们的任意一次计算,都是在遇到运算符 或者-时,才进行的。那最后那个数字,保存在num里的最后的数字,似乎是没有机会运行的,因为循环已经结束,它将被悲惨的丢弃掉。解决的办法也比较巧妙,当我们通过命令行得到整个表达式,在开始做计算之前,我们人为在表达式最后添加一个运算符,随便添加一个 或者-,都可以。这个运算符不会参于运算,只是为了让它左侧的那个数字,不被丢弃。

整个程序的完整代码如下:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(9)

这道题在洛谷上有,编号是P2788,感兴趣的同学可以去尝试一下。

到这里,这题就做完了。儿子看完后大笑着说,“完全没有必要那么麻烦,看我的”,然后他给出了如下的代码:

中值定理竞赛题目(NOIP信奥赛算法之加减算式)(10)

这段只有11行的代码,利用了C 中cin语句的一个特性,当输入譬如为1 5-3时,如果用一个整数(int)类型的变量通过循环语句连续不断的去接收它,这个变量会先得到1, 再得到 5, 再得到-3,它会把 号和-号当作该数字的符号位,而不是运算符。如果把得到的这些数字加起来, 就有1 ( 5) (-3)。其实结果与1 5-3并无不同,因此代码就可以简单到爆了。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页