递归以创建 Sum 方法

我有一个面试问题，但我无法解决它。我已经坐下来思考了一下，但我仍然想不出该怎么做。

我有3种方法。我假设使用递归将 2 个数字加在一起，所以我不能使用任何算术运算符，如 +、- 等。

这 3 种方法是 Sum、Add1、Sub1。

Add1 将 1 个整数作为参数，并以 1 为增量返回该整数。Sub1 做同样的事情，但递减 1。

Sum 方法采用 2 个整数，并使用递归返回 2 个输入整数的总和。显示实现。

此外，使用 Sum 函数如何实现一个新函数，该函数将 2 个整数作为输入并使用递归但没有算术运算符输出其乘积？

在这两种情况下，整数都是非负数。

事实上，这就是自然数算术是如何从第一原理定义的;见 http://en.wikipedia.org/wiki/Peano_axioms

让我们从头开始做这件事，为什么不呢？

零是自然的
零没有前身
每个自然都有继任者

轻松完成：

sealed class Natural
{
  private Natural predecessor;
  private Natural(Natural predecessor) 
  { 
      this.predecessor = predecessor;
  }
  // Zero has no predecessor
  public readonly static Natural Zero = new Natural(null);
  // Every number has a successor; the predecessor of that number is this number. 
  public Natural Successor() 
  { 
      return new Natural(this);
  }
  public Natural Predecessor()
  {
      return this.predecessor;
  }
  public override string ToString()
  {
    if (this == Zero) 
        return "0";
    else 
        return "S" + this.Predecessor().ToString();
  }

好吧，我们可以表示这样的任何整数。现在我们如何做加法？我们将加法定义为：

a + 0 --> a
a + S(b) --> S(a + b)

因此，让我们添加一个运算符

  public static Natural operator+(Natural a, Natural b)
  {
    if (b == Zero) 
      return a;    
    else
      return (a + b.Predecessor()).Successor();
  }
}

好吧，让我们试试吧。

Natural n0 = Natural.Zero;
Natural n1 = n0.Successor();
Natural n2 = n1.Successor();
Console.WriteLine(n0 + n0);
Console.WriteLine(n0 + n1);
Console.WriteLine(n0 + n2);
Console.WriteLine(n1 + n0);
Console.WriteLine(n1 + n1);
Console.WriteLine(n1 + n2);
Console.WriteLine(n2 + n0);
Console.WriteLine(n2 + n1);
Console.WriteLine(n2 + n2); // SSSS0

你看，二加二实际上是四。

如果你对这个主题感兴趣，我目前正在我的博客上运行一个关于从头开始推导自然和整数算术的长系列，尽管我使用的是二进制表示而不是一元表示。看

http://ericlippert.com/2013/09/16/math-from-scratch-part-one/

更一般地说：这个问题旨在测试你是否知道递归方法的基本结构;可能你不知道，让我为你列出来。C# 中的递归方法都遵循以下模式：

我们是否已经知道没有递归的问题的解决方案？如果是，则解决问题并返回结果。
我们不知道问题的解决方案。将问题分解为一个或多个较小的问题。减少必须使问题实际上更小，更接近于具有已知解决方案的问题。否则，递归不会终止。
归地解决每个问题。
结合这些问题的解决方案，为更大的问题创建一个解决方案。
返回结果。

这就是我们在加法运算符中所做的。我们首先检查我们是否知道问题的解决方案;a + 0 是 a。如果我们不知道问题的解决方案，那么我们就会提出一个较小的问题;如果我们先于第二次召唤，那么我们离我们知道如何解决的问题又近了一步。

Add1(value) {
  return value + 1;
}
Sub1(value) {
  return value - 1;
}
Sum(value1 , value2) {
   if(value2 == 0) {
       return value1;
   }
   value1 = Add1(value1);
   value2 = Sub1(value2);
   return Sum(value1, value2);
}
Prod(value1, value2) {
    if(value2 == 0) {
       return 0;
   }
   value2 = Sub1(value2);
   return Sum(value1, Prod(value1, value2));
}

嗯，他们是想雇佣糟糕的程序员吗？无论如何，可以通过让 sum 函数获取其第二个参数、加/递减 1 并调用自身来完成。

sum(arg1,arg2)
{
if(arg2>0)
{
new1=Add1(arg1)
new2=Sub1(arg2)
return sum(new1,new2)
}
else{return arg1;}
}

我讨厌这类面试问题，因为我发现在面试的相关压力下很难回答。

这是Add1，Sub1，Sum，Product 所有这些都是在没有正式使用+或-符号的情况下完成的。

    static int Add1(int value) {
        return System.Threading.Interlocked.Increment(ref value);
        }
    static int Sub1(int value) {
        return System.Threading.Interlocked.Decrement(ref value);
        }
    static int Sum(int value1, int value2) {
        return RecursiveAdd(value1, value2);
        }
    static int Product(int value1, int value2) {
        return RecursiveProduct(value1, value2);
        }
    static int RecursiveAdd(int v1, int v2) {
        if (v2 == 0) { return v1; }
        v2 = Sub1(v2);
        v1 = Add1(v1);
        return RecursiveAdd(v1, v2);
        }
    static int RecursiveProduct(int v1, int v2) {
        if (v2 == 0) { return 0; }
        v2 = Sub1(v2);
        return RecursiveAdd(v1, RecursiveProduct(v1, v2));
        }

递归函数 Sum ：

int Sum(int n1, int n2) {
  if (n2 == 0) return n1;
  return Sum(add1(n1), sub1(n2));
}

和Prod ：

int Prod(int n1, int n2) {
  if(n1 == 1) return n2;
  if(n2 == 1) return n1;
  n2 = Sub(n2);
  return Sum(n1, Prod(n1, n2));
}

您可以

直接实现此类，它将适用于任何类型的T。

public abstract class Summable<T>
{
    public abstract Summable<T> Add1();
    public abstract Summable<T> Sub1();
    public abstract Summable<T> Zero { get; } //Identity for addition
    public abstract Summable<T> One { get; } //Identity for multiplication
    public abstract bool Equals(Summable<T> other);
    public abstract override string ToString();
    public static Summable<T> Sum(Summable<T> x, Summable<T> y)
    {
        if (y == y.Zero)
            return x;
        if (x == y.Zero)
            return y;
        else
            return Sum(x.Add1(), y.Sub1());
    }
    public static Summable<T> Multiply(Summable<T> x, Summable<T> y)
    {
       var zero = x.Zero;
        var one = x.One;
        if (x == zero || y == zero)
            return zero;
        if (y == one)
            return x;
        if (x == one)
            return y;
        return Sum(x, Multiply(x, y.Sub1()));
    }
    public static bool Equal(Summable<T> x, Summable<T> y)
    {
        if (object.ReferenceEquals(x, null) || object.ReferenceEquals(y, null))
            return false;
        return x.Equals(y);
    }
    public static bool operator ==(Summable<T> x, Summable<T> y)
    {
        return Equal(x, y);
    }
    public static bool operator !=(Summable<T> x, Summable<T> y)
    {
        return !Equal(x, y);
    }
}

所以对于整数（或者可能是 uints），它会是这样的：

public sealed class Int : Summable<int>
{
    protected int n;
    public Int(int n)
    {
       if(n < 0)
           throw new ArgumentException("n must be a non negative."); 
       this.n = n;
    }
    public override Summable<int> Add1()
    {
        return new Int(n + 1);
    }
    public override Summable<int> Sub1()
    {
        return new Int(n - 1);
    }
    public override Summable<int> Zero
    {
        get
        {
            return new Int(0);
        }
    }
    public override Summable<int> One
    {
        get
        {
            return new Int(1);
        }
    }
    public override bool Equals(Summable<int> other)
    {
        var x = other as Int;
        if (Object.ReferenceEquals(x, null))
            return false;
        return this.n == x.n;
    }
    public override string ToString()
    {
        return n.ToString();
    }
}

相关内容

最新更新

热门标签：