Министерство Образования Российской Федерации
Пензенский Государственный Педагогический Университет
им.В.Г. Белинского
Кафедра прикладной математики-информатики
Курсовая работа
по дисциплине "Программирование"
Тема: "Выявление функциональной зависимости
в массиве данных"
Выполнил: ст. гр. МП-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
sysstat. 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 <SYSSTAT. 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,"matrican");
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_matrican");
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");
}
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: Kursovikdat. 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," Keysn");
kk=1;
for (Lt=1; Lt<=m; Lt++)
{
fprintf (f," Lt=%1dn",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с.