Игра «Акинатор». Язык программирования: С++. Среда разработки: Microsoft Visual Studio 2010

Московский государственный университет экономики, статистики и информатики Институт Компьютерных Технологий Кафедра Математического обеспечения информационных систем и инноватики (МОИСиИ)

Курсовая работа

по курсу «Объектно-ориентированное программирование (ООП (2))»

на тему

" Игра «Акинатор». Язык программирования: С++. Среда разработки: Microsoft Visual Studio 2010

Выполнил студент группы ДКО-201:

Наразин И.В.

ДКО-10 161

Руководитель Переверзев И.Ю.

Москва, 2012 г.

• Задание
• Структура программы
• Исходный код
• Литература

Задание

Разработка игры «Угадай персонажа». Суть игры: пользователь загадывает персонажа, затем отвечает на предлагаемые программой вопросы. В итоге программа угадывает загаданного персонажа.

В программе учесть:

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

2) Обучаемость. Программа должна запоминать новых персонажей и новые вопросы, корректировать свою базу данных.

3) Каждый вопрос должен дать программе как можно больше информации. Т. е. вопрос не должны выбираться случайно.

1. Алгоритмы и методы

База данных программы состоит из двух файлов:

Responses. txt — все возможные ответы программы

Questions. txt — все возможные вопросы.

Вид записи в responses. Txt

Каждый раз список возможных вариантов ответов сортируется по вероятностям. Новый вопрос берется из списка вопросов самого, на данный момент, вероятного ответа. Первые несколько вопросов — самые наиболее встречающиеся в векторах ответов персонажей. Они нужны для первоначального отсева персонажей.

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

Ответ считается найденным, если разность между двумя, на данный момент самыми вероятными ответами, будет больше заранее заданной константы. Если пользователь загадал персонажа, которого нет в базе, то программа выдаст текущего наиболее вероятного (подходящего для данной базы) персонажа. А пользователь может скорректировать ответ программы.

Для добавления нового персонажа, пользователю предлагается ввести имя. Если его нет в базе (если есть, программа выдала неверный результат из-за небольшой базы), то он добавляется в базу ответов, а вектор его вопросов будет равен вектору положительных ответов в рамках данной игры.

Дальше пользователю предлагается ввести вопросов, который позволит отличить персонажа пользователя от персонажа, выданного программой. Этот вопрос запоминается в базе и заносится в вектор ответов для нового персонажа. Сам персонаж так же заносится в базу.

игра программа алгоритм

Структура программы

Основной алгоритм заключен в класс toguess. Методы:

toguess () — конструктор. Считывание базы из файлов.

void save () — сохранение измененной базы

void newgame () — новая игра, сброс вектора положительных ответов, загрузка скорректированной базы

int getQuestion () — выдает новый вопрос

void setQuestion (int id, bool q); - корректирует вероятности ответов в соответствии с ответом пользователя на вопрос с id.

int getResponse (int id=0); - попытка получить ответ

char* getfResponse (int id); - возвращает ответ с данным id в векторе

void setResponse (int id, bool flag); - корректирует базу, если программа угадала правильно. Не нужен, пока база мала. Имеет смысл, когда база больше нескольких тысяч вариантов

void newResponse (char* response); - добавляет в базу нового персонажа

void newQuestion (char* q); - добавляет в базу новый вопрос

void dellQuestion (int id); - удаляет вопрос из векторов ответов персонажей.

Приватные методы:

bool findInVector (std: vector v, int id); - ищет id в векторе. Если находит, возвращает true

bool findInVector (std: vector v, int id); - ищет id в векторе. Если находит, возвращает true

int maxid (std: vector _questions); - возвращает максимальный id в векторе

char* addspaces (char* str); - заменяет нижниче пдчеркивания на пробелы

char* toniceview (char* str); - переводит из транслита в кириллицу

bool havequestions (); - true, если есть вопросы, на которые пользователь не ответил

int populatQuestion (); - возваращет id самого популярного вопроса в векторах ответов персонажей

Исходный код

Класс toguess

Toguess. h

#include

class toguess

{

private:

struct s_question // структура вопросов

{

char* question;

int id;

};

struct s_response // структура ответов

{

char* response;

std: vector idQuest;

double probability;

};

// Постоянаая база для всей игры

std: vector questions;

std: vector responses;

// Временная база для одной игры

std: vector donequest;

std: vector Tquestions;

std: vector Tresponses;

int step;

bool findInVector (std: vector v, int id);

bool findInVector (std: vector v, int id);

int maxid (std: vector _questions);

char* addspaces (char* str);

char* toniceview (char* str);

bool havequestions ();

int populatQuestion ();

public:

toguess ();

void save ();

void newgame ();

int getQuestion ();

void setQuestion (int id, int q);

int getResponse (int id=0);

char* getfResponse (int id);

void setResponse (int id, bool flag);

void newResponse (char* response);

void newQuestion (char* q);

void dellQuestion (int id);

};

Toguess. cpp

#include «StdAfx. h»

#include

#include «toguess. h»

#include

#include

#include

using namespace std;

toguess: toguess ()

{ // конструктор

char* db_q_filename = «questions. txt» ;

char* db_r_filename = «responses. txt» ;

// Загружаем базу данных

// База вопросов

FILE *file = fopen (db_q_filename," r");

if (! file)

{

return;

}

while (! feof (file)) {

char word [1025];

int id;

fscanf (file," /%s /%i «,&word,&id);

char *question = new char [strlen (word)];

strcpy (question, word);

// toniceview (question);

s_question _Q;

_Q. id = id;

_Q. question = question;

questions. push_back (_Q);

}

fclose (file);

// База ответов (персонажей)

file = fopen (db_r_filename," r");

if (! file)

{

return;

}

while (! feof (file)) {

char resp [1025];

int countq;

float pro;

fscanf (file," %s /%i" ,&resp,&countq);

char *response= new char [strlen (resp)];

strcpy (response, resp);

vector quests;

for (int i=1; i<=countq; i++)

{

int temp;

fscanf (file, «%i «,&temp);

quests. push_back (temp);

}

fscanf (file, «%f/ «,&pro);

s_response thisResponse;

thisResponse. idQuest = quests;

thisResponse. probability = pro;

thisResponse. response = response;

responses. push_back (thisResponse);

}

fclose (file);

}

void toguess: newgame () {

// Старт новой игры

donequest. clear ();

Tquestions. clear ();

Tresponses. clear ();

Tresponses = responses;

Tquestions = questions;

for (int i=0; i

{

reverse (Tresponses [i]. idQuest. begin (), Tresponses [i]. idQuest. end ());

}

step = 0;

}

int toguess: getQuestion () {

// новый вопрос

// Каждый новый вопрос берется у самого подходяешго на данный момент персонажа,

// Таким образом, либо повысится вероятность того, что он и есть персонаж

// либо полностью исключится (или понизится?)

int id;

while (Tresponses [Tresponses. size () — 1]. idQuest. size () >0&&Tresponses [Tresponses. size () — 1]. idQuest [Tresponses [Tresponses. size () — 1]. idQuest. size () — 1] ==-1) Tresponses [Tresponses. size () — 1]. idQuest. pop_back ();

while (Tresponses [Tresponses. size () — 2]. idQuest. size () >0&&Tresponses [Tresponses. size () — 2]. idQuest [Tresponses [Tresponses. size () — 2]. idQuest. size () — 1] ==-1) Tresponses [Tresponses. size () — 2]. idQuest. pop_back ();

if (step>3)

{

if (Tresponses [Tresponses. size () — 1]. idQuest. size () ==0)

{

if (Tresponses [Tresponses. size () — 2]. idQuest. size ()! =0)

{

id=Tresponses [Tresponses. size () — 2]. idQuest [Tresponses [Tresponses. size () — 2]. idQuest. size () — 1];

}

else

{ // если о обоих на данный момент самых вероятных ответов больше не осталось вопросов, и их вероятности раны, лбио почти одинаковы,

// то понимажем их вероятность и переходи к другим вопросам.

if (Tresponses [Tresponses. size () — 1]. probability-Tresponses [Tresponses. size () — 2]. probability<0.01 && havequestions ())

{

Tresponses [Tresponses. size () — 1]. probability/=1.5;

Tresponses [Tresponses. size () — 2]. probability/=1.5;

for (int i = Tresponses. size () — 1; i > 0; i—)

{

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

{

if (Tresponses [j]. probability > Tresponses [j + 1]. probability)

swap (Tresponses [j], Tresponses [j + 1]);

}

}

return getQuestion (); // Отсортировав в соотв. с новыми вероятностями, берем вопрос.

}

return — 1; // ответ — на данный момент самый вероянтый. Ответ не точный, но система делает вывод, что дальше спрашивать смысла нет

}

}

else

{

id=Tresponses [Tresponses. size () — 1]. idQuest [Tresponses [Tresponses. size () — 1]. idQuest. size () — 1];

}

}

else // первые три (?) вопроса берем для первоначальной сортировки воросов, самые общие вопросы, по мнению системы

{

id = populatQuestion ();

}

step++;

for (int i=0; i

{

if (Tquestions [i]. id == id)

{

std: cout<<<" [0/½/¾] «;

return id;

}

}

}

void toguess: setQuestion (int id, int q) // корректируем текущую базу в соответсвии с овтетом на вопрос

{

if (q==1)

{

// У всех вариантов ответа, у которых есть даннный вопрос, повышаем вероятность

int k = 0; int ii=0;

for (int i=0; i

{

if (findInVector (Tresponses [i]. idQuest, id))

{

k++;

ii=i;

Tresponses [i]. probability*=4;

for (int j=0; j

{

if (Tresponses [i]. idQuest [j] ==id) Tresponses [i]. idQuest [j] =-1;

}

}

else

{

// если вопроса нет, понижаем вероятность

Tresponses [i]. probability/=1.5;

}

}

if (k==1) Tresponses [ii]. probability+=0.2; // если персонаж с даным ответом тоько один, то его вероятность резко повышается

// сортируем все ответы в соответствии их вероятности

for (int i = Tresponses. size () — 1; i > 0; i—)

{

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

{

if (Tresponses [j]. probability > Tresponses [j + 1]. probability)

swap (Tresponses [j], Tresponses [j + 1]);

}

}

donequest. push_back (id);

}

else if (! q)

{ // ЕСЛИ ОТВЕТ ЛОЖЬ

// У всех вариантов ответа, у которых есть даннный вопрос, понижаем вероятность

for (int i=0; i

{

if (findInVector (Tresponses [i]. idQuest, id))

{

Tresponses [i]. probability/=4;

// if (Tresponses [i]. probability<0) {Tresponses [i]. probability*=0.001; Tresponses [i]. probability=abs (Tresponses [i]. probability); }

for (int j=0; j

{

if (Tresponses [i]. idQuest [j] ==id) Tresponses [i]. idQuest [j] =-1;

}

}

else

{

// а у кого нет, повышаем

Tresponses [i]. probability+=0.05;

}

}

// сортируем все ответы в соответствии их вероятности

for (int i = Tresponses. size () — 1; i > 0; i—)

{

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

{

if (Tresponses [j]. probability > Tresponses [j + 1]. probability)

swap (Tresponses [j], Tresponses [j + 1]);

}

}

}

else if (q==3)

{ // Ответ Скорее да

int k = 0; int ii=0;

for (int i=0; i

{

if (findInVector (Tresponses [i]. idQuest, id))

{

k++;

ii=i;

Tresponses [i]. probability*=3;

for (int j=0; j

{

if (Tresponses [i]. idQuest [j] ==id) Tresponses [i]. idQuest [j] =-1;

}

}

else

{

// если вопроса нет, понижаем вероятность

Tresponses [i]. probability-=0.01;

}

}

if (k==1) Tresponses [ii]. probability+=0.15; // если персонаж с даным ответом тоько один, то его вероятность резко повышается

// сортируем все ответы в соответствии их вероятности

for (int i = Tresponses. size () — 1; i > 0; i—)

{

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

{

if (Tresponses [j]. probability > Tresponses [j + 1]. probability)

swap (Tresponses [j], Tresponses [j + 1]);

}

}

donequest. push_back (id);

}

else if (q==4)

{

for (int i=0; i

{

if (findInVector (Tresponses [i]. idQuest, id))

{

Tresponses [i]. probability-=0.15;

if (Tresponses [i]. probability<0) { Tresponses [i]. probability*=0.001; Tresponses [i]. probability=abs (Tresponses [i]. probability); }

for (int j=0; j

{

if (Tresponses [i]. idQuest [j] ==id) Tresponses [i]. idQuest [j] =-1;

}

}

else

{

// а у кого нет, повышаем

Tresponses [i]. probability+=0.045;

}

}

// сортируем все ответы в соответствии их вероятности

for (int i = Tresponses. size () — 1; i > 0; i—)

{

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

{

if (Tresponses [j]. probability > Tresponses [j + 1]. probability)

swap (Tresponses [j], Tresponses [j + 1]);

}

}

}

}

bool toguess: findInVector (std: vector v, int id)

{

for (int i=0; i

{

if (v [i] ==id) return true;

}

return false;

}

bool toguess: findInVector (std: vector v, int id)

{

for (int i=0; i

{

if (v [i]. id==id) return true;

}

return false;

}

int toguess: getResponse (int id)

{

// попытка получить ответ

// Ответ есть, если разница между вероятностью двух, на данный

// момент самых подходящих, ответов больше какой-то константы

if (Tresponses [Tresponses. size () — 1]. probability-Tresponses [Tresponses. size () — 2]. probability >= 0.05 || id<0)

{ // ответ есть

return Tresponses. size () — 1;

}

else return 0;

}

char* toguess: getfResponse (int id)

{

return Tresponses [id]. response;

}

void toguess: setResponse (int id, bool flag)

{

// if (flag)

// responses [id]. probability+=0.001;

}

void toguess: newResponse (char* response)

{

for (int i=0; i

{

if (strcmp (responses [i]. response, response) ==0) return;

}

// Добавление новго ответа в базу;

s_response thisResponse;

thisResponse. idQuest = donequest;

thisResponse. probability = 0.001;

thisResponse. response = response;

responses. push_back (thisResponse);

}

void toguess: save ()

{ // деструктор

// сохранение базы

FILE* file=fopen («responses. txt» ," w");

if (! file)

{

cout<<" Error!" <

return;

}

for (int i=0; i

{

fprintf (file," %s /%i «, responses [i]. response, responses [i]. idQuest. size ());

for (int j=0; j

fprintf (file," %f/ n", responses [i]. probability);

}

fclose (file);

ofstream file1 («questions. txt»);

if (file1. fail ())

{

cout<<" Error!" <

return;

}

for (int i=0; i

{

file1<<" /" <<<" /" <<<" «<

}

}

void toguess: newQuestion (char* q)

{

// новый вопрос

cout<< «Введите вопрос, который позволит отличить «<<» от «<<

char _newQ [2024];

cin>>_newQ;

char* newQ=new char [strlen (_newQ)];

strcpy (newQ,_newQ);

s_question thisQuestion;

thisQuestion. id = maxid (questions) +1;

thisQuestion. question = newQ;

for (int i=0; i

{

if (strcmp (responses [i]. response, q) ==0)

{

responses [i]. idQuest. push_back (thisQuestion. id);

}

}

questions. push_back (thisQuestion);

}

int toguess: maxid (vector _questions)

{

int max=0;

for (int i=0; i<_questions. size (); i++)

{

if (_questions [i]. id>max) max=_questions [i]. id;

}

return max;

}

void toguess: dellQuestion (int id)

{

// удаление вопроса

for (int i=0; i

{

if (findInVector (Tresponses [i]. idQuest, id))

{

for (int j=0; j

{

if (Tresponses [i]. idQuest [j] ==id) Tresponses [i]. idQuest [j] =-1;

}

}

}

}

char* toguess: addspaces (char* str1)

{

char* str=new char [strlen (str1)];

strcpy (str, str1);

// добавление пробелов

for (int i=0; i

{

if (str [i] =='_') str [i] =' ';

}

return str;

}

char* toguess: toniceview (char* str1)

{

// перевод str в номарлный вид (удаление _ и перевод из транслита)

int i=0;

char* str = new char [strlen (str1) +1];

while (i

{

switch (str1 [i])

{

case 'A': str [i] ='a'; break;

case 'B': str [i] ='b'; break;

case 'C': str [i] ='c'; break;

case 'D': str [i] ='d'; break;

case 'F': str [i] ='f'; break;

case 'E': str [i] ='e'; break;

case 'G': str [i] ='g'; break;

case 'H': str [i] ='h'; break;

case 'I': str [i] ='i'; break;

case 'J': str [i] ='j'; break;

case 'K': str [i] ='k'; break;

case 'L': str [i] ='l'; break;

case 'M': str [i] ='m'; break;

case 'N': str [i] ='n'; break;

case 'O': str [i] ='o'; break;

case 'P': str [i] ='p'; break;

case 'Q': str [i] ='q'; break;

case 'R': str [i] ='r'; break;

case 'S': str [i] ='s'; break;

case 'T': str [i] ='t'; break;

case 'U': str [i] ='u'; break;

case 'V': str [i] ='v'; break;

case 'W': str [i] ='w'; break;

case 'X': str [i] ='x'; break;

case 'Y': str [i] ='y'; break;

case 'Z': str [i] ='z'; break;

default: str [i] =str1 [i];

}

i++;

}

str [strlen (str1)] ='';

vector temp;

i=0;

while (i

{

switch (str [i])

{

case 'a': temp. push_back ('а'); break;

case 'b': temp. push_back ('б'); break;

case 'c':

if (str [i+1] =='h') {temp. push_back ('ч'); i++; }

else temp. push_back ('с'); break;

case 'd': temp. push_back ('д'); break;

case 'f': temp. push_back ('ф'); break;

case 'e': temp. push_back ('е'); break;

case 'g': temp. push_back ('г'); break;

case 'h': temp. push_back ('х'); break;

case 'i': temp. push_back ('и'); break;

case 'j':

if (str [i+1] =='a') {temp. push_back ('я'); i++; }

else temp. push_back ('й'); break;

case 'k': temp. push_back ('к'); break;

case 'l': temp. push_back ('л'); break;

case 'm': temp. push_back ('м'); break;

case 'n': temp. push_back ('н'); break;

case 'o': temp. push_back ('о'); break;

case 'p':

if (str [i+1] =='h') {temp. push_back ('ф'); i++; }

else temp. push_back ('п'); break;

case 'q': temp. push_back ('б'); break;

case 'r': temp. push_back ('р'); break;

case 's':

if (str [i+1] =='h') {temp. push_back ('ш'); i++; }

else temp. push_back ('с'); break;

case 't': temp. push_back ('т'); break;

case 'u': temp. push_back ('у'); break;

case 'v': temp. push_back ('в'); break;

case 'w': temp. push_back ('р'); break;

case 'x': break;

case 'y': temp. push_back ('у'); break;

case 'z':

if (str [i+1] =='h') {temp. push_back ('ж'); i++; }

else temp. push_back ('з'); break;

case '_': temp. push_back (' '); break;

case ''': temp. push_back ('ь'); break;

default: temp. push_back (str [i]);

}

i++;

}

char *returnStr = new char [temp. size () +1];

for (int i=0; i

{

returnStr [i] =temp [i];

}

// returnStr [temp. size ()] ='? ';

returnStr [temp. size ()] ='';

returnStr =toupper (returnStr [0]);

if (temp. size () >8)

return addspaces (returnStr);

else return addspaces (str1);

}

bool toguess: havequestions ()

{

for (int i=0; i

{

for (int j=0; j

{

if (Tresponses [i]. idQuest [j]! ='-1') return true;

}

}

return false;

}

int toguess: populatQuestion ()

{

int maxCount = 0;

int mid = 0;

for (int _id=1; _id<=questions [questions. size () — 1]. id; _id++) // для каждого вопроса

{

int thisCount=0;

for (int i=0; i

{

for (int j=0; j

{

if (Tresponses [i]. idQuest [j] ==_id) thisCount++;

if (thisCount>maxCount)

{

maxCount=thisCount;

mid = _id;

}

}

}

}

return mid;

}

1. Герберт Шилдт «Самоучитель C++» БХВ-Петербург, 2003 г. 687 стр.

2. MSDN

3. С. Окулов «Программирование в алгоритмах». Бином, 2007г

4. Б. Страуструп «Язык программирования С++»

5. Р. Лафоре «ООП в С++»

6. Д. Либерти, Б. Джонс «C++ за 21 день» Вильямс

7. Разработка приложений на MS Visual Studio. Учебный курс. (Официальное пособие Microsoft).

8. В. М. Виртас «Методы решения задач по информатике» Бином, 2007г