| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Найти максимальное число конечного ряда |
| Автор: Akina 21.2.2005, 12:04 |
| Имется программа, которая получает некое целое число N (порядка 100-1000) и по нему генерирует нумерованный список N случайных чисел диапазона 0...MaxLongInt. Требуется написАть программу, которая: 1) Получает на входе N. 2) Получает на входе первое число списка. 3) Принимает решение, является ли сообщенное ей только что число наибольшим в списке или нет, и сообщает это решение. 4) Если программа приняла решение что число - не наибольшее, ей сообщается следующее число списка. 5) Происходит переход на шаг 3). Программа работает до тех пор пока она не примет решение о том что очередное число - наибольшее в списке, либо пока список не закончится. Есссно требование к программе - угадывание максимального числа из списка с максимально возможной вероятностью. |
| Автор: Akina 21.2.2005, 13:26 |
| НаписАл на 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 случайных списков). |
| Автор: maxim1000 21.2.2005, 13:30 |
| парочка вопросиков: 1. числа в разных ячейках независимы? (это я так, на всякий случай) 2. какую информацию может использовать функция (только текущее значение или предыдущие тоже)? Добавлено @ 13:31 упс... пока писал, появился новый пост 2. отпадает 3. а почему на VB?????  |
| Автор: Akina 21.2.2005, 14:02 | ||||||
а что попалось... тем более что VBA у каждого под рукой есть... |
| Автор: maxim1000 21.2.2005, 20:54 |
| нее, задачка тут интересная есть такое решение: выбирать то, что более вероятно (максимум здесь или будет дальше) но это не проходит для общего критерия... |
| Автор: Akina 22.2.2005, 09:03 | ||||
ну чуть выше - процедура генерации файла с массивом чисел же ж... чего спрашиваешь?
так основной вопрос - КАК? чтобы с максимальной вероятностью попасть в точку... рожденный мной алгоритм дает в среднем 36-40% (на выборке из 10 тыс. случайных списков) - и я даже решить не могу, хорошо это или это плохо и возможно гораздо лучше... |
| Автор: maxim1000 22.2.2005, 10:45 |
| ну нет, придумать алгоритм и потом просто померять его эффективность и решить много/мало... при таком подходе всегда останутся сомнения "а нельзя ли лучше", это - вообще опасный подход, его стоит использовать лишь в плохо формализованных задачах или там, где оптимальный метод ну никак не придумывается а оптимальный алгоритм ищется по критерию - максимум вероятности успеха, она записывается через решение на текущем шаге и вероятность успеха на следующем (в случае, если решение - продолжать) я крутил-крутил, пока не выкрутил думаю, скоро получится |
| Автор: Akina 22.2.2005, 11:10 |
| Вот в том и фигня, что пока у меня лично не вытанцовывается алгоритм... т.е. можно попробовать на основе предыдущих значений считать вероятность того что очередное число - максимальное, предполагая равномерное распределение в заданном диапазоне 0...MaxLongInt, но хотелось бы решить несколько более общую задачу - для неограниченных значений... |
| Автор: maxim1000 22.2.2005, 11:38 | ||||
у меня как раз трудности больше технического характера я пытаюсь использовать именно тот подход, который описал: тупо максимизировать вероятность успеха, она, конечно же, зависит от количества оставшихся чисел, но еще пришлось добавить зависимость от максимума всех предыдущих, и уже эта функция, вроде бы выражается реккурентно
если имеется в виду произвольные распределения, то, думаю, с этим больших проблем не возникнет (надо только, чтобы функция распределения выражалась как-нибудь попроще, или вообще свести все это к численным методам)... |
| Автор: Akina 22.2.2005, 11:53 | ||||
не только произвольные, но и неограниченные (т.е. не имеющие ни минимально, ни максимально возможного значения)...
вот это я вроде и реализовал... может, криво, раз получается 36-40%... |
| Автор: maxim1000 22.2.2005, 12:07 | ||||||
тогда было бы интересно посмотреть тут есть один момент, на который можно пойматься: можно подумать, что на каждом шаге нужно просто выбрать, что более вероятно - максимум это или нет, это несколько отличается от условия задачи (это было бы решением в том случае, если бы после ответа "да,максимум" обработка бы продолжалась и давалась бы возможность исправиться Добавлено @ 12:08
вот в том-то и дело: если алгоритм получен путем строгих рассуждений, то нет сомнений - это оптимум, и ничего лучше не найти Добавлено @ 12:08
протестировано? или так, просто потому, что показалось, что результаты низкие? |
| Автор: Akina 22.2.2005, 12:19 | ||||||
увы, сплошная псевдоквазия...
да. как только сказано "максимум" - обработка заканчивается.
не хочу пока - чужое решение зачастую направляет мысль в том же направлении, и, следовательно, можно потерять более подходящий путь... |
| Автор: maxim1000 22.2.2005, 13:06 | ||
тоже правильно сегодня дома покручу, возможно, завтра что-нибудь будет... |
| Автор: MBo 22.2.2005, 18:14 |
| Если не ошибаюсь, эта задача аналогична задаче о выборе принцессой жениха. Hint - для больших N отсматривается N/e кандидатов. BTW, родственной задаче была посвяшена диссертация небезызвестного Б.А.Березовского |
| Автор: maxim1000 24.2.2005, 15:28 |
| вчера так странно получилось... наличие заданий совпало с желанием поработать выкладываю сегодня... Добавлено @ 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  ну и понаписывал я тут... когда со скроллингом пишешь, незаметно, а тут... |
| Автор: Akina 24.2.2005, 16:03 |
| maxim1000 Распечатываю, буду осмысливать... |
| Автор: MBo 24.2.2005, 16:21 |
| Брошюра о разборчивой принцессе (~200 Kb): http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf |
| Автор: maxim1000 24.2.2005, 17:18 | ||
почитал, интересная задачка но не совсем та, которая тут стоит, хотя тот подход, который я использовал совпадает с описанным (что и не удивительно: среди подобных задач редкие не решаются с использованием динамического программирования) здесь нет информации о распределении "качества" женихов, а только попарное сравнение с одной стороны может показаться, что эта задача сложнее, т.к. информации меньше но это было бы так, если бы требовался одинаковый результат, а в обеих задачах требуется найти оптимальный подход более того, эта задача даже проще, чем та, которая сформулирована в начале темы: дело в том, что причиной сложности этой задачи является необходимость "тянуть" за собой предысторию: 1. в случае в задачей о принцессе предыстория довольно простая - просто 1 бит (лучший из известных или нет) 2. в этой задаче предыстория представляет собой число (из большого множества), а значит, приходится оперировать функциями от этого числа... кстати, баловался с критериями, нашел еще одну простую задачку (ее как раз можно решить и для произвольных распределений): условия - как в начале темы, критерий - мат.ожидание выбранного элемента эта задача еще проще задачи о принцессе: тут вообще не нужно смотреть на предысторию |