计算思维实践之路(一)

宇哥小屋 2020-01-05

展开全文

6月11日，晴。“重五山村好，榴花忽已繁”。

在计算机的法则里，计算思维重于一切。大部分人一开始就把自己束缚在一张乏味的语法清单上，久而不入其门，何不一开始就沿着计算思维对程序进行理解，在不断尝试中寻求着转化的灵感。

例1 “今有物不知其数，三三数之剩二（就是这个数除以三的余数是二的意思），五五数之剩三，七七数之剩二，问物几何。”（孙子算经）

俺老猪是这样想的：

X÷3=A…2 ==>X=3xA+2，列出除以3余2的数：2,5,8,11,14,17,20,23,26,...;

X÷5=B…3 ==>X=5xB+3，列出除以5余3的数： 3,8,13,18,23,28,...;

X÷7=C…2 ==>X=7xC+2，列出除以7余2的数： 2,9,16,23,30,...;

挨个去找到符合条件的数，俺老猪发现了符合题目条件的不只一个解，可能有无穷多个解，筛出的最小数是23，正好是俺老猪一顿的馒头数，哈哈..,吃馒头去了...

老猪的思维代表了一般人朴素的思维过程，贪吃贪睡的猪无能都会想到，不用拐弯抹角，很直接，此方法的优点就是直接，简单；缺点是罗列数较多，计算并筛选将很费时，特别是当需要的数增大时（如求10000以内符合条件的数），工作量将无法承受。还有木有更好的方法？

老猪的枚举法就是凑，很‘笨’，但也最直观。适合小学生学习。即，当A=7、B=4、C=3时，X 都等于23。所以最小X=23。由于3、5、7的最小公倍数是105，所以，通解 X=23+105K (K=0、1、2、3、…)。

猪无能就知道好吃懒惰，俺沙悟净谨守佛门戒律，踏踏实实，对计算机也悟出了一点点门道，待俺试上一试。

1、任务分析

2、流程图

3、代码实现

/*
ID: <span style="font-family:Comic Sans MS;">saheshang</span>
PROG: hanxin
LANG: C++
*/
#include <stdio.h>
int main() {
    int x,n;
    scanf("%d",&n);
    for( x=0;x<n;x++){
    	if(((x%3)==2)&&((x%5)==3)&&((x%7)==2)){
    		    printf("%d\n",x);
		}
	}
	return 0;
}

其中，n为需要在多大的数里面寻找符合条件的数，几秒就得出100以内符合条件的数，比猪无能强多啦。

沙僧的思维比猪无能强点，利用计算机一丝不苟、不厌其烦的特点，暴力枚举每个数，苦苦寻找符合三个条件的数，此方法的优点就是代码简单明了；缺点是有点笨，还有木有更优化的方法？

猪无能笨，沙悟净拙，俺老孙深得菩提老祖真传，会十八般武艺，腾云驾雾，且有金刚不坏之身。大闹天宫，力战千军万马，保唐僧西天取经过五关斩六将。区区一个小问题，何足挂齿哉。

菩提老祖亲授孙子算法秘诀如下：

找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加（15*2+21*3+70*2）得到和233。
用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数。

/*
ID: sunwukong
PROG: hanxin
LANG: C++
*/
#include<iostream>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	int n=(a*70+b*21+c*15)%105;
	if(n>100||n<10) cout<<"No answer"<<endl;
	else cout<<n<<endl;
}

a,b,c分别代表余数。

这猴头果然颇有点小聪明，孙子算法的关键，在于70、21和15这三个数的确定。后来流传的《孙子歌》中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。《孙子算经》没有说明这三个数的来历。

实际上，它们具有如下特性：这三个数可以从最小公倍数M=3×5×7=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。假令k1=2，K2=1，K3=1，那么整数Ki（i=1，2，3）的选取使所得到的三数70、21、15被相应模数相除的时候余数都是1。由此出发，立即可以推出，在余数是R1、R2、R3的情况下的情况。

这就是所谓的“一次同余式”问题。哈哈！又落脚到数学模型了。用现代数学语言表示，就是求解一次同余式组：
　　N≡R1（mod3）≡R2（mod5）≡R3（mod7）
其解可表示为：
　　N＝70 R1＋21 R2＋15 R3－105P
这里P为整数，在上述问题中，R1＝R3＝2，R2＝3，取P＝2，得到答案：N＝23。
　　在明朝程大位的数学著作《算法统宗》中，上述题解被写成一首在数学史上流传颇广的歌诀：
　　三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知。

同余方程组的解法： x≡2(mod3)

x≡3(mod5)
x≡2(mod7)

∵模3、5、7两两互素（质）
∴知同余式组有整数解

用孙子定理解题如下：

       b1＝2　 b2＝3    b3＝2
       m1＝3　m2＝5　 m3＝7
       M＝m1×m2×m3＝3×5×7＝105      ...最小公倍数
       M1＝M÷m1＝105÷3＝35              ...古代叫衍数
     M2＝M÷m2＝105÷5＝21
     M3＝M÷m3＝105÷7＝15

①M1×M1'≡35×M1'≡1(mod3) ...分堆求一
　　　　　即（3×11＋2）M1'≡1(mod3)
　　　　　　　　　　2×M1'≡1(mod3)
　　　　　得M1'＝2 ...古代叫乘率

     ②M2×M2'≡21×M2'≡1(mod5)
                即21×M2'≡1(mod5)
                得M2'＝1
      ③M3×M3'≡15×M3'≡1(mod7)
                即15×M3'≡1(mod7)
　　　　　得M3'＝1

∴x≡bi×Mi×Mi'＝b1×M1×M1'＋b2×M2×M2'＋b3×M3×M3'

=2×35×2＋3×21×1＋2×15×1

=233mod(M)

=233mod(105)

=23mod(105)

即x＝23＋105 t（t是整数　t＝0，±1，±2，±3……）