第二次课后作业答案 函数式编程和逻辑式编程

Presentation on theme: "第二次课后作业答案 函数式编程和逻辑式编程"— Presentation transcript:

1 第二次课后作业答案 函数式编程和逻辑式编程
第二次课后作业答案 函数式编程和逻辑式编程

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

3 使用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)] ]

4 使用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 递归会产生重复计算，并需要在调用到最底层之前保存之前计算过的结果；迭 代计算量相对小一些，但需要额外的变量。

5 用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).

6 用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(_,_,_,_).