1.3数学预备知识 1.3.1集合 1、集合的概念 集合(Set)是由一些确定的、彼此不同的成员(Member)或者元素(Element))构成的一个整体。 成员取自一个更大的范围，称为基类型(Base Type))。集合中成员的个数称为集合的基数 (Cardinality). 例如，集合R由整数3、4、5组成，写成R={3,4,5}。此时R的成员是3、4、5，R 的基类型是整型，R的基数是3。依赖于集合的基类型，它的成员经常有一个线性顺序。 集合的每个成员或者是基类型的一个基本元素(Base Element),或者它本身也是一个集 合。我们把是集合的成员叫做该集合的子集(Subset),子集中的每个成员都属于该集合。没有 元素的集合称为空集(Empty Set.又称为Null Set),记作中。如上例中，3是R的成员，记为： 3∈R,6不是R的成员，记为：6年R。{3,4是R的子集。 2、集合的表示法 (1)穷举法：S={2,4,6,8,10: (2)描述法：S={x水是偶数，且0<x≤10；。 3、集合的特性 (1)确定性：任何一个对象都能被确切地判断是集合中的元素或不是： (2)互异性：集合中的元素不能重复： (3)无序性：集合中元素与顺序无关。 1.3.2常用的数学术语 计量单位(Ui):按照EEE规定的表示法标准，字节缩写为B",位缩写为"b",兆字节(220 字节)缩写为缩写为"MB”,千字节(210字节)缩写为"KB"。 阶乘函数(Factorial Function):阶乘函数nl是指从I到n之间所有整数的连乘，其中n为 大于0的整数。因此，51=1·2·3·4·5=120。特别地，01=1。 取下整和取上整(Floor and Ceiling):实数x的取下整函数(Floor)记为Floor(23.5=23,返 回不超过x的最大整数。例如，F1oor(233.4)=233,与F1oor(233.0)的结果相同。实数x的取 上整函数(Ceiling)记为Ceiling(23.5=24,返回不小于x的最小整数.例如，Ceiling(233.4=234, 与Ceiling(234.0)=234的结果相同。 取模操作符(Modulus):取模函数返回整除后的余数，有时称为求余。在JAVA语言中取 模操作符的表示为n%m。从余数的定义可知，n%m得到一个整数，满足n=qm+r,其中q为 一个整数，且0≤r<m。 6
6 1.3 数学预备知识 1.3.1 集合 1、集合的概念 集合(Set)是由一些确定的、彼此不同的成员(Member)或者元素(Element)构成的一个整体。 成员取自一个更大的范围，称为基类型(Base Type)。集合中成员的个数称为集合的基数 (Cardinality)。 例如，集合 R 由整数 3、4、5 组成，写成 R={3，4，5}。此时 R 的成员是 3、4、5，R 的基类型是整型，R 的基数是 3。依赖于集合的基类型，它的成员经常有一个线性顺序。 集合的每个成员或者是基类型的一个基本元素(Base Element)，或者它本身也是一个集 合。我们把是集合的成员叫做该集合的子集(Subset)，子集中的每个成员都属于该集合。没有 元素的集合称为空集(Empty Set,又称为 Null Set)，记作Φ。如上例中，3 是 R 的成员，记为： 3∈R，6 不是 R 的成员，记为：6∉ R。{3，4}是 R 的子集。 2、集合的表示法 （1）穷举法：S＝{2，4，6，8，10}； （2）描述法：S＝{x|x是偶数，且0<x≤10}。 3、集合的特性 （1）确定性：任何一个对象都能被确切地判断是集合中的元素或不是； （2）互异性：集合中的元素不能重复； （3）无序性：集合中元素与顺序无关。 1.3.2 常用的数学术语 计量单位(Unit)：按照 IEEE 规定的表示法标准，字节缩写为"B"，位缩写为"b"，兆字节(220 字节)缩写为缩写为"MB"，千字节(210 字节)缩写为"KB"。 阶乘函数(Factorial Function)：阶乘函数 n!是指从 1 到 n 之间所有整数的连乘，其中 n 为 大于 0 的整数。因此，5!=1·2·3·4·5=120。特别地，0!=1。 取下整和取上整(Floor and Ceiling)：实数 x 的取下整函数(Floor)记为 Floor (23.5)=23，返 回不超过 x 的最大整数。例如，Floor (233.4)=233，与 Floor (233.0)的结果相同。实数 x 的取 上整函数(Ceiling)记为 Ceiling (23.5)=24，返回不小于 x 的最小整数。例如，Ceiling (233.4)=234， 与 Ceiling (234.0)=234 的结果相同。 取模操作符（Modulus）：取模函数返回整除后的余数,有时称为求余。在 JAVA 语言中取 模操作符的表示为 n%m。从余数的定义可知，n%m 得到一个整数，满足 n=qm+r，其中 q 为 一个整数，且 0≤r＜m
1.3.3对数 一般地，如果a(a>0,a≠1)的b次幂等于N,就是a-N,那么数b叫做以a为底N的 对数(Logarithm),记作logN-=b,其中a叫做对数的底数，N叫做真数。 从定义可知，负数和零没有对数。事实上，因为a>0,所以不论b是什么实数，都有a >0,这就是说不论b是什么数，N永远是正数，因此负数和零没有对数。 编程人员经常使用对数，它有两个用途。第一，许多程序需要对一些对象进行编码，那 么表示n个编码至少需要多少位呢？答案是Ceiling (log)。例如，如果要存储1000个不同 的编码，至少需要Ceiling(log210)=10位(10位可以产生1024个不同的可用编码)。第二， 对数普遍用于分析把问题分解为更小子问题算法。在一个线性表中查找指定值所使用的折半 查找算法就是这样一种算法。折半查找算法首先与中间元素进行比较，以确定下一步是在上 半部分进行查找还是在下半部分进行查找。然后继续将适当的子表分半，直到找到指定的值。 一个长度为的线性表被很系次分半，直到最后的子表中只有一个元素，一共需要讲行多少 次呢？答案是1og”次。本书中用到的对数几乎都以2为底，这是因为数据结构和算法总是 把事情一分为二，或者用二进制位来存储编码。 1.4算法和算法分析 1.4.1算法 l、定义：算法(Algorithm)是对特定问题求解步骤的一种描述，是指令的有限序列。 其中每一条指令表示一个或多个操作。 2、特性： (1)输入有0个或多个输入 ①求阶乘的算法需要输入n的值 import java.util.*;/加载java.util类库里的所有类 public class FUN3 public static void main(String[]args) int m; Scanner reader=new Scanner(System.in); /实例化Scanner类对象reader System.out.print("请输入正整数：")； /调用readeri对象的相应方法，读取键盘数据 m=reader.nextInt(); >
7 1.3.3 对数 一般地，如果 a(a＞0，a≠1)的 b 次幂等于 N，就是 a b=N，那么数 b 叫做以 a 为底 N 的 对数（Logarithm），记作 logaN=b，其中 a 叫做对数的底数，N 叫做真数。 从定义可知，负数和零没有对数。事实上，因为 a＞0，所以不论 b 是什么实数，都有 a b ＞0，这就是说不论 b 是什么数，N 永远是正数，因此负数和零没有对数。 编程人员经常使用对数，它有两个用途。第一，许多程序需要对一些对象进行编码，那 么表示 n 个编码至少需要多少位呢？答案是 Ceiling (log2 n)。例如，如果要存储 1000 个不同 的编码，至少需要 Ceiling (log2 1000)=10 位（10 位可以产生 1024 个不同的可用编码）。第二， 对数普遍用于分析把问题分解为更小子问题算法。在一个线性表中查找指定值所使用的折半 查找算法就是这样一种算法。折半查找算法首先与中间元素进行比较，以确定下一步是在上 半部分进行查找还是在下半部分进行查找。然后继续将适当的子表分半，直到找到指定的值。 一个长度为 n 的线性表被促逐次分半，直到最后的子表中只有一个元素，一共需要进行多少 次呢？答案是 log2 n次。 本书中用到的对数几乎都以 2 为底，这是因为数据结构和算法总是 把事情一分为二，或者用二进制位来存储编码。 1.4 算法和算法分析 1.4.1 算法 1、定义：算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。 其中每一条指令表示一个或多个操作。 2、特性： （1）输入 有 0 个或多个输入 ① 求阶乘的算法需要输入 n 的值 import java.util.*;//加载java.util类库里的所有类 public class FUN3 { public static void main(String[] args) { int m; Scanner reader=new Scanner(System.in); //实例化Scanner类对象reader System.out.print("请输入正整数："); //调用reader对象的相应方法，读取键盘数据 m=reader.nextInt();
System.out.println(fun(m)); reader.close(); public static double fun(int n) if (n =1) return 1; else return fun(n-1)*n; ②也可以有两个或多个输入 例求两个整数m和n的最大公约数和最小公倍数，需要输入m和n的值。 ()求两个非负正数a和b(要求>b)的最大公约数可以使用辗转相除法。其算法描述为： 1)a除以b得到的余数为c(0<-c<b): 2)若c=0则算法结束，b为最大公约数。否则转3)： 3)a=b,b-c,转1)： (2)最小公倍数=a◆b/最大公约数(a.b) /*求两个正整数的最大公约数与最小公倍数 【提示】： (1)求两个非负正数a和b(要求a>b)的最大公约数可以使用辗转相除法。其算法描述为： 1)a除以b得到的余数为c(0<=c<b): 2)若c=则算法结束，b为最大公约数。否则转3)： 3)a=b,b=c转1)： (2)最小公倍数=a·b/最大公约数(a,b) 米/ package dspackagel; import java.uti1.*;/加载java.uti1类库里的所有类 public class maxgysmingbs public static void main(String[]args) int p,q Scanner reader=new Scanner(System.in); System.out.print("请输入正整数：")； p=reader.nextInt(); System.out.print("请输入正整数：")； q=reader.nextInt(); int m gys(p,q); 8
8 System.out.println(fun(m)); reader.close(); } public static double fun(int n) { if (n == 1) return 1; else return fun(n - 1) * n; } } ② 也可以有两个或多个输入 例求两个整数 m 和 n 的最大公约数和最小公倍数，需要输入 m 和 n 的值。 (1)求两个非负正数a和b（要求a>b）的最大公约数可以使用辗转相除法。其算法描述为： 1）a除以b得到的余数为c（0<=c<b）； 2）若c=0则算法结束，b为最大公约数。否则转3）； 3）a=b，b=c，转1）； (2)最小公倍数=a * b / 最大公约数(a, b) /*求两个正整数的最大公约数与最小公倍数 【提示】： (1)求两个非负正数a和b（要求a>b）的最大公约数可以使用辗转相除法。其算法描述为： 1）a除以b得到的余数为c（0<=c<b）； 2）若c=0则算法结束，b为最大公约数。否则转3）； 3）a=b，b=c转1）； (2)最小公倍数=a * b / 最大公约数(a, b) */ package dspackage1; import java.util.*;//加载java.util类库里的所有类 public class maxgysmingbs { public static void main(String[] args) { int p,q; Scanner reader=new Scanner(System.in); System.out.print("请输入正整数："); p=reader.nextInt(); System.out.print("请输入正整数："); q=reader.nextInt(); int m = gys(p,q);
int n=gbs(p,q); System.out.print("最大公约数为："+m); System.out.print("最小公倍数为："+n); static int gbs(inta,intb)/最小公倍数 int temp=0; if (a b){temp a;a b;b temp; return a *b/gys(a,b); static int gys(inta,intb)/最大公约数 int temp =0; if (a b){temp a;a b;b temp; int c=a%b; while(c !0) a b; b=C: c a b; return b; 2 ③也可以没有输入 package dspackagel; public class app1_5 public static void main(String[]args){ System.out.println("hello world ") (2)输出有一个或多个输出（处理结果） ①求阶乘的算法一个输出 ②可以有两个输出 package dspackagel; public class app1_6{ public static void main(String[]args){ int num1=3; int num2 5; 9
9 int n = gbs(p,q); System.out.print("最大公约数为:"+m); System.out.print("最小公倍数为:"+n); } static int gbs(int a, int b) //最小公倍数 { int temp = 0; if (a < b) { temp = a; a = b; b = temp; } return a * b / gys(a, b); } static int gys(int a, int b)// 最大公约数 { int temp = 0; if (a < b) { temp = a; a = b; b = temp; } int c = a % b; while(c != 0) { a = b; b = c; c = a % b; } return b; } } ③ 也可以没有输入 package dspackage1; public class app1_5 { public static void main(String[] args) { System.out.println("hello world "); } } （2）输出 有一个或多个输出(处理结果) ① 求阶乘的算法一个输出 ② 可以有两个输出 package dspackage1; public class app1_6 { public static void main(String[] args) { int num1=3; int num2 = 5;
System.out.print1n("交换前：num1="+num1+",num2="+num2); int temp num1;num1 num2;num2 temp; System.out.println("交换后：num1="+num1+",num2="+num2); 2 此算法，最后在屏幕上显示的交换后：numl=5,num2=3就是算法的输出。并不一定非得在 屏幕显示或打印出米才算是算法的输出，算法的处理结果都称为算法的输出。没有 System.(i语句，算法的处理结果即算法的输出也是numl=5,num2=3. (3)确定性每步定义都是确切、无歧义的，而不是含糊的，模棱两可的。 "手举过头顶"是不确定的、含糊的，是双手都举过头？还是左手，或右手，举过头顶多 少厘米，不同的人可以有不同的理解。 (4)有穷性算法应在执行有穷步后结束，死循环的算法是不符合设计要求的。 package dspackagel; public class app1_7{ public static void main(String[]args){ int is1; while(i>0) System.out.println("hello world ") 事实上，"有穷性"是指合理的范围内，（计算机执行1000年才结束的算法，虽然是有穷 的，但超过了合理的限度，也不行。》 (5)有效性每一条运算能有效的执行，并能得到确定的结果。例如，若-O,则执行 a是不能有效执行的。 1.4.2算法设计的要求 对于一个特定的问题，采用的数据结构不同，其设计的算法一般也不同，即使在同一种 数据结构下，也可以采用不同的算法。那么，对于解决同一问题的不同算法，选择哪一种算 法比较合适，以及如何对现有的算法进行改进，从而设计出更适合于数据结构的算法，这就 是算法评价的问题。评价一个算法优劣的主要标准如下： 1、正确性(correctness)4!=4×3×2×1=24算出别的数来，算法没有意义了) 正确的层次： (1)不含语法错误（编译通过的程序，有没有逻辑错误不确定） (2)几组输入数据能得出正确的结果（我们做的程序） (3)典型、苛刻、刁难性数据能得出正确的结果（软件验收标准达到©层次） (4)一切合法输入（几乎不可能达到） 2、可读性(readbility) 必须被人容易理解，通常做法加注释。编程尽量用大众化思路，避免标新立异，用极其
10 System.out.println("交换前: num1="+ num1+",num2="+num2); int temp = num1; num1 = num2; num2 = temp; System.out.println("交换后: num1="+ num1+",num2="+num2); } } 此算法，最后在屏幕上显示的交换后:num1=5,num2=3 就是算法的输出。并不一定非得在 屏幕显示或打印出来才算是算法的输出，算法的处理结果都称为算法的输出。没有 System.out.println()语句，算法的处理结果即算法的输出也是 num1=5,num2=3. （3）确定性 每步定义都是确切、无歧义的,而不是含糊的，模棱两可的。 "手举过头顶"是不确定的、含糊的，是双手都举过头？还是左手，或右手，举过头顶多 少厘米，不同的人可以有不同的理解。 （4）有穷性 算法应在执行有穷步后结束，死循环的算法是不符合设计要求的。 package dspackage1; public class app1_7 { public static void main(String[] args) { int i=1; while(i>0) System.out.println("hello world "); } 事实上，"有穷性"是指合理的范围内，（计算机执行 1000 年才结束的算法，虽然是有穷 的，但超过了合理的限度，也不行。） （5）有效性 每一条运算能有效的执行，并能得到确定的结果。例如，若 b=0，则执行 a/b 是不能有效执行的。 1.4.2 算法设计的要求 对于一个特定的问题，采用的数据结构不同，其设计的算法一般也不同，即使在同一种 数据结构下，也可以采用不同的算法。那么，对于解决同一问题的不同算法，选择哪一种算 法比较合适，以及如何对现有的算法进行改进，从而设计出更适合于数据结构的算法，这就 是算法评价的问题。评价一个算法优劣的主要标准如下： 1、正确性（correctness）4！=4×3×2×1=24(算出别的数来，算法没有意义了) 正确的层次： （1）不含语法错误（编译通过的程序，有没有逻辑错误不确定） （2）几组输入数据能得出正确的结果（我们做的程序） （3）典型、苛刻、刁难性数据能得出正确的结果（软件验收标准达到 c 层次） （4）一切合法输入（几乎不可能达到） 2、可读性（readbility） 必须被人容易理解，通常做法加注释。编程尽量用大众化思路，避免标新立异，用极其