Поиск наименьшего числа с помощью турнирной скобки

Question

Я пишу программу, которая должна найти наименьшее число в турнирной скобке. Например, есть массив

int[] a = new int[4] {4, 2, 1, 3} 

и сравнивающих чисел, стоящих рядом друг с другом Я выбрать самые маленькие. (min(4, 2) -> 2, min(1, 3) -> 1, а затем я сравниваю 1 и 2, 1 является самым маленьким, так что это победитель, но сравнивать 2 и 1. невозможно. Только 0 [0] с 1, [2] с [ 3] и т. Д. В общем случае a [2 * i] с [(2 * i) +1] - что-то вроде этого

Первый вопрос: если есть n чисел, все дерево состоит из 2n- 1. Я должен создать массив из 4 или 7 элементов? 4 кажется лучшим вариантом.

Второй вопрос: если я сравниваю 4 и 2, а 2 меньше, я должен сделать [0] = 2, а затем при сравнении 1 и 3 a 1 = 1. Наконец, сравнивая [0] с 1 и помещая smal чтобы номер не был [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; 
} 

Можете ли вы указать, что я делаю хорошо, и что должно быть улучшено?

Answer 1

Существует различные простые решения, которые используют функции, установленные в C#:

int min = myArray.Min(); 
//Call your array something other than 'a' that's generally difficult to figure out later 

В качестве альтернативы это будет цикл с Еогеаспом через все ваши ценности.

int minint = myArray[0]; 
foreach (int value in myArray) { 
    if (value < minint) minint = value; 
} 

1 - О каком дереве вы говорите? У вашего массива есть n значений для начала, поэтому он будет иметь n значений max. Если вы имеете в виду количество значений во всех массивах, которые вы создадите, это 2n-1, это все равно не означает, что вам нужно поместить все это в 1 массив, создать массив, использовать его и затем создать другой массив. C# GC будет собирать объекты ссылочного типа, у которых нет указателей (они не будут использоваться снова), так что это будет разумная память, если это вас беспокоит?

2 - Отправьте свой код. Есть несколько ошибок, но, скорее всего, вы сможете изменить текущие значения массива или создать новый массив. Temp int не понадобится.

3 - Вышеупомянутые опубликованные algos являются «простейшими», используя встроенные функции, доступные для C#. Если это домашнее задание, отправьте код.

В качестве общего направления использование рекурсивной функции, вероятно, будет наиболее элегантным (и некоторые общие чтения по сортировкам слияния окажутся полезными для вас в будущем).

Answer 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; 
    } 
} 

EDIT: код не тестировался и ошибок, возможно, поскользнулся в, так как это было напечатано на Android приложение.

EDIT: Забыл сказать, как вы называете этот метод. Как так:

int min = Minimum (myArray, 0, myArray.Length -1); 

EDIT: Или создать другую перегрузку:

int Minimum (int [] values) 
{ 
    return Minimum (values, 0, values.Length -1); 
} 

И назвать использование только:

int min = Minimum (myArray); 

EDIT: А вот не-рекурсивный метод (голый в виду, что этот метод фактически модифицирует массив):

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]; 
}