笔记
似乎这一部分都是涉及最大公因数之类的数学类的内容。
30. Determine Whether a Given Integer Number Is Prime
印象里应该有更简单的方法。
let is_prime n =
let limit = int_of_float ((float_of_int n +. 0.5) ** 0.5) in
let rec aux now num =
if now = 1 then true
else if n mod now = 0 then false
else aux (now-1) num in
aux limit n;;
val is_prime : int -> bool = <fun>
差不多一个意思。我先开了方，由最大可能向下计算，不用每个数都进行一次平方后比较了，它为什么要这么做呢，一次开方效率这么低吗？
果然答案介绍了个更简单的方法。Sieve of Eratosthenes
牛啊牛啊，但这个能用到这一题上吗？这一题不是要判断是否为质数吗，难道每判断一次算一次？
# let is_prime n =
let n = abs n in
let rec is_not_divisor d =
d * d > n || (n mod d <> 0 && is_not_divisor (d + 1)) in
n > 1 && is_not_divisor 2;;
val is_prime : int -> bool = <fun>
31. Determine the Greatest Common Divisor of Two Positive Integer Numbers
辗转相除法
let rec gcd a b =
let (a,b) = if a> b then (a,b) else (b,a) in
if a mod b = 0 then b
else gcd (a mod b) b;;
val gcd : int -> int -> int = <fun>
标注答案巧妙的交换了下顺序，就不用额外处理谁大谁小的问题了，巧妙啊。
# let rec gcd a b =
if b = 0 then a else gcd b (a mod b);;
val gcd : int -> int -> int = <fun>
32. Determine Whether Two Positive Integer Numbers Are Coprime
赖皮赖皮
let coprime a b =
if gcd a b = 1 then true else false;;
val coprime : int -> int -> bool = <fun>
# (* [gcd] is defined in the previous question *)
let coprime a b = gcd a b = 1;;
val coprime : int -> int -> bool = <fun>
33. Calculate Euler’s Totient Function Φ(m)
Euler’s so-called totient function φ(m) is defined as the number of positive integers r (1 ≤ r < m) that are coprime to m. We let φ(1) = 1.
Find out what the value of φ(m) is if m is a prime number. Euler’s totient function plays an important role in one of the most widely used public key cryptography methods (RSA). In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).
描述都说了后面再优化，那这个皮非赖不可了。
let phi n =
let rec aux n now =
if now = 1 then 1
else if coprime now n then 1 + (aux n (now-1))
else aux n (now-1)
in
aux n (n-1);;
val phi : int -> int = <fun>
# (* [coprime] is defined in the previous question *)
let phi n =
let rec count_coprime acc d =
if d < n then
count_coprime (if coprime n d then acc + 1 else acc) (d + 1)
else acc
in
if n = 1 then 1 else count_coprime 0 1;;
val phi : int -> int = <fun>
34. Determine the Prime Factors of a Given Positive Integer
Construct a flat list containing the prime factors in ascending order.
这里是不需要判断是否为质数的。应为对因数的判断是由小到大进行的，必然已经判断过非质数的因数了，所以结果里只会有因数。我猜测在逻辑上没有更优化的做法了。
let factors n = if n = 1 then [] else
let rec aux num now = if num mod now = 0
then if num = now then [now]
else now::aux (num/now) now
else aux num (now+1)
in
aux n 2;;
val factors : int -> int list = <fun>
# (* Recall that d divides n iff [n mod d = 0] *)
let factors n =
let rec aux d n =
if n = 1 then [] else
if n mod d = 0 then d :: aux d (n / d) else aux (d + 1) n
in
aux 2 n;;
val factors : int -> int list = <fun>
35. Determine the Prime Factors of a Given Positive Integer (2)
Construct a list containing the prime factors and their multiplicity.
Hint: The problem is similar to problem Run-length encoding of a list (direct solution).
癌，偷，偷就完事了。
咋回事呢，顺序还反了，得改改。
let factors_encode n=
let encode list =
let rec aux count acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (x, count + 1) :: acc
| a :: (b :: _ as t) -> if a = b then aux (count + 1) acc t
else aux 0 ((a, count + 1) :: acc) t in
List.rev (aux 0 [] list)
in
encode (factors n);;
val factors_encode : int -> (int * int) list = <fun>
也是，递归的逻辑类似，没必要处理完了再来一遍，两个可以合在一起。
# let factors n =
let rec aux d n =
if n = 1 then [] else
if n mod d = 0 then
match aux d (n / d) with
| (h, n) :: t when h = d -> (h, n + 1) :: t
| l -> (d, 1) :: l
else aux (d + 1) n
in
aux 2 n;;
val factors : int -> (int * int) list = <fun>
36. Calculate Euler’s Totient Function Φ(m) (Improved)
See problem “Calculate Euler’s totient function φ(m)” for the definition of Euler’s totient function. If the list of the prime factors of a number m is known in the form of the previous problem then the function phi(m) can be efficiently calculated as follows: Let [(p1, m1); (p2, m2); (p3, m3); ...] be the list of prime factors (and their multiplicities) of a given number m. Then φ(m) can be calculated with the following formula:
φ(m) = (p1 - 1) × p1m1 - 1 × (p2 - 1) × p2m2 - 1 × (p3 - 1) × p3m3 - 1 × ⋯
let phi_improved n =
let rec acc l=
match l with
| [] -> 1
| (p, m)::t -> (p-1) * int_of_float (float_of_int p ** float_of_int (m-1)) * (acc t)
in
acc (factors_encode n);;
val phi_improved : int -> int = <fun>
对异常输入更健壮。哦，我又搞成会爆栈的了，不好，我写的时候还想着怎么简单判断函数是否为尾递归，癌，该多想想的。
(* Naive power function. *)
let rec pow n p = if p < 1 then 1 else n * pow n (p - 1)
(* [factors] is defined in the previous question. *)
let phi_improved n =
let rec aux acc = function
| [] -> acc
| (p, m) :: t -> aux ((p - 1) * pow p (m - 1) * acc) t
in
aux 1 (factors n)
37. Compare the Two Methods of Calculating Euler’s Totient Function
Use the solutions of problems “Calculate Euler’s totient function φ(m)” and “Calculate Euler’s totient function φ(m) (improved)” to compare the algorithms. Take the number of logical inferences as a measure for efficiency. Try to calculate φ(10090) as an example.
logical inferences 是什么指标？递归次数吗？也没说啊
# (* Naive [timeit] function. It requires the [Unix] module to be loaded. *)
let timeit f a =
let t0 = Unix.gettimeofday() in
ignore (f a);
let t1 = Unix.gettimeofday() in
t1 -. t0;;
val timeit : ('a -> 'b) -> 'a -> float = <fun>
Unix 在浏览器 playground 里还没有，引用不到，查了半天也搞不了，我换了个库。
不过想想也是，Unix 接口估计是大部分语言啊，环境啊都支持的，多学多用好吧，倒是没想到在线 playground 在用了。
let timeit f a =
let t0 = Sys.time () in
ignore (f a);
let t1 = Sys.time () in
t1 -. t0
还挺明显。
timeit phi 10090;;
- : float = 0.00299978256225585938
timeit phi_improved 10090;;
- : float = 0.
38. A List of Prime Numbers
Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.
不是，意思还有更简单的方法？但又是简单难度，那就一个一个算呗。
我还以为会卡死，还挺快，不过也是，好像就一个 n^2 复杂度，主要是 is_prime 比较快，是开方了再遍历的。
let rec all_primes min max= if min > max+1 then []
else if is_prime min then min :: all_primes (min+1) max
else all_primes (min+1) max
let rec all_primes a b =
if a > b then [] else
let rest = all_primes (a + 1) b in
if is_prime a then a :: rest else rest;;
39. Goldbach’s Conjecture
Goldbach’s conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers. Write a function to find the two prime numbers that sum up to a given even integer.
let goldbach n =
let rec aux min max=if min>=max then raise Not_found
else if is_prime min && is_prime (max-min) then (min, max-min)
else aux (min+1) max
in
aux 2 n;;
val goldbach : int -> int * int = <fun>
哦，闭包直接用就完事了，还多搞了，没想到。
# (* [is_prime] is defined in the previous solution *)
let goldbach n =
let rec aux d =
if is_prime d && is_prime (n - d) then (d, n - d)
else aux (d + 1)
in
aux 2;;
val goldbach : int -> int * int = <fun>
40. A List of Goldbach Compositions
Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.
In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.
癌，会用库了。
let goldbach_list min max =
List.filter_map (fun e-> if e mod 2 = 0 then Some (e, (goldbach e)) else None) (range min max);;
val goldbach_list : int -> int -> (int * (int * int)) list = <fun>
描述中要求的。
List.length (List.filter (fun (num,(less,bigger))->less>50) (goldbach_list 3 3000));;
- : int = 10
撒情况，才 10 个。
List.filter (fun (num,(less,bigger))->less>50) (goldbach_list 3 3000);;
- : (int * (int * int)) list =
[(992, (73, 919)); (1382, (61, 1321)); (1856, (67, 1789));
(1928, (61, 1867)); (2078, (61, 2017)); (2438, (61, 2377));
(2512, (53, 2459)); (2530, (53, 2477)); (2618, (61, 2557));
(2642, (103, 2539))]
标准答案用的也是 filter。
# (* [goldbach] is defined in the previous question. *)
let rec goldbach_list a b =
if a > b then [] else
if a mod 2 = 1 then goldbach_list (a + 1) b
else (a, goldbach a) :: goldbach_list (a + 2) b
let goldbach_limit a b lim =
List.filter (fun (_, (a, b)) -> a > lim && b > lim) (goldbach_list a b);;
val goldbach_list : int -> int -> (int * (int * int)) list = <fun>
val goldbach_limit : int -> int -> int -> (int * (int * int)) list = <fun>
总结
多用用库函数好吧，List 函数式那一套都挺全的，用就完事了。
文档信息
- 本文作者：nyaaar
- 本文链接：https://nyaaarlathotep.github.io/2024/08/29/Ocaml-99-%E9%97%AE%E9%A2%98%E7%AC%94%E8%AE%B0-2/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）