На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Гадалка Шеннона
    Не встречал ли кто "Гадалку Шеннона"?
    Вот ее краткое описание:
       Человек пишет на бумаге число 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
            а не можете ли вы, дескать, на пальцах объяснит данный алгоритм? как именно он работает? как именно проходит анализ?

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

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

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

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

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

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

                  ЗЫ я дату видел, и надеялся что кто-то из активных в данное время форумчан заметят пост и ответят =)
                    Заметь числа ПСЕВДОСЛУЧАЙНЫЕ, т.е. они только похожи на случайные. Раз вероятность угадывания всего 55% можно сказать, что в данном случае он неплохо справляется.
                      Pegas
                      Возвращаясь к твоему вопросу: когда-то давно я тоже читал про этот алгоритм и закодил его, а потом поражался его проницательности. Вкратце, простейшая версия этого алгоритма работает так: пусть угадывание ведется на основе N предыдущих загаданных чисел (они программе известны). Программа собирает статистику - сколько раз N+1-е число было единицей или нулем в зависимости от предыдущих. Если единиц было больше, то пишет "1", иначе "0". Числа, которые загадывает человек, она отгадывает легко, так как людям свойственно (например) после 5 подряд идущих единиц загадать 0. Что касается генераторов псевдослучайных чисел - эту прогу, как выяснилось, можно использовать как еще один тест на качество генерируемых чисел. Для качественного генератора процент угадывания должен колебаться в районе 50%.
                        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                        0 пользователей:


                        Рейтинг@Mail.ru
                        [ Script execution time: 0,0359 ]   [ 15 queries used ]   [ Generated: 21.05.24, 06:27 GMT ]