Выявление функциональной зависимости в массиве данных

Министерство Образования Российской Федерации

Московский Государственный Педагогический Университет

Кафедра прикладной математики-информатики

















Курсовая работа

по дисциплине «Программирование»



Тема: «Выявление функциональной зависимости

в массиве данных»





















	

	

	

	Москва-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.



Контрольный пример

5. 









Заключение



На данном тестовом наборе программа функционирует успешно. Поставленная задача выполнена полностью, оформление соответствует требованиям ЕСПД.








Приложение А.









САМООРГАНИЗАЦИЯ  МАССИВА













начало









открытие 

   файла







mt=m













tabl



vivod_1

















 create_domain









analiz_1





new_table











vivod_2



















 2

 analiz_n





 1























kk = 1







j = kn[Lt – 1] + 1

Lt = 1..m



















i = 1..Lt

Цикл 1

















k[j + i – 1]







j = j + Lt















Цикл 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);

}


Список использованной литературы



		С.В. Самуйлов «Алгоритмы поиска и сортировки». – Пенза: изд-во «ПГУ», 1998 – 36 с.

		Б. Карпов, Т. Баранова «С++ Специальный справочник». – С-Петербург: Изд-во «Питер», 2009 – 480 с.

		В.М. Линьков, В.В. Дрождин «Программирование на языке паскаль» Пенза, ПГПУ им. В.Г. Белинского, 2007 – 70.

		В.В. Подбельский, С.С. Фомин «Программирование на языке С++» – Москва, 2008–600 с.

		Уоллес Вонг, «Основы программирования для чайников» 2002 – 336 с.

		О.Л. Голицына, И.И. Попов «Основы алгоритмизации и программирования», 2008–446 с.