FRМІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Курсова робота з програмування
На тему:
"ПРОГРАМУВАННЯ"
Завдання на курсову роботу
з дисципліни “Програмування”
Прізвище, ім’я студента
Мандзевич Н. Т.
Група
КІ-21
Тема курсової роботи
Програмування
Завдання 1
3.5. У місті розташовано n автобусних зупинок, позначених числами з N={1,2,....,n}. В текстовому файлі записано k автобусних маршрутів, заданих послідовностями сусідніх зупинок при русі автобуса в одному напрямку:
М1={P11,P12,...,P1m1},
М2={P21,P22,...,P2m2},
.....
Mk={Pk1,Pk2,...,Pkmk}, де Pij натуральне число з N.
Написати програму, що по заданих номерах зупинок I і J визначає найбільш швидкий шлях переміщення пасажира з зупинки I у зупинку J з використанням наявних маршрутів автобусів при умові, що час руху між сусідніми зупинками у всіх маршрутах однаковий і у 3 рази менший за час зміни маршруту. Автобуси можуть рухатись в обох напрямках.
Завдання 2
4.12. Дано послідовність натуральних чисел ( значення кожного числа від 1 до 1000 ). Послідовність може бути не відсортована. Треба знайти варіант найбільшої (по кількості елементів) неспадаючої послідовності, складеної з чисел цього ряду. Порядок включення чисел у неспадаючу послідовність повинен відповідати порядку слідування чисел у початковій послідовності.
Приклад: Вхідні дані Результат
59 4
4 18
21 27
36 34
18 45
27 47
79 93
34
45
47
34
93
Завдання видано
30 березня 2011 р
Керівник:
Карпін О. О.
Студент:
Мандзевич Н. Т.
Анотація
Курсова робота з курсу “ Програмування” на тему ”Програмування” виконана з використанням можливостей та засобів С++ та Microsoft Visual Studio 2010. Основною метою даної курсової роботи є дослідження алгоритмів з використанням різних структур даних: списків стеків черг дерев та графів (згідно завдання). Програми написані за всіма правилами структурного програмування.
В пояснювальній записці до курсової роботи приведені теоретичні обґрунтування до задачі, описи алгоритму задачі та результати тестування і висновки.
Тексти програм подані у додатках.
Повністю курсова робота складається з теоретичної частини, пояснювальної записки, додатків та демонстраційних програм.
Зміст
Вступ 5
1. Завдання 1 6
1.1. Теоретична частина 6
1.2. Опис алгоритму 7
1.3. Система тестів 7
1.4. Специфікація програми 7
1.5. Результати виконання програми 9
2. Завдання 2 10
2.1. Теоретична частина 10
2.2. Опис алгоритму 11
2.3. Система тестів 12
2.4. Специфікація програми 12
2.5. Результати виконання програми 13
Висновки 14
Список літератури 15
Додатки 16
Вступ
Структура даних - програмна одиниця, що дозволяє зберігати і обробляти безліч однотипних і / або логічно пов'язаних даних в обчислювальній техніці. Для додавання, пошуку, зміни та видалення даних структура даних надає деякий набір функцій, складових її інтерфейс. Структура даних часто є реалізацією будь-якого абстрактного типу даних.
При розробці програмного забезпечення велику роль грає проектування сховища даних і представлення всіх даних у вигляді безлічі пов'язаних структур даних.
Добре спроектоване сховище даних оптимізує використання ресурсів (таких як час виконання операцій, на обсяг оперативної пам'яті, число звернень до дискових накопичувачів), необхідних для виконання найбільш критичних операцій.
Структури даних формуються за допомогою типів даних, посилань і операцій над ними в обраному мовою програмування.
Різні види структур даних підходять для різних додатків; деякі з них мають вузьку спеціалізацію для певних завдань. Наприклад, B-дерева зазвичай підходять для створення баз даних, в той час як хеш-таблиці використовуються повсюдно для створення різного роду словників, наприклад, для відображення доменних імен в інтернет-адреси комп'ютерів.
При розробці програмного забезпечення складність реалізації і якість роботи програм істотно залежить від правильного вибору структур даних. Це розуміння дало початок формальним методам розробки та мов програмування, в яких саме структури даних, а не алгоритми, є наріжним архітектури програмного засобу. Велика частина таких мов володіє певним типом модульності, що дозволяє структурам даних безпечно використовуватися в різних додатках. Об'єктно-орієнтовані мови, такі як Java, C # і C + +, є прикладами такого підходу.
Багато класичних структур даних представлені в стандартних бібліотеках мов програмування або безпосередньо вбудовані в мови програмування. Наприклад, структура даних хеш-таблиця вбудована в мови програмування Lua, Perl, Python, Ruby, Tcl і ін. Широко використовується стандартна бібліотека шаблонів STL мови C + +.
Завдання 1
Теоретична частина
Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.
Така черга повністю аналогічна звичній черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)
Основні операції з чергою
англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).
англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).
Дек (від англ. Double ended queue — двобічна черга) — абстрактна структура даних, елементи якої можуть додаватись як на початок, так і в кінець.
Типові операції:
Додавання елемента в кінець черги
Додавання елемента в початок черги
Вибірка останнього елемента
Вибірка першого елемента
Перевірка першого елемента (без видалення з деку)
Перевірка останнього елемента (без видалення з деку)
Алгоритм розв’язку
Вводимо N кількість зупинок. В текстовий файл записуємо маршрут. Натискаємо сформувати структуру, яка формує черги з вхідних даних. Вводимо I i J. Перевіряємо на наявність прямого маршруту. Далі перевіряємо на наявність пересадки, шукаємо I в черзі беремо наступне число і шукаєм його в інших чергах, якщо є шукаємо J.
Система тестів
У випадку коли у файлі з вхідними даними не вказано меред маршрутом кількість зупинок, яких містить цей маршрут, то програма буде працювати не відповідно до бажаного результату.
Специфікація програми
В клас стандартного діалогового вікна було додано такі елементи:
Button1 – кнопка за допомогою якої виводиться умова задачі
Button2 – кнопка за допомогою якої зчитуються вхідні дані з файлу
Button3 – кнопка за допомогою якої формується кінцевий результат
StaticText1 –поле яке виводить повідомлення про те, скільки було задано вхідних маршрутів
StaticText2 – текстове поле яке виводить повідомлення з кінцевим результатом
В клас стандартного діалогового вікна було додано такі функції:
void Dialog1::OnBnClickedButton2() – Зчитує з текстового файлу вхідні дані
void Dialog1::OnBnClickedButton3()- Проводить основні обрахунки, і виводить результат.
Результати виконання програми
/
/
Завдання 2
Теоретична частина
Дерево — в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:
існує один віокремлений вузол — корінь дерева
інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин в свою чергу є деревом. Дерева T1…Tm мають назву піддерев даного кореня.
З визначення випливає, що кожна вершина є в свою чергу коренем деякого піддерева. Кількість піддерев вершини має назву ступеня цієї вершини. Вершина ступеню нуль має назву кінцевої або листа. Некінцева вершина також має назву вершини розгалуження .
Нехай x — довільна вершина дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вершини на цьому шляху називаються предками x; якщо деяка вершина y є предком x, то x називається нащадком y. Нащадки та предки вершини x, що не збігаються з нею самою, називаються власними нащадками та предками. Кожну вершину x, в свою чергу, можна розглядати як корінь деякого піддерева, елементами якого є вершини-нащадки x.
Якщо вершини x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називається батьком до y, а y — дитиною x. Коренева вершина єдина не має батьків.
Вершини, що мають спільного батька, називаються братами. Вершини, що мають дітей, називаються внутрішніми. Глибиною вершини x називається довжина шляху від кореня до цієї вершини. Максимальна глибина вершин дерева називається висотою.
Якщо існує відносний порядок на піддеревах T1…Tm, то таке дерево називається впорядкованим або пласким.
Лісом називають множину дерев, які не перетинаються.
Найчастіше дерева в інформатиці зображують з коренем, який знаходиться зверху (говорять, що дерево в інформатиці «росте вниз»).
Важливим окремим випадком кореневих дерев є бінарні дерева, які широко застосовуються в програмуванні і визначаються як множина вершин, яка має відокремлений корінь та два піддерева (праве та ліве), що не перетинаються, або є пустою множиною вершин (на відміну від звичайного дерева, яке не може бути пустим).
Алгоритм розв’язку
Вводимо вхідну послідовність. Нажимаємо на кнопку пошуку. Йде пошук найдовшої неспадної послідовності шляхом повного перебору підмножин даної множини чисел знаходимо множину яка є неспадною записуємо її, і продовжуємо шукати послідовність яка є більше даної поки не переберемо всі підмножини.
Система тестів
У випадку коли в послідовності існує багато вхідних даних, або в цій послідовності будуть знаходитись дуже великі числа, то програма може працювати некоректно і відповідь може не співпадати з потрібним результатом.
Специфікація програми
В клас стандартного діалогового вікна було додано такі елементи:
Button1 – проводить основні обчислення, виводить результат
Button2 – виводить умову задачі на екран
EditText – зчитує вхідні дані
В клас стандартного діалогового вікна було додано такі функціїї:
void Dialog2::OnBnClickedButton1() – проводить обчислення, видає резільтат
Результати виконання програми
/
Висновки
Виконуючи дану курсову роботу, я ознайомився з такими структурами даних як дек і граф. Вивчив методи і принципи роботи з ними і алгоритми, що базуються на їх використанні (представлені в стандартних бібліотеках). Закріпив знання про створення SDI-аплікацій.
Список Літератури
ГОСТ 19.701-90 (ИСО 5807-85) ЕСПД. Схемы алгоритмов и программ, данных и систем. Условные обозначения и правила выполнения.
Берзтисс А.Т. Структуры данных . – М.:Статистика, 1974 - 408 с.
А.Ахо, Дж.Хопкрофт, Дж.Ульман, Д.Джеффри. Структуры данных и алгоритмы.; Пер. с англ.– М.:Изд.дом ”Вильямс”, 2001. – 384 с.
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с.
Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry, Elsevier, pp. 425–461; Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes", Archivum mathematicum Т. 40 (3): 315–320.
http://ru.wikipedia.org/wiki/Структура_данных
http://uk.wikipedia.org/wiki/Дерево_(структура_даних)
http://uk.wikipedia.org/wiki/Черга_(структура_даних)
http://uk.wikipedia.org/wiki/Дек
Загальне меню
/**************************************************************\
FILE : KursщмфDlg.h
AUTHOR : Mandzevych Nazar
DESCRIPTION : Work 2
CLASSES : Dialog2
COPYRIGHT : Copyright Nazar Mandzevych (c) 2011
\**************************************************************/
// KursovaDlg.h : header file
//
#pragma once
// CKursovaDlg dialog
class CKursovaDlg : public CDialogEx
{
// Construction
public:
CKursovaDlg(CWnd* pParent = NULL); // standard constructor
// Dialog Data
enum { IDD = IDD_KURSOVA_DIALOG };
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
// Implementation
protected:
HICON m_hIcon;
// Generated message map functions
virtual BOOL OnInitDialog();
afx_msg void OnPaint();
afx_msg HCURSOR OnQueryDragIcon();
DECLARE_MESSAGE_MAP()
public:
afx_msg void OnBnClickedButton1();
afx_msg void OnBnClickedButton2();
};
// KursovaDlg.cpp : implementation file
//
#include "stdafx.h"
#include "Kursova.h"
#include "KursovaDlg.h"
#include "afxdialogex.h"
#include "Dialog1.h"
#include "Dialog2.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#endif
// CKursovaDlg dialog
Dialog1 d1;
Dialog2 d2;
CKursovaDlg::CKursovaDlg(CWnd* pParent /*=NULL*/)
: CDialogEx(CKursovaDlg::IDD, pParent)
{
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CKursovaDlg::DoDataExchange(CDataExchange* pDX)
{
CDialogEx::DoDataExchange(pDX);
}
BEGIN_MESSAGE_MAP(CKursovaDlg, CDialogEx)
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON1, &CKursovaDlg::OnBnClickedButton1)
ON_BN_CLICKED(IDC_BUTTON2, &CKursovaDlg::OnBnClickedButton2)
END_MESSAGE_MAP()
// CKursovaDlg message handlers
BOOL CKursovaDlg::OnInitDialog()
{
CDialogEx::OnInitDialog();
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
d1.Create(IDD_DIALOG1,this);
d2.Create(IDD_DIALOG2,this);
d1.ShowWindow(SW_HIDE);
d2.ShowWindow(SW_HIDE);
// TODO: Add extra initialization here
return TRUE; // return TRUE unless you set the focus to a control
}
// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.
void CKursovaDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting
SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialogEx::OnPaint();
}
}
// The system calls this function to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CKursovaDlg::OnQueryDragIcon()
{
return static_cast<HCURSOR>(m_hIcon);
}
void CKursovaDlg::OnBnClickedButton1()
{
d1.ShowWindow(SW_SHOW);
}
void CKursovaDlg::OnBnClickedButton2()
{
d2.ShowWindow(SW_SHOW);
}
Завдання 1
/**************************************************************\
FILE : Dialog1.h
AUTHOR : Nazar Mandzevych
DESCRIPTION : Work 1
CLASSES : Dialog1
Bus stop
COPYRIGHT : Copyright Nazar Mandzevyh (c) 2011
\**************************************************************/
// Dialog1 dialog
/*===================== Dialog1 =================*/
#pragma once
// Dialog1 dialog
class Dialog1 : public CDialogEx
{
DECLARE_DYNAMIC(Dialog1)
public:
Dialog1(CWnd* pParent = NULL); // standard constructor
virtual ~Dialog1();
// Dialog Data
enum { IDD = IDD_DIALOG1 };
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
DECLARE_MESSAGE_MAP()
public:
int n;
int i;
int j;
afx_msg void OnBnClickedButton1();
afx_msg void OnBnClickedButton2();
afx_msg void OnBnClickedButton3();
int strukture;
int arr[100][100];
CString str;
CString str1;
};
/**************************************************************\
FILE : Dialog1.cpp
AUTHOR : Nazar Mandzevych
DESCRIPTION : Work 1
CLASSES : Dialog1
Bus stop
COPYRIGHT : Copyright Nazar Mandzevych (c) 2011
\**************************************************************/
/*================= IMPORT DECLARATIONS =============*/
// Dialog1.cpp : implementation file
//
#include "stdafx.h"
#include "Kursova.h"
#include "Dialog1.h"
#include "afxdialogex.h"
#include <fstream>
#include <iostream>
using namespace std;
// Dialog1 dialog
IMPLEMENT_DYNAMIC(Dialog1, CDialogEx)
Dialog1::Dialog1(CWnd* pParent /*=NULL*/)
: CDialogEx(Dialog1::IDD, pParent)
, n(0)
, i(0)
, j(0)
, strukture(0)
, str1(_T(""))
{
}
Dialog1::~Dialog1()
{
}
void Dialog1::DoDataExchange(CDataExchange* pDX)
{
CDialogEx::DoDataExchange(pDX);
DDX_Text(pDX, IDC_EDIT1, n);
DDV_MinMaxInt(pDX, n, 1, 99);
DDX_Text(pDX, IDC_EDIT2, i);
DDX_Text(pDX, IDC_EDIT3, j);
DDX_Text(pDX, IDC_STATIC16, strukture);
DDX_Text(pDX, IDC_EDIT4, str1);
}
BEGIN_MESSAGE_MAP(Dialog1, CDialogEx)
ON_BN_CLICKED(IDC_BUTTON1, &Dialog1::OnBnClickedButton1)
ON_BN_CLICKED(IDC_BUTTON2, &Dialog1::OnBnClickedButton2)
ON_BN_CLICKED(IDC_BUTTON3, &Dialog1::OnBnClickedButton3)
END_MESSAGE_MAP()
// Dialog1 message handlers
void Dialog1::OnBnClickedButton1()
{
MessageBox(L"У місті розташовано n автобусних зупинок, позначених числами з N={1,2,....,n}. В текстовому файлі записано k автобусних маршрутів, заданих послідовностями сусідніх зупинок при русі автобуса в одному напрямку:\r\nМ1={P11,P12,...,P1m1},\r\nМ2={P21,P22,...,P2m2},\r\n.....\r\nMk={Pk1,Pk2,...,Pkmk}, де Pij натуральне число з N.\r\nНаписати програму, що по заданих номерах зупинок I і J визначає найбільш швидкий шлях переміщення пасажира з зупинки I у зупинку J з використанням наявних маршрутів автобусів при умові, що час руху між сусідніми зупинками у всіх маршрутах однаковий і у 3 рази менший за час зміни маршруту. Автобуси можуть рухатись в обох напрямках.", L"Умова задачі 3.5", MB_OK);
}
void Dialog1::OnBnClickedButton2()
{
for(int q = 0; q < 100; q++)
for(int qq = 0; qq < 100; qq++)
arr[q][qq] = 0;
UpdateData();
ifstream f ("input.txt");
int
now_line = 0;
bool
interrupt = true;
while((!f.eof()) && (interrupt))
{
int
kilkist;
f >> kilkist;
for(int k = 0; (k < kilkist) && (interrupt); k++)
{
f >> arr[now_line][k];
if(arr[now_line][k] > n)
{
MessageBox(L"Введено зупинку з номером, що більше за кількість зупинок :(", L"Error");
interrupt = false;
now_line = -1;
}
}
now_line++;
}
f.close();
strukture = now_line;
UpdateData(false);
}
void Dialog1::OnBnClickedButton3()
{
str.Empty();
char
t[3];
int
temp,
mem_1,
mem_2;
for(int k = 0; k < 100; k++)
{
temp = 0;
for(int kk = 0; (kk < 100) && (temp != 7); kk++)
{
if((arr[k][kk] == i) && (temp == 0))
{
temp = 1;
mem_1 = kk;
}
if((arr[k][kk] == j) && (temp == 0))
{
temp = 2;
mem_2 = kk;
}
if((arr[k][kk] == i) && (temp == 2))
{
temp = 7;
mem_1 = kk;
}
if((arr[k][kk] == j) && (temp == 1))
{
temp = 7;
mem_2 = kk;
}
}
if(temp == 7)
{
str += "Знайдено прямий маршрут (";
for(int h = 0; h < 3; h++)
t[h] = 0;
if(k < 9)
t[0] = k+1 + '0';
if(k > 8)
{
t[0] = (k+1)/10 + '0';
t[1] = (k+1)%10 + '0';
}
str += t;
str += ") - ";
if(mem_1 <= mem_2)
{
for(int g = mem_1; g <= mem_2; g++)
{
for(int h = 0; h < 3; h++)
t[h] = 0;
if(arr[k][g] < 10)
t[0] = arr[k][g] + '0';
if(arr[k][g] > 9)
{
t[0] = arr[k][g]/10 + '0';
t[1] = arr[k][g]%10 + '0';
}
str += t;
str += " ";
}
}
if(mem_1 > mem_2)
{
for(int g = mem_1; g >= mem_2; g--)
{
for(int h = 0; h < 3; h++)
t[h] = 0;
if(arr[k][g] < 10)
t[0] = arr[k][g] + '0';
if(arr[k][g] > 9)
{
t[0] = arr[k][g]/10 + '0';
t[1] = arr[k][g]%10 + '0';
}
str += t;
str += " ";
}
}
str += "\r\n";
}
}
//PERESADKA
int
temp_l,
mem_0;
for(int k = 0; (k < 100) && (arr[k][0] != 0); k++)
{
temp = 0;
for(int kk = 0; (kk < 100) && (arr[k][kk] != 0); kk++)
{
if((arr[k][kk] == i) && (temp == 0))
{
temp = 1;
mem_0 = kk;
}
if((temp == 1) && (mem_0 != kk))
{
//тут ми найшли в маршруті к зупинку і (мем_0)
for(int l = 0; (l < 100) && (arr[l][0] != 0); l++)
{
temp_l = 0;
if(l != k)
{
for(int ll = 0; (ll < 100) && (temp_l != 7) && (arr[l][ll] != 0); ll++)
{
if((arr[l][ll] == j) && (temp_l == 1))
{
temp_l = 7;
mem_2 = ll;
}
if((arr[l][ll] == arr[k][kk]) && (temp_l == 2))
{
temp_l = 7;
mem_1 = ll;
}
if((arr[l][ll] == arr[k][kk]) && (temp_l == 0))
{
temp_l = 1;
mem_1 = ll;
}
if((arr[l][ll] == j) && (temp_l == 0))
{
temp_l = 2;
mem_2 = ll;
}
}
if((temp_l == 7) && ((arr[l][mem_2] == i) || (arr[l][mem_2] == j)))
{
str += "Знайдено маршрут (";
for(int h = 0; h < 3; h++)
t[h] = 0;
if(k < 9)
t[0] = k+1 + '0';
if(k > 8)
{
t[0] = (k+1)/10 + '0';
t[1] = (k+1)%10 + '0';
}
str += t;
str += ", ";
for(int h = 0; h < 3; h++)
t[h] = 0;
if(l < 9)
t[0] = l+1 + '0';
if(l > 8)
{
t[0] = (l+1)/10 + '0';
t[1] = (l+1)%10 + '0';
}
str += t;
str += ") з 1 пересадкою - ";
for(int g = mem_0; g <= kk; g++)
{