Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм по Монти Холлу / 14 сообщений из 14, страница 1 из 1
15.12.2012, 08:07
    #38080384
vimer.c
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Привет всем!
Вот маленькая программа для отработки алгоритма по Монти-Холла. Задача из тервера, если кто не слышал, вот линк . Мне известно, что все сводится к selected_door!=right_door, была поставлена задача реализовать именно всю ситуацию, полностью. Привожу код, вывод программы тоже приложен к сообщению.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
#include <stdio.h>
#include <stdlib.h>

char init_doors(char *doors) {
	int i;
	for(i=0; i<3; i++) {
		doors[i] = 0;
	}
	i = rand() %3;
	doors[i] = 1;
	return i;
}

char select_door(void) {
	return rand() %3;
}

char select_another_door(char first_selected_door,
	char opened_door) {
	char another_door = 0;
	while((another_door==opened_door)||(another_door==first_selected_door))
		another_door++;
	return another_door;
}

char open_wrong_door(char selected_door, char right_door) {
	char wrong_door = 0;
	while((wrong_door==right_door)||(wrong_door==selected_door))
		wrong_door++;
	return wrong_door;
}

char play_monty(void) {
	char doors[3];
	char right_door;
	char selected_door;
	char opened_door;
	right_door = init_doors(doors);
	selected_door = select_door();
	opened_door = open_wrong_door(selected_door, right_door);
	selected_door = select_another_door(selected_door, opened_door);
	return (selected_door==right_door);
}

char play_nomonty(void) {
	char doors[3];
	char right_door;
	char selected_door;
	right_door = init_doors(doors);
	selected_door = select_door();
	return (selected_door==right_door);
}

int main(int argc, char **argv) {
	int i, j;
	int monty_stat, nomonty_stat;
	int monty_perc, nomonty_perc;
	char games_monty[101], games_nomonty[101];
	srand(time(NULL));
	monty_stat=nomonty_stat=0;
	games_monty[100] = 0;
	games_nomonty[100] = 0;
	for(j=0;j<50;j++) {
		for(i=0;i<100;i++) {
			games_monty[i]=(play_monty()) ? '*' : ' ';
			games_nomonty[i]=(play_nomonty()) ? '*' : ' ';
			((games_monty[i]=='*') && monty_stat++);
			((games_nomonty[i]=='*') && nomonty_stat++);
		}
		printf("%s|%s\n", games_nomonty, games_monty);
	}
	monty_perc = ((int)monty_stat/50);
	nomonty_perc = ((int)nomonty_stat/50);
	printf("%86d of 5000[%3d%]|%86d of 5000[%3d%]\n",
		nomonty_stat, nomonty_perc, monty_stat, monty_perc);
	return 0;
}


Вызывает сомнения реализация функций open_wrong_door() и select_another_door(). Посоветуйте, как их можно по-другому реализовать?
...
Рейтинг: 0 / 0
16.12.2012, 02:45
    #38080863
Perler
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Просто в тему, как-то писал на perle:

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
sub random_int_in ($$) {
    my($min, $max) = @_;
    return $min if $min == $max;
    ($min, $max) = ($max, $min) if $min > $max;
    return $min + int rand(1 + $max - $min);
}

sub game{
	 $car = random_int_in(1,3);
	#print "Машина в $car двери.\n";
	 $choose = random_int_in(1,3);
	#print "Игрок выбрал $choose дверь.\n";
	do { 
		 $opendoor = random_int_in(1,3);
	} while( ( $opendoor ==  $car) || ( $opendoor ==  $choose) );
	#print "Ведущий открыл проигрышную дверь $opendoor.\n";
	 $enddoor = 6 - $choose - $opendoor;
	#print "Игрок меняет дверь с $choose на $enddoor.\n";
	if($enddoor == $car){
		#print "Игрок победил!\n\n";
		return 1;
	} else{
		#print "Игрок проиграл!\n\n";
		return 0;
	}
	}
$win = 0;
$count = 10000000;
for(my $i = 0; $i<=$count; $i++){
$win += game();
}
print "Побед - $win, в $count испытаний\n";
<STDIN>;
...
Рейтинг: 0 / 0
16.12.2012, 12:55
    #38080939
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Perl конечно покомпактнее выглядит.

А глядя на скрин почему-то вспомнилось Conway's Game of Life и Adom.
...
Рейтинг: 0 / 0
17.12.2012, 15:54
    #38082125
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
чёт я не понял...
У меня вероятность выигрыша игрока остается равной 1 / 3,
что я и ожидал увидеть

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
from random import shuffle, randint

win = 0

for i in range(0, 10000):
    x = [0, 1, 2]
    shuffle(x)
    y = randint(0, 2)
    if x[y] != 0:
        del x[y]
        t = randint(0, 1)
        if x[t] == 0:
            win += 1

print 1.0 * win / 10000
...
Рейтинг: 0 / 0
17.12.2012, 16:03
    #38082156
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
rt5858,

Код: python
1.
if x[y] != 0:

А где else? Автопроигрыш? Вообще, это что за эксперимент?
...
Рейтинг: 0 / 0
17.12.2012, 16:51
    #38082279
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Abstraction,

ну, протупил я =)
почти двое суток не спал - в голове розовый туман
...
Рейтинг: 0 / 0
21.12.2012, 06:01
    #38087650
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
короче, вот как должно быть (и вер. выиграть авто теперь равна 2/3):
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
from random import shuffle, randint

win = 0

for i in range(0, 100000):
    x = [0, 1, 2]
    shuffle(x)
    y = randint(0, 2)
    if x[y] != 0:
        win += 1
        """
        del x[y]
        t = randint(0, 1)
        if x[t] == 0:
            win += 1
        """

print 1.0 * win / 100000


0 - это у меня авто

Т.е., если игрок на первом ходу угадал дверь с авто, то он однозначно проиграл,
а если не угадал, то он однозначно выиграет (считаем, что он обязательно изменит свой первоначальный выбор). Муть какая-то для домохозяек.
...
Рейтинг: 0 / 0
21.12.2012, 06:03
    #38087651
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
коммент не подсветился.... да и х. с ним
...
Рейтинг: 0 / 0
21.12.2012, 06:24
    #38087658
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
хорошо
Будем считать, что после предложения ведущего изменить свой выбор
игрок подбрасывает монетку и, если выпал 0, то свой выбор он не меняет,
а если 1, то меняет. В таком раскладе вероятность заполучить авто = 1/2
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
from random import shuffle, randint

win = 0

for i in range(0, 100000):
    x = [0, 1, 2]
    shuffle(x)
    y = randint(0, 2)
    if x[y] == 0:
        if randint(0, 1) == 0: ## игрок бросает монетку;
            win += 1
    else:
        if randint(0, 1) == 1: ## игрок бросает монетку;
            win += 1

print 1.0 * win / 100000
...
Рейтинг: 0 / 0
23.12.2012, 15:37
    #38089669
Perler
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
rt5858короче, вот как должно быть (и вер. выиграть авто теперь равна 2/3):
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
from random import shuffle, randint

win = 0

for i in range(0, 100000):
    x = [0, 1, 2]
    shuffle(x)
    y = randint(0, 2)
    if x[y] != 0:
        win += 1
        """
        del x[y]
        t = randint(0, 1)
        if x[t] == 0:
            win += 1
        """

print 1.0 * win / 100000


0 - это у меня авто

Т.е., если игрок на первом ходу угадал дверь с авто, то он однозначно проиграл,
а если не угадал, то он однозначно выиграет (считаем, что он обязательно изменит свой первоначальный выбор). Муть какая-то для домохозяек.

Один код лучше другого)
Какой толк после этого:
[SRC Python] if x[y] != 0:
win += 1
что-то ещё писать дальше? Если не равно и так победа и win + 1, при любой другой ситуации проигрыш.

То что с монеткой ты описывал, а что там должно было быть как не стремящаяся вероятность к 0,5 ?
...
Рейтинг: 0 / 0
23.12.2012, 18:50
    #38089817
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Perler,

так, хорошо. А что тогда надо?
Я написал код, который проводит 100000 игр и показывает,
что вероятность выиграть авто равна 2/3 (при обязательной смене первоначального выбора).

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
from random import shuffle, randint

win = 0

for i in range(0, 100000):
    x = [0, 1, 2]
    shuffle(x)
    y = randint(0, 2)
    if x[y] != 0:
        win += 1

print 1.0 * win / 100000


IDLE 1.2
>>> ================================== RESTART =======
>>> 
0.66743
>>> 


Чё еще нужно?
И не надо раздувать из блохи слона.
...
Рейтинг: 0 / 0
23.12.2012, 18:53
    #38089819
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Perler,
авторКакой толк после этого:
[SRC Python] if x[y] != 0:
win += 1
что-то ещё писать дальше?
ты просто Питон не знаешь (а я не знаю Перл):
то, что между утроенными кавычками - это коммент.
...
Рейтинг: 0 / 0
23.12.2012, 20:49
    #38089917
Perler
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
rt5858,
Насчёт кавычек сразу не уловил что это коммутируемый блок.
Сейчас питон осваиваю, нравится, лёгок в усвоении по сути день на освоение синтаксиса и имея справку по встроенным функциям можно уже писать приложения, легче Perl'a в разы осваивается.
...
Рейтинг: 0 / 0
23.12.2012, 21:09
    #38089931
rt5858
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм по Монти Холлу
Perlerrt5858,
Насчёт кавычек сразу не уловил что это коммутируемый блок.
Сейчас питон осваиваю, нравится, лёгок в усвоении по сути день на освоение синтаксиса и имея справку по встроенным функциям можно уже писать приложения, легче Perl'a в разы осваивается.
Очень и очень правильный ход с твоей стороны - взяться за Питошу.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм по Монти Холлу / 14 сообщений из 14, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]