数格子

我发现程序员最经常干又不太容易弄对的一件事情就是数格子。所以得好好整理一下。。
好吧,也说不上不容易弄对了。。是我智商太低总也弄不对。。。不能因此就认为别人也弄不对。。

举个最简单的例子。你有a个格子,要从第b个开始(包含)连续搬c个,怎么搬。
简单嘛,从b开始,到b+c和a中的较小值(不含)(注意b是从0开始计算的序号,并且0<=b<a ,a和c都是正整数)
搬动的区间是[b,min{b+c,a})

其实a,b,c都是我命名很完好的变量名:allitemNum, begin, count.恰好abc了。不知为何这么巧。

然后遇到一个反过来的例子,就把我搞晕掉了。还是这a个格子,但是这回要从后往前数第b个,连续向前搬c个。
我承认。。这个问题我反复搞错,整整弄了一天时间。。确实是智商有问题吧。。
先找出来这个反过来数到b,他的序号是多少呢?
数到b,所以是b+1个格子。于是前面差了a-(b+1)个格子。这么多格子里面并没有包含反过来数到b的那一个。如果要包含他,还得加一。于是包含反过来数到b的那个格子,从第0个到他,一共是a-(b-1)+1个格子。序号就应该是a-(b-1)+1-1,简单来说就是a-b-1。
(再次承认我肯定是想麻烦了。。不过就是想不明白。。画了好多图了。。哪位智商高的给我指条明路。。)
然后还需找出在向前数c个,那个格子在哪里。
这回好办了,到第b个总共b+1个格子,在向前数c个就是b+c+1个。他的序号是b+c。把这个序号替换掉上面的b就得到a-b-c-1。
要注意上面那个a-b-1这个格子还是要包含的(要搬走的),所以再向后续一个格子。而前面这个起始点,必须比0小。
于是得到搬动的区间是[max{a-b-c-1,0},a-b)

呼,就这么简单的几句话,想了我一整天。。真是糊涂啊糊涂。。而且到现在都想不出合适的理解这些代数的方法。。只能硬推。。肯定是小脑发育不全。。

能记录下来的还有一些可以算是定理的东西吧。就称之为数格子定理好了。

用两个序号相减,得到的是两个序号之间的格子数量,包含前端不含后端。
比如。。8-3=5
0,1,2,[3,4,5,6,7),8,9

因此同理,从某个序号加上一个数量,得到新的序号是包含他自己向后数那么多个的序号,含前端不含后端。

3+5=8
0,1,2,[3,4,5,6,7),8,9
8+(-5)=3
0,1,2,3,(4,5,6,7,8],9

总数量为a的格子里面,b与a-b-1轴对称
10-2-1 = 7
0,1,[2],3,4,5,6,[7],8,9

最后就是编程技巧,要搬格子的话,先算好区间[b,e),之后好办

for(int i = 0; i+b < e; i++){
dest[i] = source[b+i];
}

好吧再次承认这么脑残的东西我也搞不明白实在太傻逼了。。不过咱就是傻逼怎么着了!!
上次还遇到更傻逼的事情

UINT a = 2,b = 3;
if(0<a-b){...}

结果居然这个判断就掉进去了。我百思不得其解。为什么0<-1居然能是true呢,为什么为什么呢。。
终于悟了unsigned int 没有-1, -1是最大值。。。哭死。。果然还是上课没认真听讲下课没好好完成作业啊。。
这也是一个问题,就是格子的序号一般怕太多格子数不完了都用unsigned int的。但是一般也可能会需要用序号相减来计算之间的格子数量的情况。结果这里面就产生了矛盾。当然经常记着去比较一下大小先还是对的。但是那样也还是很麻烦哪。。。