Министерство образования и науки Российской Федерации

ФГАОУ ВПО «Уральский федеральный университет 
имени первого Президента России Б.Н.Ельцина»
Факультет ускоренного обучения
Кафедра программных средств и систем

Оценка проекта

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

РАЗРАБОТКА ПРОГРАММЫ ДЛЯ РЕШЕНИЯ ЗАДАЧИ 
«Паркет»

КУРСОВАЯ  РАБОТА
по дисциплине «Программирование на языках высокого уровня»

Пояснительная записка
231000 1210 015 ПЗ

Руководитель доц., к.т.н.						С.И. Тимошенко

Студент гр. УОЗ-120202 (651)					А.А. Ушаков

Екатеринбург 2013
ФГАОУ ВПО «Уральский федеральный университет 
имени первого Президента России Б.Н.Ельцина»
Факультет ускоренного обучения
Кафедра программных средств и систем

  УТВЕРЖДАЮ:	
Зав. кафедрой ПСС

_________________
В.И.Суханов
“20” ноября 2012г.

ЗАДАНИЕ
на курсовую работу по дисциплине
«Программирование на языках высокого уровня»

Студент группы					УОЗ-120202с (651)
Специальность					231000 ПИ 
Фамилия, имя, отчество				Ушаков Антон Алексеевич
Руководитель курсовой работы			Тимошенко Сергей Иванович 
Срок проектирования				с 25.01.13 по 20.05.13 

1 Тема курсовой работы: Разработка программы для решения задачи «Паркет».
2 Содержание курсовой работы: Необходимо разработать средствами Java программу со следующими возможностями:
а) требуется определить количество всех возможных способов укладки паркета  для  конкретных  значений  М<20,  N<8.
б) на  месте  ненайденных результатов должен стоять символ «*».
в) при описании программы должны использоваться схема работы системы (ГОСТ 19.701-90);
г) оформление пояснительной записки к курсовой работе должно соответствовать ГОСТ 2.105-90, 7.32-2001 и 7.1-2003;
д) подробное описание задачи должно совпадать с условиями, приведенными на страницах 119-121 книги Окулова С.М. Программирование в алгоритмах 2004. 341 с.
3 Курсовое проектирование закончено ______________________________
4 Оценка проекта _________________________________________________

Руководитель_______________________

Члены комиссии____________________
Содержание

Содержание
Введение
1 Постановка задачи
2 Анализ поставленной задачи
2.1 Основные объекты задачи и их взаимодействие
2.2 Структуры данных
2.3 Алгоритм
2.4 Схема работы системы
3 Описание результатов разработки
Заключение
Список использованных источников
Приложение А  (справочное)
Приложение Б (справочное) Руководство пользователя
Б.1 Минимальные системные требования
Б.2 Установка и удаление программы

Введение
               Целью курсовой работы является разработка программы, позволяющей определить количество всех возможных способов укладки паркета для конкретных значений m20, n8 – «Паркет». Для разработки программы будем использовать язык программирования Java. Пол можно покрыть паркетом различными способами. Для определенности, остановимся на варианте, предложенном Окуловым С.М. (Программирование в алгоритмах). При разработке программы, будем руководствоваться описанием задачи в книге Окулова С.М. «Программирование в алгоритмах». Цель программы состоит в следующем. Комнату размером N*M единиц требуется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений (М<20, N<8, M, N — целые). Пол можно покрыть паркетом различными способами. Все возможные способы укладки приведены на рисунке.

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

1 Постановка задачи
              Требуется определить количество всех возможных способов укладки паркета для конкретных значений М<20, N<8. Результат задачи — таблица, содержащая 20 строк и 8 столбцов. Элементом таблицы является число, являющееся решением задачи для соответствующих N и М. На месте ненайденных результатов должен стоять символ «*». 
             Описание результатов разработки оформить в виде пояснительной записки, в соответствии с ГОСТ 2.105-90, 7.32-2001 и 7.1-2003. При описании программы использовать схемы работы системы (ГОСТ 19.701-90). Подробное описание сути задачи должно соответствовать страницам 119-121 книги «Программирование в алгоритмах» / С.М.Окулов. 2004. – 342 с.

2 Анализ поставленной задачи
2.1 Основные объекты задачи и их взаимодействие
Рассмотрим поставленную задачу. 

Пусть i - длина комнаты (1i8), j - ширина комнаты (1j20). «Разрежем» комнату на части. Разрез проводится по вертикали. Плитки, встречающиеся на пути разреза, обходим справа, т.е. при движении сверху вниз на каждом шаге либо обходим справа выступающую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует 1, отсутствие обхода - 0. На рисунке сечение выделено «жирной» линией, ему соответствует двоичное число 00100011 (35).  Количество различных сечений 2' (пронумеруем их от 0 до 2'-1), где i — длина комнаты.
Каким образом программа будет покрывать плитку? Необходимо воспользоваться одним из методов сокращения перебора. Окулов С.М. в книге «Программирование в алгоритмах» предлагает для решения данной задачи применить метод «Композиция».

2.2 Структуры данных
             Не будем пока учитывать то, что некоторые из сечений не могут быть получены. Обозначим парой (k,j) комнату с фиксированной длиной i, правый край которой не ровный, а представляет собой сечение с номером k. B[k,j] - количество вариантов укладки паркета в такой комнате. Задача в такой постановке сводится к нахождению B[0,j] - количество укладок паркета в комнате размером (i,j) с ровным правым краем.
              Считаем, что B[0,0]=1 при любом i, ибо комната нулевой ширины, нулевого сечения и любой длины укладывается паркетом, при этом не используется ни одной плитки. Кроме этого считаем B[k,0]=0 для всех сечений с номерами k<>0, так как ненулевые сечения при нулевой ширине нельзя реализовать.
2.3 Алгоритм
              Попытаемся найти B[k,j] для фиксированного i. Предположим, что нам известны значения B[l,j-1] для всех сечений с номерами l (0l2i-1). Сечение l считаем совместимым с сечением k, если путем добавления целого числа плиток паркета из первого можно получить второе. Тогда B[k,j]=B[l,j-1], суммирование ведется по всем сечениям l, совместимым с сечением k.
Рассмотрим вопрос о том, что значит совместимое сечение.
Необходимо различать понятия совместимость сечений в целом и совместимость в отдельном разряде. При анализе последнего входными данными являются значения разрядов сечений и информация о предыстории процесса (до текущего разряда) - целое или нецелое количество плиток уложено (значение переменной b). Выходными данными - признак - целое, нецелое количество плиток, требуемых для перевода сечения l в сечение k, или решение о том, что анализ продолжать не следует - сечения несовместимы. В данном случае этапу написания логики предшествует анализ на бумаге. Пример этой работы приведен в таблице. 2.3

l	k	Значе-ние b	Новое значе-
ние b или резуль-
тат	Примечания	
1	0	false	false	До данного разряда уложено целое число плиток. Для перехода от l к k не надо ничего укладывать. Переходим к следующему разряду. 	
1	0	true	несовмести-мы	До этого разряда уложено нецелое число плиток, а на этом «закрываем доступ». Сечения несовместимы.	
0	1	false	false	Укладываем целую плитку, количество уложенных плиток остается целым.	
0	1	true	несовмести-мы	Для перехода к новому сечению в этом разряде необходимо уложить целую плитку. Однако, укладывая её мы «перекрываем» доступ к нецелой плитке, уложенной до этого.	
0	0	false	true	До этого разряда между сечениями было уложено целое число плиток, а на этом можно уложить только полплитки.	
0	0	true	false	Нецелую плитку дополняем до целой.	
1	1	false	несовмести-мы	В этом разряде l лежит целая плитка. Необходимо уложить целую плитку для того, чтобы была 1 в этом разряде сечения k, но сделать этого мы не можем. Аналогично и для случая, когда b=true.	
Таблица. 2.3

             Данный анализ совместимости сечений будет реализован в отдельной функции.
Осталось сделать еще несколько замечаний. Во-первых, если произведение n на m нечетно (размеры комнаты), то количество укладок паркетом такой комнаты равно 0. Во-вторых, при m=1 и четном n ответ равен 1. Еще одно замечание касается точности результата. Для бОльших значений n и m получаются довольно большие числа. Но думаю, использование BigInteger, должно решить этот момент.
Таким образом, у нас в решении в исходном коде будет функция, вычисляющая некоторую степень двойки, функций проверяющая совместимость сечений, основной метод осуществляющий вычисление, и главный метод, в котором выводим результат в консоль.

2.4 Схема работы системы

Начало

IF
k <= 0

RETURN 1

RETURN (long)

Конец

Оформим описанный алгоритм в виде схем работы системы по ГОСТ 19.701-90. 

FALSE

TRUE

Рисунок 2.1 – Схема работы системы (long St2)

Начало

int i;
        long d;
        boolean b, res;
        res = false;
        b = false;

FALSE

FOR
(i = 1; i <= pi; i++)

TRUE

d = St2(i)

IF
((k & d) == 0) //{определяется значение разряда с номером d для сечения k}

res = !b;

RETURN RES;

Конец

Рисунок 2.2 – Схема работы системы (метод Can)

Конец

max = St2(i) - 1;
B[0][0] = BigInteger.ONE;

FOR
(i = 1; i <= 8; i++)

int i, j, k, l;
long max;

Начало

FALSE

TRUE

FOR
(j = 1; j <= 20; j++) {
                //Сечение с номером k
                for (k = 0; k <= max; k++) {
                    //Сечение с номером l
                    for (l = 0; l <= max; l++) //if (Can(k,l,i))

Рисунок 2.3 – Схема работы системы (метод Solve)

Начало

FOR
(int m = 0; m <= 20; m++)

FOR
(int n = 0; n <= 8; n++) 
{A[n][m] = BigInteger.ZERO;}

FALSE

TRUE

FOR
(int m = 0; m <= 20; m++)

FOR
(int n = 0; n <= 255; n++) 
{B[n][m] = BigInteger.ZERO;}

Solve();

FALSE

TRUE

FOR
(int m = 1; m <= 20; m++)

FOR
(int n = 1; n <= 8; n++)

System.out.println();

Конец

FALSE

TRUE

Рисунок 2.4 – Схема работы системы (метод Main)
3 Описание результатов разработки
             При решении вопроса о совместимости сечений следует различать понятия совместимость сечений в целом и мост в отдельном разряде. При анализе последнего входными данными являются значения разрядов сечений и информация о предыстории процесса (до текущего разряда) — целое или нецелое количество плиток уложено. Выходными данными — признак — целое, нецелое количество плиток, требуемых для перевода сечения I в сечение &, или решение о том, что анализ продолжать не следует — сечения несовместимы. Оставим эту часть работы и доведение схемы решения до работающего варианта на самостоятельное выполнение. Еще несколько замечаний. Во-первых, если произведение N на М нечетно(размеры комнаты),то количество укладок паркетом такой комнаты равно 0. Во-вторых, при М=1 и четном N ответ равен 1.   
             В-третьих, результирующая таблица симметрична относительно главной диагонали. В-четвертых, для комнат размером 2*? достаточно просто выводится следующая рекуррентная формула: A[2,t]=A[2,t-l]+A[2,t-2] (ряд Фибоначчи). Эти замечания реализуются на этапе предварительной обработки и приводят к незначительной модификации логики процедуры Solve. Еще одно замечание касается точности результата. Для больших значений N и М необходимо организовать вычисления с использованием «длинной» арифметики (i=8, j=20).

Заключение
В курсовой работе описан процесс разработки через вычисление программы–задачи «Паркет». Исследованы метод «решета» и различные варианты перебора. Результаты всех исследованных алгоритмов перебора в табличной форме приведены в приложении А. Приложение Б включает в себя руководство пользователя, описывающее: исходный код программы, процессы установки, настройки и удаления программы. Окончательная версия программы – консольное Windows приложение для Java платформы. 

Список использованных источников

1 	Окулов С.М. Программирование в алгоритмах [Текст] / С.М.Окулов.2004г. – 341 с.
2 	Ноутон П. JavaTM 2 [Текст] : пер. с англ. / П.Ноутон, Г. Шилдт. – СПб. : БХВ-Петербург, 2005. – 1072 с.
3 	Кичигин В.Н. Оформление курсовых и дипломных проектов [Текст] : методические указания для студентов технических специальностей / В.Н.Кичигин, И.Е.Мясников, С.И.Тимошенко. – Екатеринбург: ГОУ ВПО «УГТУ-УПИ», 2005. – 80 с.
4 	Тимошенко С.И. Порядок выполнения и требования к оформлению курсовой работы по дисциплине «Программирование на языках высокого уровня» [Текст] : методические указания / С.И.Тимошенко. – Екатеринбург: изд. ИПК УГТУ, 2004. – 16 с.

Приложение А 
public class Main {

    //Временная, для вычислений
    static BigInteger[][] B = new BigInteger[256][21];
    //Результирующая таблица
    static BigInteger[][] A = new BigInteger[9][21];

    //Вычисляет k - ю степень 2
    public static long St2(int k) {
        if (k <= 0) {
            return 1;
        } else {
            return (long) Math.pow(2, k);
        }
    }

    //{k,l -номера сечений, pi - количество анализируемых разрядов сечений}
    public static boolean Can(int k, int l, int pi) {
        int i;
        long d;
        boolean b, res;
        res = false;
        b = false;
        for (i = 1; i <= pi; i++) {
            d = St2(i);
            if ((k & d) == 0) //{определяется значение разряда с номером d для сечения k}
            {
                if ((l & d) == 0) {
                    b = !b;
                } else {
                    if (b) {
                        return false;
                    }
                }
            } else if (((l & d) != 0) || b) {
                return false;
            }
        }
        ;
        res = !b;
        return res;
    }

    //Основная логика
    public static void Solve() {
        int i, j, k, l;
        long max;
        //Цикл по значению длины комнаты
        for (i = 1; i <= 8; i++) {
            max = St2(i) - 1;
            B[0][0] = BigInteger.ONE;
            //Цикл по значению ширины комнаты
            for (j = 1; j <= 20; j++) {
                //Сечение с номером k
                for (k = 0; k <= max; k++) {
                    //Сечение с номером l
                    for (l = 0; l <= max; l++) //if (Can(k,l,i))
                    {
                        //Проверка совместимости сечений
                        boolean r = Can(k, l, i);
                        if (r) {
                            B[k][j] = B[k][j].add(B[l][j - 1]);
                        }
                    }
                }
                A[i][j] = B[0][j];
            }
        }
    }

    public static void main(String[] args) {
        //забиваем нулями таблицы
        for (int m = 0; m <= 20; m++) {
            for (int n = 0; n <= 8; n++) {
                A[n][m] = BigInteger.ZERO;
            }
        }
        for (int m = 0; m <= 20; m++) {
            for (int n = 0; n <= 255; n++) {
                B[n][m] = BigInteger.ZERO;
            }
        }
        //производим расчет
        Solve();

        //выводим результаты
        for (int m = 1; m <= 20; m++) {
            for (int n = 1; n <= 8; n++) {

                    if (n * m % 2 != 0) {
                        String val="*";
                        for(int p=0;p<25;p++)
                            val+=" ";
                        System.out.print(val);
                    } else
                    if (m == 1 && n % 2 == 0) {
                        String val="1";
                        for(int p=0;p<25;p++)
                            val+=" ";
                        System.out.print(val);
                    } else {
                        String val=A[n][m].toString();
                        int v=val.length();
                        for(int p=0;p<26-v;p++)
                            val+=" ";
                        System.out.print(val);
                }
            }
            System.out.println();
        }
    }
}
Приложение Б
(справочное)
Руководство пользователя
Б.1 Минимальные системные требования
Для установки и запуска игровой программы «Быки и коровы» необходимо выполнение следующих минимальных требований:
•	операционная система MS Windows (любая версия);
•	установленная виртуальная машина Java (Java 2 Platform, Standard Edition), не ниже пятой версии. Установочные файлы Java можно загрузить с сервера компании Sun, по адресу: http://java.sun.com.
Б.2 Установка и удаление программы
Для установки программы:
а)	Скопируйте папку bc (содержащую файлы программы) в любую директорию Вашей системы (например, в C:\Program Files).
б)	В папке bc, находится ярлык запуска программы. Скопируйте его на рабочий стол.
в)	Щелкните правой кнопкой мыши по скопированному ярлыку «Быки и коровы» и в контекстном меню выберите пункт «Свойства». В открывшемся окне свойств измените значение поля «Рабочая папка:» на название директории, в которую была скопирована программа (например, C:\Program Files). Нажмите кнопку «ОК» 
г)	Для запуска программы используйте созданный ярлык.
а)	Удалите папку bc (из директории, в которую она была установлена).
б)	Удалите с рабочего стола ярлык «Быки и коровы».