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

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

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

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

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

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.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 )
     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<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");

  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 = '-';
     }
     printf("? \%d - \%d ? \%0.3f ? \%d ? \%c ?\n", ans[depth], t_ans, (all_answer-wrong_answer)/(all_answer+1.0), all_answer, c );
  }
}

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

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

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

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

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

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

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

#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 - 17.01.07, 21:44

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

Сообщение отредактировано: Pacific - 18.01.07, 06:42

Pacific

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

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

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

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