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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Модификация эталонного проекта «Выпуклая оболочка»

Информация:

Тип работы: курсовая работа. Добавлен: 30.05.2012. Сдан: 2010. Страниц: 17. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Федеральное агентство
по образованию 
 

Государственное образовательное  учреждение
Московский  государственный  индустриальный университет
(ГОУ  МГИУ) 

Кафедра информационных технологий и систем в экономике и управлении 
 
 
 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
курсовой  работы  
 

Тема: Модификация эталонного проекта «Выпуклая оболочка» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                              Студент jjgfb ghd
                                              Группа 2291
                                              Преподаватель Носова Т.К. 
 
 
 
 
 

Москва 2010 

АННОТАЦИЯ
      В данной курсовой работе требуется  модифицировать текст эталонного  проекта «Выпуклая оболочка» таким образом, чтобы индуктивно определить, количество рёбер выпуклой оболочки, параллельных оси ординат. Программа написана на языке C++. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СОДЕРЖАНИЕ 

Введение.......................................................................................................................................................4
    Теоретическая часть
      Описание Выпуклой оболочки......................................................................................................5
      Описание алгоритма программы...................................................................................................6
    Проектная часть.....................................................................................................................................7
      Описание структуры программы..................................................................................................7
      Описание класса R2Point...............................................................................................................7
        Назначение............................................................................................................................7
        Описание данных..................................................................................................................7
        Описание методов................................................................................................................7
          Описание конструктора R2Point()................................................................................7
          Описание метода dist.....................................................................................................7
          Описание метода area....................................................................................................7
          Описание метода equal..................................................................................................8
          Описание метода isTriangle...........................................................................................8
          Описание метода inside.................................................................................................8
          Описание метода light...................................................................................................8
          Описание метода test.....................................................................................................8
      Описание класса Deq......................................................................................................................8
        Назначение............................................................................................................................8
        Описание данных..................................................................................................................8
        Свойства Deq........................................................................................................................9
        Описание методов класса Deq.............................................................................................9
      Описание класса Figure..................................................................................................................9
        Назначение............................................................................................................................9
        Описание методов................................................................................................................9
      Описание класса Polygon.............................................................................................................10
        Описание данных..................................................................................................................10
        Описание методов................................................................................................................10
          Описание конструктора Polygon ().............................................................................10
          Описание метода add...................................................................................................10
          Описание метода grow.................................................................................................10
          Описание метода count................................................................................................11
      Описание класса Segment.............................................................................................................11
        Назначение..........................................................................................................................11
        Описание данных................................................................................................................11
        Описание методов..............................................................................................................11
          Описание метода add...................................................................................................11
          Описание метода count................................................................................................11
      Описание класса Point..................................................................................................................12
        Назначение..........................................................................................................................12
      Описание класса Void...................................................................................................................12
        Назначение..........................................................................................................................12
      Описание класса Convex..............................................................................................................12
        Назначение..........................................................................................................................12
        Описание данных................................................................................................................12
      Описание функции main....................................................................................................12
    Испытательная программа..................................................................................................................14
Заключение.................................................................................................................................................16
Список  литературы....................................................................................................................................17
Приложение 1. Примеры работы программы…………………………………………………………..18
Приложение 1. Текст программы………….…………………………………………………………….20 

 

ВВЕДЕНИЕ
    Цель  данной курсовой работы - модифицировать текст эталонного проекта «Выпуклая оболочка», для индуктивного определения количества ребер выпуклой оболочки, параллельных оси ординат. Для этого понадобится добавить несколько методов, помогающих сделать этот расчет. Программа написана на языке С++. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 

1.1. Описание Выпуклой оболочки 

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







 

Рис.1.1 Выпуклая оболочка точек плоскости  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

      Проверка  условия выполняется с помощью метода test. Этот метод проверяет, параллельно ли ребро оси ординат. Если условие выполняется, то возвращается единица, в противном случае – ноль. На рис.2 отрезок аb (рис.2) параллелен оси ординат, test возвращает единицу. Отрезок ae не параллелен оси ординат, следовательно, test возвращает ноль, и т.д. Проверив все точки на рис.2, найдем одно ребро, удовлетворяющие условию.
 
Рис. 1.2. Выпуклая оболочка с ребром, параллельным оси ординат 
 
 
 
 
 
 
 
 
 
 
 

2. ПРОЕКТНАЯ ЧАСТЬ
2.1. Описание структуры проекта
      В данном проекте используется метод  проектирования сверху вниз.
2.2. Описание класса R2Point
2.2.1. Назначение
      Класс R2Point хранит данные о координатах точки на плоскости и методы, работающие с этой точкой на плоскости.
2.2.2. Описание данных
      Данными класса являются координаты точки на плоскости.
2.2.3.Описание методов
          Описание конструкторов
      Класс R2Point содержит 2 конструктора. В конструкторе без параметров координаты точки обнуляются. Конструктор с параметром через заголовок записывает новые координаты точки.
          Описание метода dist
      Этот  метод предназначен для вычисления расстояния между двумя точками по формуле
sqrt((a.x-b.x) +(a.y-b.y)), где а.х - абсцисса точки а, b.х - абсцисса точки b, а.у -ордината точки а, b.у - ордината точки b. 
 
 
 

Рис. 2.2.3.2 Нахождение расстояния между двумя точками
2.2.3.3.    Описание метода area
      Этот  метод предназначен для вычисления площади треугольника по трем точкам через формулу S =1/2((а.х - с.х) * (b.у - с.у) - (а.у - с.у) * (b.х - с.х)). Площадь может быть как положительной, так и отрицательной, зависит от порядка вершин. 
 
 
 
 

Рис 2.2.3.3 Нахождение площади треугольника по трем точкам
2.2.3.4.    Описание метода equal
    Сравнивает  точки, чтобы не было совпадений по координатам (совпадающих точек).
2.2.3.5.    Описание метода isTriangle
    Определяет, лежат ли три точки на одной  прямой. 
 
 
 
 

    Рис. 2.2.3.5 (а)(лежат)            Метод isTrianglе           Рис. 2.2.3.5 (б)(не лежат)
          Описание метода inside
    Определяет, не находится ли некоторая точка  на прямой между двумя другими. 
 
 
 

Рис. 2.2.3.6 Метод inside
            Описание метода light
    Определяет, освещено ли ребро выпуклой оболочки из заданной точки. Если точка освещает хотя бы одно ребро, значит она снаружи.
            Описание метода test
    Проверяет, параллельно ли ребро оси ординат.(см. рис.1.2.) 

2.3.     Описание класса Deq
2.3.1.  Назначение
    Класс Deq служит для хранения вершин выпуклой оболочки, а также хранит данные и
методы, работающие с методом Deq. Deq представляет собой непрерывную реализацию дека объектов типа R2Point. Deg имеет head (голову) и tail (хвост).

2.3.2.  Описание данных

 
      Данными класса Deq является одномерный массив длинной в 16 элементов. Данными является адрес головы, хвоста, размер Deq.
    Array - массив, хранящий в себе вершины оболочки
    Size - переменная для хранения количества элементов в Deq
    Head – номер элемента головы
    Tail - номер элемента хвоста 
 
 
 

    Рис. 2.3.2 Класс Deq 
 

2.3.3. Свойства Deq
    Deq - обладает следующими свойствами:
    Читать и записывать можно только в хвост и голову
    Средние элементы Deq недоступны
    При записи элемента, он присоединяется к Deq
    При чтении первого элемента, этот элемент исчезает из Deq
    При чтении элемента из головы, головным становится следующий элемент
    При чтении из хвоста, хвостом становится предыдущий элемент
2.3.4. Описание методов класса Deq
    Forward- используется для чтения из головы
    Backward - используется для чтения из хвоста
    PushFront – используется для записи нового элемента в голову
    PushBack – используется для записи нового элемента в хвост
    PopFront – используется для чтения с удалением из головы
    РорВаск – используется для чтения с удалением из хвоста
    Front – используется для просмотра того, что в голове
    Back – используется для просмотра того, что в хвосте
 
2.4. Описание класса Figure
2.4.1. Назначение 

      Класс Figure содержит общие для выпуклой оболочки методы, которые должны быть виртуальными - add, perimeter, area и count; его наследниками являются классы Void, Point, Segment, Polygon. 

2.4.2.  Описание методов 

    Метод area предназначен для вычисления площади.
    Метод perimeter предназначен для вычисления периметра.
    Метод add предназначен для добавления новой вершины в оболочку.
    Метод count предназначен для возвращения количества ребер выпуклой оболочки, параллельных оси ординат.
 
2.5. Описание класса Polygon
2.5.1. Описание данных
    Данными в этом классе являются  S – площадь фигуры , P – периметр фигуры , k - счетчик рёбер, параллельных оси ординат.
2.5.2. Описание методов
2.5.2.1. Описание конструктора Polygon()
      Конструктор Polygon заносит в Deq три вершины оболочки. Он создает треугольник и вычисляет периметр и площадь получившейся фигуры. 

2.5.2.2 Описание метода add
      Этот  метод предназначен для добавления новых вершин в Deq. Но при добавлении новой точки возможны два случая:
    Если в многоугольнике освещённых рёбер нет, то это означает, что новая точка попала внутрь или на границу старой выпуклой оболочки, и делать ничего не надо.
    Если же освещённые ребра есть, то их надо удалить и соединить ребра с новой точкой. При реализации метода add (только в том случае, если есть освещенные ребра) выполняется следующие действия:
    удаляют ребра, попавшие внутрь оболочки
    уменьшается периметр оболочки на длину удаленных ребер
    увеличивается площадь оболочки на величину, равную площади треугольника, образованного удаляемым ребром и добавляемой точкой
    к оболочке добавляется два новых ребра, а к её периметру сумма их длин.
 
      2.5.2.3 Описание метода grow
      Предназначен  для пересчета периметра и  площади, который необходимо производить  после удаления каждого ребра. В него передаются координаты удаляемых рёбер и координаты новой точки. После этого начинается корректировка площади, периметра и счётчика k, считающего количество ребер, параллельных оси ординат. Допустим, имеется выпуклая оболочка (рис.2.5.2.3(а)). Введем точку t (рис.2.5.2.3(б)). Точка t освещает ребра ае и ed. Метод grow вычтет из счетчика k удаляемые ребра, удовлетворяющие условию, вычтет длину данных ребер из периметра выпуклой оболочки, прибавит площадь треугольника aet и aed к площади выпуклой оболочки и удалит из программы точку е, записав на ее место точку t. Далее прибавит к площади выпуклой оболочки площадь треугольника atd , к периметру прибавит длины ребер at и td, прибавит к счетчику k добавленные ребра, удовлетворяющие условию. 
 
 
 
 
 
 
 
 
 

    Рис.2.5.2.3(а) Предыдущее состояние выпуклой оболочки   Рис.2.5.2.3(б)Следующее состояние 
 

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

2.6. Описание класса Segment 

2.6.1.  Назначение 

          Класс Segment - класс «двуугольник». Он предназначен для работы с двуугольником. В
данном классе также содержится метод count, который увеличивает счетчик k на единицу при
условии, что данный отрезок, будет параллелен оси ординат. 

2.6.2.  Данные
    Данными класса Segment являются 2 точки типа R2Point.
2.6.3.  Описание методов
      2.6.3.1.  Описание метода add
      Метод add предназначен для добавления новой вершины в оболочку. Если
      площадь для трех точек положительна, то add возвращает указатель на Polygon.
      2.6.3.2. Описание метода count
      Метод count предназначен для возвращения количества ребер выпуклой 
оболочки, параллельных оси ординат.

2.7. Описание класса Point
2.7.1.  Назначение
      Класс Point - класс «одноугольник». Данные класса – координаты одной точки. Периметр и площадь здесь являются нулевыми. Метод area возвращает 0, потому что у точки нет площади. Метод add передает управление классу Segment, если новая точка образует отрезок. Также после добавления новой точки управление может остаться у класса Point (в случае совпадения точки с имеющейся), для этого используют метод equal. Здесь метод count также возвращает ноль, так как в данном классе присутствует лишь одна точка .
2.8.  Описание класса Void
2.7.1.  Назначение
      Класс Void -класс «нульугольник». Методы perimeter, area и count здесь возвращают нулевые значения, так как пары чисел для проверки area в этом массиве нет. . Возвращаемым значением метода add является объект Point. 

2.9. Описание класса Convex 

2.9.1.  Назначение
           Этот класс предназначен для связи главной функции с промежуточными классами
2.9.2.Описание  данных
      Данными класса является указатель на различные  классы
2.10. Описание функции main 

      В функции main происходит ввод координат точки и вывод площади, периметра и количества ребер, параллельных оси ординат. Главная функция зациклена оператором while. Выход из программы осуществляется путем ввода координат точки (-100;-100) или Ctrl+C.
      На  рисунке 2.10 изображена блок-схема главной функции.
      Блок 1 - начало
      Блок 2 - ввод вершин оболочки
    Блок 3 - проверка условия. Если хотя бы одна из координат точки равна -100, тогда осуществляется выход из программы, в противном случае программа выполняется
      Блок 4 - вывод параметров оболочки на экран
      Блок 5 - конец программы. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


Рис. 2.10 Блок-схема 
 
 
 
 
 
 
 
 
 
 

3.ИСПЫТАТЕЛЬНАЯ ПРОГРАММА 

     В табл.1 приведены примеры ручного  и машинного счёта, по которым  проверяется правильность работы программы. 

      Таблица 1                

Номер испытания Координаты  точек Ручной  счёт Машинный  счёт
x y P S Кол. P S Кол.
1 0 0 0 0 0 0 0 0
0 1 2 0 1 2 0 1
0 2 4 0 1 4 0 1
2 1 0 0 0 0 0 0 0
1 4 8 0 1 8 0 1
5 4 13,6 8 1 13,6569 8 1
3 4 5 0 0 0 0 0 0
4 0 10 0 1 10 0 1
9 4 16,5 12,5 1 16,5021 12,5 1
 
 
 
На рис.3.1-3.3 получено графическое представление данной проверки. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

                                  
  

ЗАКЛЮЧЕНИЕ 

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

СПИСОК  ЛИТЕРАТУРЫ
1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦМНО, 2000.
2. Подбельский В.В. /Язык С++ / – М.: МГИЭМ, 2008. 
3. Роганов Е.А. /Основы информатики и программирования - М.: МГИУ, 2001. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ПРИЛОЖЕНИЕ 1 

Пример  работы программы 
 

Рис.1 Пример 1 
 
 
 
 
 
 
 


Рис.2 Пример 2

Рис.3 Пример 3
 
 
 
 
 
 
 
 
 
 
 
ПРИЛОЖЕНИЕ 2 

Текст программы 
 

// Pol.cpp : Defines the entry point for the console application.
// 

//#include "stdafx.h"
#include <iostream.h>
#include <math.h> 

//Klass, opisyvauchiy tochku (Point) na ploskosti (R2)
class  R2Point
{
private:
      double x,y; 

public:
      R2Point(double a, double b)
       {
      x=a; y=b;
       };
      R2Point()
       {
       x=0; 
       y=0; 
       };
      double dist(R2Point a, R2Point b)
       {
       return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
       };
      double area(R2Point a, R2Point b, R2Point c)
       {
       double s= 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));
       return (s);
       };
      int equal(R2Point a, R2Point b)
       {
       return (a.x==b.x && a.y==b.y);
       };
      int isTriangle(R2Point a, R2Point b, R2Point c)
       {
       return (area(a, b, c) != 0.0);
       };
            int inside(R2Point a, R2Point b)
       {
       return ((a.x <= x && x <= b.x || a.x >= x && x >= b.x) &&
             (a.y <= y && y <= b.y || a.y >= y && y >= b.y));
       };
            int light(R2Point a, R2Point b)
       {
       double s=area(a, b, *this);
       return (s < 0.0 || (s == 0.0 && ! inside(a, b)));
       };
            int test(R2Point a, R2Point b)
            {
            if (a.x == b.x)
            return(1);
            else return(0);
            }
}; 

//Nepreryvnaya realizaciya deka
class Deq
{    
      //private final static int DEFSIZE = 16;
       R2Point array[16];
      int size, head, tail;
      int forward (int index)
       {
       return (++index <16 ? index : 0);
       };
      int backward (int index)
       {
       return (--index >=0 ? index : 15);
       };
       public: Deq (int razmer)
       {
       size=head=0;
       tail=15;
       };
       public: Deq()
       {
       size=head=0;
       tail=15;
//  this(DEFSIZE);
       };
       public: int length()
       {
       return (size);
       };
       public: void pushFront(R2Point p)
       {
       array[head=backward(head)]=p;
       size +=1;
       };
       public: void pushBack(R2Point p)
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.