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

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

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

им.В.Г. Белинского

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


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

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

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

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

Выполнил: ст. гр. МП-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. Контрольный пример

/>


/>


Заключение

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


Приложения/> <td/> />
  Приложение А

/>

/> /> /> /> /> /> /> /> /> /> /> /> /> <td/>   /> /> /> /> />

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

  /> /> <td/> /> /> /> /> /> />   /> /> <td/>   /> /> /> /> /> /> />

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

  /> /> /> /> /> /> />  


  Приложение Б

# 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.        С.В. Самуйлов “Алгоритмы поиска и сортировки”. — Пенза: изд-во «ПГУ»,2008 — 36с.

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

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

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

 

еще рефераты
Еще работы по информатике, программированию