除模传奇

2019-04-13 14:45发布

    你没看走眼,我也没有打错字,标题就是除模传奇;作为一个星迷,用这样一个标题来包装日志,是天经地义的事。但是,标题只是这篇日志的表面现象,其实日志的真正身份还是两个字——编码:优雅的计算机除法、优雅的计算机取模。     《编程之美》的开胃题目【让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增长比较快,会不会导致溢出错误?   *****************************************************************************************************************************************************************************************