你没看走眼，我也没有打错字，标题就是除模传奇；作为一个星迷，用这样一个标题来包装日志，是天经地义的事。但是，标题只是这篇日志的表面现象，其实日志的真正身份还是两个字——编码：优雅的计算机除法、优雅的计算机取模。     《编程之美》的开胃题目【让CPU占有率曲线听你指挥】里要画正弦曲线，那果断要有取模运算的在场啊；还有【中国象棋将帅问题】，取模运算也华丽现身。对了，今年华为编程赛初赛的第一个题目【批次就餐问题】，个人觉得也是取模的问题呢。。。唉，又不小心触动了伤心神经。然后，如果可以无视自己的实践引例的小儿科程度的话，那我就要肆无忌惮地来两个mini引例了。 ******************************************************************************************************     引例1：[大整数乘法]:做这些工作，都是纠结于计算机的表示能力问题啊，要让它hold住，不要overflow。所以就： void big_num_product(char a[],char b[],char *product) /*C语言实现*/ { int la = strlen(a),lb = strlen(b); /*乘数a,b的位数*/ int i,j,c; for(i = la - 1;i >= 0;--i) { for(j = lb - 1;j >= 0;--j) { *(product + i + j + 1) += (*(a + i) - '0') * (*(b + j) - '0'); /*字符转数字后再相乘*/ c = *(product + i + j + 1) / 10; /*判断有无进位*/ if(c) /*有进位*/ { *(product + i + j + 1) = *(product + i + j + 1) % 10; *(product + i + j) += c; } } } }
    引例2：[约瑟夫环]: 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。（感谢百度百科对我的科普）
void josephus_cpp(int n,int k,int m) /*C++实现*/ { bool *p = new bool[n]; memset(p,0,n * sizeof(*p)); int a = n; int idx; for (int i = k - 1;n > 0;--n) { int b; b = i + m - 1; idx = b % a; for (int j = i;j <= b;++j) if (p[j % a]) { ++b; idx = b % a; } p[idx] = 1; cout << ++idx << endl; i = b + 1; } //delete [] p; }

    看到除模的出场了吗？虽然低调，但是给力，它们像导师一样，不让蠢蠢欲动的子民偏离轨道。必要时，就会制造除美丽的周期。     但是，优雅的背后，是不菲的消耗。《编程珠玑》里面提到，除法的机内实现相比于乘法来说，明显要比乘法复杂、耗时。有一些行之有效的针对特定情况的改进方法，比如，在编程过程中，用逻辑位移来实现除2的各次幂。取模的开销也大，但是《编程珠玑》[第二版 黄倩/钱丽艳中文译本P88]提到：     “杂技”算法要求: k = (j + rotdist) % n;
    用下面的语句块来实现上面的功能，避免了直接取模的开销:
k = j + rotdist; while (k >= n) /*此处的while在原书中为if，应该错了吧？或者至少不妥？*/ k -= n;     这么做果然对整个函数的运行时间有影响吗？我也还没有搞[弄诵]，所以，传奇还要延续。   ***************************************************************************************************************************************************************************************** Review @ 2012-05-02      josephus_cpp()函数中，修改了入口参数n，不好的习惯吧，把a和n的角 {MOD}对换一下是不是好一点？   Review @ 2012-05-03       josephus_cpp()函数中，当n,m很大时，变量b增长比较快，会不会导致溢出错误？   *****************************************************************************************************************************************************************************************