线性表的深入应用.docVIP

线性表的深入应用 【学习与辅导方式】 自学为主，所有提到的例题和算法都要编写完整的程序，有疑问的地方可以在论坛中提问。 【学习要点】 （1）了解高精度计算中数据处理方法，掌握常见高精度计算方法 （2）了解数据处理的常用方法：排序与查找，理解它们的概念 （3）掌握常见排序与查找的基本方法及算法的时间复杂性 （4）能够比较多种排序算法的优缺点及空间、时间的复杂性 （5）理解散列查找、哈希函数的概念，并能够进行简单应用 1 高精度运算 由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最多只能输出16位有效数字，如果超过16位，则只能按浮点形式输出，另外，一般计算机实数表示的范围为1038，如果超过这个范围，计算机就无法表示了。但是我们可以通过一些简单的办法来解决这个问题。这就是我们要说的高精度计算。 基本方法在计算机上进行高精度计算，首先要处理好以下几个基本问题： 数据的接收与存储； 计算结果位数的确定； 进位处理和借位处理； 商和余数的求法； 下面我们逐一介绍一下这几个问题的解决方法。 数据的接收与存储要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。： ①当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。 ②当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。 ③各数位分离。 ）计算结果位数的确定 ①两数之和位数最大为较大的数的位数加1。 ②乘积位数最大为两个因子的位数之和。 ③阶乘与乘方位数可以采用对数运算来确定位数。 进位处理和借位处理 ①进位处理 进位。如果某个单元中的数大于10，则将该单元中的数减去10，并将进位标志T设为1当对下一单元进行时，加上前一个单元的进位标志T同时将T再次置为0，不断重复，直到最高位为止。 减法的借位处理 （4）商和余数的求法 设A，B分别为不大于9位的整数，则： C:=A DIV B为商的整数部分 X:=A MOD B为余数 算法与实例 例1 输入格式：输入的第一行是一个1到1000的整数N，表示总共有N位水王参加了争霸赛。以下依次给出每位水王的描述，一位水王的描述占据两行，第一行为一个仅由字母和数字组成的长度不超过20的字符串，代表这个水王的ID，第二行一个高精度的整数(非负数)，代表这个水王的发贴数。注意，这个整数的首位没有不必要的0。考虑到IOIForum的数据库是有限的，所有水王发贴数的总长度（注意，是总长度而不是总和）不会超过10000。除了字母、数字和必要的换行，输入中不会出现空格等字符。 输出格式：依次输出按照发贴数从大到小排好序的各位水王的ID，每个ID占据单独的一行。不能有任何多余的字符。若几个ID的发贴数相同，则按照ID的字典顺序先后排列。 样例： WATER.IN WATER.OUT 6 lowai 1534534124561243453 zhouyuan 23453265344 Maolaoda 23442353452342 BuTaoCaiGuai 7568784573464 ArthurKing 97534892734723947 hyyylr6Lowai ArthurKing Maolaoda BuTaoCaiGuai Zhouyuan Hyyylr6 （1）时间、空间估算 从空间上考虑，如果发帖数按位存储的话，需要占用内存103*104=10MB。可以承受。 从时间上考虑，本题主要的耗时是排序和比较，由于水王数达到103，且每个水王的发帖数达104，因此，选择快排是比较好的做法。时间估算为。 （2）核心算法——高精度数的比较 【例例 用A，B，C三个字母组成长度为3的字符串，但每个字母都不允许重复使用，并且每个字母都不能摆在自己序号的位置上，则符合条件的只有两个字符串：BCA，CAB。对于键盘输入的N（N≤17）,则意味着给出了A1,A2,…An个不同的字母(例如N=3时,A1=A,A2=B,A3=C),用它们组成长度为N的字符串,但每个字母不允许重复使用,并且每个字母都不能摆在自己序号的位置上。问有多少个符合条件的字符串。 （1）算法分析 根据题意，N个字母构成了错排，根据错排公式，符合条件的字符串共有： 由于N≤17，因此需要用高精度数表示运算结果。 （2）核心算法 估算结果，最大值不超过1617，因此位数最大不超过21位。 ① 高精度加法 ② 高精度乘法——高精度乘以单精度 【例麦森数 ，需要考虑优化，可以采用数位压缩的方式。如每9位存储在一个单元中，正好符合longint的运算范围。 在本题中，任务1比较简单，直接采用对数运算即可： 任务2中，由于2P末位必然大于0，因此只要在输出时大于末位进行减1处理就可以了。 核心算法——高精度加法