简单算法实现之《中国剩余定理》

中国剩余定理
这个定理之前没见过,是在RSA算法原理(一)中提到的,想深入了解的可以去读下。

故事背景
  • 韩信点兵

秦朝末年,楚汉相争。一次,韩信将1500名将士与楚王大将李锋交战。苦战一场,楚军不敌,败退回营,汉军也死伤四五百人,于是韩信整顿兵马也返回大本营。当行至一山坡,忽有后军来报,说有楚军骑兵追来。只见远方尘土飞扬,杀声震天。汉军本来已十分疲惫,这时队伍大哗。韩信兵马到坡顶,见来敌不足五百骑,便急速点兵迎敌。他命令士兵3人一排,结果多出2名;接着命令士兵5人一排,结果多出3名;他又命令士兵7人一排,结果又多出2名。韩信马上向将士们宣布:我军有1073名勇士,敌人不足五百,我们居高临下,以众击寡,一定能打败敌人。汉军本来就信服自己的统帅,这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动,鼓声喧天,汉军步步进逼,楚军乱作一团。交战不久,楚军大败而逃。

题目就是:将军点兵,三三数余2,五五数余3,七七数余2。问兵几何?

  • 孙子算经

今有物,不知其数,三三数之,剩二,五五数之,剩三,七七数之,剩二,问物几何?
答曰:二十三  
术曰:三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并之,得二百三十三,以二百一十减之,即得。凡三三数之剩一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五,即得。

《孙子算经》里给出了解决办法

步骤一
1
2
3
除3余2 -> 取140
除5余3 -> 取63
除7余2 -> 取30
步骤二:
1
2
对上面取到的数求和
140 + 63 + 30 = 233
步骤三
1
2
3
用上面求出的结果减去210,就是结果
233 - 210 = 23
结果也就是23了

不过那140,63,30,还有210是怎么来的呢?这就涉及到中国剩余定理的算法原理了。

中国剩余定理原理

1
2
3
4
5
#题目:
设要求的数为x,每个除法的结果分别为k1,k2,k3,那么就有:
[1] x / 3 = k1 + 2
[2] x / 5 = k2 + 3
[3] x / 7 = k3 + 2
1
2
3
4
5
1.对步骤一中的式子1求解过程为:取式子2和式子3中除数(5和7)的最小公倍数LCM(35),
然后把这个LCM作为x带入式子1。如果LCM不能适应式子1,就对LCM再加上一个LCM,
然后带入式子1中......直到满足式子1为止。

按照这个求解过程,分别对3个式子求解,取到的结果为:35,63,30
1
2
3
2.把上面求到的结果求和

35 + 63 + 30 = 128
1
2
3
4
5
3.这里对3个式子的除数取最小公倍数

3,5,7的最小公倍数为105
然后用上面的结果减去这个最小公倍数,就是结果了
128 - 105 = 23

这里估计有人要问了:这个35也不是140,而且105也不等于210啊?! 这个不用纠结,这个跟古代数学的发展史有关嘛! 当然,这是我瞎说的,想要深挖的可以去研究下相关资料。

-

下面具体说代码实现

首先创建个model类,类里面有除数和余数2个属性,然后提供一个遍历构造器,方便使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@interface CRTModel : NSObject

@property (assign, nonatomic) NSInteger divider;

@property (assign, nonatomic) NSInteger remain;

+(instancetype)modelWithDivider:(NSInteger)divider
                         remain:(NSInteger)remain;

@end

@implementation CRTModel

+(instancetype)modelWithDivider:(NSInteger)divider remain:(NSInteger)remain
{
    CRTModel *model = [[self alloc] init];
    model.divider = divider;
    model.remain = remain;
    return model;
}

@end

还需要用到2个函数,最大公约数GCD和最小公倍数LCM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-(NSInteger)gcdOf:(NSInteger)a and:(NSInteger)b
{
//这里用__block修饰也可以
    static const NSInteger(^GCDRecursionBlock)(NSInteger,NSInteger) 
    = ^(NSInteger ra, NSInteger rb){
        if (!ra || !rb) return MAX(ra, rb);
        return GCDRecursionBlock(rb,ra%rb);
    };
    return GCDRecursionBlock(a,b);
}

//最小公倍数
-(NSInteger)lcmOf:(NSInteger)a and:(NSInteger)b
{
    return a * b / [self gcdOf:a and:b]; //最小公倍数等于两数之积除以最大公约数
}

然后开始实现算法

1
2
3
4
5
0.先创建3个Model,把题目"抄"一遍

CRTModel *model1 = [CRTModel modelWithDivider:3 remain:2];
CRTModel *model2 = [CRTModel modelWithDivider:5 remain:3];
CRTModel *model3 = [CRTModel modelWithDivider:7 remain:2];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1.取到算法中步骤1的结果:

-(NSInteger)getSubMinNumberOfDivider1:(NSInteger)divider1
                              divider2:(NSInteger)divider2
                           andDivider3:(NSInteger)divider3
                             remainOf3:(NSInteger)remainOf3
{
    NSInteger lcm = [self lcmOf:divider1 and:divider2];
    NSInteger result = lcm;
    while ((result % divider3) != remainOf3) {
        result += lcm;
    }
    return result;
}

NSInteger a = [self getSubMinNumberOfDivider1:model1.divider divider2:model2.divider andDivider3:model3.divider remainOf3:model3.remain];
NSInteger b = [self getSubMinNumberOfDivider1:model2.divider divider2:model3.divider andDivider3:model1.divider remainOf3:model1.remain];
NSInteger c = [self getSubMinNumberOfDivider1:model3.divider divider2:model1.divider andDivider3:model2.divider remainOf3:model2.remain];
1
2
3
2.求和

NSInteger sum = a + b + c;
1
2
3
4
5
6
7
8
9
3.求全部除数的最小公倍数,然后求结果

//使用"更相减损术"
NSInteger lcmOfAll = 
    [self lcmOf:[self lcmOf:model1.divider and:model2.divider] and:model3.divider];
    
//求结果
NSInteger result = sum - lcmOfAll;
NSLog(@"计算结果为:%ld + %ld * k (k为自然数)",result,lcmOfAll);

就这么多了。这是我昨晚回顾RSA加密时候看到的,刚好就学习下了,其实想再复习下欧拉函数什么的,都忘光了! 有时间就搞!!

热评文章