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

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

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

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

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

По дисциплине “Программирование”

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

В массиве данных”

Москва-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. Инструкция пользователю

Программа предназначена для определения функциональной зависимости в массиве данных.

Программа функционирует на IBMPC/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);

}

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

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

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

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

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

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

6.О. Л. Голицына, И. И. Попов “Основы алгоритмизации и программирования”, 2008-446 с.


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