2

我尝试添加由列表表示的数字，例如：

0 = []
1 = [1]
2005 = [2005]
123456 = [3456; 12]
1234567890 = [7890; 3456; 12]
1000000001 = [1; 0; 10]

所以add [9999] [1] = [0;1]

我已经这样做了：

let rec add l1 l2 =
match l1, l2 with
| n::l1', m::l2' -> if n+m < 10000 then
                        (n+m)::(add l1' l2')
                    else
                        begin
                            match l1', l2' with
                            | p::l1'', q::l2'' -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                            | p::l1'', [] -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                            | [], q::l2'' -> ((n+m) - 10000)::(add l1' ((1+q)::l2''))
                            | [], [] -> ((n+m) - 10000)::[1]
                        end
| [], [] -> []
| m::l1', [] -> m::(add l1' [])                    
| [], m::l2' -> m::(add [] l2')

但它不适用于类似于add [9999;9999] [1] which give[0; 10000]而不是[0;0;1].

随身携带有问题，但我找不到。

它适用于add [8500;6000] [5600;452].

4

3 回答 3

4

在我看来，您的案例假设数字始终小于或等于 9999，但是当有进位时，情况并非如此。因此，即使其中一个列表为空，您也需要检查 10000。

于 2012-11-22T21:09:17.243 回答
2

问题在于您的非规范化表示，它可以临时创建大于 9999 的数字，这是您在所有地方都不期望的。这是一个带有显式进位的简单解决方案，可以避免该问题：

let base = 10_000
let rec add' xs ys c =
  match xs, ys with
  | [], [] -> if c = 0 then [] else [c]
  | [], zs | zs, [] -> add' [0] zs c
  | x::xs', y::ys' -> (x + y + c) mod base :: add' xs' ys' ((x + y + c) / base)
let add xs ys = add' xs ys 0
于 2012-11-22T21:48:58.860 回答
0

让我们看看您的代码中的问题。我已将我对问题的解释放在评论中：

let rec add l1 l2 =
   match l1, l2 with
   | n::l1', m::l2' -> if n+m < 10000 then
                       (n+m)::(add l1' l2')
                       else
                       begin
                         (* in all these cases you don't check if 1+p is > base *) 
                         match l1', l2' with
                          | p::l1'', q::l2'' -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                          | p::l1'', [] -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                          | [], q::l2'' -> ((n+m) - 10000)::(add l1' ((1+q)::l2''))
                          | [], [] -> ((n+m) - 10000)::[1]
                       end
   | [], [] -> []
   (* and the error above causes problem in these arms, since m can now be > base *)
   | m::l1', [] -> m::(add l1' [])
   | [], m::l2' -> m::(add [] l2')

让我们先把特殊情况放在首位，用一个值替换文字常量，去掉多余的括号并修复进位错误。

let rec add l1 l2 base =
   match l1, l2 with
   | [], [] -> []
   | m::l1', []
   | [], m::l1' -> if m >= base then m-base::add l1' [1] base else m::l1'
   | n::l1', m::l2' -> let r = n + m in 
                       if r < base then
                         r::add l1' l2' base
                       else begin
                         match l1', l2' with
                          | [], []      -> [r-base ; 1]
                          | p::l1'', []
                          | [], p::l1'' -> r-base::add [] (1+q::l1'') base
                          | p::l1'', _  -> r-base::add (1+p::l1'') l2' base
                       end

现在我们可以看到可以提取一些代码并将其转换为专用函数：

let rec add l1 l2 base =
   let rec carry = function 
    | [] -> []
    | [x] when x >= base -> [x-base;1]
    | x::y::l when x >= base -> x-base::carry (y+1::l)
    | l -> l
   in
   match l1, l2 with
   | [], [] -> []
   | l1, []
   | [], l1 -> carry l1
   | n::l1', m::l2' -> let r = n + m in
                       if r < base then
                         r::add l1' l2' base
                       else begin
                         match l1', l2' with
                          | [], []     -> [r-base ; 1]
                          | l1'', []
                          | []  , l1'' -> carry (r::l1'')
                          | p::l1'', _ -> r-base::add (1+p::l1'') l2' base
                       end

现在您的代码应该可以使用保留的进位，并且可以使用任何自然基础。

于 2012-11-23T14:38:04.393 回答