Міністерство Освіти Російської Федерації
Московський Державний Педагогічний Університет
Кафедра прикладної математики-інформатики
Курсова робота
з дисципліни «Програмування»
Тема: «Виявлення функціональної залежності
в масиві даних »
Москва-2009
Введення
В даний час формалізовані багато завдань, що виникають у процесі людської діяльності, і все ширше здійснюється їх автоматизація на основі засобів обчислювальної техніки.
Одним з методів формалізації є алгоритмічне рішення завдань. Ефективність алгоритмічного методу полягає в тому, що він дозволяє легко автоматизувати рішення задачі шляхом складання програми на одному з мов програмування.
Простим у вивченні, добре формалізованим і широко поширеним мовою програмування є мова C + +. Його формальна строгість, висока потужність конструкцій оголошення та обробки даних, можливості об'єктного програмування, а також загальна спрямованість на навчання методам програмування вигідно виділяють цю мову серед інших мов програмування високого рівня.
З ходом науково-технічного прогресу людство все більше потребує зручному способі зберігання і пошуку даних.
Самоорганізуються списки (таблиці) забезпечують способи найбільш ефективного зберігання, пошуку і найкращою обробки даних. Саме тому самоорганізуються таблиці набувають все більшого значення в сучасному світі. В умовах глобальної комп'ютеризації самоорганізуються таблиці з чинника вузькопрофесійного призначення переходять на більш глобальний і, більше того, навіть побутовий рівень!
У цій роботі наводиться одна з реалізацій найпростішої самоорганізується таблиці, з самоорганізацією методом транспозиції.
1. Формальна постановка задачі
Визначити функціональну залежність у масиві даних.
2. Опис алгоритму
Програма складається з одного головного модуля, в якому використовуються оператори стандартних бібліотек:
· 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 Кб дискової пам'яті.
Для завершення роботи з програмою необхідно натиснути клавішу 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);
}
2. Б. Карпов, Т. Баранова «С + + Спеціальний довідник». - С-Петербург: Изд-во «Пітер», 2009 - 480 с.
3. В.М. Ліньков, В.В. Дрождин «Програмування на мові паскаль» Пенза, ПДПУ ім. В.Г. Бєлінського, 2007 - 70.
4. В.В. Подбельський, С.С. Фомін «Програмування на мові С + +» - Москва, 2008-600 с.
5. Уоллес Вонг, «Основи програмування для чайників» 2002 - 336 с.
6. О.Л. Голіцина, І.І. Попов «Основи алгоритмізації та програмування», 2008-446 с.
Московський Державний Педагогічний Університет
Кафедра прикладної математики-інформатики
Курсова робота
з дисципліни «Програмування»
Тема: «Виявлення функціональної залежності
в масиві даних »
Москва-2009
Введення
В даний час формалізовані багато завдань, що виникають у процесі людської діяльності, і все ширше здійснюється їх автоматизація на основі засобів обчислювальної техніки.
Одним з методів формалізації є алгоритмічне рішення завдань. Ефективність алгоритмічного методу полягає в тому, що він дозволяє легко автоматизувати рішення задачі шляхом складання програми на одному з мов програмування.
Простим у вивченні, добре формалізованим і широко поширеним мовою програмування є мова 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.
Контрольний приклад
Висновок
На даному тестовому наборі програма функціонує успішно. Поставлена задача виконана повністю, оформлення відповідає вимогам ЕСПД.
mt = m |
vivod_1 |
analiz_1 |
vivod_2 |
create_domain |
tabl |
початок |
відкриття файлу |
new_table |
| |||||||||||||||||||
k [j + i - 1] |
j = j + Lt |
2 |
1 |
Lt = 1 .. m |
j = kn [Lt - 1] + 1 |
Цикл 1 |
i = 1 .. Lt |
Цикл 1 |
kk = 1 |
| |||||||||||||||||
кінець |
# 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);
}
Список використаної літератури
1. С.В. Самуйло «Алгоритми пошуку і сортування». - Львів: вид-во «ПГУ», 1998 - 36 с.2. Б. Карпов, Т. Баранова «С + + Спеціальний довідник». - С-Петербург: Изд-во «Пітер», 2009 - 480 с.
3. В.М. Ліньков, В.В. Дрождин «Програмування на мові паскаль» Пенза, ПДПУ ім. В.Г. Бєлінського, 2007 - 70.
4. В.В. Подбельський, С.С. Фомін «Програмування на мові С + +» - Москва, 2008-600 с.
5. Уоллес Вонг, «Основи програмування для чайників» 2002 - 336 с.
6. О.Л. Голіцина, І.І. Попов «Основи алгоритмізації та програмування», 2008-446 с.