рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Философия
- /
- Data Structures and Algorithms in C++
Реферат Курсовая Конспект
Data Structures and Algorithms in C++
Data Structures and Algorithms in C++ - раздел Философия, Unit 1. Transitioning To C++ · 1.1 C++ Introduced...
Unit 1. Transitioning to C++
· 1.1 C++ Introduced
· 1.2 Data Structures and Algorithms in C++
· 1.3 Basic C++ Programming
· 1.4 Memory Management
· 1.5 Mechanisms for Code Reuse and Abstraction
Assessments
· Exercise 1
1.1 C++ Introduced
This module of the course introduces the C++ programming language. An overview of the key features of C++ follows a discussion of its history and development as a programming language. This module also demonstrates compilation and execution of a simple C++ program.
· 1.1.1 C++ Background · 1.1.2 Compiling and Running a C++ Program | ||||||||||||
| 1.1.1 C++ Background. History C++ is a modern object-oriented programming language that supports many of the same features as Java, including classes, inheritance, polymorphism, and exceptions. As you know and will continue to learn, these features are excellent tools for creating and maintaining large software systems. Together they allow the software's design to follow the shape of the problem closely, which reduces the amount of code that needs to be written while at the same time maximizing the readability of the code. C++ isn't an entirely new language. It is based on the C programming language. C was designed to be a small, simple language, which programmers could use to produce very fast code. C++ adds to C many of the Java-like features such as classes and inheritance. In doing so, C++ became a much larger language than C, but one better suited for large-scale projects. Because C++ compilers can compile C programs, C++ gained rapid acceptance in the market. Today, there are literally millions of lines of C++ code in use by a wide variety of software applications. For those interested in the timeline, C was first invented in 1970. The language became an ANSI standard in 1980. The first book about ANSI C was published in 1983. C++, originally called "C with Classes," debuted in 1983. The name C++ was coined in 1983. The first C++ book was published in 1985. The Java programming language, in development for several years, debuted in 1995. The C++ language became an ISO standard in 1998. | 1.1.1 C ++ История и главные особенности. История C++ современный язык объектно-ориентированного программирования, основан на языке программирования C. C был разработан как простой (краткий) язык, чтобы программисты могли использовать его для написания очень маленьких кодов. C ++ добавляет в C многое из Java, как то классы и наследование. При этом C ++ стал намного большим языком чем C и стал пригодным для проектов любого масштаба. Поскольку C++ компиляторы понимают программы в C, C++ получил широкое распространение. Сегодня пользователями C++ являются миллионы людей. Первоначально, в 1970 году был создан язык C. В 1980 он стал стандартом ANSI. В 1983 была издана первая книга о ANSI C. C++, первоначально назывался "C с классами" возник в 1983, и в том же году был переименован C ++. В 1985 была издана первая книга по C++, в 1998 C++ стал стандартом Международной Организации по Стандартизации. | |||||||||||
| Figure 1 History of C, C++, and Java | ||||||||||||
| Key Features.Here is a list of some of the key features of C++. · C++ is strongly typed. This simply means that every object must belong to a certain type and that operations such as assignment or comparison are only permitted between objects of the same type. · C++ has the concept of a class, a type of record that combines data members and the functions that operate on the data. Ignoring various minor differences, classes in C++ are very similar to classes in Java. · C++ supports parameterized types, or templates. Templates make it possible to define, say, a single vector class that works for Booleans, characters, integers, reals, and so on. This can be done in Java by leveraging inheritance. For instance, a vector of type java.lang.Object can operate on other types since all classes eventually inherit from java.lang.Object. This Java approach, however, sacrifices static type checking. The real advantage of C++ templates is that their use does not prohibit the compiler from performing static, or compile-time, type checking. · Similar to Java, C++ supports inheritance, a mechanism that makes it possible to build new classes (called derived classes) on top of an existing class (called the base class) without having to reiterate the base class design for each new class. · C++ supports polymorphism. In C++, polymorphism is achieved through the use of virtual functions and pointer variables. Together with inheritance, this turns C++ into a full-fledged object-oriented language. · C++ comes with two libraries known as the Standard Library and the Standard Template Library (STL)—both of which extend the capabilities of the base language. The Standard Library supplies all the old C libraries as well as new input and output facilities. The STL provides a library of container types (types that hold or "contain" collections of objects) as well as a set of attendant algorithms (which are general-purpose algorithms for common data structures). That is, the STL supplements the built-in types of C++ with vectors, linked lists, and other useful types. | Вот список некоторых из главных особенностей языка: · C++ строго типизирован. Это означает, что каждый объект должен принадлежать определенному типу и что операции, такие как назначение или сравнение разрешены только между объектами одного типа. · C++ поддерживает понятия классов, в типах прописывает комбинации элементов данных и функции, которые воздействуют на данные. Классы в C++ очень схожи с классами в Java. · C++ поддерживает параметризованные типы, или шаблоны. Шаблоны позволяют определить, скажем, единственный векторный класс, который работает для Booleans, целые и вещественные числа и так далее. Реальное преимущество C++ шаблонов состоит в том, что их использование не мешает компилятору статически, или в процессе компиляции, проверять типы. · Подобный Jаva, C ++ поддерживает механизм наследования который позволяет строить новые классы (названные производными классами) поверх существующего класса (назваемый базовым классом), снимая необходимость повторять проект базового класса для каждого нового класса. · C++ поддерживает полиморфизм, который достигается с помощью действительных функций и переменных указателя. · В C++ включены две библиотеки, известные как Стандартная Библиотека и Стандартная Библиотека Шаблонов (STL) позволяющие расширять способности языка. Стандартная Библиотека снабжает все старые (и новые) библиотеки C. STL добавляет встроенные типы C++ с векторами, связанными списками и другими полезными типами. | |||||||||||
| 1.1.2 Compiling and Running a C++ Program Hello World! ; Phases of C++ Program Development ; Edit; Preprocess; Compile; Link; Execute; Compiling and Running a Program Hello World! To get an idea of what a C++ program looks like, we can look at a very simple example. The Hello World! example remains a popular first program when learning any programming language. What follows is a C++ implementation of Hello World! | 1.1.2 Компилирование и программирование в C ++ Программа Привет Мир! Фазы C ++: Редактирование; Препроцессор; Compile; Связь; Выполнить; Компилирование и управление программой. Чтобы понять то, на что похожа программа C ++, рассмотрим очень простой пример - Привет Мир! | |||||||||||
| 1: #include <iostream> 2: #include <cstdlib> 3: 4: using namespace std; 5: 6: int main (int argc, char* argv[]) { 7: 8: // Say hello. 9: cout « "Hello World!" « endl 10: 11: /* indicate normal termination 12: return EXIT_SUCCESS; 13: } Listing 1 The Hello World!program | ||||||||||||
| It is important to notice that C++ source code resembles Java source code. Many of the keywords in the above listing (int, void, return) have similar meanings in Java. In C++, as in Java, a semi-colon is used to terminate the end of a line of code. Also, curly braces define the beginning and ending of functions much the same way in Java. Source code comments look the same in C++. Actually, in the above listing, we can see two different types of C++ comments in use. The first, in line 8, uses the double slash style of comment. In line 11, we see a second style that allows a comment to span multiple lines. C++ and Java share many other similarities. In summary, we can say that C++ and Java have similar syntax. The syntax of a programming language describes the words and symbols that are important to a programming language. Syntax also describes how programmers can arrange these words and symbols to achieve some higher-level meaning. The syntax of C++ and Java Variable declaration and initialization, operators, control structures, and function declaration are areas where C++ and Java share other similarities in syntax. Phases of C++ Program Development C++ programmers must perform five steps, edit, preprocess, compile, link, and execute, to produce an executing copy of a program. Edit The first step involved in taking a program from source to execution is the creation of a file that contains the source code. The program that is used to create a source code file is called an editor. Editors that programmers use range from simple and generic text editors (such as Notepad in Windows or vi in UNIX) to sophisticated editors that typically come as part of Integrated Development Environments (IDEs). These sophisticated editors are quite powerful since they provide functionality that is geared towards the creation and maintenance of source code. The syntax coloring in Listing 1 is one example of the type of functionality that sophisticated editors provide. Preprocess Preprocessing involves the modification of C++ source code files prior to compilation. The first two lines from Listing 1 contain commands called preprocessor directives, which inform the preprocessor to perform some action. In Listing 1, the first two lines instruct the preprocessor to include the contents of files into the program source code. Preprocessing also involves the text substitution of macros. A more detailed discussion of the preprocessor can be found in 1.3.4 The Preprocessor. Compile Preprocessing usually is performed automatically, just before the compile step. Compiling is a complex process that converts the preprocessed source code into object code. Part of the compile process involves verifying that the syntax of the source code is valid. Often, when a program is compiled (especially the first time it is compiled), something is wrong with the syntax. This is referred to as a "compile error." When faced with a compile error, a programmer must return to the first step of this process and edit the source code to remove the error. The software tool used to compile source code, not surprisingly, is known as a compiler. An example of a C++ compiler is the GNU Compiler Collection, or GCC. The GNU Compiler Collection actually compiles many different programming languages, one of which is C++. GCC is also free software. This compiler can be obtained through the Cygwin environment. Link Linking is a step that is typically performed by the same tool that compiles a program. The linking process involves combining the object code produced by the compiler with other precompiled library code. The result of the operation of the linker is an executable image. This executable image is a file that contains the compiled and linked object code of the program, stored in persistent storage (the hard drive). Execute After the program source code has been edited, preprocessed, compiled, and linked into an executable image, the program is ready to be executed, or run. Errors encountered at this point are known as "runtime errors," and are typically more difficult to correct than compile errors, since they may involve problems in the logic of the program. Compiling and Running a Program Quite often, however, the steps preprocess, compile, and link are often informally grouped together and referred to as "compiling." It is easy to see why this is done when we consider that the tools that programmers use often perform these groups of related tasks together. For example, using GCC through MinGW, we can preprocess, compile, and link all in one step. The following command line assumes the source code file is named hello.cpp. $ g++ hello.cpp Example 1 Compiling hello.cpp As a result of the execution of the above command, the source-code file hello.cpp will first be preprocessed, then compiled, and then linked to produce an executable image named a.exe. The default filename a.exe can be overridden using the -o compiler option. $ g++ hello.cpp -o hello.exe Example 2 Overriding the default output file name Additional options (-ansi and -pedantic) inform the compiler that it should only compile programs that are ANSI C++ compliant and that it should issue warnings when it encounters code that violates the ANSI standard. Using these options helps to locate and prevent certain types of errors. $ g++ -ansi -pedantic hello.cpp -o hello.exe Example 3 Conforming to the ANSI standard We can run the program now that it has been compiled into an executable. From the command shell, we issue the following command: $ ./hello.exe Example 4 Running the compiled program The following screen shot depicts the results of the compilation and execution of the program. | Важно заметить, что исходный код в C++ напоминает исходный код в Java. У многих из ключевых слов в вышеприведенном коде (int, void, return) есть подобные значения в Java. В C++, как в Java, точка с запятой используется, чтобы закончить конец строки. Кроме того, фигурные скобы определяют начало и окончание функций почти так же как в Java. Комментарии выглядят одинаково. Фактически, в вышеприведенном коде, мы можем видеть два различных типа комментариев. Первое, в строке 8, используется двойной слеш. В строке 11 приведен второй стиль, который позволяет записывать комментарии в несколько строк. C ++ и Java имеют много других общих черт. В резюме отметим, что C ++ и Java имеют подобный синтаксис. Синтаксис языка программирования описывает слова и символы, которые важны для языка программирования. Синтаксис также описывает, как программисты могут комбинировать эти слова и символы, чтобы достигнуть некоторого высокоуровневого значения. Синтаксис C++ и Java одинаково инициализируют переменные, операторы, структуры контроля. Фазы развития программы C ++ В C ++ необходимо выполнить пять шагов: редактирование, предварительная обработка, компилирование, связывание и исполнение, чтобы произвести выполнение программы. Редактирование (написание кода) Первый шаг это создание файла, который содержит исходный код. Пишется исходный код при помощи редактора. В качестве редакторов могут служить любые текстовые редакторы, или специализированный Integrated Development Environments (IDE). Вид синтаксиса в Listing 1 как пример функциональных возможностей. Препроцесс Препроцесс производит модификацию исходного кода программы C++ до компиляции. Первые две линии в Listing 1 содержат команды, названные директивами препроцессора, сообщают препроцессору о выполнении некоторых действий. Они инструктируют препроцессор включить содержание файлов в исходный текст программы. Препроцесс также производит макроопределения. Более детальное обсуждение препроцессора приведено в 1.3.4 Препроцессор. Компилирование Компилирование это процесс, который преобразовывает предварительно записанный исходный текст в код объекта. Вначале производится проверка и подтверждение, что синтаксис исходного текста корректен. Нередко, когда программа компилируется (особенно в первый раз), кое-что является неправильным в синтаксисе. Это обстоятельство указывается в "compile error". Тогда необходимо вернуться к первому шагу и отредактировать исходный код (исправить ошибку). Инструмент производящий компилирование называют компилятором. Примером C++ компилятора является GNU Compiler Collection или GCC. GCC бесплатное программное обеспечение. Связывание. Связывание это шаг, который выполняется тем же самым инструментом, который компилирует программу. Процесс связывания вовлекает объединение кодов объекта, произведенного компилятором с другим предварительно собранным кодами библиотеки. Результат операции связывания исполнительский файл, который содержит скомпилированный и связанные коды объекта программы, сохраненные на жестком диске. Выполнить После того, как исходный код программы был отредактирован, предварительно обработан, скомпилирован и связан в файл, программа готова и может быть выполненна. Ошибки, с которыми сталкиваются на данном этапе, известны как "runtime errors" которые на много труднее исправить, чем предыдущие ошибки, так как они включают проблемы логики программы. Компилирование и Управление Программой Весьма часто предварительные процессы шагов компилирования и связки группируются и называют "компилированием". Так делается, потому что используя GCC через MinGW, мы можем предварительно обработать, скомпилировать и связать все в одном шаге. Следующая командная строка предполагает, что файл исходного текста называют hello.cpp. $ g++ hello.cpp Example 1 Compiling hello.cpp В результате выполнения вышеупомянутой команды файл исходного текста hello.cpp будет сначала предварительно обработан, затем собран, и затем связан, чтобы произвести файл, названный как a.exe. Имя файла по умолчанию a.exe может быть изменен, используя «-o» выбор компилятора. $ g++ hello.cpp -o hello.exe Example 2 Overriding the default output file name Дополнительные опции (-ansi и -pedantic) указывают компилятору, что он должен собрать программы которые соответствуют ANSI C++ Использование этих опций помогают определить местонахождение и предотвратить некоторые типы ошибок. $ g++ -ansi -pedantic hello.cpp -o hello.exe Example 3 Conforming to the ANSI standard Теперь можно управлять программой запустив ее на вылонение следующей командой: $ ./hello.exe Example 4 Running the compiled program Следующий скрин-шот изображает результаты компиляции и выполнение программы. | |||||||||||
| Figure 1 After compilation and execution | ||||||||||||
| The compiling and linking of programs that consist of many files can be simplified using a makefile. A makefile is a text file that defines the relationships and dependencies between the files that are used to create a project. The main advantage of using a makefile is that they allow a programmer to compile only those source code files that have changed since the last compile. This can be very time saving when working with projects that consist of many source code files. Understanding the syntax and rules available in makefiles is beyond the scope of this course. | Компилирование и соединение программ, которые состоят из многих файлов, могут быть упрощены, используя makefile. makefile - текстовый файл, который определяет отношения и зависимости между файлами в создающемся проекте. Главное преимущество использования makefile состоит в том, что он позволяет программисту собирать только те файлы исходного текста, которые изменились. Это может быть очень экономичным, особенно работая с проектами, которые состоят из многих файлов исходного текста. Понимание синтаксиса и правил, доступных в makefiles, вне области этого курса. | |||||||||||
| 1.2 Data Structures and Algorithms in C++ 1.2.1 What are Data Structures and Algorithms? · Data Structures · Algorithms In just about every aspect of today's modern world, we encounter information in all shapes and sizes. The amount of information we encounter is sometimes so large that without an effective method of storage and representation, the information is rendered useless. Think of all the books contained in your local library. Without the storage system implemented by the librarians, it would be virtually impossible to find a specific book. Even when faced with just a small amount of information, a structured representation can prove to be invaluable. For instance, think of the problems that could arise if people did not stand in line while waiting to purchase tickets at a movie theater. The line prevents the people waiting from just standing around arguing over whose turn is next. In a sense, the line serves as a way to store information. A data structure, in the simplest terms, is a structured representation of information. Both the system used to store books in the library and the line of people at the movie theater are real world instances of data structures. Considering a larger context, data structures typically represent, or store, data to facilitate solving some problem. In the library example, the problem that the data structure helps solve is locating a specific book. At the movie theater, people wait in a line so it is easy to determine whose turn is next. A data structure can be composed of simple pieces of data. Consider your address as a data structure. There are several items in this data structure, all of which are simple pieces of data. First, there is the street address, which is usually a number followed by a street name. Add to that the city name, the state or province abbreviation, and the postal code, and you have a very useful data structure composed simply of numbers and words. Data structures can also be complex in that they can contain other data structures. For example, a library contains many bookcases, which in turn contain many books. Sitting on the shelf of one of these bookcases could be a cardboard box that also contains a few books. In this example, the bookcase is a data structure composed of books and boxes of books. The boxes are also data structures, since they store books as well. Here we have a data structure (a bookcase) that is composed of another data structure (a box). Both data structures provide a way to store information (the books) to help solve some problem (finding a specific book). A filing cabinet full of folders of papers is another good example of how data structures can be composed of other data structures. In this case, the cabinet as a whole is a data structure. The cabinet is composed of cabinet drawers, which are composed of folders, which are composed of files. | 1.2 Алгоритмы и Структуры Данных в C ++ 1.2.1 Каковы Структуры Данных и Алгоритмы? · Структуры Данных · Алгоритмы Количество информации, с которой мы сталкиваемся в современном мире, является иногда настолько большим, что без эффективного метода хранения и представления, она может быть бесполезной. Вспомните хотя бы обо всех книгах, содержащиеся в Вашей местной библиотеке. Без системы хранения, осуществленной библиотекарями, было бы фактически невозможно найти определенную книгу. Даже когда сталкиваешься с только небольшим количеством информации, структурированное представление, может оказаться полезным. Структуры данных, выражаясь простым языком, являются структурированным представлением информации. Структура данных может быть представлена простыми частями данных. Рассмотрим почтовый адрес как структуру данных. В этой структуре данных есть несколько пунктов и все они являются простыми частями данных. Так, есть уличный адрес, представленный числом и названием улицы. Далее название города, государства и индекс, и у Вас есть очень полезная структура данных, составленная просто из чисел и слов. Но структуры данных могут также быть сложными, т.е. они могут включать в себя другие структуры данных. Например, библиотека содержит много книжных шкафов, которые в свою очередь содержат много книг. На полке одного из этих книжных шкафов могут находиться картонные коробки, которые также содержат несколько книг. В этом примере книжный шкаф - структура данных, составленная из книг и коробок книг. Коробки - также структуры данных, так как они тлже хранят книги. Здесь у нас есть структура данных (книжный шкаф), который составлен из другой структуры данных (коробка). | |||||||||||
| Figure 1 A filing cabinet as a data structure Algorithms | ||||||||||||
| In addition to having a data structure that represents information, some sequence of actions, or series of steps, needs to be taken to solve a problem. The series of steps that manipulate and uses a data structure to solve a problem is called an algorithm. Let's think back to the example of the line at the movie theater. Here, the problem at hand is the management of a group of people waiting to buy tickets. The data structure is a line of people. The algorithm involves removing a person from the beginning of the line (until the line is empty) when the ticket cashier becomes available. 1. Wait for the cashier to become available. 2. Remove the customer that is at the beginning of the line. 3. Let the cashier help this removed customer. 4. Go to step 1. The steps contained in an algorithm are performed in a mechanical fashion. From the example above, first we do step 1, then we do step 2, then we do step 3, then we repeat with step 1. Algorithms can involve this type of repetition, and they can also involve simple branching or decision making (if "this," then do "that"). Since computers can perform these tasks very rapidly, it should be no surprise that algorithms play such a prominent role in computers and computer science. A recipe for baking a cake is another good example of an algorithm. In a recipe for a cake there clearly defined steps that are followed. First, the oven has to be preheated. Then we have to mix the ingredients. The cake batter is then poured into a pan, which is then placed into the oven, and so on. The algorithm involved in baking a cake has clearly defined inputs (the ingredients) and a clearly defined output (the cake). | Ряд шагов, которые управляют и используют структуры данных, чтобы решать те или иные проблемы, называют алгоритмом. Давайте вспомним, к примеру, очередь в кинотеатре. Здесь, проблема в том чтобы управлять группой людей, стоящих в очереди, чтобы купить билеты. Структура данных - очередь людей. Алгоритм решения в том, чтобы удалить человека с головы очереди (если очередь существует), после того как кассир становится ему доступным. 1. Ожидание в очереди, пока кассир не оказался ему доступным. 2. Действие кассира по запросу клиента. 3. Удалите клиента из начала очереди, после общения с кассиром. 4. Вернуться в шаг 1. Шаги, содержавшиеся в алгоритме, выполняемы механическим способом. Сначала мы делаем первый шаг, затем 2, затем 3, и затем возвращаемся в шаг 1. Так как компьютеры могут выполнить эти задачи (шаги) очень быстро, должно не быть удивительно, что алгоритмы играют такую важную роль в компьютерах и компьютерной науке. Рецепт для того, чтобы испечь пирог является другим хорошим примером алгоритма. В рецепте для пирога необходимо точно определить шаги, которые необходимо выполнить. Во-первых, духовка должна быть предварительно подогретая. Затем мы должны смешать компоненты и получить жидкое тесто. Жидкое тесто пирога тогда льют в кастрюлю, когда она помещена в духовку, и так далее. Только тогда мы поучим пирог, если строго выполним шаги алгоритма. | |||||||||||
1.2.2 Problem Solving with Data Structures and Algorithms
| 1.2.2 Решение Проблемы со Структурами Данных и Алгоритмами Multiple Solutions Один из преобладающих вопросов, к которым мы обращаемся в этом курсе, это то, как мы используем структуры данных и алгоритмы, чтобы решать проблемы? Обычно нет только одного решения для какой либо проблемы. Часто есть множественное решение, с своими определенными преимуществами и недостатками. Пример библиотеки показывает наличие множественных подходов к решению проблемы, имеющие собственные преимущества и недостатки. Одно решение этой проблемы вовлекает использование иерархической системы, например, чтобы хранить вместе книги по связанным разделам. Или подход когда можно хранить все книги по "Политике" вместе. Тогда одна полка содержала бы книги по "Истории Политики", в то время как другая полка будет содержать книги по "Современной Политике." Принимая этот алгоритм надо будет разделить книги на "Историю Политики", "Историю испанской Политики," "История бразильской Политики," "История итальянской Политики," и так далее. Алгоритм, чтобы найти определенную книгу вовлекает человека, идущего сначала к книжной полке "Политики", затем к "Истории Политики" и так далее пока он не найдет книгу, которую он искал. Другое представление вовлекает книги хранения в алфавитном порядке авторов. В пределах этих категорий представление устраивает книги в алфавитном порядке по имени автора книги. После того, как мы нашли книгу, используя первое представление, мы найдем другие книги по той же самой определенной теме, а не книги написанными тем же самым автором. Это различие может быть преимуществом или неудобством, в зависимости от целей поиска. Например, исследуя определенную тему было бы полезно видеть все другие книги по теме. Multiple Representations Иногда можно решать две (или больше) неодинаковые проблемы, используя одну и ту же структуру данных и алгоритм. Рассмотрим список следующих проблем и соответствующих решений: | |||||||||||
Table 1 Different problems with similar solutions | ||||||||||||
| Each of the problems in the table above essentially is solved using some type of list to represent the data. The algorithms involved in solving the problems may vary slightly, but essentially the algorithm traverses each list and performs some action (updating a grade, marking an item as complete). Refining the Representation The refinement of an initial representation can often lead to a more elegant solution. Consider the problem of garbage removal from an office building. We'll add a restriction that recyclable materials (we will just consider paper) must be separated from the non-recyclable garbage. One way to represent the problem is to simply provide a "recycle" dumpster and a garbage dumpster outside the building. The algorithm to solve the problem involves each employee carrying their garbage (with their hands!) outside to these dumpsters, where they then separate the paper from the rest of the garbage. This works, and it solves the problem, but it would probably lead to unhappy employees who will grow tired of the tedious process of walking outside and back each time they want to throw something away. We can optimize our representation slightly by placing trashcans on each floor of the office building. The algorithm for this representation requires each employee to carry their garbage and paper to the trashcan on their floor. Then, at the end of the day, someone carries the trashcans from each floor to the dumpsters outside, where they separate the paper from the garbage. This again solves the problem, and it probably will make the employees happier, but it still requires employees to carry their garbage to a central trashcan. It also is a lot of work for the person who has to empty and sort all the floor trashcans. Let's refine the representation even further by placing trashcans in each office. We'll also add wheels to the trashcans that reside on each floor. Now, each employee throws their garbage and paper into their own office trashcan and at the end of the day, one person wheels the floor trashcan from office to office, emptying the office trashcans. They then separate this garbage outside into the two dumpsters. We've reached an improved solution, but one that still involves a good deal of sorting and separating of the garbage and recyclable paper. What if we optimized by placing, in addition to the garbage can, a recycle basket in each office? We will also attach a recycling basket to the trashcan on wheels. This basket collects the paper thrown into the office recycle baskets. In this representation, each employee throws their unneeded paper into their recycle basket and their garbage into their garbage can. At the end of the day, one person walks around each floor with the trashcan on wheels, emptying both the garbage can and the recycle basket from each office. They then empty the can and the basket into the appropriate dumpsters outside. This solution keeps the employees happy, and reduces the work of the person who takes the garbage and paper outside. Actually, this refined representation eliminates the separating of garbage altogether. This is really an optimal solution! Decomposing the Representation After a representation of a problem has been established, the next step that can be taken involves identifying the key entities, or objects, that make up the representation. Just as important as identifying these objects, we will try to understand the relationship between these objects. This process of identifying objects and relationships is known as decomposition. Decomposition, in the basic sense, involves the "breaking down" of a problem representation into its core components. Looking back at our refined representation of the garbage collection problem, let's try to identify some of the key objects. There are definitely a lot of office garbage cans and recycle baskets, since every office has one of each. We also have two cans on wheels for each floor (one for regular garbage, and one for recyclable paper), and a recycle dumpster and a trash dumpster outside the office building. Listing these objects, we can see we basically have different types of things that store garbage. · outside garbage bin · outside recycle bin · garbage can on wheels · attached recycle basket · office garbage can · office recycle basket All of these objects are just bins of some sort since they essentially store materials. A bin that stores garbage is just a specific type of a bin. Likewise, a bin that stores recyclable paper is another type of bin (even though we call it a "basket"). From our list above, we can get more specific with the types of bins that our representation uses: · GarbageBin is a type of Bin · RecycleBin is a type of Bin · GarbageDumpster is a type of GarbageBin · RecycleDumpster is a type of RecycleBin · OfficeGarbageCan is a type of GarbageBin · OfficeRecycleBasket is a type of RecycleBin · FloorTrashCan is a type of Bin, it contains a GarbageBin and a RecycleBin Our decomposition now illustrates the relationships between the objects. This is an important step in solving any problem since understanding relationships helps allows us to better design a solution. | Каждая из проблем в таблице выше по существу решена, используя некоторый тип списка. Алгоритмы, вовлеченные в решение проблем, могут измениться немного, но по существу алгоритм выполняет некоторое действие. Refining the Representation Обработка начального представления может часто приводить к более изящному решению. Рассмотрим проблему удаления мусора из офиса в здании. Мы добавим ограничение, что годные для повторного использования материалы (речь идет только о бумаге), необходимо отделить от негодной. Один из способов решения проблемы состоит в том, чтобы просто перерабатывать мусорный контейнер и мусорную корзину вне здания. Алгоритм предусматривает чтобы каждый служащий несущий мусор отделял пригодную бумагу от остальной части мусора. Это вполне может работать, и это решает проблему, но это вероятно привело бы к несчастным служащим, которые будут уставать от утомительного процесса ходьбы к контейнерам наружу и назад каждый раз, когда они хотят выбросить что то. Мы можем оптимизировать процесс немного, помещая корзинки на каждом полу здания офиса. Алгоритм для этого представления требует, чтобы каждый служащий относил мусор и бумагу вначале в корзину. И только в конце дня, кто-то относил бы эти корзины наружу здания в контейнер. Такая схема тоже решает проблему, и она вероятно сделает служащих более счастливыми, но она все еще требует, чтобы служащие относили свой мусор к центральному контейнеру. Это также - большая работа для человека. Давайте усовершенствуем алгоритм еще далее, поместим корзинки в каждом офисе. Теперь, каждый служащий может бросать мусор и бумагу в собственном офисе в корзину и только в конце дня один человек соберет весь мусор со всех офисов и вынесет его наружу. Разделение на годную и негодную также произведется снаружи в два разных контейнера. Вероятно это и есть улучшенное решение, но оно все еще вовлекает большую сортировку и отделение годной для повторного использования бумаги и негодной. Что, если оптимизироваться еще раз, помещая, в дополнение к корзине в офисах еще корзину для годной дла повторного использования бумаги. ……………………………………………………………………………………… Это решение приведет к тому что служащие вполне окажутся осчастливленными, потому что это уменьшает работу для человека, который собирает мусор и бумагу на наружном контейнере. Фактически, это усовершенствованное представление устраняет отделение мусора в целом. Decomposing the Representation После того, как решение проблемы осуществлено, следующий шаг, который может быть сделан, это идентификация ключевых лиц, или объектов, которые составляют представление. Необходимо понять отношения между этими объектами. Этот процесс идентификации объектов и отношений известен как разложение. Разложение, в основном смысле, вовлекает "разрушение" представления проблемы на его основные компоненты. Оглядываясь назад на наше усовершенствованное представление проблемы сбора мусора, попытаемся идентифицировать некоторые из ключевых объектов. Есть определенно много корзин для мусора в офисах. У нас также есть две карзины на колесах для каждого этажа (один негодного мусора, и один для годной бумаги), и мусорный контейнер вне здания офиса. Перечисляя эти объекты, мы можем видеть, что у нас в основном есть различные типы мусорных корзин. · outside garbage bin · outside recycle bin · garbage can on wheels · attached recycle basket · office garbage can · office recycle basket Все эти объекты - только мусорные ведра некоторого вида, так как они по существу хранят материалы. Мусорное ведро, которое хранит мусор, является только определенным типом мусорного ведра. Аналогично, мусорное ведро, которое хранит годную для повторного использования бумагу, является другим типом мусорного ведра (даже при том, что мы называем это "корзиной"). Тогда: · GarbageBin - тип Мусорного ведра · RecycleBin - тип Мусорного ведра · GarbageDumpster - тип GarbageBin · RecycleDumpster - тип RecycleBin · OfficeGarbageCan - тип GarbageBin · OfficeRecycleBasket - тип RecycleBin · FloorTrashCan - тип Мусорного ведра, он содержит GarbageBin и RecycleBin Наше разложение теперь иллюстрирует отношения между объектами. Это - важный шаг в решении любой проблемы начиная с понимания, что отношения помогают нам лучше проектировать решение. | |||||||||||
|
Новости и инфо для студентов