我對這個沒有想法。我自己最初嘗試過，然后從 SO 和 google 復制，它適用于除一個之外的所有情況，但是仍然沒有找到一種遞回演算法，該演算法對于我的作業中的特定測驗用例來說足夠快：/
無論如何，這是為什么：
public static int FindMaximum(int[] array)
{
if (array is null)
{
throw new ArgumentNullException(nameof(array));
}
if (array.Length == 0)
{
throw new ArgumentException(null);
}
return FindMaxRec(array, array.Length);
}
public static int FindMaxRec(int[] arr, int n)
{
if (n == 1)
{
return arr[0];
}
return Math.Max(arr[n - 1], FindMaxRec(arr, n - 1));
}
不適用于此TestCase？：
[Test]
[Order(0)]
[Timeout(5_000)]
public void FindMaximum_TestForLargeArray()
{
int expected = this.max;
int actual = FindMaximum(this.array);
Assert.AreEqual(expected, actual);
}
編輯 1：
這雖然作業正常，但我需要遞回：
public static int FindMaximum(int[] array)
{
if (array is null)
{
throw new ArgumentNullException(nameof(array));
}
if (array.Length == 0)
{
throw new ArgumentException(null);
}
int maxValue = int.MinValue;
for (int i = 0; i < array.Length; i )
{
if (array[i] > maxValue)
{
maxValue = array[i];
}
}
return maxValue;
}
uj5u.com熱心網友回復：
您可以嘗試將陣列分成兩部分：
public static int FindMaximum(int[] array) {
if (null == array)
throw new ArgumentNullException(nameof(array));
if (array.Length <= 0)
throw new ArgumentException("Empty array is not allowed.", nameof(array));
return FindMaxRec(array, 0, array.Length - 1);
}
private static int FindMaxRec(int[] array, int from, int to) {
if (to < from)
throw new ArgumentOutOfRangeException(nameof(to));
if (to <= from 1)
return Math.Max(array[from], array[to]);
return Math.Max(FindMaxRec(array, from, (from to) / 2),
FindMaxRec(array, (from to) / 2 1, to));
}
演示：
Random random = new Random(123);
int[] data = Enumerable
.Range(0, 10_000_000)
.Select(_ => random.Next(1_000_000_000))
.ToArray();
Stopwatch sw = new Stopwatch();
sw.Start();
int max = FindMaximum(data);
sw.Stop();
Console.WriteLine($"max = {max}");
Console.WriteLine($"time = {sw.ElapsedMilliseconds}");
結果：
max = 999999635
time = 100
uj5u.com熱心網友回復：
將簡單的線性演算法轉化為遞回演算法的一種簡單方法是利用enumerator陣列的 。
public static int FindMax(int[] values)
{
using var enumerator = values.GetEnumerator();
return FindMaxRecursively(enumerator, int.MinValue);
}
private static T FindMaxRecursively<T>(IEnumerator<T> enumerator, T currentMax) where T : IComparable
{
if (!enumerator.MoveNext()) return currentMax;
var currentValue = enumerator.Current;
if (currentValue.CompareTo(currentMax) > 0) currentMax = currentValue;
return FindMaxRecursively(enumerator, currentMax);
}
這通過了您的測驗用例并使用遞回。
編輯：這是上述內容的一個更適合初學者的版本，并附有注釋來解釋它在做什么：
public static int FindMax(IEnumerable<int> values)
{
using var enumerator = values.GetEnumerator();//the using statement disposes the enumerator when we are done
//disposing the enumerator is important because we want to reset the index back to zero for the next time someone enumerates the array
return FindMaxRecursively(enumerator, int.MinValue);
}
private static int FindMaxRecursively(IEnumerator<int> enumerator, int currentMax)
{
if (!enumerator.MoveNext()) //move to the next item in the array. If there are no more items in the array MoveNext() returns false
return currentMax; //if there are no more items in the array return the current maximum value
var currentValue = enumerator.Current;//this is the value in the array at the current index
if (currentValue > currentMax) currentMax = currentValue;//if it's larger than the current maximum update the maximum
return FindMaxRecursively(enumerator, currentMax);//continue on to the next value, making sure to pass the current maximum
}
可能有助于理解這一點的是，這IEnumerator就是啟用foreach回圈的原因。在幕后，foreach回圈只是反復呼叫MoveNext具有IEnumerator. 這是有關該主題的更多資訊。
uj5u.com熱心網友回復：
public static int findMax(int[] a, int index) {
if (index > 0) {
return Math.max(a[index], findMax(a, index-1))
} else {
return a[0];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/329928.html