Форум на Исходниках.RU

Гадалка Шеннона

Pacific — Thu, 18 Jan 2007 19:26:52 +0000

Pacific: Pegas
Возвращаясь к твоему вопросу: когда-то давно я тоже читал про этот алгоритм и закодил его, а потом поражался его проницательности. Вкратце, простейшая версия этого алгоритма работает так: пусть угадывание ведется на основе N предыдущих загаданных чисел (они программе известны). Программа собирает статистику - сколько раз N+1-е число было единицей или нулем в зависимости от предыдущих. Если единиц было больше, то пишет "1", иначе "0". Числа, которые загадывает человек, она отгадывает легко, так как людям свойственно (например) после 5 подряд идущих единиц загадать 0. Что касается генераторов псевдослучайных чисел - эту прогу, как выяснилось, можно использовать как еще один тест на качество генерируемых чисел. Для качественного генератора процент угадывания должен колебаться в районе 50%.

Гадалка Шеннона

amk — Thu, 18 Jan 2007 18:55:32 +0000

amk: Заметь числа ПСЕВДОСЛУЧАЙНЫЕ, т.е. они только похожи на случайные. Раз вероятность угадывания всего 55% можно сказать, что в данном случае он неплохо справляется.

Гадалка Шеннона

Pegas — Thu, 18 Jan 2007 09:36:12 +0000

Pegas: Pacific

я использовал стандартный псевдо случайный генератор чисел из С++. я в нём не силён, так что криптографические генераторы заюзать проблематично.

ЗЫ я дату видел, и надеялся что кто-то из активных в данное время форумчан заметят пост и ответят =)

Гадалка Шеннона

Pacific — Thu, 18 Jan 2007 06:40:00 +0000

Pacific: Pegas
Ты смотрел на дату первого поста? Вряд-ли они тебе уже ответят. Твой генератор не очень качественный, раз программа стабильно угадывает его значения с вероятностью > 50%. Попробуй криптографические генераторы, или вместо случайных бит используй биты какого-нибудь зашифрованного RAR-архива. Их-то эта прога точно не сможет угадать.

Гадалка Шеннона

Pegas — Wed, 17 Jan 2007 15:23:40 +0000

Pegas: пожалуйста, ответьте на мой вопрос - это действительно важно. я приложу все усилия, что бы понять =)

ЗЫ вроде алгоритм не сложный должен быть, но что-то само не приходит((

ЗЗЫ вот немного изменённый вышепреведённый код:

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <time.h>

#include <stdlib.h>

#define SCANCODE_ONE 49

#define SCANCODE_ZERO 48

typedef unsigned short us;

typedef unsigned char uc;

typedef unsigned long ul;

typedef struct

{

ul zero;

ul one;

} datatype;

// çàïðîñ ñèìâîëà ñ êëàâû

uc getnum(void)

{

/* uc j, k=0;

while ( !kbhit() );

while ( !k )

k = getch();

j=255;

if ( k == SCANCODE_ONE )

j=1;

if ( k == SCANCODE_ZERO )*/

int j=rand()%2;

return j;

}

void updatedata(datatype **data, uc *ans, uc depth)

{

int i, k;

ul j;

for ( i=(depth-1); i>=0; i-- ) {

j=0;

for ( k=(depth-1); k>=i; k-- )

j += ans[k] * (1<<(depth-1-k));

if ( ans[depth] == 1)

data[depth-1-i][j].one++;

if ( ans[depth] == 0)

data[depth-1-i][j].zero++;

}

uc analyse(datatype **data, uc *ans, uc depth)

{

int i, k;

ul j, zero=0, one=0;

for ( i=(depth-1); i>=0; i-- ) {

j=0;

for ( k=(depth-1); k>=i; k-- )

j += ans[k] * (1<<(depth-1-k));

one += data[depth-1-i][j].one;

zero += data[depth-1-i][j].zero;

}

if ( zero > one )

return 0;

else

return 1;

}

void main ( void )

{

srand((unsigned)time(NULL));

ul all_answer=0, wrong_answer=0;

int depth;

datatype **data;

uc *ans;

us i;

uc t_ans, c;

printf("\nDepth (1..20) : "); scanf("\%d", &depth);

ans = (uc *)calloc( depth+1, sizeof(uc *));

if ( ((data = (datatype **)malloc( depth * sizeof(datatype *) )) == NULL) ) {

puts("Not enough memory!");

exit(1);

}

for ( i=0; i<depth; i++ )

if ( (data[i] = (datatype *)calloc( (1+(1<<(i+1))), sizeof(datatype) )) == NULL) {

puts("Not enough memory!");

exit(1);

}

printf("\nPress '0' or '1'.");

printf("\nAny other key - exit.\n\n");

int xy=0;

while (1) {

for ( i=0; i<depth; i++ )

ans[i] = ans[i+1];

t_ans = analyse(data, ans, depth);

if ( (ans[depth] = getnum()) == 255)

return;

updatedata(data, ans, depth);

all_answer++;

c = '+';

if ( t_ans != ans[depth] ) {

wrong_answer++;

c = '-';

}

xy = xy+1;

if ((xy%1000000)==0)

printf("? \%d - \%d ? \%0.3f ? \%d ? \%c ?\n", ans[depth], t_ans, (all_answer-wrong_answer)/(all_answer+1.0), all_answer, c );

}

здесь числа задаёт генератор случайных чисел. объясните мне, дураку, почему этот алгоритм разгадывает числа, задаваемые генератором случайных чисел? причём результат угадывания( если установить глубину поиска равной 20 ) всегда больше 50%. зачастую 53-54 процента.

что за фигня?

Гадалка Шеннона

Pegas — Wed, 03 Jan 2007 23:22:48 +0000

Pegas: а не можете ли вы, дескать, на пальцах объяснит данный алгоритм? как именно он работает? как именно проходит анализ?

Заранее благодарен за любую помощь!

ЗЫ с С++ не слишком знаком, так что разобраться в выше приведённом коде весьма затруднительно =)

Гадалка Шеннона

GrAnd — Thu, 22 Aug 2002 09:42:30 +0000

GrAnd: Для реализации данного алгоритма поможет простой статистический анализ вариантов человека. Т.е. если процент выпадения у человека 1 больше, чем 0, то и вариант ответа машины будет склоняться к 1. Данный анализ здорово помагает для безошибочного анализа ответов ;D ;D ;D

Гадалка Шеннона

Poisson — Thu, 15 Aug 2002 08:16:50 +0000

Poisson: Ниже мой старый исходник, по-моему это то, о чем ты спрашивал.

#include
#include
#include
#include

#define SCANCODE_ONE 49
#define SCANCODE_ZERO 48

typedef unsigned short us;
typedef unsigned char uc;
typedef unsigned long ul;

typedef struct
{
ul zero;
ul one;
} datatype;

// запрос символа с клавы
uc getnum(void)
{
uc j, k=0;
while ( !kbhit() );
while ( !k )
k = getch();
j=255;
if ( k == SCANCODE_ONE )
j=1;
if ( k == SCANCODE_ZERO )
j=0;
return j;
}

void updatedata(datatype **data, uc *ans, uc depth)
{
int i, k;
ul j;
for ( i=(depth-1); i>=0; i-- ) {
j=0;
for ( k=(depth-1); k>=i; k-- )
j += ans[k] * (1<<(depth-1-k));
if ( ans[depth] == 1)
data[depth-1-i][j].one++;
if ( ans[depth] == 0)
data[depth-1-i][j].zero++;
}
}

uc analyse(datatype **data, uc *ans, uc depth)
{
int i, k;
ul j, zero=0, one=0;

for ( i=(depth-1); i>=0; i-- ) {
j=0;
for ( k=(depth-1); k>=i; k-- )
j += ans[k] * (1<<(depth-1-k));
one += data[depth-1-i][j].one;
zero += data[depth-1-i][j].zero;
}
if ( zero > one )
return 0;
else
return 1;
}

void main ( void )
{
ul all_answer=0, wrong_answer=0;
uc depth;
datatype **data;
uc *ans;
us i;
uc t_ans, c;

printf("\nDepth (1..20) : "); scanf("\%d", &depth);

ans = (uc *)calloc( depth+1, sizeof(uc *));

if ( ((data = (datatype **)malloc( depth * sizeof(datatype *) )) == NULL) ) {
puts("Not enough memory!");
exit(1);
}

for ( i=0; i if ( (data[i] = (datatype *)calloc( (1+(1<<(i+1))), sizeof(datatype) )) == NULL) {
puts("Not enough memory!");
exit(1);
}

printf("\nPress '0' or '1'.");
printf("\nAny other key - exit.\n\n");

while (1) {
for ( i=0; i ans[i] = ans[i+1];
t_ans = analyse(data, ans, depth);

if ( (ans[depth] = getnum()) == 255)
return;

updatedata(data, ans, depth);
all_answer++;

c = '+';
if ( t_ans != ans[depth] ) {
wrong_answer++;
c = '-';
}
printf("? \%d - \%d ? \%0.3f ? \%d ? \%c ?\n", ans[depth], t_ans, (all_answer-wrong_answer)/(all_answer+1.0), all_answer, c );
}
}

Гадалка Шеннона

stx — Tue, 30 Jul 2002 04:24:08 +0000

stx: ты насчет этого,http://zab.megalink.ru/depart/vm/olimp/lec/pg03.htm
да это просто забавно, я хочу сказать.

Гадалка Шеннона

hunter — Sat, 27 Jul 2002 19:04:36 +0000

hunter: Не встречал ли кто "Гадалку Шеннона"?
Вот ее краткое описание:
Человек пишет на бумаге число 0 или 1. Машина этого числа не знает, но печатает 0, 1 или 2. Двойка говорит, что машина не берётся угадать написанное число, а 0 или 1 - её предположение о написанном числе. После этого человеку сообщают предположение машины, а в машину вводят число, написанное человеком.

Если встречали и у Вас есть подробное описание алгоритма или работающая программа то немогли бы Вы мне ее выслать?
Не знаете ли Вы другие алгоритмы, решающие эту задачу?