节计算学科中核心概念.pptxVIP

第4章　　　计算学科中的核心概念;4.1 引 言;4.2 算 法;4.2.1 算法的历史简介;; 例4.1 问：方程13x+26y=52有无整数解？ 答：13和26的最大公因子是13，13又可整除52，故该方程有整数解（如x=2，y=1即方程的解）。 例4.2 问：方程2x+4y=15有无整数解？ 答：2和4的最大公因子是2，2不能整除15，故该方程无整数解。 因此可以看出，对于两个未知数的线性丢番图方程来说，求解的关键就是求最大公因子。公元前300年左右，欧几里德在其著作《几何原本》（Elements）第七卷中阐述了关于求解两个数最大公因子的过程，这就是著名的欧几里德算法：给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。 ;;4.2.2 算法的定义和特征;;;4.2.3 算法实例;;; 斐波那契数列不仅包含着一个有趣的“兔子问题”，而且还是一个关于加法算法的典型实例。下面，给出求解前个斐波那契数的算法。 设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的值，即定义中的Fn+1，变量Z表示后一个数的值，即定义中的Fn+2。那么求解问题的自然语言描述如下： （1）如果n=0，那么将0赋值给Y，并输出Y，转步骤（11）继续执行； （2）将0赋给X，将1赋值给Y； （3）输出X、Y； （4）将1赋值给I； （5）如果I大于-1，则转到步骤（11），否则继续执行；;;4.2.4 算法的表示方法;;;;;;;;;;;;4.2.5 算法分析;;;;4.3 数据结构;4.3.1 数据结构的基本概念;;;4.3.2 常用的几种数据结构;;;;4.4 程 序;;4.5 软 件;4.6 硬 件;4.7 数据存储和表示;4.7.1 进位制数及其相互转换; 1.十进制数与二进制数之间的转换 我们知道在表示十进制数的时候，从右边起的第1个数字是1（100 = 1），第2个数字是10（101 = 10），第3个数字是100（102 = 100），第4个数字是1000（103 = 1000），以此类推。如果我们要把十进制整数3254展开，我们很容易知道存在如下的关系，3254=3*103 +2*102 +5*101 +4*100 。 这样的关系同样存在二进制数中，只是这里的基数不是10，而变成了2。这时，从右边起的第1个数字就是1（20 = 1），第2个数字就是2（21 = 2），第3个数字是4（22 = 4），第4个数字就是8（23 = 8）了。从这一点出发，我们很容易找到十进制和??进制转换的方法。 （1）十进制数转换为二进制数 ; 若R表示十进制整数，Kn-1 ，Kn-2 ，Kn-3 … K1 ，K0 表示二进制数的各位数，最低（右）端一位为K0， 最高（左）端一位为Kn-1。为了区分十进制数和二进制数，我们分别给十进制数和二进制数加上下标10和2，即有如下形式 （R)10 = （Kn-1Kn-2Kn-3…K1K0)２　 ① 与上文提到的十进制的展开类似，我们可以将上式写为 （Kn-1Kn-2Kn-3…K1K0)２ = Kn-1*2n-1 +Kn-2*2n-2+Kn-3*2n-3+…+K1*21+K0*20 ② 显然，从等式右边看，除最后一项K0以外，其余每项都包含有２的因子，它们都能２除尽。故R除以2，它们的余数即为K0，商变为Kn-1*2n-2+Kn-2*2n-3+Kn-3*2n-4+K1*20，将得到的商再除以2，余数即为K1 ，商变为Kn-1*2n-3 +Kn-2*2n-4+Kn-3*2n-5+…+K2*20 ，这样依次下去，分别得到K2 ，K3 ，K4 … Kn ，最终得到二进制数的各位数。十进制数126的转换如下图所示。; 根据上图，十进制数126可以用二进制数1111110表示（这里只讨论数之间的转换，没有涉及标准格式的存储，为了方便，如无特殊说明，不用0去补足计算机的实际位数）。 （126）10 = （1111110）2 （2）二进制数转换为十进制数 二进制数转换为十进制数比较简单，由①式和②式我们很容易得到; (R)10 = Kn-1*2n-1 +Kn-2*2n-2+Kn-3*2n-3+…+K1*21+K0*20 我们只要简单地将每一位与其对应为的2的幂次方相乘，然后求和。比如 (1111110)2 = 1*26+1*25+1*24+1*23+1*22+1*21+0*20 = 64+32+16+8+4+2+0 =(126)10 。