Отчет
По лабораторной работе № 1 “ Поиск битового образа”
курса “Основы информатики”
Студента группы А1-05
Гельмана Ю. В.
Москва 2011
Содержание
1. | Формулировка задачи | 3 |
2. | Представление данных и ограничения | 4 |
3. | Описание функций программы | 5 |
3.1. | Иерархическая схема | 5 |
3.2. | Прототипы функций | 6 |
4. | Алгоритм решения задачи | 7 |
5. | Тестовые наборы данных и реакции | 12 |
6. | Исходный текст программы | 13 |
7. | Описание тестирования программы | 18 |
8. | Анализ работы по решению задачи | 24 |
Формулировка задачи
Составить алгоритм и написать на языке Си программу, осуществляющую следующие действия.
Вводится последовательность строк символов не длиннее 16 символов. Каждая строка считается числом (кодом) в двоичной системе и после ввода преобразуется в unsigned int. Допустимые символы в строке: "0", "1". Первая строка длиной не более 5 символов (битов) задает битовый образ для поиска в последующих строках. Максимальное количество строк равно 8. Для каждой входной строки, начиная со 2-й, попытаться найти битовый образ, задаваемый 1-й строкой (а не подстроку в строке символов), и подсчитать количество вхождений образа в 16-битовое слово (unsigned int). Сформировать также статистическую информацию.
|
|
Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
Представление данных и ограничения
Таблица 2.1. Данные и ограничения
Имя константы или переменной | Вид | Тип | Глобальная или локальная в функции | Область допустимых значений | Особые ситуации и реакции на них |
dlina | константа | int | глобальная | 20 | Максимальная длинна строки - берется с запасом, т.к. в строку могут входит дополнительные символы, такие как конец строки и т.д. |
b[8] | массив | unsigned int | глобальная | unsigned int | Двоичные коды строк. |
l[8] | массив | unsigned int | глобальная | l[i]<=16 | Длинны строк. |
c[7] | массив | unsigned int | глобальная | unsigned int | Количество вхождений образа в строки. |
maska | переменная | unsigned int | глобальная | unsigned int | Начальное число, вводимое пользователем. Выход за ОДЗ невозможен. |
m | переменная | unsigned int | глобальная | От 2 до 8 | Количество строк. |
d[dlina] | промежуточная переменная | char | Readwritefile Readwritecons | char | Числа в виде строк символов. |
r | промежуточная переменная | int | Readwritefile Readwritecons | int | Счетчик значения двоичного разряда в 10-ой СС. |
e | промежуточная переменная | int | raschet | int | Текущая обрабатываемая строка. |
obr | промежуточная переменная | int | raschet | 2^5 | Битовый образ первой строки. |
|
|
Описание функций программы
Иерархическая схема
main - основная функция
printf - стандартный форматный вывод
scanf - стандартный форматный ввод
readwritefile – ввод и первичная обработка необходимых значений из файла
fopen – открытие файла для чтения
fgets – считывание символа из файла
strlen – нахождение длинны строки
printf - стандартный форматный вывод
printf - стандартный форматный вывод
fclose – закрытие файла
readwritecons - ввод и первичная обработка необходимых значений с клавиатуры
printf - стандартный форматный вывод
scanf - стандартный форматный ввод
fgets – считывание символа
mask – создание маски битового образа
raschet – подсчет количества вхождений битового образа в каждую из строк
printf - стандартный форматный вывод
vivod – вывод данных на экран или в файл
printf - стандартный форматный вывод (14 вызовов)
fopen – открытие файла для записи
fclose – закрытие файла
printf - стандартный форматный вывод
scanf - стандартный форматный ввод
Прототипы функций
Void readwritefile(b, l, m)
/*****
Вход: | Значение ‘f’ переменной k. |
Действие: | Считывает из файла строки в массив char d[dlina]. Длину строки записывает в массив int l[8]. Преобразует строки d в соответствующую ей ячейку массива int b[8]. Считает количество строк m. |
Выход: | Массивы b, l и переменная m. |
*****/
;
Void readwritecons(b, l, m);
/*****
Вход: | Значение ‘c’ переменной k. |
Действие: | Считывает с клавиатуры строки в массив char d[dlina]. Длину строки записывает в массив int l[8]. Преобразует строки d в соответствующую ей ячейку массива int b[8]. Считает количество строк m. |
Выход: | Массивы b, l и переменная m. |
*****/
;
Void mask(l, maska);
/*****
Вход: | Длинна первой строки(битовый образ). |
Действие: | Создает число из всех единиц единиц, количество которых равно количеству цифр в двоичной записи первого числа (маску). |
Выход: | Переменная maska. |
*****/
;
Void raschet(b, l, c, m, maska);
/*****
Вход: | Массивы b, l, maska и переменная m. |
Действие: | Подсчитывает количество вхождений образа в строки и записывает в массив с. |
Выход: | Массив с. |
*****/
;
Void vivod(b, l, c, m, k);
/*****
Вход: | Массивы b, l, c и переменнst m и k. |
Действие: | Выводит все полученные в ходе вычислений данные на экран или в файл. |
Выход: | Нет. |
*****/
;
Алгоритм решения задачи
«с» |
main: |
«f» |
Вход |
readwritefile |
readwritecons |
scanf |
Mask |
Выход |
raschet |
vivod |
Тестовые наборы данных и реакции
Таблица 5.1. Тест реакции для чисел.
№ теста | Входные данные | Результат работы программы | Результат проверки |
1 | 0101 1010101 100101 | B Vsevo vvedeno 3 strok i 17 simvolov. Minimalnaia dlinna stroki 4, maksimalnaia - 7. Kod pervoi stroki - 5. Kod stroki 2 - 85. 2 vhogdenii obraza. Kod stroki 3 - 37. 1 vhogdenii obraza. Maksimalnoe vhogdenie obraza 2 ras v stroke 2. | верно |
2 | 10101 1010101 1001010 1111000011110000 1010101010101010 111010101 101111101 | Vsevo vvedeno 7 strok i 69 simvolov. Minimalnaia dlinna stroki 5, maksimalnaia - 16. Kod pervoi stroki - 21. Kod stroki 2 - 85. 2 vhogdenii obraza. Kod stroki 3 - 74. Net vhogdenii obraza. Kod stroki 4 - 61680. Net vhogdenii obraza. Kod stroki 5 - 43690. 6 vhogdenii obraza. Kod stroki 6 - 469. 2 vhogdenii obraza. Kod stroki 7 - 381. Net vhogdenii obraza. Maksimalnoe vhogdenie obraza 6 ras v stroke 5.Maksimalnoe vhogdenie obraza 6 ras v stroke 5. | верно |
3 | 10101 1010101 001001010 1111111111111111 | Vsevo vvedeno 4 strok i 37 simvolov. Minimalnaia dlinna stroki 5, maksimalnaia - 16. Kod pervoi stroki - 21. Kod stroki 2 - 85. 2 vhogdenii obraza. Kod stroki 3 - 74. Net vhogdenii obraza. Kod stroki 4 - 65535. Net vhogdenii obraza. Maksimalnoe vhogdenie obraza 2 ras v stroke 2. | верно |
Исходный текст программы
Исходный текст программы находится в файле obras.c
#include <stdio.h>
#pragma hdrstop
#include <string.h>
#include <tchar.h>
//---------------------------------------------------------------------------
#pragma argsused
#define dlina 20
void readwritefile(int* b, int* l, int* m)
/*****
Вход: | Значение ‘f’ переменной k. |
Действие: | Считывает из файла строки в массив char d[dlina]. Длину строки записывает в массив int l[8]. Преобразует строки d в соответствующую ей ячейку массива int b[8]. Считает количество строк m. |
Выход: | Массивы b, l и переменная m. |
*****/
|
|
{
int i = 0, r;
int j;
char d[dlina];
FILE *f;
f = fopen("file.txt", "rb");
while (!feof(f))
{
fgets(d, dlina, f);
if (feof(f))
{
l[i] = strlen(d);
} else
{
l[i] = strlen(d)-2;
}
r = 1;
b[i] = 0;
for (j = l[i]; j > 0; --j)
{
b[i] += r * (d[j-1]-48);
r *= 2;
}
printf("Stroka: %s ", d);
printf("kod stroki: %d.\n", b[i]);
++i;
}
fclose(f);
m[0] = i;
}
void readwritecons(int* b, int* l, int* m)
/*****
Вход: | Значение ‘c’ переменной k. |
Действие: | Считывает с клавиатуры строки в массив char d[dlina]. Длину строки записывает в массив int l[8]. Преобразует строки d в соответствующую ей ячейку массива int b[8]. Считает количество строк m. |
Выход: | Массивы b, l и переменная m. |
*****/
{
int i, r, j, h;
char d[dlina];
printf("Vvedite chislo strok.");
scanf("%d", &h);
gets(d);
for (i = 0; i < h; i++)
{
gets(d);
l[i] = strlen(d);
r = 1;
b[i] = 0;
for (j = l[i]; j > 0; --j)
{
b[i] += r * (d[j-1]-48);
r *= 2;
}
}
m[0] = i;
}
void mask(int* l, int* maska)
/*****
Вход: | Длинна первой строки(битовый образ). |
Действие: | Создает число из всех единиц единиц, количество которых равно количеству цифр в двоичной записи первого числа (маску). |
Выход: | Переменная maska. |
*****/
{
int i, j;
j = 1;
maska[0] = 1;
for (i = 1; i < l[0]; i++) {
j *= 2;
maska[0] += j;
}
}
void raschet(int* b, int* l, int* c, int* m, int* maska)
/*****
Вход: | Массивы b, l, maska и переменная m. |
Действие: | Подсчитывает количество вхождений образа в строки и записывает в массив с. |
Выход: | Массив с. |
*****/
{
int i, j, r, e, obr;
obr = b[0];
for (i = 1; i < (m[0]); i++)
{
e = b[i];
j = l[i];
c[i] = 0;
while ((e >= obr) && (j >= l[0]))
{
r = e & maska[0];
printf("%d ", r);
if (r == obr){ ++c[i];}
e = e >> 1;
--j;
}
}
}
void vivod(int* b, int* l, int* c, int* m, char* k)
Void vivod(b, l, c, m, k);
/*****
Вход: | Массивы b, l, c и переменнst m и k. |
Действие: | Выводит все полученные в ходе вычислений данные на экран или в файл. |
Выход: | Нет. |
*****/
|
|
;
{
int m1, m2, n, i, c1, c2;
n = l[0];
m1 = l[0];
m2 = l[0];
c1 = c[1];
c2 = 1;
for (i = 1; i < m[0]; i++) {
if (l[i] < m1) {m1 = l[i];}
if (l[i] > m2) {m2 = l[i];}
if (c[i] > c1) {c1 = c[i]; c2 = i;}
n += l[i];
}
printf("\nVsevo vvedeno %d strok i %d simvolov.\n", m[0], n);
printf("Minimalnaia dlinna stroki %d, maksimalnaia - %d.\n", m1, m2);
printf("Kod pervoi stroki - %d.\n", b[0]);
for (i = 1; i < m[0]; i++) {
printf("Kod stroki %d - %d. ", i + 1, b[i]);
if (c[i] == 0) {
printf("Net vhogdenii obraza.\n");
}else
{
printf("%d vhogdenii obraza.\n", c[i]);
}
}
printf("Maksimalnoe vhogdenie obraza %d ras v stroke %d.\n", c1, c2+1);
if (k = 'f') {
FILE *f;
f = fopen("file2.txt", "wt");
fprintf(f, "\nVsevo vvedeno %d strok i %d simvolov.\n", m[0], n);
fprintf(f, "Minimalnaia dlinna stroki %d, maksimalnaia - %d.\n", m1, m2);
fprintf(f, "Kod pervoi stroki - %d.\n", b[0]);
for (i = 1; i < m[0]; i++) {
fprintf(f, "Kod stroki %d - %d. ", i + 1, b[i]);
if (c[i] == 0) {
fprintf(f, "Net vhogdenii obraza.\n");
}else
{
fprintf(f, "%d vhogdenii obraza.\n", c[i]);
}
}
fprintf(f, "Maksimalnoe vhogdenie obraza %d ras v stroke %d.\n", c1, c2+1);
fclose(f);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int b[8], l[8], c[7], maska[1], m[1];
char k[1];
int k1;
printf("Vvedite \"f\" dla vvoda informacii is faila, \"c\" - dla vvoda s klaviatyri.\n");
scanf("%c", &k[0]);
if(k[0] == 'f')
{
readwritefile(b, l, m);
} else
{
readwritecons(b, l, m);
};
mask(l, maska);
raschet(b, l, c, m, maska);
vivod(b, l, c, m, k);
printf("Vvedite liboi simvol dlia zakritiia programi.\n");
scanf("%d", &k1);
return 0;
}