c # — Нахождение наименьшего числа, используя турнирную скобку
Я пишу программу, которая должна найти наименьшее число в турнирной таблице. Например есть массив
int[] a = new int[4] {4, 2, 1, 3}
и сравнивая числа, стоящие рядом друг с другом, я выбираю самое маленькое. (min(4, 2) -> 2, min(1, 3) -> 1и затем я сравниваю 1 и 2, 1 — наименьшее, поэтому он победитель, но невозможно сравнить 2 и 1. Просто [0] с1, [2] с [3] и т. д. В общем случае [2 * i] с [(2 * i) +1] for(int i=0; i<a.Length/2; i++) <- что-то вроде этого
Первый вопрос: если есть n чисел, все дерево состоит из 2n-1 скобок. Я должен создать массив из 4 или 7 элементов? 4 кажется лучшим вариантом.
Второй вопрос: если я сравниваю 4 и 2, а 2 меньше, я должен сделать a [0] = 2, а затем при сравнении 1 и 3 a1 = 1? Наконец, сравнивая [0] с1 и положить наименьшее число в [0]? Может потребоваться временный int.
Последний вопрос: что вы предлагаете сделать проще всего? Я едва мог найти информацию об этом алгоритме. Я надеюсь, что вы направите мой разум в рабочий алгоритм.
Не много, но я выкладываю свой код:
int[] a = new int[4] { 4, 2, 1, 3 };
int tmp = 0;
for (int i = 0; i < (a.Length)/2; i++)
{
if (a[tmp] > a[tmp + 1])
{
a[i] = a[i + 1];
}
else if(a[tmp] < a[tmp +1])
{
a[i] = a[i + 1];
}
tmp = tmp + 2;
}
Можете ли вы указать, что я делаю хорошо, и что должно быть улучшено?
Решение
Если стиль турнира является обязательным, рекурсивный подход кажется наиболее подходящим:
int Minimum (int [] values, int start, int end)
{
if (start == end)
return values [start];
if (end - start == 1)
if ( values [start] < values [end])
return values [start];
else
return values [end];
else
{
int middle = start + (end - start) / 2;
int min1 = Minimum (values, start, middle);
int min2 = Minimum (values, middle + 1, end);
if (min1 < min2)
return min1;
else
return min2;
}
}
РЕДАКТИРОВАТЬ: код не тестировался и ошибки могли появиться, так как он был напечатан в приложении для Android.
РЕДАКТИРОВАТЬ: Забыл сказать, как вы называете этот метод. Вот так:
int min = Minimum (myArray, 0, myArray.Length -1);
РЕДАКТИРОВАТЬ: Или создать другую перегрузку:
int Minimum (int [] values)
{
return Minimum (values, 0, values.Length -1);
}
А для звонка используйте всего лишь:
int min = Minimum (myArray);
РЕДАКТИРОВАТЬ: И вот нерекурсивный метод (имея в виду, что этот метод на самом деле изменяет массив):
int Minimum(int[] values)
{
int step = 1;
do
{
for (int i = 0; i < values.Length - step; i += step)
if(values[i] > values[i + step])
values[i] = values[i + step];
step *= 2;
}
while(step < values.Length);
return values[0];
}
Другие решения
Существуют различные простые решения, использующие функции, установленные в C #:
int min = myArray.Min();
//Call your array something other than 'a' that's generally difficult to figure out later
В качестве альтернативы это зациклится с foreach через все ваши ценности.
int minint = myArray[0];
foreach (int value in myArray) {
if (value < minint) minint = value;
}
1 — О каком дереве ты говоришь? Ваш массив имеет n значений для начала, поэтому он будет иметь n значений max. Если вы имеете в виду число значений во всех создаваемых вами массивах, равное 2n-1, это еще не означает, что вам нужно разместить все эти значения в одном массиве, создать массив, использовать его, а затем создать другой массив. C # GC будет собирать объекты ссылочного типа, которые не имеют указателей (не будут использоваться снова), так что будет хорошо с памятью, если это ваша проблема?
2 — Разместите свой код. Есть несколько ошибок, но, вероятно, у вас все будет хорошо, если вы измените текущие значения массива или создадите новый массив. Temp int не понадобится.
3 — Вышеприведенные алгоритмы являются «самыми простыми», используя встроенные функции, доступные для C #. Если это домашнее задание, пожалуйста, напишите код.
Как общее направление, использование рекурсивной функции, вероятно, было бы наиболее элегантным (и некоторые общие чтения по видам слияний оказались бы полезными для вас в будущем).