物不知其数

Posted on | | Visitors:
Words count in article: 2,976 字 | Reading time ≈ 12 分

文章分为三个大的部分：

大标题1是物不知其数问题的引入，大标题2将问题抽象。

大标题3、4、5是物不知其数问题的三种解法及其代码实现。

大标题6是提出的一些问题及不太完善的解释。

提醒：

看文章最好先掌握文章整体结构，电脑会比较方便，可以点击标题跳到自己想看的部分。

看代码发现看不到后边的注释的话，调整网页显示比例（Ctrl+鼠标滚轮）

另外代码里的注释也是有规律的，单独一行的注释是解释下边的几行的功能的，写在代码右边的注释解释这一行代码功能。

问题引入

秦王暗点兵和韩信乱点兵都是后人对物不知其数问题的一种故事化，有兴趣可以搜索一下。

物不知其数问题出自《孙子算经》。

原题为：”今有物不知其数，三三数之二，五五数之三，七七数之二，问物几何？” 这道题的意思是：有一批物品，不知道有几件。如果三件三件地数，就会剩下两件；如果五件五件地数，就会剩下三件；如果七件七件地数，也会剩下两件。

问：这批物品共有多少件？ 变成一个纯粹的数学问题就是：有一个数，用3除余2，用5除余3，用7除余2。求这个数。

拿到这个问题，我们可以发现用3和7除余数都是2，自然而然想到3*7=21,21+2=23,23%5=3。所以23就是答案之一，而后边问题中我们求最小值。

这个问题之所以简单，是由于有被3除和被7除余数相同这个特殊性。

问题抽象

去除问题数据的特殊性之后，问题可以是像这样：

三人一组余两人，五人一组余三人，七人一组余四人。问：这队士兵至少有多少人？

就是说我们要找到一个最小的数，使其除以3余2，除以5余3，除以7余4

数据变量化后真正的问题改成：一个数除以x余a，除以y余b，除以z余c，找到符合这三个条件的最小的数。

三个条件按顺序分别称为条件1，条件2，条件3。

暴力

方法

定义变量n，在范围内从头到尾递增，循环内判断条件为n%3==2&&n%5==3&&n%7==4，符合条件就break

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
//找到一个最小的数，使其除以x余a，除以y余b，除以z余c
int x,y,z;	//除数
int a,b,c;	//余数
scanf("%d %d %d %d %d %d",&x,&y,&z,&a,&b,&c);
for(int n=1;;n++)	//在这里不设范围
{
    if(n%x==a&&n%y==b&&n%z==c)
    {
        printf("%d",n);
        break;
    }
}

合并

方法

题目中有三个条件，我们可以将前两个条件合并成条件A，再把条件A与第三个条件合并，最后得出结果。

过程

条件1和条件2合并成条件A

已知n除以3余2，可设n=3i+2(i是正整数)，使i从1变大，判断3i+2除以5是否余3。

我们发现当i=2时，3i+2=8除以5余数为3，即n=8时除以3余2，除以5余3。

然后前两个条件就被我们合并成了条件A：n=15i+8，

本质是：最小的符合前两个条件的数字8加上3和5的最小公倍数15的整数倍

用到的定理：若n除以a余b，n加上a的倍数再除以a余数仍然为b。我们加上的15i即为a的倍数

注意：

是最小公倍数，不要直接看做是两数乘积，因为只有在指出三个除数两两互质的情况下，两数乘积即为最小公倍数，在这里提醒一下，不要理解错误。

如果用的不是最小公倍数，我们下边n增加的单位就变大了，可能会求不到最小值，而题目要求是取得符合要求的最小值。

条件A和条件3合并成结果

我们再使条件A和第三个条件合并，n=15i+8(i是正整数)，使i从1变大，判断15i+8除以7的余数是否为4。

我们发现当i=3时，15i+8=53除以7余4，53即为答案

拓展

过程中条件合并了两次，让我想到定义一个函数。这个函数要调用两次

写一个比伪代码还伪的代码： 结果 合并(条件，条件)

代码实现

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
int Gcd(int a,int b)				//Greatest Common divisior
{
	int c;
    //辗转相除法求最大公约数 Greatest Common Divisor
    /* 余数不为0，继续相除，直到余数为0 */
	while(b!=0)  								 
	{
		c=a%b;
		a=b;
		b=c;
	}
    return a;
}

最小公倍数

1
2
3
4
5
int Lcm(int a,int b)				//Least Common Multiple				 
{
    //最小公倍数等于乘积除以最大公约数
    return a*b/Gcd(a,b);
}

求结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//找到一个最小的数，使其除以x余a，除以y余b，除以z余c

int x,y,z;	//除数
int a,b,c;	//余数
scanf("%d %d %d %d %d %d",&x,&y,&z,&a,&b,&c);
//合并条件1和条件2
int i=1;
while((x*i+a)%y!=b)					//循环跳条件为(x*i+a)%y==b
    i++;
//得到条件A
int d=x*i+a;						//得到条件A
//合并条件A和条件3
int j=1;
while((Lcm(x,y)*j+d)%z!=c)			//while((Lcm(x,y)*j+d)%z !=c)求得的不一定是最小值
    j++;
//得到结果
int result=Lcm(x,y)*j+d;			//int result=x*y*j+d求得的不一定是最小值
printf("%d",result);

中国剩余定理

方法

除数分别是3、5、7，用70(5乘7乘2)乘以用3除的余数，用21(3乘7)乘以用5除的余数，用15(3乘5)乘以用7除的余数，然后把这三个乘积相加。加得的结果如果比105(3乘5乘7)大，就除以105，所得的余数就是满足题目要求的最小正整数解。

过程

除数两两结合得到公倍数

对所得公倍数的目标(要求)：除以另外一个除数余1

这一步骤中，不用关注三个条件要求余几，条件中的余几会在下一步体现

条件一：用3除

这里是用3除，求另外两个除数的公倍数，并要求用3除余1,5*7=35除以3余2,5乘7乘2=70除以3余1，所以是70

条件二：用5除

3*7=21除以5余1，所以是21

条件三：用7除

3*5=15除以7余1，所以是15

公倍数乘以余数相加

70*2+21*3+15*4=263

解读加法：设上式为q+p+r=n。只判断加法会不会影响满足条件1(用3除余2)即可推导出是否满足另外两个条件。

若n除以a余b，n加上a的倍数再除以a余数仍然为b，这里n为140，a为3，b为2，加上的p、r之和是3的倍数，所以余数仍为2，仍满足条件1。（发现百度百科这条定理写错了，嘻。我这数学水平也就能折腾折腾小学数学了吧）

【百度】您于2018-08-31提交的百科词条“秦王暗点兵”版本已通过，查看词条内容：（ http://dwz.cn/s4JsvyGW ）。感谢您参与编写百度百科，亿万网友因您的贡献受益。

9月1日跑步时收到这条短信，这比兴奋剂还兴奋剂，就想来段加速跑。wuhu~

同理可得，通过加法之后我们得到了一个同时满足三个条件的数字

检验是否最小

用上边得到的数字不断减去三个除数的最小公倍数直至数字小于最小公倍数(其实就是得到的数字除以公倍数取余了)，得到最终答案！

解读：其实就是上边加粗定理的变式，若n除以a余b，n减去a的倍数再除以a余数仍然为b，只是可能说成余数是几不太合理，但要懂那个意思。

拓展

个人感觉过程中的前两步完全可以合成一步，在代码实现中很容易就可以看出来，拆开反而更难理解…(差评)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//找到一个最小的数，使其除以x余a，除以y余b，除以z余c
int x,y,z;										//除数
int a,b,c;										//余数
scanf("%d %d %d %d %d %d",&x,&y,&z,&a,&b,&c);
//求第二、三个除数的公倍数
int i=1;
while((Lcm(y,z)*i%x)!=1)
    i++;
//求第一、三个除数的公倍数
int j=1;
while(((Lcm(x,z)*j%y))!=1)
    j++;
//求第一、二个除数的公倍数
int k=1;
while((Lcm(x,y)*k%z)!=1)
    k++;
//公倍数乘以对应余数后求和
int sum=0;
sum+=Lcm(x,z)*j*b;
sum+=Lcm(y,z)*i*a;
sum+=Lcm(x,y)*k*c;
//确认最小值
printf("%d\n",sum%Lcm(Lcm(x,y),z));


/*拓展对应的代码~~~~~~~~可以替代5到23行
int sum = 0;
//求第二、三个除数的公倍数同时乘以相应余数求和
int i = 1;
while ((Lcm(y, z)*i%x) != a)
    i++;
sum += Lcm(y, z)*i;
//求第一、三个除数的公倍数同时乘以相应余数求和
int j = 1;
while (((Lcm(x, z)*j%y)) != b)
    j++;
sum += Lcm(x, z)*j;
//求第一、二个除数的公倍数同时乘以相应余数求和
int k = 1;
while ((Lcm(x, y)*k%z) != c)
    k++;
sum += Lcm(x, y)*k;
//确认最小
printf("%d\n", sum % Lcm(Lcm(x, y), z));
*/

瑕不掩瑜

如果输入 3 3 3 1 1 1(可能这有点刁钻啊)

合并法中，会发现结果是7，但按照我们给出的题目结果应该是1啊！？

7的来源是：

第一次合并为3*1+1=4，除以3余1，符合条件2，所以得到4；

第二次合并为4*1+1=7，除以3余1，符合条件3，结果为7。

所以答案是7的原因是因为我们默认i是从1开始增长，它代表我们要求的数一定大于三个除数，算经中的问题其实也隐含了这个条件结果要大于三个除数。

如果i从0开始增长，最终答案会是1。

在中国剩余定理中，我们会发现无法跳出循环while ((Lcm(y, z)*i%x) != a) i++;，

原因可能就是定理不适用这种情况吧。我没有深入了解中国剩余定理及其使用。因为我是从韩信点兵的题目了解到这些知识的。搜了一下中国剩余定理，发现它是数论里的一个知识，似乎使用也有一些条件，这里不再过多探索。

emm还是去看了下，中国剩余定理用的时候已经假设了三个除数两两互质。所以输入3 3 3 1 1 1这种就没必要了。但如果能弄懂3 3 3 1 1 1，还是可以让我们对定理有个更好的理解。

(放过我吧，每次写完东西都会发现bug，让我不爽..再多的抽象，也得加点前提条件呐。哪有那么多适用于所有情况的东西，真理也是少之又少。但简单的东西又没那么值得写，最多算个记录罢了)

作者：@臭咸鱼

本文为作者原创，转载请注明出处：https://chouxianyu.github.io/2018/09/01/物不知其数/#more