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

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

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

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

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

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

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

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

Москва-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 Кб дисковой памяти.

# 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)

=(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 с.