Министерство Образования Российской Федерации
Московский Государственный Педагогический Университет
Кафедра прикладной математики-информатики
Курсовая работа
по дисциплине «Программирование»
Тема: «Выявление функциональной зависимости
в массиве данных»
Москва-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.
/>
Заключение
На данном тестовом наборе программа функционирует успешно. Поставленная задача выполнена полностью, оформление соответствует требованиям ЕСПД.
/>Приложение А.
/>
/>
/>
/>
/>
/>/>
/>
/>
/>
/>/>
/>
/>
/>
/>
/>
/>
/>/>
/>
/>
/>/>
/>/>
/>
/>
/>
/>/>/>/>
/>/>
/>/>
/>
/>
/>/>/>
/>/>/>/>
/>
/>
/>/>
/>/>/>
/>
/>
/>
/>/>
/>/>
/>
/>Приложение Б--PAGE_BREAK--
# include
# include
# include
# include
# include
# include
# include
# include
# include
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
for (j=0; j
{
a[i] [j]=rand()%(n+m);
if (a[i] [j]
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
fprintf (f,» a % 1d», i);
fprintf (f, "\n»);
for (i=0; i
{
for (j=0; 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
fprintf (f,» a % 1d», dn[i] [1]);
fprintf (f, "\n»);
for (i=0; i
{
for (j=0; 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
{
dn[num] [2]=dn [num-1] [2]; продолжение
--PAGE_BREAK--
j=0;
for (i=0; i
if (a[i] [num]!=0)
{
ii=1;
while ((ii
ii=ii+1;
if (ii
{
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
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
for (j=0; j
fprintf (f, "», d[i] [j]);
fprintf (f, "\n»);
}
fclose(f);
}
void first_key()
{
unsigned short i;
for (i=0; 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
kt[i]=kt [i-1]+1;
}
else
kt[1]=0;
}
void new_table()
{
unsigned short i, j, ii;
for (i=1; i
for (j=1; j
if (a[i] [dn[j] [1]]=0)
b[i] [j]=-1;
else
{
ii=dn [j-1] [2]+1;
while ((iid[ii] [1]))
ii=ii+1;
if ((ii
b[i] [j]=ii-dn [j-1] [2];
else
b[i] [j]=0;
}
}
void analiz_1 ()
{
unsigned short i, j; продолжение
--PAGE_BREAK--
kn[0]=0;
kn[1]=0;
j=0;
for (i=1; 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
mm[i]=dn[i] [2] – dn [i-1] [2];
kn[2]=kn[1];
for (Lt=2; Lt
{
first_key();
do
{
yes_key=1;
i=2;
while (yes_key && (i
{
j=kn [i-1]+1;
while (yes_key && (j
{
jj=j;
ii=1;
while (yes_key && (jj-j
{
if (k[jj]
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
{
j+=i;
break;
}
else
ii=ii+1;
}
}
i=i+1;
}
if (yes_key)
{
i=1;
for (i=0; i
s[i]=0;
while (yes_key && (i
{
j=1;
ii=0;
while ((j0))
{
ii=ii*mm [kt[j]]+b[i] [kt[j]] – 1;
j=j+1;
}
i=i+1;
if (j>Lt)
{
if (s [ii>>5]&(1
yes_key=0;
else
s [ii>>5]|=(1
} продолжение
--PAGE_BREAK--
}
if (yes_key)
{
kk=kk+1;
for (i=1; 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
for (j=kn [i-1]+1; 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
{
fprintf (f,» Lt=%1d\n», Lt);
j=kn [Lt-1]+1;
while (j
{
for (i=1; 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 с.