一单元习题答案

习题1.1

2 如果告诉你，设立美国专利体系的基本目的是促进“有用的技术”，那么你认为算法能是否应该允许申请专利呢

不应该允许申请专利，算法是一种一般性的只能能工具，是一种脑力智力的产出，是一系列解决问题的明确指令，“有用的技术”是通过算法这个工具产生的但是算法本身不能算是“有用的技术”

3 按照算法的精确性写出你从学校到家里的驾驶指南

按照算法的精确性写出你最喜欢的菜的烹饪方法

算法的精确性：算法的每个步骤是具体的、可操作的；每一个步骤都没有歧义。

4 设计一个计算⌊\lfloor⌊ n\sqrt{n}n​ ⌋\rfloor⌋的算法，n是任意正整数。除了赋值和比较计算，该算法只能用到基本的四则运算操作

代码：

public int roundingDown(int n){if (n!=1){for (int i=n/2;i>0;i--){if (i*i<=n){return i;}}}return 0;}

5 设计一个算法，在已经排序的两个列表中，找出所有相同的元素。例如，列表 2，5，5，5和2，2，3，5，5，7。应该输出2，5，5；给定的两个列表长度分别位m，n，你设计的算法最大比较次数是多少？

代码：

public class FindIdentical {public static void main(String[] args) throws IOException {List<Integer> list1 = new ArrayList<Integer>();List<Integer> list2= new ArrayList<Integer>();List<Integer> list3= new ArrayList<Integer>();List<Integer> max= new ArrayList<Integer>();List<Integer> min= new ArrayList<Integer>();int c=0;Scanner sc =new Scanner(System.in);System.out.println("请输入排好序的List1"+":(以0结尾)");for (int j=0;;j++){int num1=sc.nextInt();if (num1==0){break;}list1.add(num1);}System.out.println("请输入排好序的List2"+":(以0结尾)");for (int j=0;;j++){int num2=sc.nextInt();if (num2==0){break;}list2.add(num2);}if (list1.size()>list2.size()){max=list1;min=list2;}else {max=list2;min=list1;}for (int s=0;s<max.size();s++){c++;if (min.size()==0){break;}if (min.get(0).equals(max.get(s))){c++;list3.add(min.get(0));min.remove(0);max.remove(s);s=0;}}System.out.println("相同元素：");for (int i=0;i<list3.size();i++){System.out.print(list3.get(i)+"/");}}}

*最大比较次数 mxxxn *

6 a 用欧几里得算法求gcd(31415,14142)

b 用欧几里得算法求gcd(31415,14142),速度是检查min{m,n}和gcd(m,n)间连续整数的算法的多少倍？

a 欧几里得算法见前面的文章，答案是：1 b gcd(31415,14142)做除法做了11次 连续整数算法 每次做1或者2次除法 所以是 114142/11= 1300214142/11=2600 之间

7 证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数（m，n）都成立

这个我不会

8 对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?

对于任何形如0<=m<n的一对数字,欧几里得算法在第一次迭代时交换m和n, 即 gcd(m,n)=gcd(n,m) 并且这种交换处理只发生一次.

9 a 对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?  

b 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?

a 一次(能整除的m,n) b 5次 gcd(5,8)

10 a 在欧几里得的书里，欧几里得算法用的不是整数除法，而是减法。请用伪代码描述这个版本的欧几里得算法。

b 欧几里得游戏： 一开始，板上写有两个不相等的正整数。两个玩家交替下数字，每一次，当前玩家都必须在板上写出任意两个板上数字的差，而且这个数字必须是新的，也就是说，不能与板上任何一个已有数字相同，当玩家再也写不出新数字是，他就输了。请问你是选择先行动还是后行动呢？

a 直接写代码：

public static int Euclid(int m, int n){//辗转相减// int t;//判断大小// t=m>n?m:n;// n=m<n?m:n;// m=t;int r=m-n;while (r!=0){if (r>n){m=r;}else {m=n;n=r;}r=m-n;}return n;}

b 由a可以得知，最后是得出最大公约数，如果最开始写的两个数中的大数max除以最大公约数得到的值能够整除2，第一个行动的人赢，反之，，

代码：

public class EuclidGame {public static void main(String[] args){System.out.println("输入两个不相等的数:");Scanner scanner=new Scanner(System.in);System.out.println("先写：");int m=scanner.nextInt();System.out.println("后写：");int n=scanner.nextInt();int t;//判断大小t=m>n?m:n;n=m<n?m:n;m=t;whoWin(Euclid(m,n),m);}public static int Euclid(int m, int n){//辗转相除int r=0;while (n!=0){r=m%n;m=n;n=r;}return m;}public static void whoWin(int gcdNum,int max){if((max/gcdNum)%2!=0){System.out.println("先行动");}else {System.out.println("后行动");}}}

11 扩展欧几里得算法

（详细写在欧几里得那篇文章里（现在已经写了））