Имется программа, которая получает некое целое число N (порядка 100-1000) и по нему генерирует нумерованный список N случайных чисел диапазона 0...MaxLongInt.

Требуется написАть программу, которая:
1) Получает на входе N.
2) Получает на входе первое число списка.
3) Принимает решение, является ли сообщенное ей только что число наибольшим в списке или нет, и сообщает это решение.
4) Если программа приняла решение что число - не наибольшее, ей сообщается следующее число списка.
5) Происходит переход на шаг 3).

Программа работает до тех пор пока она не примет решение о том что очередное число - наибольшее в списке, либо пока список не закончится.

Есссно требование к программе - угадывание максимального числа из списка с максимально возможной вероятностью.

НаписАл на VB6 программу, которая может тестировать решения. Если есть желание опробовать свой алгоритм - присылайте.

Решение принимается в виде функции

Function DetectMax(TotalCount As Integer, CurrentCount As Integer, RandList() As Long) As Boolean

где на входе:
TotalCount - количество чисел в списке всего;
CurrentCount - номер числа в списке;
RandList - массив элементов с 1 по CurrentCount списка.

На выходе - значение DetectMax:
True - последнее число будет максимальным в списке, дальше искать не нужно;
False - последнее число не максимальное в списке, нужно попробовать следующее.

Соответственно функция вызывается с CurrentCount = 1, 2, 3 ... до тех пор пока при очередном вызове она не вернет True. Если последнее число - максимальное в списке, то +1 к удачным попыткам.

Мой результат - 36% угадывания (10000 случайных списков).

парочка вопросиков:
1. числа в разных ячейках независимы? (это я так, на всякий случай)
2. какую информацию может использовать функция (только текущее значение или предыдущие тоже)?
Добавлено @ 13:31
упс... пока писал, появился новый пост
2. отпадает
3. а почему на VB?????

Цитата(maxim1000 @ 21.2.2005, 14:30)

1. числа в разных ячейках независимы?

Код

Randomize Timer NumCount = 100 + Rnd * 900 Open "\numbers.txt" For Output As #1 Print #1, NumCount For i = 1 To NumCount    Print #1, Rnd * MaxLongInt Next i Close

Цитата(maxim1000 @ 21.2.2005, 14:30)

3. а почему на VB?????

а что попалось... тем более что VBA у каждого под рукой есть...

нее, задачка тут интересная
есть такое решение: выбирать то, что более вероятно (максимум здесь или будет дальше)
но это не проходит для общего критерия...

Цитата(Sardar @ 21.2.2005, 21:40)

Числа настоящие, а не машинные?

ну чуть выше - процедура генерации файла с массивом чисел же ж... чего спрашиваешь?

Цитата(maxim1000 @ 21.2.2005, 21:54)

есть такое решение: выбирать то, что более вероятно (максимум здесь или будет дальше)

так основной вопрос - КАК? чтобы с максимальной вероятностью попасть в точку... рожденный мной алгоритм дает в среднем 36-40% (на выборке из 10 тыс. случайных списков) - и я даже решить не могу, хорошо это или это плохо и возможно гораздо лучше...

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

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

я крутил-крутил, пока не выкрутил думаю, скоро получится

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

Цитата

Вот в том и фигня, что пока у меня лично не вытанцовывается алгоритм...

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

Цитата

но хотелось бы решить несколько более общую задачу - для неограниченных значений...

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

Цитата(maxim1000 @ 22.2.2005, 12:38)

если имеется в виду произвольные распределения

не только произвольные, но и неограниченные (т.е. не имеющие ни минимально, ни максимально возможного значения)...

Цитата(maxim1000 @ 22.2.2005, 12:38)

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

вот это я вроде и реализовал... может, криво, раз получается 36-40%...

Цитата

вот это я вроде и реализовал...

тогда было бы интересно посмотреть
тут есть один момент, на который можно пойматься:
можно подумать, что на каждом шаге нужно просто выбрать, что более вероятно - максимум это или нет, это несколько отличается от условия задачи (это было бы решением в том случае, если бы после ответа "да,максимум" обработка бы продолжалась и давалась бы возможность исправиться
Добавлено @ 12:08

Цитата

может, криво, раз получается 36-40%...

вот в том-то и дело: если алгоритм получен путем строгих рассуждений, то нет сомнений - это оптимум, и ничего лучше не найти

Добавлено @ 12:08

Цитата

Собстна эти результаты можно получить посадив обезьяну за комп и предлагать ей сказать правильно не правильно

протестировано?
или так, просто потому, что показалось, что результаты низкие?

Цитата(maxim1000 @ 22.2.2005, 13:07)

если алгоритм получен путем строгих рассуждений

увы, сплошная псевдоквазия...

Цитата(maxim1000 @ 22.2.2005, 13:07)

это было бы решением в том случае

да. как только сказано "максимум" - обработка заканчивается.

Цитата(maxim1000 @ 22.2.2005, 13:07)

было бы интересно посмотреть

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

Цитата

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

тоже правильно
сегодня дома покручу, возможно, завтра что-нибудь будет...

Если не ошибаюсь, эта задача аналогична задаче о выборе принцессой жениха.
Hint - для больших N отсматривается N/e кандидатов.

BTW, родственной задаче была посвяшена диссертация небезызвестного Б.А.Березовского

вчера так странно получилось... наличие заданий совпало с желанием поработать
выкладываю сегодня...
Добавлено @ 15:28
так, с одной стороны получилось, но не до той степени, до которой хотелось бы...

мы имеем кучу случайных величин q,q1,q2... (ну не знаю я, как сюда вставить традиционную кси ), распределенных одинаково и независимо
функция распределения F(x)=P{q<x}
наша задача - максимизировать P{все будет хорошо/осталось N шагов}
обозначение покороче: P{ok/N}
дальше будет несколько формул, возможно, у кого-то вызовут скуку, уж звиняйте
нумерация будет обозначать номер шага с конца (последний имеет номер 1)
P{ok/N}=SxP{ok,qN=x/N}
(Sx - сумма по всем x)
P{ok/N}=SxP{ok/qN=x,N}P{qN=x}
введем обозначение p(x)=P{qN=x}
P{ok/N}=Sx( P{ok/qN=x,N}p(x) )
на каждом шаге мы принимаем булевое решение: максимум или нет, зависит оно от всех предыдущих значений и текущего
P{ok/N}=Sx( P{ok,yN=1/qN=x,N} + P{ok,yN=0/qN=x,N} )p(x)
рассмотрим каждой слагаемое отдельно:
в первом случае ok означает, что мы угадали, и максимум находится в этой позиции:
P{ok,yN=1/qN=x,N}=P{qN>=q1,q2.../qN=x,N}=P{x>=q1,q2...}=(F(x))^(N-1) (в степени)
во втором случае угадали мы или нет описывается такой формулой:
P{x<max/N-1}=1-( (F(x))^(N-1) )
и тут есть небольшая ловушка: можно подумать, что это и есть вероятность успеха...нет...
если мы угадали на этом шаге, то у нас есть неплохие шансы ошибиться дальше, поэтому:
P{ok,yN=0/qN=x,N}=P{x<max,ok/N-1}=P{x<max/N-1}*P{ok/max>x,N-1}=
=(1- ( (F(x))^(N-1) ) )*P{ok/max>x,N-1}
таким образом, на следующем шаге мы получаем новый объект:
P{ok/max>x,N-1} - его мы и будем рассматривать до конца задачи, т.к. он является единственной неизвестной величиной для принятия решения
в нем естественным образом учтена информация о предыдущих элементах - просто ограничение на максимум
вспомним запись вероятности успеха:
P{ok/N}=Sx( P{ok,yN=1/qN=x,N} + P{ok,yN=0/qN=x,N} )p(x)
yN - величина определенная для каждого x, поэтому ненулевым будет только одно слагаемое в этой сумме
кроме того, для каждого x мы можем выбирать решение независимо от других, главное - оптимальность
вот и поставим в каждом элементе суммы то значение yN, которое даст бОльшую вероятность успеха в данном случае
P{ok/N}=Sx max( P{ok,yN=1/qN=x,N} , P{ok,yN=0/qN=x,N} )p(x)=
=Sx max( F(x)^(N-1) , (1-F(x)^(N-1))*P{ok/max>x,N-1} )p(x)
здесь неизвестно только P{ok/max>x,N-1}
но его можно с помощью тех же преобразований выразить реккурентно через P{ok/max>x',N-1}
единственное отличие будет таким: если xN не будет удовлетворять условию xN>x, то оно не сможет быть максимумом
поэтому в выражении появится еще один множитель:
(!шаг уменьшился)
(!я переобозначил x через t, а x - теперь счетчик новой суммы)
P{ok/max>t,N-1}=Sx max( F(x)^(N-2)*P{x>t} , (1-F(x)^(N-2))*P{ok/max>x,max>t,N-2} )p(x)
P{x>t}: запись может показаться несколько странной, т.к. x,t - вполне детерминированные числа
она просто обозначает:
1 - если x>t
0 - иначе
теперь разобъем сумму на две: x<t и x>t
P{ok/max>t,N-1}=S1+S2
S1=S[x<t] max( 0 , (1-F(x)^(N-2))*P{ok/max>x,max>t,N-2} )=S(x<t) (1-F(x)^(N-2))*P{ok/max>x,max>t,N-2}p(x)
еще можно заметить, что при этом условии max>x,max>t эквивалентно max>t
S1=S[x<t] (1-F(x)^(N-2))*P{ok/max>t,N-2}p(x)
второе слагаемое:
S2=S[x>t] max( F(x)^(N-2) , (1-F(x)^(N-2))*P{ok/max>x,N-2} )p(x)

введем обозначения:
1. F(x)^N=FN(x)
2. P{ok/max>t,N}=fN(t)

получим: f[N+1](t)=( S[x<t](1-FN(x))fN](t) )+( S[x>t]max( FN(x) , (1-FN(x))*fN(x) )p(x)
вот, собственно и все...
у нас есть правило для вычисления fN(t)
есть правило для принятия решения на N+1 шаге:
1. если x<t => 0
2. если x>t:
2.1. если FN(x)>(1-FN(x))fN(x) => 1
2.2. иначе => 0
Добавлено @ 15:32
т.е. в конце концов мы получили интегральное уравнение (в общем случае, а для дискретных останется сумма), в котором под знаком интеграла стоит max
крутил я его крутил, ничего полезного не выкрутил
получается, что точно решить задачу таким методом не получается, если сл.величины могут принимать бесконечное количество значений (и не важно непрерывные это или дискретные)
для тех, которые имеют конечное количество значений (дискр.равномерная, биномиальная) нужно хранить всю функцию в виде вектора
для остальных можно попробовать приближенные вычисления, но исследовать влияние вычислительных ошибок в этом случае у меня рука не поднимается
также пробовал исследовать это при больших N, тоже ничего...
Добавлено @ 15:36
ну и понаписывал я тут... когда со скроллингом пишешь, незаметно, а тут...

maxim1000
Распечатываю, буду осмысливать...

Брошюра о разборчивой принцессе (~200 Kb):
http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf

Это сообщение отредактировал(а) MBo - 24.2.2005, 16:23

Цитата

Брошюра о разборчивой принцессе (~200 Kb):

почитал, интересная задачка
но не совсем та, которая тут стоит, хотя тот подход, который я использовал совпадает с описанным (что и не удивительно: среди подобных задач редкие не решаются с использованием динамического программирования)
здесь нет информации о распределении "качества" женихов, а только попарное сравнение
с одной стороны может показаться, что эта задача сложнее, т.к. информации меньше
но это было бы так, если бы требовался одинаковый результат, а в обеих задачах требуется найти оптимальный подход
более того, эта задача даже проще, чем та, которая сформулирована в начале темы:
дело в том, что причиной сложности этой задачи является необходимость "тянуть" за собой предысторию:
1. в случае в задачей о принцессе предыстория довольно простая - просто 1 бит (лучший из известных или нет)
2. в этой задаче предыстория представляет собой число (из большого множества), а значит, приходится оперировать функциями от этого числа...

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