第十一周周报

——陈长洪

周一白天我试着完善了蓝桥杯校内赛小数点后出现数字的题目。这道题我在周日下午没有想出好的结束条件，只是设置了一个取余次数大于20000就结束的条件，这样说不定是有误差的。瞿学长给了我一个建议，添加一个判断余数是否在前面出现过的条件。我想这道题肯定不能直接用数组或链表来做，时间复杂度太大了。于是我打算直接用容器map来实现标记某个余数是否出现过。这样就可以做到万无一失了。

周六听瞿学长讲解蓝桥杯的这6个题目，我发现我之前做的题目有些是有问题的。

比如第一题，我之前写那个程序的时候没有注意到可以输入多组数据，所以我当时写程序只是输入了一个n和n个数据就结束了，完全不能再输入一组数据。然后我再仔细审视这道题，发现这道题的陷阱还挺多的。比如我之前以为输入-1结束，就错误的以为没有数据的值会等于-1，所以将-1作为该位置的数是不可用的标记。这很显然是错误的，题目只是说这些数据是有排列顺序的，并没有说这些数一定都是大于0的，甚至没有说这组数是从大到小还是从小到大！蓝桥杯的题目果然陷阱重重。所以我重写这个程序的时候费了很多心思，比如该怎样剔除重复的元素，我想过用两次循环，但是这样就要两次遍历数组。我想试试能不能直接在输入的时候直接输出结果，即将元素录入数组的时候就判断它是否和之前的相等，这样只需要一次录入数据的时候就可以判断出结果。

主要代码和运行结果

我运用一个t来代表前面的元素的数值。每次处理一个n个元素的数组，先创建一个大小为n的数组a，先输出第一个元素，输出这个元素，然后让t等于第一个元素，后面每次输入新数值就判断这个元素是否和t相等，如果相等就跳到下一次输入，不相等就输出这个元素，让t等于这个元素。释放掉这个数组，获取下一个数组的大小或者结束符号-1到n中，判断n是否为-1，若是-1，结束这个程序。

第二题：

这道题和学长的讲解让我更深层次的理解了进制转换的关系，之前只是简单的位数乘以进制的几次方，现在通过进位和借位还有辗转相除法可以解决绝大部分进制转换的问题了。

代码和结果分析：

1024先-1再除以26得余数9，9加’A’得到第10个字母J，第二位是1023除26得39，第二位再减1除26余12，是第12个字母M，第三位同理，是A。

第三题：

这道题我考试的时候是用的另一种方法来做的：先喝完手上所有的饮料，将能兑的盖子都对了，剩下的继续留在手上，兑完后再全喝掉，同样将能兑的对了喝掉，盖子留手上直到手上的盖子数量低于3个，统计喝了的瓶数。结果和题目给的例子相同，我就没仔细想了。星期六学长告诉了我们另一种思路，时间复杂度是1，而且逻辑方面更严谨一些。为了验证我的是否正确，我用所有n的可能取值比对了两个结果，发现结果都是相等的，都是对的。不过很显然，学长的方法时间复杂度更低，是更优的算法。

第四题：

这个题目我考试的时候只设置了一个最高除20000次的限制，并没有想到更好的办法让它停止。星期一的时候通过学长知道判断余数是否出现过可以确定是否循环，但是也没有考虑过可不可能循环无限进行下去。直到学长在星期六的下午讲解这道题的时候说了一个定了，整数P/Q最多除Q+1次就会遇到0或者循环，即两个整数相除不可能出现无限不循环小数。

代码和结果分析：

130除15得8余10，100除15得6余10，和之前的余数相同，所以遇到了循环节，无限6循环，所欲13除15小数点后只有6和8。

第五题：

考试的时候我通过写出多个数列，发现后一个数列的情况是前两个数列情况之和的结论，于是直接用解斐波那契数列的方法来解这道题。但是由于粗心大意，没有准确的推算结果的可能取值范围，考试的时候是用int型来存这个数列，很显然，当n足够大的时候，会发生溢出。学长还在周六的时候提供了另一种解题思路，用深度搜索的方法来得出结果，我将这种算法写出来了，但是时间复杂度没控制好，准备以后再优化。

第六题：

这个题目我是用开始的两个点来抽象出一个行动方向，然后角的关系，知道转向后，y方向为转向前x方向速度反方向（或者说是值的负数），x方向为转向前y方向速度的方向（或者说值相等）。然后再对转向后x，y的值除以x，y的最大公因数，再加上转向后的起点，即第二个点的值，就可以得到第三个点。

代码和结果分析：

15 3到12 6可以得出行动方向x：y为-3:3，所以转向后行动方向比值为3:3，3:3的最大公因数是3，所以行动后的点为13 7。

总结：

通过这次蓝桥杯的校赛，我知道我存在的许多问题。

例如第一题，我没有读清楚题目，导致我的程序根本不满足题目的要求，不能处理第二组和更多组的数据。

第二题我只知道那样处理n结果是对的，并不知道为什么是对的，只知其然不知其所以然。

第四题我由于没有找到关键点，导致我的程序只能通过“循环20000次”，用很多次判断来判断是否满足要求，并不是严谨的判断，最后的结果也不是可靠的。

第五题发现了规律，但是最后居然被“数据溢出“这种低级错误绊了一跤，真是马虎不得呀。

我处理问题有时候能找到解法，但是总是因为疏忽大意犯错，我以后一定要小心翼翼的做事，防止再犯低级错误错。