Решение головоломок

Размещено на http://www.allbest.ru/

7

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Новокузнецкий филиал-институт Кемеровского государственного университета

Факультет информационных технологий

Кафедра общей и прикладной информатики

КУРСОВАЯ РАБОТА

по курсу: “Языки программирования и методы трансляции”

на тему: “Решение головоломок”

Выполнил:

ст. гр. ПМИ-052

Ляпин М.Э.

Члены комиссии:

Проверил:

ст. преп. Веслов К.Н.

Новокузнецк, 2007

РЕФЕРАТ

Отчет содержит 19 страниц, 10 рисунков, 4 источника, 2 приложения.

ГОЛОВОЛОМКА, АЛГОРИТМ, КОМБИНАЦИЯ, РЕЖИМ, ПЕРЕБОР.

Целью данной курсовой работы является приобретение знаний и практических навыков самостоятельного программирования задач в среде Windows, а также освоение инструментальных средств отладки и методов программирования.

Была разработана программа "Дешифратор". Программа позволяет решать задачи из класса головоломок. При необходимости может быть использована для шифрования отдельных (либо комбинаций в количестве не более трех) слов. Имеет 2 режима работы: «Разные буквы соответствуют обязательно разным цифрам» и «Разные буквы могут обозначать и одинаковые цифры».

ЗАДАНИЕ НА ПРОЕКТИРОВАНИЕ

Составить программу для разгадывания головоломок типа:

В таких головоломках одинаковые буквы обозначают одинаковые цифры, требуется найти эти цифры. Реализовать пользовательский интерфейс для ввода головоломок.

Программа должна иметь следующие возможности:

- два режима: "разные буквы соответствуют обязательно разным цифрам" и "разные буквы могут обозначать и одинаковые цифры";

- * означает любую цифру;

- некоторые цифры могут быть указаны явно.

СОДЕРЖАНИЕ

Введение

1. Основная часть

1.1 Анализ задачи

1.2 Описание алгоритма

1.3 Описание программы

Заключение

Список литературы

Приложение А. Листинг программы

Приложение Б. Контрольные примеры

ВВЕДЕНИЕ

Основная цель данной курсовой работы - обучение. Студент учится формировать постановку задач, составлять алгоритмы их решения и формализовать эти алгоритмы в популярной среде программирования. В ходе написания программы студент осваивает язык C++ и особенности его трансляции в компиляторе Builder.

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

Для достижения этих целей была выбрана задача «Решение головоломок». Уровень сложности этой задачи позволяет ознакомиться с основными этапами написания реальных программ, и приобрести определенные навыки программирования.

Для решения задачи был использован метод математического моделирования на ЭВМ.

ОСНОВНАЯ ЧАСТЬ

Анализ задачи

Данную задачу для решения удобно разбить на несколько подзадач, а именно:

1) отдельно осуществить подготовку данных;

2) отдельно их обработку;

3) отдельно сделать вывод результата.

Подготовка данных состоит в:

- вводе исходных слов;

- определении длин этих слов, формировании строки, склеенной из этих трех слов и нахождении длины этой строки (назовем ее «строка1»);

- формирование на основе полученных значений максимально и минимально возможных чисел - границ перебора;

- перебор всех возможных чисел от нижней границы до верхней и одновременно их передача обрабатывающей функции.

Обработка данных заключается в:

- принятии пары возможных чисел;

- преобразовании этих чисел и их суммы в строки;

- проверке равенства суммарной длины полученных строк длине строки1;

- формирование строки, склеенной из полученных шаг назад строк (назовем ее «строка2»);

- обработке явно введенных цифр (если они есть), а именно - проверке равенства цифр, находящихся на одинаковых позициях в строке 1 и в строке 2.

- обработка условия «разные буквы обязательно соответствуют разным цифрам», если оно включено, т.е. проверка того, что любым двум разным элементам строки 1 всегда соответствуют разные элементы строки 2.

- проверка соответствия одинаковым буквам одинаковых цифр, т.е. проверка того, что любым двум одинаковым элементам строки1 всегда соответствуют одинаковые элементы строки2, т.е. одна буква - одна цифра.

Вывод результатов включает в себя в зависимости от полученного сигнала

- вывод сообщения о готовности программы к дальнейшим действиям и непосредственно вывод полученных результатов

или

- вывод сообщения об ошибке.

Описание алгоритма

Размещено на http://www.allbest.ru/

7

Рисунок 1 - Общая блок-схема программы.

решение алгоритм головоломка программа

Размещено на http://www.allbest.ru/

7

Рисунок 2 - Блок-схема функции подготовки данных.

Размещено на http://www.allbest.ru/

7

Рисунок 3 - Блок-схема функции обеспечения проверок.

Размещено на http://www.allbest.ru/

7

Рисунок 4 - Блок-схема функции вывода данных.

Рисунок 5 - Блок-схема функции вывода сообщения об ошибке.

Описание программы

Принцип работы программы несложен и понятно изложен на блок-схеме. Основной функцией программы является функция Func.

bool __fastcall Func(const int x, int y)

С помощью этой функции осуществляются все необходимые проверки (подробно см. Рисунок 2).

Входными данными являются числа типа int x и y, соответствующие словам s1 и s2.

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

При открытии программы появляется такое окно:



Рисунок 6 - Начало работы.

В верхней части окна пользователь может выбрать один из режимов: «Разные буквы соответствуют обязательно разным цифрам» и «Разные буквы могут обозначать и одинаковые буквы.

Рисунок 7 - Вид после окончания расчета.

Затем в нижней части окна под названием "Исходные данные" необходимо ввести нужные слова, после чего нажать кнопку справа "ОК". После того, как расчет будет окончен, в нижней части окна, в поле данных, в котором по умолчанию высвечивается фраза “Возможные варианты”, появятся соответствующие числа (см. рис. 7).

Если окажется, что такой комбинации цифр не существует, то вместо чисел появятся сообщения об ошибке (см. Рисунок Б.3).

ЗАКЛЮЧЕНИЕ

В результате выполнения курсовой работы были получены навыки составления алгоритма для поставленной задачи и воплощения этого алгоритма в текст программы, написанной на языке C++ в среде Builder. А также было разработано программное средство, успешно решающее поставленную задачу, т.е. была написана программа, работающая в двух режимах, позволяющая разгадывать головоломки.

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

При желании, возможно, расширить класс таких задач путём добавления режимов, при которых слова будут не складываться, а умножаться и т.п.

СПИСОК ЛИТЕРАТУРЫ

1. Страуструп Б. Язык программирования С++. / Б.Страуструп. - Киев: ДиаСофт, 1993. - 540c.

2. Павловская Е.А. Программирование на языке высокого уровня / Павловская Е.А.. - Минск: Питер, 2005. - 460с.

3. Гради Б. Объектно-ориентированный анализ и проектирование с примерами приложений на С ++ / Б. Гради, пер. с англ. М.: Бином, 1998. - 340 c.

4. Клетков Ю. Практика программирования: С++. / Клетков Ю. - Санкт-Петербург: БХВ-Петербург, 2002. - 449с.

ПРИЛОЖЕНИЕ А

Листинг программы.

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

#include <math.h>

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

int L,x,y;

AnsiString s,r;

bool raz;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

bool __fastcall Func(const int x,int y)

{int i,j;

AnsiString a,b,c,p;

a=IntToStr(x);

b=IntToStr(y);

c=IntToStr(x+y);

if (a.Length()+b.Length()+c.Length()!=L) return false;

p=a+b+c; // p - строка, состоящая из чисел x,y,z

//обработка явно введенных цифр

for(i=1;i<=p.Length();i++)

if(((s[i]=='0')||(s[i]=='1')||(s[i]=='2')||(s[i]=='3')||(s[i]=='4')

||(s[i]=='5')||(s[i]=='6')||(s[i]=='7')||(s[i]=='8')||(s[i]=='9'))

&& (p[i]!=s[i]))

return false;

//обработка условия: разные буквы обязательно соответствуют разным цифрам

if(raz)

for(i=1;i<=L;i++)

for(j=i;j<=L;j++)

if((s[i]!=s[j])&&(p[i]==p[j])) return false;

//проверка соответствия одинаковым буквам одинаковых цифр

for(i=1;i<=L;i++)

for(j=i;j<=L;j++)

if((s[i]==s[j])&&(p[i]!=p[j])) return false;

return true;

}

//---------------------------------------------------------------------------

void __fastcall FunWrite(int x,int y)

{

Form1->ComboBox1->Text="Готово";

Form1->ComboBox1->Items->Add(IntToStr(x)+" + "+IntToStr(y)+" = "+

IntToStr(x+y));

}

//---------------------------------------------------------------------------

void __fastcall FunError()

{

Form1->ComboBox1->Text="Ошибка";

Form1->ComboBox1->Items->Clear();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{

bool usl=false;

AnsiString s1,s2,s3;

int L1,L2,L3,max1,min1,max2,min2,min3;

Form1->ComboBox1->Text="Подождите";

Form1->ComboBox1->Items->Clear();

if(RadioGroup1->ItemIndex==0) raz=true;

else raz=false;

s1=Edit1->Text;

s2=Edit2->Text;

s3=Edit3->Text;

s=s1+s2+s3; //s - строка, склеенная из введенных слов

L1=s1.Length();

L2=s2.Length();

L3=s3.Length();

L=L1+L2+L3; //L - длина всех слов в сумме

//определение максимально и минимально возможных чисел

max1=pow(10,L1)-1; min1=pow(10,L1-1);

max2=pow(10,L2)-1; min2=pow(10,L2-1);

min3=pow(10,L3-1);

//перебор возможных чисел

for(x=min1;x<=max1;x++)

for(y=min2;y<=max2;y++)

if(x+y>min3)

if(Func(x,y))

{ FunWrite(x,y);

usl=true;

}

if(!usl)

FunError();

}

//---------------------------------------------------------------------------

ПРИЛОЖЕНИЕ Б

Контрольные примеры

1) Выбран режим "Разные буквы обязательно соответствуют разным цифрам"

Рисунок Б.1 - Работа программы в первом режиме.

2) Выбран режим "Разные буквы могут обозначать и одинаковые цифры"

Рисунок Б.2 - Работа программы во втором режиме.

3) В случае если комбинации чисел, удовлетворяющей всем условиям задачи, не существует, появится сообщение об ошибке.

Рисунок Б.3 - Случай, когда комбинации чисел не существует.

Размещено на Allbest.ru