第二次作业 11061008 谢子鸣

  本次作业是实现二位的最大子序列的算法。由于有了第一次的一维数组的经验,二维数组我也决定向着一维数组的方法上靠。二维数组的不确定性很大,单凭每一行的一位数组的大小无法确定整个二维数组的大小。所以说,只能把每一种一位数组的情况都尝试一下才能得出正确的结果。首先我大概的思路是将每一种一位数组的组合都尝试一下。如:1,2,3,4就可以尝试1、12、123、1234、2、23、234、3、34、4这所有情况,分别计算每种情况的和,让后行的概念就消除了,剩下的就与一位数组求最大子段和的方法相同了。但是对于每行所有情况的求和,便是一个花费时间较多的事情,如果每种情况都进行一次累加的话,进行了大量的重复计算,所以需要进行代码的简化。首先想到的是如在所给的例子中,在求值时可以用到先前的值,如在求1234的和时,可以使用已知的123的和再加上4的值便是1234的和了。这样一定程度的减少了计算的复杂度,但是这并不是最好的情况,受到了上学期算法课的某道例题的启发,一行的所有的和都可以表示为一些和的减法,如:23=123-1 3=123-12。所以一行仅需计算1,12,123,1234的值即可。这样大大降低了运算所需的时间复杂度。这样单行和的问题也解决了,剩下的问题就与一维数组没有区别了,二位数组的问题也就解决了。

  接下来是二维数组单向的连接问题了,由于我解决这道题的方法的问题,在我这里横向连接和竖向连接没法完全一致的完成,所以分开进行,首先在数据输入的时候,直接将数组复制输入不同模式下需要的输入量不同。

  然后依旧是换汤不换药,老方法,对于每行进行求值进入最后部分。虽说在横向连接的时候我构造了一个双倍的二位数组,但是题目要求只是一个数组的首尾连接,所以不能完全使用之前的代码,需要进行一些限制。本来内层循环j是应该小于等于y的,但是此时会有数组的长度大于原长y/2,所以把长度限制在y/2上。竖直扩展也是类似的意思,长度会超过原长,所以也要进行限制,但是由于代码的特殊性,限制的方法也比较特殊,我的方法是引入了一个counter变量里记录当前的竖直长度,并在合适的时间来斩断和减小问题也得以解决。

而轮胎的问题也就是讲竖直和横向的结合,无需多谈。

  这次的编程经历使我意识到对于问题的分解是一个非常重要的工作。如果说,本次的作业老师直接是给出让球轮胎问题的话,想必要使我花上几倍的时间来解决这问题,但是老师给的问题是引导性的,一步一步,每一步的问题都是可轻松解决的,这样轻松解决了一系列的问题,竟然最后解决了一个较大的问题,这种工作的思路值得我去好好思考,以我的经验来看,将问题划分为容易的步骤将是一个比解决问题还要困难的工作,所以还需多多学习。

以下是测试用例以及结果:

原文地址:https://www.cnblogs.com/nikeceo/p/3348343.html