Задача теории CS: оценка каждого элемента в массиве только один раз и выбор наибольшего значения - PullRequest
Новая
       12

Задача теории CS: оценка каждого элемента в массиве только один раз и выбор наибольшего значения

1 голос
/ 04 августа 2011

Мы рассмотрели эту проблему на уроке теории в колледже.

Установка выглядит так:

Вам представлен массив из N значений.Вы знаете длину массива, но не диапазон значений.Вам представлены элементы по одному.Каждое значение может быть проверено только один раз, и если значение не выбрано, когда оно представлено, оно отбрасывается.Цель состоит в том, чтобы выбрать максимальное значение.

Существует алгоритм, который дает лучший шанс выбора максимума, чем 1 / N, но я не могу вспомнить, что это такое.

Ответы [ 2 ]

4 голосов
/ 04 августа 2011

Это называется проблема секретаря .

0 голосов
/ 04 августа 2011

Самый простой способ, который я знаю, - это перебирать массив.Вы создаете переменную, вставляете в нее первое значение массива, а затем, перебирая каждое значение в массиве, сравниваете сохраненное значение с текущим значением, а если текущее значение больше хранимого, вы помещаете текущее значение всохраненное значение, заменяя нижнее значение.

Синтаксис будет меняться в зависимости от того, какой язык программирования вы используете, но основное представление будет следующим: 

Dim MaxValue as integer   
Dim ArrayOfN as Array   
Dim N as integer  
Dim i as integer  

ArrayOfN = [0,10,87,6,59,1200,5] 'In this case there are 7 values in the array  
N = 7 'You would typically want to programically get the size of the array but I can't remember the syntax  
MaxValue = ArrayOfN(0)  
For i = 0 to N - 1 'Assumes iteration of 1  
    If MaxValue < ArrayOfN(i) Then    
        MaxValue = ArrayOfN(i)  
    End IF     
Next

Я в основном использовал vb для кодированияпример, но я знаю, что некоторые синтаксис является неправильным, особенно для массива.Однако, поскольку у меня нет сейчас доступа к любому программному обеспечению для кодирования, это лучшее, что я могу сделать.При кодировании чего-то, что вы можете окончательно выбрать наибольшее значение, нет никакой неопределенности.Есть и более эффективные способы сделать это.Например, если у вас есть возможность использовать функцию array.sort, вы можете получить максимальное значение всего за 2 строки кода.Однако, поскольку вы не указали никаких языков программирования и, увидев ответ yi_H, я начинаю думать, что вы не хотели знать, как программировать решение, а просто хотели назвать проблему.

...