第一次课后作业 1. C/C++/Java 哪些值不是头等程序对象 2. C/C++/Java 哪些机制采用的是动态束定

C/C++/Java 哪些值不是头等程序对象 在程序语言学中把相当于数学对象的程序对象叫做头等对象，因为它们作为运算对象的权利未受到任何限制。程 序对象的权限具体说来是： 可作为操作数出现在表达式中求值。 可作为单独的存储实体。 可作为参数传递到过程或函数。 可作为函数返回值。 可以构成复杂的数据结构。 函数抽象（即函数名）不能作函数返回值。 数组元素（单个，如a[3]）不是可存储体，也不能作为函数返回值。 变量引用（如&j）不能在表达式中求值。 类和结构体的抽象（类名）不是头等程序对象，但具体的实例是头等程序组对象。

C/C++/Java 哪些机制采用的是动态束定 动态束定又叫动态联编，是指联编在程序运行时动态地进行，根据当时的情况来确定调用哪个 同名函数。动态联编对成员函数的选择是基于对象的类型，针对不同的对象类型将做出不同的编译 结果。 C++ 继承 通过基类指针指向子类型的对象并调用虚函数来实现 Java 继承（普通类和抽象类）、接口 通过继承中超类对象引用变量引用子类对象来实现 通过接口类型变量引用实现接口的类的对象来实现 C 没有

C++ 动态束定 - 继承 class A { public: virtual void f() {cout<<"A"<<endl;} }; class B : public A{ virtual void f() {cout<<"B"<<endl;} void main(){ A* p = NULL; A a; B b; p = &a; p->f(); // A p = &b; p->f(); // B }

Java 动态束定 - 继承 class A { void f() { System.out.println(“This is A”); } class B extends A { System.out.println(“This is B”); class Main{ public static void main(String[] args) { A a = new A(); B b = new B(); a.f(); // This is A a=b; a.f(); // This is B }

Java 动态束定 – 接口 interface A { void f(); } class B implements A { public void f() { System.out.println(“This is B”); class C implements A { System.out.println(“This is C”); class Main { public static void main(String[] args) { A a; a= new B(); a.f(); // This is B a = new C(); a.f(); // This is C }

比较分析C/C++和Java的参数传递机制，以及它们各自的优缺点 按值传递：void f(int x) : f(var) 实参和形参各自占有独立的存储单元，调用时将实参的值拷贝给形参，在被调用的函数执行时,访问 的是形参单元，函数调用结束后形参所占据的存储空间就被系统收回了。 按地址传递: void f(int* x) : f(&var) 按指针传递，它将一个变量的地址传送给调用函数的形参，在函数中可以改变实参。 按引用传递：void f(int& x) : f(var) 通过引用进行参数传递，效果与传递指针一样，但不必申请额外的空间。形参相当于实参的别名， 改变形参的值实际就是改变实参的值。

比较分析C和Java的参数传递机制，以及它们各自的优缺点 按值传递基本数据类型 和C++一样，针对基本数据类型以及String。 按值传递复合数据类型（原理类似于C/C++的按地址传递） 主要是针对复合数据类型，它传递的是一个对象句柄的拷贝，在函数中可以改变变量的值。 优缺点： C/C++中的指针（按地址传递）可以毫无约束地操作内存中的东西，功能强大但危险。 对于基本数据类型，Java不能在函数中对基本数据类型进行修改操作，会增加不便；对于复合数据类型， Java只能传递对象的引用，在函数中会对对象产生影响。 而C/C++对于对于基本数据类型和复合数据类型，既可以传递引用，又可以传递对象的拷贝（按值传递）， 更加灵活。

第二次课后作业：函数式编程和逻辑式编程 1. 使用Miranda编写归并排序 2.使用Miranda语言分别实现斐波那契数列的递归和迭代程序 3.用prolog给定一个整数范围，打印所有偶数及并将此偶数表示为两个素数之 和（哥德巴赫猜想）。 如输入为：？- goldbach_list(9,12). 输出： 10 = 3 + 7 12 = 5 + 7

使用Miranda编写归并排序 merge a [] = a merge [] b = b merge (ah:at) (bh:bt) = ah: (merge at (bh:bt)), ah <= bh = bh: (merge (ah:at) bt), otherwise mergeSort L = L, len < 2 = (merge (mergeSort left) (mergeSort right), othereise where len=#L mid=len / 2 left=[ L!i | i <-[0..(mid-1)] ] right=[ L!i | i <-[mid..(len-1)] ]

使用Miranda语言分别实现斐波那契数列的递归和迭代程序，注意递归和迭代的区别 递归： Fib n = 0， n=0 = 1， n=1 = Fib (n-1) + Fib (n-2)， n>1 迭代： Fib n = Fib_iter 0 1 n Fib_iter a b n = a, n=0 = Fib_iter b a+b n-1, n>0 递归会产生重复计算，并需要在调用到最底层之前保存之前计算过的结果；迭 代计算量相对小一些，但需要额外的变量。

用prolog给定一个整数范围，打印所有偶数及并将此偶数表示为两个素数之和（哥德巴赫猜想） % 判断P是否是素数 is_prime(2). is_prime(3). is_prime(P) :- integer(P), P > 3, P mod 2 =\= 0, \+ has_factor(P,3). % N 是否有不小于 L 的奇数因子 has_factor(N,L) :- N mod L =:= 0. has_factor(N,L) :- L * L < N, L2 is L + 2, has_factor(N,L2). % 验证哥德巴赫猜想，其中L是和为N的两个素数 goldbach(4,[2,2]) :- !. goldbach(N,L) :- N mod 2 =:= 0, N > 4, goldbach(N,L,3). goldbach(N,[P,Q],P) :- Q is N - P, is_prime(Q), !. goldbach(N,L,P) :- P < N, next_prime(P,P1), goldbach(N,L,P1). next_prime(P,P1) :- P1 is P + 2, is_prime(P1), !. next_prime(P,P1) :- P2 is P + 2, next_prime(P2,P1).

用prolog给定一个整数范围，打印所有偶数及并将此偶数表示为两个素数之和（哥德巴赫猜想） % 打印所有满足A<=N<=B且为偶数的N的哥德巴赫组合 goldbach_list(A,B) :- goldbach_list(A,B,2). goldbach_list(A,B,L) :- A =< 4, !, g_list(4,B,L). % //是除操作，不过只保留整数 goldbach_list(A,B,L) :- A1 is ((A+1) // 2) * 2, g_list(A1,B,L). g_list(A,B,_) :- A > B, !. g_list(A,B,L) :- goldbach(A,[P,Q]),print_goldbach(A,P,Q,L), A2 is A + 2, g_list(A2,B,L). print_goldbach(A,P,Q,L) :- P >= L, !, writef('%t = %t + %t',[A,P,Q]), nl. print_goldbach(_,_,_,_).

BNF范式 Chomsky的四种文法 产生式 左符号集→右符号集 由左符号集推导出右符号集 0型文法 产生式 左符号集→右符号集 由左符号集推导出右符号集 0型文法 α→β α∈(N∪T)+，β∈(N∪T)* 递归可枚举语言 图灵机可以识别 1型文法 α A β→αBβ α,β∈(N∪T)*， A∈N， B∈(N∪T)+ 上下文相关文法上下文敏感语言 线性有界自动机可识别 2型文法 A→α α∈(NUT)*, A∈N 上下文无关文法语言 非确定下推自动机可识别

BNF范式 1 2 3 3型文法 A→αB｜Bα α∈T*, A,B∈N 正则文法 正则语言 有限自动机可以识别 正则文法 正则语言 有限自动机可以识别 可消除右端非终法符 P可以成为终结符表达式 例： N={S,R,Q}, T={a,b,c} P={S→Ra，S→Q，R→Qb，Q→c} 则有 S→Ra→Qba→cba|S→Q→c R→Qb→cb Q→c 简单语言用 3型，汇编，词法子语言 最常用 2型 0、1型无法判定二义性, 不常用 1 2 3

BNF范式 BNF： ::= 被定义为（代替→） < > 指示非终结 终结符直接写出(或黑体) ｜ 或者 有扩充： [ ] 括号内容是可选的 { } 括号内容可重复0至多次 或扩充： C+ 'Kleene加' C可重复1至多次 C* ‘Kleene星’ C可重复0至多次

Lambda 表达式 求证：zerop 1 = F 证： zerop 1 = (λn.n(λx.F)T ) 1 = 1 (λx.F)T β归约[1/n] = (λp.λq.pq) (λx.F)T = (λq.(λx.F)q)T β归约[(λx.F)/p] = (λx.F)T β归约[T/q] 或者η归约 = F η归约 求证：zerop 0 = T 证： zerop 0 = (λn.n(λx.F)T ) 0 = 0 (λx.F)T β归约[0/n] = (λp.λq.q) (λx.F)T = (λq.q)T β归约[(λx.F)/p] = T β归约[T/q]

并发程序设计 结果应该为: 线程 1: 1 线程 1: 2 线程 1: 3 线程 1: 4 线程 1: 5 线程 2: 6 线程 2: 7 线程 2: 8 线程 2: 9 线程 2: 10 ... 线程 3: 71 线程 3: 72 线程 3: 73 线程 3: 74 线程 3: 75 启动 3 个线程打印递增的数字, 线程 1 先打印 1,2,3,4,5, 然后是线程2 打 印 6,7,8,9,10, 然后是线程 3 打印 11,12,13,14,15。 接着再由线程 1 打 印 16,17,18,19,20....以此类推, 直到 打印到 75。 程序的输出如右方所示。 请用多种方法（synchronized、 Lock 等）控制线程，实现输出打印。 基本所有同学都能给出2-3种实现方法，并给出代码、编译环境和打印结果。

实现方法1 通过全局变量或标志位来 指定当前由哪一个线程打 印数据。 class OrderPrint extends Thread { private static int who = 1; // whose turn to print private static int number = 1; // number to print private int limit; // how many numbers I can print private int count; // how many numbers printed so far private int me; // self id number public OrderPrint(int total, int id) { limit = total; me = id; count = 0; } // indicates which thread to print numbers public int whoseTurn() { return who; } // set next thread to run public void setWho(int turn){ who = turn; } public void run() { while (true) { if (whoseTurn() == me) { // my turn to print numbers for (int i = 0; i < 5; i++) { System.out.println("线程" + me + ": " + number); count++; number++; } setWho(me+1 > 3 ? 1 : me+1); // set who to next one to print if (count >= limit) // enough number have been printed return ; public static void main(String[] args) { // each thread prints total of 75/3 numbers new OrderPrint(75/3, 1).start(); new OrderPrint(75/3, 2).start(); new OrderPrint(75/3, 3).start(); 实现方法1 通过全局变量或标志位来 指定当前由哪一个线程打 印数据。 简单清晰，不会发生资源 竞争（同一时间只有一个 线程修改变量值，其他线 程只是读取变量值）。 代码来自：SY1306230_余恒洋

实现方法2 采用原始的synchronized, wait(), notify(), notifyAll()等方式控制线 程。 特点 利用synchronized实现互斥变量的保护，如果互斥变量当前的标号 不等于线程的ID号就让他等待，否则进入访问区域，访问之后对互斥 变量的计数进行更新，以便下一个线程可以访问互斥变量，并通知所 有等待的线程互斥变量空闲。 特点 synchronized是在JVM层面实现的，不但可以通过一些监控工具监 控synchronized的锁定，而且在代码执行时出现异常，JVM会自动 释放锁定。 在资源竞争不是很激烈的情况下，偶尔会有同步的情形下， synchronized很合适。因为编译程序通常会尽可能的进行优化 synchronize，另外可读性非常好。 基本所有同学都能给出2-3种实现方法，并给出代码、编译环境和打印结果。

实现方法2 static class Printer implements Runnable{ static int num = 1; //开始数字 static final int END = 75; int id; public Printer(int id) {this.id = id;} @Override public void run(){ synchronized (Printer.class) { while(num <= END){ //如果是属于自己的数，依次打印出来五个 if(num / 5 % 3 == id - 1){ for(int i = 0; i < 5; i++) System.out.println("线程" + id + ": " + num++); //放弃CPU使用权，唤醒等待在Print.class队列上的的打印线程 Printer.class.notifyAll(); }else{ try { //如果不属于自己的数，把当前线程挂在Printer.class //这个对象的等待队列上（也是放弃CPU使用权），等待唤醒 Printer.class.wait(); } catch (InterruptedException e) { System.out.println("id" + "被打断了"); } 实现方法2 public static void main(String[] args) { new Thread( new Printer(i)).start(); new Thread( new Printer(2)).start(); new Thread( new Printer(3)).start(); }

实现方法3 采用JDK并发包提供的Lock, Condition等类的相关 方法控制线程。 特点 每次一个线程执行完五个打印任务时，指定将要唤醒 的下一个进程，而不是唤醒所有进程。 特点 lock是通过代码实现的，要保证锁定一定会被释放， 就必须将unLock()放到finally{}中 在资源竞争不是很激烈的情况下，Synchronized的性能要优于ReetrantLock（如本题），但是在资源竞争很激烈的情况下则相反 Java线程同步的其他方法：volatile,CountDownLatch,CyclicBarrier,DelayQueue,PriorityBlockingQueue，ScheduledExecutor，Semaphore，Exchanger

效率对比 1 安全性 synchronized是在JVM层面上实现的，不但可以通过一些监控工 具监控synchronized的锁定，而且在代码执行时出现异常，JVM 会自动释放锁定，但是使用Lock则不行，lock是通过代码实现的， 要保证锁定一定会被释放，就必须将unLock()放到finally{}中。 2 效率 在资源竞争不是很激烈的情况下，Synchronized的性能要优 于ReetrantLock（如本题），但是在资源竞争很激烈的情况 下则相反。

线程安全/同步总结1 保证线程安全的三种方法： 实现同步机制的方法： 不要跨线程访问共享变量； 使共享变量是final类型的； 将共享变量的操作加上同步。 实现同步机制的方法： 同步代码块 synchronized(同一个数据){} 同一个数据：就是N条线程同时访问一个数据。 同步方法 public synchronized 数据返回类型 方法名(){} 在资源竞争不是很激烈的情况下，偶尔会有同步的情形下，synchronized很合适。因为编译程序通常会尽可能的进行优化synchronize，另外可读性非常好。

线程安全/同步总结2 通过使用同步方法，可非常方便的将某类变成线程安全的类，线程安全特征如下： 该类的对象可以被多个线程安全的访问。 每个线程调用该对象的任意方法之后，都将得到正确的结果。 每个线程调用该对象的任意方法之后，该对象状态依然保持合理状态。 注意：不要对线程安全类的所有方法都进行同步，只对那些会改变共享资源方法的进行同步。 基本所有同学都能给出2-3种实现方法，并给出代码、编译环境和打印结果。

理发师问题 理发店理有一位理发师、一把理发椅和 n把供等候理发的顾客坐的椅子。如果没有 顾客，理发师便在理发椅上睡觉。一个顾客到来时，它必须叫醒理发师。如果理发 师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

public synchronized boolean isEmpty() { if (cnt == 0) { return true; } public class OS_Barber1{ static int cnt = 0; static int MAX = 5; static int busy = 0; static Semaphore sem=new Semaphore(1); public static void main(String args[]) throws InterruptedException{ OS_Barber1 bar=new OS_Barber1(); for(int i=1;i<=20;i++){ new Thread(new Bar1(bar,i)).start(); Thread.sleep((int) (400 - Math.random() * 300)); } public synchronized boolean isFull() { if (cnt == MAX) return true; return false; public synchronized boolean isEmpty() { if (cnt == 0) { return true; } return false; public synchronized boolean isBusy() { if (busy == 1) {

System.out.println("Con"+index+" is wake"); busy=1; if(cnt==1) System.out.println("Con"+index+" is wake"); busy=1; System.out.println("Con"+index+" is Serving"); Thread.sleep(1000); System.out.println("Con"+index+" is leaving"); cnt--; //sem.release(); synchronized (this){ busy=0; notify(); //唤醒 } if(cnt==0) System.out.println("Bar is sleep"); public void Gobar(int index) throws InterruptedException{ System.out.println("Con"+index+" is coming"); cnt++; //判断是否满 if(isFull()){ System.out.println("Is full,"+"Con"+index+" is leaving"); cnt--; }else{ if(busy==1){ System.out.println("Con"+index+" is waitting"); } synchronized (this){ while(busy==1){ wait(); //若有人在理发，则等待

class Bar1 implements Runnable { OS_Barber1 ob; int index; public Bar1(OS_Barber1 ob,int i) { this.ob = ob; index=i; } @Override public void run() { try { ob.Gobar(index); } catch (InterruptedException e) { e.printStackTrace();