信息学奥赛基础知识

Pascal教程1.计算机基础知识1.1数制及其转换第一章计算机基础知识第一节数制及其转换一、二、八、十六进制转十进制的方法：乘权相加法。例如：（11010110）2=1×27+1×26+0×25+1×24+0×23+1×22+1×21+0×20=（214）10（2365）8=2×83+3×82+6×81+5×80=（1269）10（4BF）16=4×162+11×161+15×160=(1215)10带小数的情况：（110.011）2=1×22+1×21+1×20+0×2-1+1×2-2+1×2-3=（6.375）10（5.76）8=5×80+7×8-1+6×8-2=（5.96875）10（D.1C）16=13×160+1×16-1+12*16-2=（13.109375）10二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。例一：（43）10=（101011）2例二：（0.375）10=（0.011）2三、二进制转八进制的方法1位数八进制与二进制对应表八进制二进制00001001201030114100510161107111转换方法:对二进制以小数点为分隔，往前往后每三位划为一组，不足三位补0，按上表用对应的八进制数字代入即可。例如：(10111011.01100111)=010,111,011.011,001,110=（273.36）8三、二进制转十六进制的方法1位数十六进制与二进制对应表十六进制二进制00000100012001030011401005010160110701118100091001A1010B1011C1100D1101E1110F1111转换方法:对二进制以小数点为分隔，往前往后每四位划为一组，不足四位补0，按上表用对应的十六进制数字代入即可。例如：(10111011.01100111)=1011,1011.0110,0111=（BB.67）16四、进制的英文表示法：以上都是用括号加数字的表示方法，另外还有英文表示法，就是以BIN、OCT、HEX、DEC分别代表二、八、十六、十进制。或者只写第一个字母。例如1101B表示是二进制。有些地方为了避免“O”跟“0”混淆，把O写成Q。1.2算术运算和逻辑运算第二节算术运算和逻辑运算一、二进制的算术运算1、加法运算规则：0+0=00+1=11+0=11+1=102、减法运算规则：0-0=00-1=1（向高位借1）1-0=11-1=03、乘法运算规则：0×0=00×1=01×0=01×1=1二、逻辑运算1、基本运算①逻辑乘，也称“与”运算，运算符为“·”或“∧”0·0=00·1=01·0=01·1=1使用逻辑变量时，A·B可以写成AB②逻辑加，也乘“或”运算，运算符为“+”或“∨”0+0=00+1=11+0=11+1=1③逻辑非，也称“反”运算，运算符是在逻辑值或变量符号上加“—”0=11=02、常用运算异或运算：A⊕B=A·B＋A·B2、基本公式①0，1律A·0=0A·1=AA＋0=AA＋1=1②交换律A＋B=B＋AA·B=B·A③结合律A＋B＋C=（A＋B）＋C=A＋（B＋C）A·B·C=（A·B）·C=A·（B·C）④分配律A·（B＋C）=A·B＋A·C⑤重叠律A＋A＋...＋A=AA·A·...·A=A⑥互补律A+A=1A·A=0⑦吸收律A＋A·B=AA·（A＋B）=AA＋A·B=A＋BA·（A＋B）=A·B⑧对合律对一个逻辑变量两次取反仍是它本身⑨德·摩根定理A+B=A·BA·B=A＋B三、逻辑代数的应用1、逻辑表达式化简例如：F=A·B＋A·B＋A·B=A·B＋A（B＋B）（利用分配律）=A·B＋A（利用互补律以及0，1律）=A＋B（利用吸收律）2、对指定位进行运算，假设变量A有八位，内容是d7d6d5d4d3d2d1d0①将变量A的d5位清零A·（11011111）→A②将变量A的各位置1A＋（11111111）→A1.3原码、反码和补码第三节原码、反码和补码计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。一、原码求原码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位照抄。【例1】X=+1001001[X]原=01001001【例2】X=-1001001[X]原=11001001二、反码求反码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位按位取反。【例3】X=+1001001[X]反=01001001【例4】X=-1001001[X]反=10110110三、补码求补码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位按位取反后，最低位加1。【例5】X=+1001001[X]补=01001001【例6】X=-1001001[X]补=10110111四、补码加减法计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。1、补码加法[X+Y]补=[X]补+[Y]补【例7】X=+0110011,Y=-0101001，求[X+Y]补[X]补=00110011[Y]补=11010111[X+Y]补=[X]补+[Y]补=00110011+11010111=00001010注：因为计算机中运算器的位长是固定的，上述运算中产生的最高位进位将丢掉，所以结果不是100001010，而是00001010。2、补码减法[X-Y]补=[X]补-[Y]补=[X]补+[-Y]补其中[-Y]补称为负补，求负补的方法是：对补码的每一位（包括符号位）求反，最后末位加“1”。【例8】X=+0111001,Y=+1001101，求[X-Y]补[X]补=00111001[Y]补=01001101[-Y]补=10110011[X-Y]补=[X]补+[-Y]补=00111001+10110011=11101100五、数的表示范围通过上面的学习，我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示0~255共256个数（00000000~11111111），如果是有符号数则能表示-128~127共256个数（10000000~01111111）。如果两个字节表示一个整数，则共有65536个数可以表示，大部分程序设计语言中整数的范围都是-32768~32767的原因，可以看出这种整数类型是16位的有符号数，而且是补码表示的。1.4浮点数的表示方法第四节浮点数的表示方法一、浮点数表示一个数的浮点形式（设基数是2）可写成：N=M×2E其中:M代表尾数,E代表阶码。计算机中浮点数只用尾数和阶码表示，其形式如下：阶码尾数符号尾数浮点数的精度由尾数决定，数的表示范围由阶码的位数决定。为了最大限度提高精度，尾数采用规格化形式，既1/2≤M1。采用二进制表示时，若尾数大于零，则规格化数应该是01XXXX的形式；若尾数小于零，则规格化数应为10XXXX的形式。二、机器零当浮点数的尾数为0或阶码为最小值时，计算机通常把该数当作零，因此程序中进行浮点运算时，判断某数是否为零，通常可以用小于某个极小值来代替。三、实例【例1】设X=0.0110×23,用补码、浮点数形式表示阶码为Xj=011，尾数为00110，这时由于X尾数不符合01XXXX的形式，因此不是规格化数，必须先进行规格化处理。方法：若尾数小于1/2，把尾数左移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码减1即可，否则继续左移和调整阶码；若尾数大于1，则把尾数右移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码加1即可，否则继续右移和调整阶码。上例中，00110左移一位为01100，符合规则化标准，此时阶码减1，为010即得到浮点表示形式。这个数具体在计算机中如何表示要看计算机中规定的阶码和尾数的位数，若阶码和尾数均为16位，则上面的数X在计算机内部表示就是00000000000000100110000000000000，不足均用零填充。1.5奇偶校验第五节奇偶校验计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类错误，在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验。奇偶校验能发现一位或奇数位错误，且不能纠正错误。一般以字节（八位二进制）为单位加1位奇偶校验位。奇偶校验分奇校验和偶校验两种。一、奇校验：一个字节前面加一位校验位使得“1”的个数保持为奇数，若八位二进制数中“1”的个数为偶数，则校验位为“1”；若八位二进制数中“1”的个数为奇数，则校验位为“0”。【例1】给1001100101101101加奇校验结果为110011001001101101二、偶校验：一个字节前面加一位校验位使得“1”的个数保持为偶数，若八位二进制数中“1”的个数为偶数，则校验位为“0”；若八位二进制数中“1”的个数为奇数，则校验位为“1”。【例2】给1001100101101101加偶校验结果为0100110011011011011.6ASCII码表第六节ASCII码表代码字符代码字符代码字符代码字符代码字符3252472H92\112p33!53573I93]113q34”54674J94^114r35#55775K95_115s36$56876L96`116t37%57977M97a117u38&58:78N98b118v39’59;79O99c119w40(6080P100d120x41)61=81Q101e121y42*6282R102f122z43+63?83S103g123{44,64@84T104h124|45-65A85U105i125}46.66B86V106j126~47/67C87W107k48068D88X108l49169E89Y109m50270F90Z110n51371G91[111o目前使用最广泛的西文字符集及其编码是ASCII字符集和ASCII码（ASCII是AmericanStandardCodeforInformationInterchange的缩写），它同时也被国际标准化组织（InternationalOrganizationforStandardization,ISO）批准为国际标准。基本的ASCII字符集共有128个字符，其中有96个可打印字符，包括常用的字母、数字、标点符号等，另外还有32个控制字符。标准ASCII码使用7个二进位对字符进行编码，对应的ISO标准为ISO646标准。下表展示了基本ASCII字符集及其编码：字母和数字的ASCII码的记忆是非常简单的。我们只要记住了一个字母或数字的ASCII码（例如记住A为65，0的ASCII码为48），知道相应的大小写字母之间差32，就可以推算出其余字母、数字的ASCII码。虽然标准ASCII码是7位编码，但由于计算机基本处理单位为字节（1byte=8bit），所以一般仍以一个字节来存放一个ASCII字符。每一个字节中多余出来的一位（最高位）在计算机内部通常保持为0（在数据传输时可用作奇偶校验位）。由于标准ASCII字符集字符数目有限，在实际应用中往往无法满足要求。为此，国际标准化组织又制定了ISO2022标准，它规定了在保持与ISO646兼容的前提下将ASCII字符集扩充为8位代码的统一方法。ISO陆续制定了一批适用于不同地区的扩充ASCII字符集，每种扩充ASCII字符集分别可以扩充128个字符，这些扩充字符的编码均为高位为1的8位代码（即十进制数128~255），称为扩展ASCII码。下表展示的是最流行的一套扩展ASCII字符集和编码：2.计算机硬件基础知识2.1中央处理器第二章计算机硬件基础第一节中央处理器一、中央处理器的组成中央处理器简称CPU，由控制器、运算器组成。运算器及控制器的基本功能：运算器是计算机