Міністерство Освіти Російської Федерації
Пензенський Державний Педагогічний Університет
ім.В.Г. Бєлінського
Кафедра прикладної математики-інформатики
Курсова робота
з дисципліни "Програмування"
Тема: "Виявлення функціональної залежності
в масиві даних "
Виконав: ст. гр. МП-11
Перевірив: к. т. н., Доцент
Пенза-2008
Зміст
Введення
Основний Розділ
1. Формальна постановка задачі
2. Опис алгоритму
3. Опис програми
4. Інструкція користувачеві
5. Контрольний приклад
Висновок
Програми
Список використаної літератури
Введення
В даний час формалізовані багато завдань, що виникають у процесі людської діяльності, і все ширше здійснюється їх автоматизація на основі засобів обчислювальної техніки.
Одним з методів формалізації є алгоритмічне рішення завдань. Ефективність алгоритмічного методу полягає в тому, що він дозволяє легко автоматизувати рішення задачі шляхом складання програми на одному з мов програмування.
Простим у вивченні, добре формалізованим і широко поширеним мовою програмування є мова C + +. Його формальна строгість, висока потужність конструкцій оголошення та обробки даних, можливості об'єктного програмування, а також загальна спрямованість на навчання методам програмування вигідно виділяють цю мову серед інших мов програмування високого рівня.
З ходом науково-технічного прогресу людство все більше потребує зручному способі зберігання і пошуку даних.
Самоорганізуються списки (таблиці) забезпечують способи найбільш ефективного зберігання, пошуку і найкращою обробки даних. Саме тому самоорганізуються таблиці набувають все більшого значення в сучасному світі. В умовах глобальної комп'ютеризації самоорганізуються таблиці з чинника вузькопрофесійного призначення переходять на більш глобальний і, більше того, навіть побутовий рівень!
У цій роботі наводиться одна з реалізацій найпростішої самоорганізується таблиці, з самоорганізацією методом транспозиції.
Основний Розділ
1. Формальна постановка задачі
Визначити функціональну залежність у масиві даних.
2. Опис алгоритму
Алгоритм обумовленою функціональної залежності складається з одного головного модуля і декількох модулів. У головному модулі знаходиться 3 циклу. У головному модулі створюється файл, в якому зберігається вся інформація. Висновок інформації проводиться у файлі "dat. Txt".
3. Опис програми
Програма складається з одного головного модуля, в якому використовуються оператори стандартних бібліотек:
stdio. h.
stdlib. h
conio. h
math. h
time. h
io. h
dos. h
string. h
sys \ stat. h
Для зберігання інформації у програмі створюється файл "dat. Txt".
Атрибут a функціонально визначає атрибут b, якщо кожному значенню атрибута a відповідає не більше одного значення атрибуту b.
4. Інструкція користувачеві
Програма призначена для визначення функціональної залежності в масиві даних.
Програма функціонує на IBM PC / AT 386 і вище і для нормальної роботи вимагає 1 Мб оперативної пам'яті і 15 Кб дискової пам'яті.
Для запуску програми необхідно запустити на виконання файл kursovic. Exe, а потім, для перегляду результату, відкрити файл dat. Txt.
Вхідні дані заповнюються в програмі випадковими цілими числах.
Для завершення роботи з програмою необхідно натиснути клавішу escape.
5. Контрольний приклад
Висновок
На даному тестовому наборі програма функціонує успішно. Поставлена задача виконана повністю, оформлення відповідає вимогам ЕСПД.
Програми
Додаток А
Додаток Б
# Include <stdio. h>
# Include <conio. h>
# Include <math. h>
# Include <stdlib. h>
# Include <time. h>
# Include <io. h>
# Include <dos. h>
# Include <string. h>
# Include <SYS \ STAT. H>
int const m = 6, n = 10, Ld = m * n / 4, Lk = m * 5;
unsigned short kk = 0;
int a [n-1] [m-1];
int b [n-1] [m-1];
unsigned short k [Lk];
unsigned short kn [m];
unsigned short d [Ld] [2];
unsigned short dn [m] [2];
unsigned short kt [m +1];
unsigned short Lt;
unsigned short mt;
/ / ------------------- / /
unsigned short i, j;
void tabl ()
{
int i;
randomize ();
for (i = 0; i <n; i + +)
for (j = 0; j <m; j + +)
{
a [i] [j] = rand ()% (n + m);
if (a [i] [j] <0)
a [i] [j] = 0;
}
}
void vivod_1 ()
{
FILE * f;
int i, j;
f = fopen ("dat. txt", "a +");
fprintf (f, "matrica \ n");
for (i = 1; i <= m; i + +)
fprintf (f, "a% 1d", i);
fprintf (f, "\ n");
for (i = 0; i <n; i + +)
{
for (j = 0; j <m; j + +)
fprintf (f, "% 3d", a [i] [j]);
fprintf (f, "\ n");
}
fprintf (f, "\ n");
fclose (f);
}
void vivod_2 ()
{
FILE * f;
int i, j;
f = fopen ("dat. txt", "a +");
fprintf (f, "new_matrica \ n");
for (i = 1; i <= m; i + +)
fprintf (f, "a% 1d", dn [i] [1]);
fprintf (f, "\ n");
for (i = 0; i <n; i + +)
{
for (j = 0; j <m; j + +)
if (b [i] [j]> 0)
fprintf (f, "% 3d", d [b [i] [j] + dn [j-1] [2]] [1]);
else
fprintf (f, "% 3d", b [i] [j]);
fprintf (f, "\ n");
}
fprintf (f, "\ n");
fclose (f);
}
/ / ------------------ / /
void create_domain ()
{
FILE * f;
unsigned short i, j, ii, jj, num;
unsigned short dt [n-1] [1];
f = fopen ("dat. txt", "a +");
dn [0] [2] = 0;
for (num = 1; num <m; num + +)
{
dn [num] [2] = dn [num-1] [2];
j = 0;
for (i = 0; i <n; i + +)
if (a [i] [num]! = 0)
{
ii = 1;
while ((ii <= j) & & (dt [ii] [1] <a [i] [num]))
ii = ii +1;
if (ii <= j)
{
if (a [i] [num] = dt [ii] [1])
dt [ii] [2] = dt [ii] [2] +1;
else
{
for (jj = j; jj> ii; jj -)
{
dt [jj +1] [1] = dt [jj] [1];
dt [jj +1] [2] = dt [jj] [2];
}
j = j +1;
dt [ii] [1] = a [i] [num];
dt [ii] [2] = 1;
}
}
else
{
j = j +1;
dt [j] [1] = a [i] [num];
dt [j] [2] = 1;
}
}
for (i = 0; i <j; i + +)
if (dt [i] [2]> 1)
{
dn [num] [2] = dn [num] [2] +1;
d [dn [num] [2]] [1] = dt [i] [1];
d [dn [num] [2]] [2] = dt [i] [2];
}
fprintf (f, "dom =% 1d", num);
for (i = dn [num-1] [2]; i <dn [num] [2]; i + +)
for (j = 0; j <= 2; j + +)
fprintf (f, "", d [i] [j]);
fprintf (f, "\ n");
}
fclose (f);
}
void first_key ()
{
unsigned short i;
for (i = 0; i <Lt; i + +)
kt [i] = i;
}
void next_key ()
{
unsigned short i, j;
j = Lt;
while ((j> 0) & & (kt [j]> = mt-Lt + j))
j = j-1;
if (j> 0)
{
kt [j] = kt [j] +1;
for (i = j +1; i <Lt; i + +)
kt [i] = kt [i-1] +1;
}
else
kt [1] = 0;
}
void new_table ()
{
unsigned short i, j, ii;
for (i = 1; i <n; i + +)
for (j = 1; j <mt; j + +)
if (a [i] [dn [j] [1]] = 0)
b [i] [j] =- 1;
else
{
ii = dn [j-1] [2] +1;
while ((ii <= dn [j] [2]) & & (a [i] [dn [j] [1]]> d [ii] [1]))
ii = ii +1;
if ((ii <= dn [j] [2]) & & (a [i] [dn [j] [1]] = d [ii] [1]))
b [i] [j] = ii-dn [j-1] [2];
else
b [i] [j] = 0;
}
}
void analiz_1 ()
{
unsigned short i, j;
kn [0] = 0;
kn [1] = 0;
j = 0;
for (i = 1; i <m; i + +)
if (dn [i] [2] = dn [j] [2])
{
kn [1] = kn [1] +1;
k [kn [1]] = i;
}
else
{
j = j +1;
dn [j] [1] = i;
dn [j] [2] = dn [i] [2];
}
mt = j;
}
void analiz_n ()
{
unsigned short mm [m-1];
unsigned short i, j, ii, jj;
char yes_key;
unsigned long s [8];
for (i = 1; i <mt; i + +)
mm [i] = dn [i] [2]-dn [i-1] [2];
kn [2] = kn [1];
for (Lt = 2; Lt <mt; Lt + +)
{
first_key ();
do
{
yes_key = 1;
i = 2;
while (yes_key & & (i <Lt))
{
j = kn [i-1] +1;
while (yes_key & & (j <= kn [i]))
{
jj = j;
ii = 1;
while (yes_key & & (jj-j <i) & & (ii <= Lt))
{
if (k [jj] <kt [ii]) {
j + = i;
break;
}
else
if (k [jj] = kt [ii])
{
jj = jj +1;
ii = ii +1;
if (jj-j> = i)
yes_key = 0;
}
else
if (Lt-ii <i + j-jj)
{
j + = i;
break;
}
else
ii = ii +1;
}
}
i = i +1;
}
if (yes_key)
{
i = 1;
for (i = 0; i <8; i + +)
s [i] = 0;
while (yes_key & & (i <= n))
{
j = 1;
ii = 0;
while ((j <= Lt) & & (b [i] [kt [j]]> 0))
{
ii = ii * mm [kt [j]] + b [i] [kt [j]] -1;
j = j +1;
}
i = i +1;
if (j> Lt)
{
if (s [ii>> 5] & (1 <<(ii & 0x1F)))
yes_key = 0;
else
s [ii>> 5] | = (1 <<(ii & 0x1F));
}
}
if (yes_key)
{
kk = kk +1;
for (i = 1; i <Lt; i + +)
{
k [kn [Lt] + i] = kt [i];
}
kn [Lt] = kn [Lt] + Lt;
}
}
next_key ();
} While (kt [1] = 0);
kn [Lt +1] = kn [Lt];
for (i = 2; i <mt; i + +)
for (j = kn [i-1] +1; j <kn [i]; j + +)
k [j] = dn [k [j]] [1];
}
}
/ / ------------------ / /
void main ()
{
FILE * f;
clrscr ();
int handle;
handle = creat ("d: \ \ Kursovik \ \ dat. txt", S_IREAD | S_IWRITE);
f = fopen ("dat. txt", "a +");
mt = m;
tabl ();
vivod_1 ();
fprintf (f, "\ n");
create_domain ();
analiz_1 ();
new_table ();
vivod_2 ();
analiz_n ();
fprintf (f, "\ n");
fprintf (f, "Keys \ n");
kk = 1;
for (Lt = 1; Lt <= m; Lt + +)
{
fprintf (f, "Lt =% 1d \ n", Lt);
j = kn [Lt-1] +1;
while (j <= kn [Lt])
{
for (i = 1; i <Lt; i + +)
fprintf (f, "% 1d", k [j + i-1]);
fprintf (f, "\ n");
j = j + Lt;
}
}
fclose (f);
}
Список використаної літератури
С.В. Самуйло "Алгоритми пошуку і сортування". - Львів: вид-во "ПГУ", 2008 - 36с.
Б. Карпов, Т. Баранова "С + + Спеціальний довідник". - С-Петербург: Изд-во "Пітер", 2008 - 480 с.
В.М. Ліньков, В.В. Дрождин "Програмування на мові паскаль" Пенза, ПДПУ ім.В.Г. Бєлінського, 2007 - 70.
В.В. Подбельський, С.С. Фомін "Програмування на мові С + +" - Москва, 2008-600С.