rulinux.net - Форум - Talks - Лоровские комментаторы неспособны решить задачку правильно.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 16:04:56 +0400

> Ничего не глючит.
глючит - левые переносы строк добавляются

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 15:20:53 +0400

Попробуй вставить сюда этот код: http://pastebin.ca/1879798

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 15:08:48 +0400

Это я его поставил.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 15:03:31 +0400

А я ставил - сам проверь. там стоит \end{highlight}

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 14:59:49 +0400

Ничего не глючит. Закрывающий тег надо ставить.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 14:28:12 +0400

Глючит чего-то вставка кода.

*Main> length (fourOf [1,1,1,1,2,2,2,2,3,3,4,4]) 495

*Main> length(filter (== 2) (map length (map nub (fourOf [1,1,1,1,2,2,2,2,3,3,4,4])))) 125

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 14:27:10 +0400

\begin[haskell]{highlight}

import Data.List

fourOf :: [a] -> [[a]] fourOf xs = [ [a,b,c,d] | (a:as)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 14:25:15 +0400

Вот переборное решение на Хаскелле. Короче рандомного получилось.

haskell





import Data.List



fourOf :: [a] -> [[a]]

fourOf xs =

  [ [a,b,c,d] | (a:as)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 13:32:22 +0400

> А чем тебе слово моделирование не нравится? То что модель простенькая?
Нам, торсионщикам, вообще пофиг как и что называть, к терминам мы не щепетильны, ибо смотрим всегда в суть вещей и прекрасно понимаем что терминологическая обёртка это всего лишь обёртка :)))

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 13:09:19 +0400

>o_O, я на С++( С по сути ) вообще-то привел решение
Кульхацкер, да. Решение прикольное.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 13:03:51 +0400

>Нет, нужно просто иметь мозги. Хотя бы немножко. :)
Да, с мозгами велосипеды можно заново переоткрыть.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 13:02:09 +0400

> в твоем случае их знает библиотека на питоне.
o_O, я на С++( С по сути ) вообще-то привел решение

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 13:01:13 +0400

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

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:59:11 +0400

>Точно так же как можно накосячить при переборе, допустив ошибку, точно так же можно накосячить и при "моделировании"
Если допустить, что это несовместные события (человек не клинический дебил), то вероятность получить одинаковый неверный ответ в обоих случаях меньше. А чем тебе слово моделирование не нравится? То что модель простенькая?

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:56:31 +0400

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

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:55:30 +0400

> для того чтобы перебор без ошибок написать нужно как минимум знать основы комбинаторики
Нет, нужно просто иметь мозги. Хотя бы немножко. :)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:52:55 +0400

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

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:23:39 +0400

в догонку.

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

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:19:19 +0400

> Ты опять ничего не понял.
Всё я прекрасно понял, не переживай, я решал такие задачи когда ты ещё пешком под стол ходил :)

Точно так же как можно накосячить при переборе, допустив ошибку, точно так же можно накосячить и при "моделировании". Ведь код, который определяет благоприятный/неблагоприятный исход по сути один и тот же. Разница в алгоритмах только в том, что в одном случае делается последовательный перебор вариантов а в другом тупо извлекается рандомное значение. Вот и всё! :)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:11:53 +0400

>Моделирование здесь нахрен не нужно. Ибо апсолютно точный а не приблизительный процент можно высчитать аналитически. Компьютер здесь нужен только для того чтобы не составлять таблицу вариантов вручную на бумажке, вот и всё. К тому же у нас могут возникнуть сомнения относитльно случайности выдаваемых софтверным ГСЧ случайных чисел ;)
Ты опять ничего не понял. Тебе объясняли, что при решении вероятностных задач легко допустить в рассуждениях ошибку, например забыв учесть какой-либо случай, как это сделали лоровские аналитики, или, наоборот, один и тот же благоприятный исход был посчитан дважды. Моделирование помогает найти такие ошибки. А софтверный генератор таки выдает равномерное распределение, что для моделирования и нужно.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 12:03:19 +0400

C_i - что мойшина за дверью i, i=1,2,3 H_ij - ведущий открывает дверь j, после того, как игрок указал на дверь i, i=1,2,3

Допустим, что машина с одинаковой вероятностью может находиться за любой дверью. Тогда P(C_1) = P(C_2) = P(C_3) = 1/3

Затем найдем вероятность того, что ведущий открывает дверь j после того, как игрок указал на дверь i, при условии, что машина находится за дверью k P(H_ij | C_k), i,j,k=1,2,3

P(H_ij | C_k) = 0, если i=j или j=k 1/2, если i=k и i!=j 1, в остальных случаях.

Чтобы найти вероятность того, что находится за дверью k, при условии что ведущий открывает дверь j после того как игрок указал на дверь i воспользуемся формулой Байеса:

P(C_k | H_ij) = P(H_ij | C_k) * P(C_k) / P(H_ij)

Так как гипотезы несовместные, то для вычисления P(H_ij) воспользуемся формулой полной вероятности.

P(H_ij) = \sum_{k=1}^n P(H_ij | C_k)*P(C_k)

Например, игрок выбрал дверь 1, а ведущий открыл дверь 3. H_13 = (1/2) * (1/3) + 1*1/3 + 0 = 1/2

Тогда вероятность того, что мойшина находится за дверью 1 будет равна P(C_1|H_13) = (1/6) / (1/2) = 1/3, а вероятность того, что мойшинка за дверью номер 2: P(C_2|H_13) = (1/3) / (1/2) = 2/3.

Таки в два раза больше.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 11:42:01 +0400

Моделирование здесь нахрен не нужно. Ибо апсолютно точный а не приблизительный процент можно высчитать аналитически. Компьютер здесь нужен только для того чтобы не составлять таблицу вариантов вручную на бумажке, вот и всё. К тому же у нас могут возникнуть сомнения относитльно случайности выдаваемых софтверным ГСЧ случайных чисел ;)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 11:03:25 +0400

http://danym.livejournal.com/8666.html

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 11:02:57 +0400

херня это все :) есть задача поставленная ТС - есть решение, а приплетать сюда "моделирование" и умные фразы - никому не надо

П.С. я убежал по делам

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:56:30 +0400

вот этим и отличается, что ты перебираешь все варианты по одному, считая их, а в остальном коде имеются все характерные признаки реального процесса извлечения случайных шаров и поиска вероятности как учит теория вероятностей, в виде предела отношения успешных и всего сделанных попыток при количестве последних, стремящемся к бесконечности. На практике разница в том, что вообще говоря надо обосновать, что все перебранные тобой варианты равновероятны. Если бы это условие не выполнялось, то найденное тобой значение не может называться вероятностью. А также следует учесть, что в рассуждениях относительно количества вариантов и методики подсчитывания успешных может закрасться ошибка. Хотя для такой простой задачи как эта обоснование достаточно очевидно, но в общем случае это важный методологический момент. Прямое моделирование содержит наименьшее количество допущений, поскольку это просто картина реальных событий, и может служить критерием истины для результатов, полученных более другими способами.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:48:49 +0400

ну тогда мой вариант "моделирования", который доказывает, что С/С++ лучше всех :)

cpp



#include 

#include 



int BitCount( int value )

{

    int res = 0;

    

    while( value != 0 )

        { value &= value - 1; ++res; }



    return res;

}



int main( void )

{

    int all = 0;

    int count = 0;

    char black, white, red, blue;



    for( int j = 0 ; j < 100000 ; ++j )

    {

        int i = rand() % 4096;

        if( BitCount( i ) != 4 )

            continue;



        black  = i & 3 ? 1 : 0;

        white  = i & 12 ? 1 : 0;

        red    = i & 240 ? 1 : 0;

        blue   = i & 3840 ? 1 : 0;



        ++all;

        if( black + white + red + blue == 2 )

            ++count;

    }



    printf( "%.2f\n", float( count ) / all );



    return 0;

}

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:38:00 +0400

> Перебор уныло же, задача слишком проста.
а чем тут собс-но перебор от "моделирования" отличается? в моем примере i просто будет рандомным - вот и вся разница, просто на одну строку больше кода

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:36:05 +0400

спасибо

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:34:53 +0400

вот же http://www.lor-ng.org/page.php?id=2 гуголем нашед

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:33:21 +0400

ахаха, я ещё раз говорю, то было моделирование процесса, а не расчёт. Перебор уныло же, задача слишком проста.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:30:38 +0400

как тут кстати в сообщение код форматированный вставлять?

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:25:30 +0400

эх вы, рандомизаторы :) тут даже простым перебором все просто и быстро решается:

http://pastebin.ca/1879651

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:19:57 +0400

вот кстати



#include 

#include 



void choose (int * chosen, int * balls) {

        int balls_shuffled [12];

        int i, j, s, n;



        for (i = 0; i < 12; i++) balls_shuffled [i] = balls [i];

        n = 12;      

        for (i = 0; i < 4; i++) {

                s = (int) ((double) n * (rand () / (RAND_MAX + 1.0)));

                chosen [i] = balls_shuffled [s];

                for (j = s; j < n - 1; j++) balls_shuffled [j] = balls_shuffled [j + 1];

                n--;

        }   

}



int main (int argc, char * argv []) {

        int balls [12] = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3}; 

        int chosen [4], cnts [4], i, s;

        long total = 0, success = 0;



        while (1) {

                choose (chosen, balls);

                for (i = 0; i < 4; i++) cnts [i] = 0;

                for (i = 0; i < 4; i++) cnts [chosen [i]] = 1;

                s = 0;       

                for (i = 0; i < 4; i++) s += cnts [i];

                total++;

                if (2 == s) success++;

                if (0 == total % 100000L) printf ("%ld of %ld, p = %f\n", total, success, (double) success / (double) total);

        }   

        return 0;

}

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:03:37 +0400

да чё там без библиотек, замена gsl_ran_choose несколькими строками в данном случае реализуется

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 10:01:17 +0400

> Я так понял что тут цикл на 100000 итераций, в котором рандомно извлекаются шары? И зачем так делать?
Ты не шаришь, это моделирование процесса называется, вот зачем.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 09:33:48 +0400

Вот, кстати, решил вспомнить си и набросал простой вариант с перебором без дополнительных библиотек:

http://pastebin.ca/1879621

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 09:10:47 +0400

>Я питона не знаю совершенно, но по-моему ты херню написал. Я так понял что тут цикл на 100000 итераций, в котором рандомно извлекаются шары? И зачем так делать?
Потому что это самое простое решение сходу, не думая. У остальных решений в треде тот же алгоритм (про хаскель умолчу - не в курсе).

Вот тебе вариант как ты хочешь:

python



from __future__ import division

import random

import itertools



balls = ['blue'] * 4 + ['red'] * 4 + ['white'] * 2 + ['black'] * 2

count = 0

success = 0



for i in itertools.permutations(balls, 4):

    if len(set(i)) == 2:

        success += 1

    count += 1



print "%i/%i, rate %f" % (success, count, (success / count))



$ python balls2.py 

3000/11880, rate 0.252525

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 08:26:23 +0400

Я питона не знаю совершенно, но по-моему ты херню написал. Я так понял что тут цикл на 100000 итераций, в котором рандомно извлекаются шары? И зачем так делать? Нужно просто перебрать все возможные варианты без рандомов. Тогда и погрешности не будет. Короче, иди, переделывай!

Так, а с гуем на QT кто-то сбацает? :)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 08:25:41 +0400

ога, извесный бага. В инклудах было stdio.h и gsl/gsl_randist.h, если кому интересно

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 08:02:07 +0400

Блин и у меня скобки съел

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 08:01:47 +0400

Инклуды пустые :) Видать местный движок поедает все что в :)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 07:56:27 +0400



#include 

#include 



int main (int argc, char * argv []) {

        gsl_rng * g_base_rnd = gsl_rng_alloc (gsl_rng_mt19937);

        int balls [12] = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3}; 

        int chosen [4], cnts [4], i, s;

        long total = 0, success = 0;



        while (1) {

                gsl_ran_choose (g_base_rnd, chosen, 4, balls, 12, sizeof (int));

                for (i = 0; i < 4; i++) cnts [i] = 0;

                for (i = 0; i < 4; i++) cnts [chosen [i]] = 1;

                s = 0;

                for (i = 0; i < 4; i++) s += cnts [i];

                total++;

                if (2 == s) success++;

                if (0 == total % 100000L) printf ("%ld of %ld, p = %f\n", total, success, (double) success / (double) total);

        }

        return 0;

}

Re: Лоровские комментаторы неспособны решить задачку правильно.

Wed, 09 Jun 2010 03:49:35 +0400

haskell





import System.Random

import System.IO.Unsafe

import Data.List



rnd :: Int -> Int -> Int

rnd a b = x where (x,_)=randomR(a,b) (unsafePerformIO newStdGen)



getnflst :: Int -> ([a], [a]) -> ([a], [a])

getnflst n ([], []) = ([], [])  

getnflst n ([], l) = ([], l)

getnflst 0 (lst, l) = (lst, l)

getnflst n (lst, l) = let r=(rnd 1 (length lst)) in

   getnflst (n-1) ((take (r-1) lst)++(drop r lst), lst!!(r-1):l)

 

solution :: (Num t, Eq a, Num a1) => [a] -> Int -> Int -> t -> a1 -> a1

solution ballset n ngood 0 count = count 

solution ballset n ngood iter count = 

   if length(nub(snd(getnflst n (ballset,[])))) == ngood then 

      solution ballset n ngood (iter - 1) (count + 1) else 

      solution ballset n ngood (iter - 1) count

*Main> (solution [1,1,1,1,2,2,2,2,3,3,4,4] 4 2 100000 0)/100000 0.25202

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 16:50:31 +0400

хотя да, там формат в конце. У тебя просто печатается так мало цифр, тогда понятно.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 16:49:24 +0400

там получается точно - 0.(25), у меня на 100000 итерации 0.25265. То, что у тебя так мало цифр в результате - подозрительно. Ашыпку не искал, была охота с позорной змеюкою связываться.

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 14:15:50 +0400

Да, я очень толст, впрочем, я и не пытался быть тоньше :)

А вот претензии к результату я не очень понимаю. Где ошибка (если не принимать во внимание питон, естественно)?

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 14:00:24 +0400

фу как толсто, тем более и результат неправильный даже

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 12:02:12 +0400

Простой для понимания вариант на питоне, чтобы позлить Бугмакера.

python



from __future__ import division

import random



balls = ['blue'] * 4 + ['red'] * 4 + ['white'] * 2 + ['black'] * 2

count = 0

success = 0



for i in range(100000):

    if len(set(random.sample(balls, 4))) == 2:

        success += 1

    count += 1



print "Success rate %4.2f" % (success / count)

$ python balls.py 

Success rate 0.25

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 11:01:41 +0400

ну а я прого сотворил. Походу последний ответ самый правильный ИМХО.

lisp



(declaim (optimize (speed 3) (safety 0)))



(defconstant *balls* '(1 1 1 1 2 2 2 2 3 3 4 4))



(defun take-four nil

        (let* ( 

                (pts (pairlis (mapcar #'(lambda (&optional unused) (random 1.0)) (make-list (length *balls*))) *balls*))

                (rnd (sort pts #'(lambda (x y) (> (first x) (first y))))))

                        (mapcar #'rest (subseq rnd 0 4))))



(defun only-two-kinds (inp)

        (= 2 (length (remove-duplicates inp))))



(defun simulate-forever nil

        (let (  

                (nt 0)                                                                                                                                       (ns 0)) 

                        (loop   

                                (incf nt)

                                (when (only-two-kinds (take-four)) (incf ns))

                                (when (integerp (/ nt 100000))

                                        (format t "found: ~A of ~A, p=~A~%" ns nt (float (/ ns nt)))))))                                                                                                                                                                                  (simulate-forever)

Re: Лоровские комментаторы неспособны решить задачку правильно.

Tue, 08 Jun 2010 08:53:30 +0400

Я считал немножко по-другому:

p = {C(8;4) - 2 + 4 * (C(6;4) -1) + C(4;4)}/{C(4;12)} = 125/495.

Можно, как и лоровский аналитик размещения использовать.

Но как до такого лоровцы докатились, представить не могу.