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

Московский государственный университет экономики, статистики и информатики

Институт Компьютерных Технологий

Кафедра Математического обеспечения информационных систем и инноватики (МОИСиИ)

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

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

на тему

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

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

Наразин И.В.

ДКО-10161

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

Москва, 2012 г.

Содержание

Задание

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

Исходный код

Литература

Задание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основной алгоритм заключен в класс 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); - добавляет в базу новый вопросdellQuestion (int id); - удаляет вопрос из векторов ответов персонажей.

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

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

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

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

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

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

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

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

Исходный код

Класс toguess

Toguess. h

#include <vector>toguess

{: s_question // структура вопросов

{

char* question;

int id;

};

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

{

char* response;

std:: vector <int> idQuest;

double probability;

};

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

std:: vector <s_question> questions;:: vector <s_response> responses;

std:: vector <s_question> Tquestions;:: vector <s_response> Tresponses;step;findInVector (std:: vector <int> v, int id);findInVector (std:: vector <s_question> v, int id);maxid (std:: vector <s_question> _questions);* addspaces (char* str);* toniceview (char* str);havequestions ();populatQuestion ();:();save ();newgame ();getQuestion ();setQuestion (int id, int q);getResponse (int id=0);* getfResponse (int id);setResponse (int id, bool flag);newResponse (char* response);newQuestion (char* q);dellQuestion (int id);

};. cpp

#include "StdAfx. h"

#include <vector>

#include "toguess. h"

#include <iostream>

#include <algorithm>

#include <fstream>namespace std;:: toguess ()

{ // конструктор* db_q_filename = "questions. txt";* db_r_filename = "responses. txt";

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

// База вопросов*file = fopen (db_q_filename,"r");(! file)

{;

}(! feof (file)) {word [1025];id;(file,"/%s /%i ",&word,&id);*question = new char [strlen (word)];(question,word);

// toniceview (question);_question _Q;

_Q. id = id;

_Q. question = question;. push_back (_Q);

}(file);

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

file = fopen (db_r_filename,"r");(! file)

{;

}(! feof (file)) {resp [1025];countq;pro;(file,"%s /%i",&resp,&countq);*response= new char [strlen (resp)];(response,resp);<int> quests;(int i=1; i<=countq; i++)

{temp;(file, "%i ",&temp);. push_back (temp);

}(file, "%f/ ",&pro);_response thisResponse;. idQuest = quests;. probability = pro;. response = response;. push_back (thisResponse);

}(file);

}toguess:: newgame () {

// Старт новой игры. clear ();. clear ();. clear ();= responses;= questions;(int i=0; i<Tresponses. size (); i++)

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

}= 0;

}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)

{(Tresponses [Tresponses. size () - 1]. idQuest. size () ==0)

{(Tresponses [Tresponses. size () - 2]. idQuest. size ()! =0)

{

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

}

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

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

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

{[Tresponses. size () - 1]. probability/=1.5;[Tresponses. size () - 2]. probability/=1.5;(int i = Tresponses. size () - 1; i > 0; i--)

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

{(Tresponses [j]. probability > Tresponses [j + 1]. probability)(Tresponses [j], Tresponses [j + 1]);

}

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

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

}

}

else

{

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

}

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

{= populatQuestion ();

}++;(int i=0; i<Tquestions. size (); i++)

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

{:: cout<<toniceview (Tquestions [i]. question) <<" [0/1/2/3/4] ";id;

}

}

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

{(q==1)

{

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

int k = 0; int ii=0;(int i=0; i<Tresponses. size (); i++)

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

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

}

}

{

// если вопроса нет, понижаем вероятность[i]. probability/=1.5;

}

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

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

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

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

{(Tresponses [j]. probability > Tresponses [j + 1]. probability)(Tresponses [j], Tresponses [j + 1]);

}

}. push_back (id);

}

else if (! q)

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

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

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

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

{[i]. probability/=4;

// if (Tresponses [i]. probability<0) {Tresponses [i]. probability*=0.001; Tresponses [i]. probability=abs (Tresponses [i]. probability); }(int j=0; j<Tresponses [i]. idQuest. size (); j++)

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

}

}

{

// а у кого нет, повышаем[i]. probability+=0.05;

}

}

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

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

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

{(Tresponses [j]. probability > Tresponses [j + 1]. probability)(Tresponses [j], Tresponses [j + 1]);

}

}

}if (q==3)

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

int k = 0; int ii=0;

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

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

{++;=i;[i]. probability*=3;(int j=0; j<Tresponses [i]. idQuest. size (); j++)

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

}

}

{

// если вопроса нет, понижаем вероятность[i]. probability-=0.01;

}

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

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

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

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

{(Tresponses [j]. probability > Tresponses [j + 1]. probability)(Tresponses [j], Tresponses [j + 1]);

}

}. push_back (id);

}if (q==4)

{(int i=0; i<Tresponses. size (); i++)

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

{[i]. probability-=0.15;(Tresponses [i]. probability<0) { Tresponses [i]. probability*=0.001; Tresponses [i]. probability=abs (Tresponses [i]. probability); }(int j=0; j<Tresponses [i]. idQuest. size (); j++)

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

}

}

{

// а у кого нет, повышаем[i]. probability+=0.045;

}

}

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

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

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

{(Tresponses [j]. probability > Tresponses [j + 1]. probability)(Tresponses [j], Tresponses [j + 1]);

}

}

}toguess:: findInVector (std:: vector <int> v, int id)

{(int i=0; i<v. size (); i++)

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

}false;

}toguess:: findInVector (std:: vector <s_question> v, int id)

{(int i=0; i<v. size (); i++)

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

}false;

}toguess:: getResponse (int id)

{

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

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

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

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

{ // ответ естьTresponses. size () - 1;

}return 0;

}* toguess:: getfResponse (int id)

{Tresponses [id]. response;

}toguess:: setResponse (int id, bool flag)

{

// if (flag)

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

}toguess:: newResponse (char* response)

{(int i=0; i<responses. size (); i++)

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

}

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

s_response thisResponse;. idQuest = donequest;. probability = 0.001;. response = response;. push_back (thisResponse);

}

void toguess:: save ()

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

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

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

{<<"Error!"<<endl;;

}(int i=0; i<responses. size (); i++)

{(file,"%s /%i ",responses [i]. response,responses [i]. idQuest. size ());(int j=0; j<responses [i]. idQuest. size (); j++) fprintf (file,"%i ",responses [i]. idQuest [j]);(file,"%f/ \n",responses [i]. probability);

}(file);file1 ("questions. txt");(file1. fail ())

{<<"Error!"<<endl;;

}(int i=0; i<questions. size (); i++)

{<<"/"<<questions [i]. question<<" /"<<questions [i]. id<<" "<<endl;

}

}toguess:: newQuestion (char* q)

{

// новый вопрос<< "Введите вопрос, который позволит отличить "<<q<<" от "<<Tresponses [Tresponses. size () - 1]. response<<endl;_newQ [2024];>>_newQ;* newQ=new char [strlen (_newQ)];(newQ,_newQ);_question thisQuestion;

thisQuestion. id = maxid (questions) +1;. question = newQ;

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

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

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

}

}. push_back (thisQuestion);

}toguess:: maxid (vector <s_question> _questions)

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

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

}max;

}toguess:: dellQuestion (int id)

{

// удаление вопроса(int i=0; i<Tresponses. size (); i++)

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

{(int j=0; j<Tresponses [i]. idQuest. size (); j++)

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

}

}

}

}* toguess:: addspaces (char* str1)

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

// добавление пробелов(int i=0; i<strlen (str); i++)

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

}str;

}* toguess:: toniceview (char* str1)

{

int i=0;* str = new char [strlen (str1) +1];(i<strlen (str1))

{(str1 [i])

{'A': str [i] ='a'; break;'B': str [i] ='b'; break;'C': str [i] ='c'; break;'D': str [i] ='d'; break;'F': str [i] ='f'; break;'E': str [i] ='e'; break;'G': str [i] ='g'; break;'H': str [i] ='h'; break;'I': str [i] ='i'; break;'J': str [i] ='j'; break;'K': str [i] ='k'; break;

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

case 'M': str [i] ='m'; break;'N': str [i] ='n'; break;'O': str [i] ='o'; break;'P': str [i] ='p'; break;'Q': str [i] ='q'; break;'R': str [i] ='r'; break;'S': str [i] ='s'; break;'T': str [i] ='t'; break;'U': str [i] ='u'; break;'V': str [i] ='v'; break;'W': str [i] ='w'; break;'X': str [i] ='x'; break;'Y': str [i] ='y'; break;'Z': str [i] ='z'; break;

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

}++;

}[strlen (str1)] ='\0';<char> temp;=0;(i<strlen (str))

{(str [i])

{'a': temp. push_back ('а'); break;'b': temp. push_back ('б'); break;'c':(str [i+1] =='h') {temp. push_back ('ч'); i++; }temp. push_back ('с'); break;'d': temp. push_back ('д'); break;'f': temp. push_back ('ф'); break;'e': temp. push_back ('е'); break;'g': temp. push_back ('г'); break;'h': temp. push_back ('х'); break;'i': temp. push_back ('и'); break;'j':(str [i+1] =='a') {temp. push_back ('я'); i++; }temp. push_back ('й'); break;'k': temp. push_back ('к'); break;'l': temp. push_back ('л'); break;'m': temp. push_back ('м'); break;'n': temp. push_back ('н'); break;'o': temp. push_back ('о'); break;'p':(str [i+1] =='h') {temp. push_back ('ф'); i++; }temp. push_back ('п'); break;'q': temp. push_back ('б'); break;'r': temp. push_back ('р'); break;'s':(str [i+1] =='h') {temp. push_back ('ш'); i++; }temp. push_back ('с'); break;'t': temp. push_back ('т'); break;'u': temp. push_back ('у'); break;'v': temp. push_back ('в'); break;'w': temp. push_back ('р'); break;'x': break;'y': temp. push_back ('у'); break;'z':(str [i+1] =='h') {temp. push_back ('ж'); i++; }temp. push_back ('з'); break;'_': temp. push_back (' '); break;'\'': temp. push_back ('ь'); break;: temp. push_back (str [i]);

}++;

}*returnStr = new char [temp. size () +1];(int i=0; i<temp. size (); i++)

{[i] =temp [i];

}

// returnStr [temp. size ()] ='? ';[temp. size ()] ='\0';[0] =toupper (returnStr [0]);(temp. size () >8)addspaces (returnStr);return addspaces (str1);

}toguess:: havequestions ()

{(int i=0; i<Tresponses. size (); i++)

{(int j=0; j<Tresponses [i]. idQuest. size (); j++)

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

}

}false;

}toguess:: populatQuestion ()

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

{thisCount=0;(int i=0; i<Tresponses. size (); i++)

{(int j=0; j<Tresponses [i]. idQuest. size (); j++)

{(Tresponses [i]. idQuest [j] ==_id) thisCount++;(thisCount>maxCount)

{=thisCount;= _id;

}

}

}

}mid;

}

Литература

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

2.       MSDN

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

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

.        Р. Лафоре “ООП в С++”

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

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

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