Результаты экзамена по курсу
Алгоритмы и алгоритмические языки.
Зима 2013г.
|
№ |
Фамилия, имя |
1В-с |
2В-с |
Задача |
Оценка |
|
01 |
Аганов Арсений |
+- |
-+ |
+- |
4(хор) |
|
02 |
Айрапетов Эдгар |
-+ |
-+ |
+. |
3(удовл) |
|
03 |
Алимгулов Наиль |
+ |
+ |
+ |
5(отл) |
|
04 |
Белова Александра |
-+ |
-+ |
+ |
3(удовл) |
|
05 |
Бурачковский Андрей |
|
|
|
|
|
06 |
Быстрыгова Анастасия |
|
|
|
|
|
07 |
Вагапов Рашид |
+- |
+. |
+- |
4(хор) |
|
08 |
Волков Сергей |
|
|
|
|
|
09 |
Ермаков Дмитрий |
+ |
+ |
+- |
5(отл) |
|
10 |
Ибрагимов Бобур |
-+ |
-+ |
+. |
|
|
11 |
Ибрагимов Ислам |
|
|
|
|
|
12 |
Исламов Шохрух |
+ |
+ |
0 |
4(хор) |
|
13 |
Каримов Тимур |
-+ |
+ |
+- |
4(хор) |
|
14 |
Ким Александр |
-+ |
+ |
+ |
|
|
15 |
Клименко Алексей |
|
|
|
|
|
16 |
Кодиров Улугбек |
+ |
+ |
+ |
5(отл) |
|
17 |
Корабаева Фируза |
+ |
+ |
+- |
5(отл) |
|
18 |
Лернер Владлен |
+ |
+- |
+ |
5(отл) |
|
19 |
Лыгин Денис |
+ |
+ |
+ |
5(отл) |
|
20 |
Маханов Владимир |
-+ |
+. |
+. |
4(хор) |
|
21 |
Меликянц Карэн |
|
|
|
|
|
22 |
Михеева Виктория |
|
|
|
|
|
23 |
Павлов Евгений |
-+ |
-+ |
+- |
3(удовл) |
|
24 |
Пак Илья |
+. |
+ |
+ |
5(отл) |
|
25 |
Пак Руслан |
0 |
0 |
+- |
3(хор) |
|
26 |
Пономаренко Бронеслава |
-+ |
-+ |
+- |
3(хор) |
|
27 |
Сагатов Шухрат |
+ |
+. |
+ |
5(отл) |
|
28 |
Саматова Воделина |
|
|
|
|
|
29 |
Солиев Бехзод |
+ |
+ |
+. |
5(отл) |
|
30 |
Фазлыев Руслан |
-+ |
+ |
+. |
4(хор) |
|
31 |
Халиков Александр |
-+ |
+. |
+- |
4(хор) |
|
32 |
Хамидов Акмаль |
-+ |
-+ |
+ |
3(хор) |
|
33 |
Хикматуллаев Акмаль |
|
|
|
|
|
34 |
Ходжабекова Шахноза |
-+ |
-+ |
+- |
3(хор) |
|
35 |
Цветиков Евгений |
-+ |
-+ |
-+ |
3(хор) |
|
36 |
Чжен Елена |
- |
-+ |
+- |
3(хор) |
|
37 |
Шабанова Юлия |
+ |
+ |
+ |
5(отл) |
|
38 |
Шульгина Екатерина |
+ |
- |
+ |
4(хор) |
|
39 |
Яковлев Тимур |
+ |
+ |
+ |
5(отл) |
|
40 |
Яснопольский Феликс |
|
|
|
|
|
41 |
Аганов Арсений |
|
|
|
|
|
42 |
Айрапетов Эдгар |
|
|
|
|
У вас есть пара дней на исправление каких-то непоняток (на апелляцию). Безусловно, я мог где-то ошибиться и как-то не туда посмотреть или что-то не заметить.
Общие замечания по задачам
Откуда такая любовь к функции fscanf при работе с текстом? В задачах с #define лучше бы было что-то вроде следующего:
{char
str[512],word1[512],word2[512]; FILE *f;
…
while(fgets(str,512,f))
{
if(sscanf(str,”%s
%s”,word1,word2)==2 && strcmp(word1,”#define”)==0)
{//word2 – требуемое имя
…
}
}
Здесь, конечно, есть проблема с длиной строки, но я бы ее игнорировал, а если бы было очень нужно, то смог бы написать функцию, вводящую строку из текстового файла, на которую не налагается ограничений на длину.
01_03
Билет 3.
Задача:
#include <stdio.h>
#include <stdlib.h>
int task(char *infile, char *outfile)
{
FILE
*in, *out;
int
i=0, j=0, k=0, l=0, len=0, f_letter=0, d_len = 7, flg = 1, temp=0;
char
string_in[3000], string_out[500], c, *d = "#define";
in
= fopen(infile, "r");
out
= fopen(outfile, "w");
if(in
!= NULL)
{
while(fscanf(in,
"%c", &c)==1)
string_in[i++]
= c;
len
= i;
for(i=0;
i<len; i++)
{
flg
= 1;
for(j=0,
l=i; l<len && j<d_len; j++, l++)
if(string_in[l]
!= d[j])
flg
= 0;
if(flg
== 1)
{
i
= l;
while(i<len
&& string_in[i] == ' ')
i++;
while(i<len
&& string_in[i] != ' ')
string_out[k++]
= string_in[i++];
i--;
string_out[k++]
= '\n';
}
}
for(i=0;
i<k; i++)
fprintf(out,
"%c", string_out[i]);
}
fclose(in);
fclose(in);
return
0;
}
Не нравится то, что весь текст файла вводится в одну строку. Во-первых, он может элементарно не поместится, во-вторых, в качестве разделителя нигде не проверяется символ перехода на следующую строку. Использовать ограничение на длину строки разумно (с использованием ф-ции fgets() ), а на длину файла – нет.
1) Сортировка
алгоритмом QuickSort. Teoрема о среднем времени работы алгоритма QSort.
2)Константы (целые,
вещественые, строковые, символьные).
Ответы:
1) Идея алгоритма
QSort.
Пусть мы сортируем
массив вещественных чисел (по возростанию).
Выбираем из массива
элемент с индексом n/2 (Медиану это
не медиана), где n-количество
элементов массива, следовательно мы разюиваем наш массив на 2 части. Затем
пробегаем по левой части массива и ищем элементы больше чем наша медиана и
запоминаем её в какую-то переменную, пусть будет "L". Затем пробегаем
по правой части и ищем элемент, который меньше медианы и запоминаем его в
переменную "R". Теперь когда мы нашли наши элементы L и R мы меняем
их местами. И прожолжаем эту операцию до тех пор пока мы не дойдем до нашей
медианы с обеих сторон таким образом
мы не подойдем к выбранному элементу ОДНОВРЕМЕННО. Назовем всю эту процедуру QSort.
После это мы
рассматриваем левую и правую части разбиения массива, рекурснивно применяя к
ним QSort до тех пор пока у нас не останется разбиение из 1 элемента. В конечном
итоге мы получим отсортированный массив.
Время работы этого
алгоритма в худщем случае равно O(N*N) где N это количество элементов
сортируемого массива.
Среднее время работы
алгоритма QuickSort равно Q(N*log2(N)), где N – количество элементов в сортируемом
массиве. Под средним временем подразумевается среднее время по всем
перестановкам любого массива входных данных длины N, состоящего из различных
элементов.
2) Константа — это
фиксированное значение, которое не может быть изменено программой. Константа
может относиться к любому базовому типу. Способ представления константы
определяется ее типом. Константы также называются литералами.
Символьные константы
заключаются в одинарные кавычки. В языке С определены многобайтовые (состоящие
из одного или более байт) и широкие (обычно длиной 16 бит) символы. Они
используются для представления символов языков, имеющих в своем алфавите много
букв. Многобайтовый символ записывается в одинарных кавычках, например, 'ху', а
широкий — с предшествующим символом L, например:
Целые константы
определяются как числа без дробной части. Например, 10 и -100 — это целые
константы. Константы в плавающем формате записываются как числа с десятичной
точкой, например, 11.123. Допускается также экспоненциальное представление
чисел (в виде мантиссы и порядка): 111.23е— 1.
По умолчанию
компилятор приписывает константе тип наименьшего размера, в ячейку которого
может уместиться константа. Но это правило имеет исключение: всем константам в
плавающем формате, даже самым маленьким, приписывается тип double (если,
конечно, они сюда помещаются).
Определение типов
констант по умолчанию является вполне удовлетворительным при разработке
большинства программ. Однако, используя суффикс, можно явно указать тип
числовой константы. Если после числа в плавающем формате стоит суффикс F, то
считается, что константа имеет тип float, а если L, то long double. Для целых
типов суффикс U означает unsigned, a L — long. Тип суффикса не зависит от
регистра, например, как F, так и f определяют константы типа float.
Шестнадцатеричные и
восьмеричные константы
Иногда удобнее
использовать не десятичную, а восьмеричную или шестнадцатеричную систему.
Шестнадцатеричная константа начинается с 0х, а восьмеричная — с 0.
Строковые константы
Язык С поддерживает
еще один тип констант, а именно — строковые. Строка — это последовательность
символов, заключенных в двойные кавычки.
Не следует путать
понятия строки и символа. Символьная константа заключается в одинарные кавычки.
Специальные символьные
константы
В языке С определены
специальные символьные константы.
Списано с адреса
http://cpp.com.ru/shildt_spr_po_c/02/0209.html
02_01
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int task_02_01(char* filename_in, char*
filename_out)
{
FILE
* f1;
FILE
* f2;
char
data[256], data2[256];
int
f=0,i,j,k;
if((f1=fopen(filename_in,"r"))==NULL)
return -1;
if((f2=fopen(filename_out,"w"))==NULL)
return -2;
while(fscanf(f1,"%s",data)==1)
{
for
(i=0; i<strlen(data); i++)
{
if(data[i]=='_')
f=1;
}
j=0;
i=0;
if(f==1)
{
while(i<strlen(data))
{
if(data[i]=='_')
{
data2[j]=toupper(data[i+1]);
j++;
i+=2;
}
else
{
data2[j]=data[i];
j++;
i++;
}
}
data2[0]=toupper(data2[0]);
for(i=0;i<j;i++)
fprintf(f2,"%c",data2[i]);
}
if
(f!=1)
{
if
(strstr(data, ";")!=NULL)
fprintf(f2,"%s\n",data);
else
if (strstr(data, "#")!=NULL)
fprintf(f2,"\n%s
",data);
else
if (strstr(data,"}")!=NULL || strstr(data,"{")!=NULL)
fprintf(f2,"\n%s\n",data);
else
fprintf(f2,"%s ",data);
}
f=0;
}
fclose(f1);
fclose(f2);
return
0;
}
В целом, на правду похоже, но fscanf(f,”%s”…) игнорирует пробелы после считанного слова, а это в ряде случаев приведет к проблемам. Для считывания строк использование этой ф-ции нежелательно. Вообще, программа сильно покорежится (переход на следующую строку в программе делается произвольным, хотя и приемлемым, способом).
Билет
1
1. Представление чисел в ЭВМ. Целые числа.
Вещественные числа. Ошибки вычислений. Машинное e.
Числа в ЭВМ могут представляться как целые и
цещественные.
Целые числа могут быть без знаковыми и со
знаком. Беззнаковые - это простое
отображение десятичного числа в двоичной
системе.
Целое число может быть представлено тремя
способами:
1.Прямой
Старший бит индикатор положительного или отрицательного числа.
2.Обратный. Отрицательное число является
двоичным числом, где инверсирован все биты.
3.Дополнительный. Похож на обратный, только
к инверсированному числу прибавляется единица.
Вещественные числа бывают с фиксированной
запятой и с плавающей запятой.
C фиксированной запятой - VB тип Currency -
восьмибайтовая переменная, которая содержит вещественное число в формате
с фиксированной десятичной запятой (четыре
десятичных знака после запятой).
Формат с плавающей запятой закреплен IEEE: Institute of Electrical and Electronics Engineers.
Представление чисел в дополнительном коде
эквивалентно представлению чисел в кольце вычетов по модулю 2n,
где n – количество бит в двоичном
представлении числа.
Следствие. Операции сложения, вычитания и
умножения корректно производятся независимо от способа
интерпретации целых чисел – дополнительного
кода (для знакового целого) или беззнакового целого.
Число представляется в виде
x = s*m*2d,
причем
s – знак (отводится один бит)
m – мантисса в виде 1.xxxxx (где x –
двоичная цифра)
d – степень (оставшиеся биты)
мантисса m представляет собой фиксированное
количество разрядов двоичной записи вещественного числа в диапазоне от 1 до 2:
1<=m<2
Мантисса всегда меньше двух, но может
равняться единице.
Разряды мантиссы включают один разряд целой части,
который всегда равен единице,
и фиксированное количество разрядов дробной
части.Двоичный код хранит только разряды дробной части мантиссы.
Число е называются машинным эпсилоном.
Величина машинного эпсилона характеризует точность операций компьютера.
Порядок плавающего числа 1.0 равен нулю. При
сложении 1.0 с числом е производится выравнивание порядка путем
многократного сдвига мантиссы числа e вправо
и увеличения его порядка на 1.
Абсолютной ошибкой приближения числа x0 с
помощью числа x такое D, что |x- x0|<D
Относительной ошибкой приближения числа x0 с
помощью числа x такое d, что |x-x0|/|x0|<d
При сложении или вычитании чисел их
абсолютные ошибки складываются, т.е.
|(x+y)–(x0+y0)|~Dx+Dy
Откровенное копирование имеет недостатки: копирование
из Word в обычный
текст не всегда корректно и в данном случае эта формула смысла не имеет, за
что, формально, оценка и снижена.
|(x – y)–(x0 – y0)|~Dx+Dy
где |x – x0|<Dx , |y – y0|<Dy .
При умножении или делении чисел их
относительные ошибки складываются, т.е.
|(x*y–x0*y0)/(x*y)|~dx+dy
|(x/y–x0/y0)/(x/y)|~dx+dy
где |x-x0|/|x| < dx ,
|y–y0|/|y|<dy.
Ну нельзя же так откровенно копировать лекци…
2. Общая структура С-программы.
Программа на С представляет собой набор
функций. Одна из функций должна иметь имя main. Система передает управление в
программу и
начинается выполнение программы main ()
int main ()
{
...
return
}
Так как main является первой функцией, то в
ней не должно содержаться само действие. В ней будут содержаться определения вспомогательных
функций.
Это абсолютно неверно.
Их количество может быть различным.
Также в любом компиляторе программ на С
присутствует препороцессор. Его функция заключается в том, чтобы обрабатывать
исходный код программы до ее компиляции.
Препроцессорные команды:
#define - предусматривает определение
макросов или препроцессорных идентификаторов. Простейшее применение - замены в
тексте программы.
#include - позволяет включать текст других
файлов в текст программы.
#undef - отменяет действие директивы #define
#if - организация условной обработки
директив
#else - организация условной обработки
директив
#endif - организация условной обработки
директив
#elif - организация условной обработки
директив
#ifdef - организация условной обработки
директив
Смысла в последних строках маловато…
#line - управление нумерацией строк в тексте
программы
#error - задает текст диагностического
сообщения, выводящегося при наличии ошибок.
Итого: про функции нет, практически ничего
(по крайней мере, правильного), а про препроцессор все слишком непонятно.
03_13
Задача:
#include <stdio.h>
#include <stdlib.h>
#include "03_13.h"
int 03_13task(const char *file_in, const char
*file_out)
{
FILE *f1,*f2;
f1 = fopen (file_in,"r" );
f2 = fopen (file_out,"w" );
int **m, str=1, iSum=0, iTotal, i=0, j=0, n=0;
if
( fscanf ( f1, "%d", &iTotal ) != 1)
{
return
-1;
fprintf(f2,"net
fayla" );
}
while
(iSum < iTotal)
iSum
= iSum + str++;
str--;
m=(int**)malloc(str*sizeof(int*)+iSum*sizeof(int));
m[0]
= (int*)(m + str);
for(i=1;i<str;i++)
m[i]
= (int*)( m[i-1] + i );
int k = 0;
for(i=0;i<str;i++)
for(j=0;j<i+1;j++)
{
if(fscanf(f1,
"%d",&n ) == 1)
{
m[i][j]
= n;
k
= k + 1;
}
}
l = 0;
for(j=0;j<i+1;j++)
{
for(i=0;i<str;i++)
{
l
= l + 1;
if(
l <= k )
{
fprintf(f2, "%d ", m[i][j]);
fprintf(f2, "\n");
}
}
}
free(m);
return
0;
}
Билет
13
Вопрос
1;
Назовём бинарными деревьями деревья, в которых задан корневой элемент
или корень и для каждой вершины существует не более двух потомков.
Бинарное дерево назовём деревом поиска, если для каждой вершины А
значения всех вершин в правом поддереве больше или равны значению А, а в левом
- меньше. Можно использовать и термины строго меньше( строго больше) , если в
дереве нет одинаковых элементов.
Под сравнением элементов подразумевается
сравнение соответствующих ключей( значений вершины ).
Родителем называется элемент, из которого
выходят потомки. В бинарном дереве их 2: правый и левый.
Ветвью дерева называется последовательность
вершин дерева, каждый последующий элемент в которой является потомком
предыдущего.Длиной ветви дерева называется количество элементов в ветви.Высотой
дерева называется максимальная длина всех ветвей дерева.
Теперь перейдём к рассмотрению сбалансированных деревьев.
Если вправо и влево от дерева выходят ветви,
то такие ветви сами являются деревьями, то есть поддеревьями основного
дерева.Если для каждой вершины А высоты левого и правого поддерева, выходящих
из А, отличаются не более чем на 1, то
такое дерево называется бинарным
сбалансированным.
Операции над сбалансированными деревьями:
1)Поиск элемента
Чтобы найти интересующий нас элемент в
дереве, воспользуемся следущим алгоритмом:
Обозначим текущую вершину латинской буквой
с, а искомый элемент буквой t. Тогда если t==NULL, то элемент в дереве
не содержится, если t==c, то возвращаем c,
если t>=c, то выполняем эту процедуру для c->right, иначе выполним эту же
процедуру для c->left
Функция поиска на языке си будет выглядеть
так:
Stree *poisk(STree * koren, int chislo)
{
if(koren==NULL)return NULL;
if(koren->value==chislo)return koren;
if(koren->value>=chislo)return poisk(koren->right,chislo);
else return poisk(koren->left,chislo);
}
2)Поиск минимального и максимального
элемента
Обозначим текущую вершину через tec, тогда
для поиска минимального элемента идём по левой ветке до последнего
элемента:
Stree *poiskmin(Stree *tec)
{
return tec->left==NULL?tec:
poiskmin(tec->left);
}
Для поиска максимального элемента идем по
правой ветке до последнего элемента:
Stree *poiskmax(Stree *root)
{
return tec->right==NULL?tec: poiskmax(tec-> right);
}
3)Добавление элемента
Добавление элемента в дерево может нарушить
уже установившийся баланс. В таком случае его нужно выровнить при помощи
вращения элементов.
4)Удаление элемента
Тут несколько случаев: если вершина является
листом, то ее можно просто удалить. Если она имеет одного потомка, то на место
вершины записываем потомка . Иначе можно из правого поддерева удаляемого
элемента взять минимальный элемент,
который будет левым, и поместить его на место удаленного.
Теперь нужно восстановить баланс, если он
нарушен. Для каждой вершины ветви дерева от A до корня нужно проверять условие
балансировки и если оно нарушилось, то нужно произвести балансировку данного
поддерева с помощью вращения.
Вопрос
2;
Как известно, в языке Си нет строкового типа
переменных. Строки здесь представляются через одномерные массивы символов,
который заканчивается символом '\0', который знаменует окончание строки.
Рассмотрим некоторые из функций для работы
со строкой:
int strlen(str) выдаёт длину строки.
сhar *strcpy(куда, откуда) копирование
строки.
char *strcat(к, откуда) Объединяет строки.
strncpy(куда, откуда, сколько) копирование
не более n символов.Символ завершения строки необходимо
скопировать вручную.
sprintf(str, «x=%d», i) «Печатает» в строку.
Может быть использовано для объединения строк.
Char *strdup(char *str) присваивание строк.
strcmp(char *s1, char *s2) сравнение строк. Возвращает 0 в случае успеха. Если больше нуля, то первая
строка больше, иначе меньше нуля.
strncmp(char *s1, char *s2) Сравнение строк
до n символа
stricmp(s1, s2) сравнение строк без учета регистра строк
Существуют следующие функции, которые не
входят в стандарт языка:
strlwr(str)уменьшаем регистр символов в
строке
strupr(str)увеличиваем регистр символов в
строке.
В этом заключается особенность языка.
04_09
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "04_09.h"
int task_04_09merge ( float *main_array, int
left_border, int middle, int right_border, float *temp_arr )
{
// Слияние двух
упорядоченных кусков массива в один отсортированный массив
int first_position = left_border;
int
second_position = middle + 1;
int
current_position = 0;
while
( first_position <= middle && second_position <= right_border )
{
if ( main_array[first_position] <= main_array[second_position] )
{
temp_arr[current_position] = main_array[first_position];
first_position = first_position + 1;
}
else
{
temp_arr[current_position] = main_array[second_position];
second_position = second_position + 1;
}
current_position = current_position + 1;
}
while ( first_position <=
middle )
{
temp_arr[current_position] = main_array[first_position];
first_position = first_position + 1;
current_position = current_position + 1;
}
while ( second_position <=
right_border )
{
temp_arr[current_position] = main_array[second_position];
second_position = second_position + 1;
current_position = current_position + 1;
}
int i
= 0, j = 0;
for (
i = left_border, j = 0; j < current_position; i ++, j ++ )
{
main_array[i] = temp_arr[j];
}
return 0;
}
int task_04_09dividing ( float *main_array, int
left_border, int right_border, float *temp_arr )
{
if ( right_border >
left_border )
{
int middle = ( right_border + left_border ) / 2;
task_04_09dividing (
main_array, left_border, middle, temp_arr );
task_04_09dividing (
main_array, middle + 1, right_border, temp_arr );
task_04_09merge (
main_array, left_border, middle, right_border, temp_arr );
}
return 0;
}
int task_04_09 ( char * filename )
{
// Из файла 04_09in.txt в массив main_array;
int
numb = 0, id = 0;
float
*main_array = NULL, *temp_arr = NULL, temp_var;
FILE * fileopen = fopen( filename, "r" );
fscanf ( fileopen, "%d", &numb );
main_array = ( float* ) malloc( numb * sizeof( float ) );
temp_arr = ( float* ) malloc( numb * sizeof( float ) );
for (
id = 0; id < numb; id ++ )
{
fscanf( fileopen, "%f", &temp_var );
main_array[id] = temp_var;
}
task_04_09dividing ( main_array, 0, numb - 1, temp_arr );
//
Запись в файл нового массива
int idc = 0;
FILE * filewrite = fopen(
"04_09out.txt", "w" );
fprintf ( filewrite, "%d
", numb );
for (
idc = 0; idc < numb ; idc ++ )
{
fprintf( filewrite, "%f ", main_array[idc] );
}
fclose( filewrite );
return 0;
}
Билет
9.
1).Структуры данных. Определения. Различные
реализации. L1 и L2 списки.
Структура данных- реализация понятия
множества элементов определенного типа.
Под реализацией обычно понимают способ хранения данных.
L1-список предполагает наличие
инициализации, взятия значения текущего элемента, перемещение текущего элемента
к следующему, установку текущего элемента в начало, уничтожение текущего
элемента, вставку нового элемента после текущего, проверку на пустоту списка и
т.д.
L2 отличается от L1 наличием доп. операций:
перемещением текущего элемента к предыдущему, вставкой нового элемента перед
текущим, проверкой в начале ли списка текущий элемент.
Ссылочная реализация списков
Алгоритмы работы со списком можно упростить,
если использовать фиктивный элемент в списке. Фиктивный элемент будет играть
роль разделителя между началом и концом списка. При этом, в качестве указателя
на головной элемент списка будет выступать указатель на следующий элемент за
фиктивным. В последнем элементе списка указатель на следующий элемент и в
первом элементе указатель на предыдущий элемент должны указывать на фиктивный
элемент. При этом, скорость работы алгоритмов повышается, но требуется память
под лишний элемент списка.
Реализация L2-списка на основе двух стеков
Интересной реализацией L2-списка является
его реализация на основе двух стеков, расположенных `вершиной друг к другу’.
Первый из стеков представляет начало списка (часть от начала списка до текущего
элемента включительно), а второй – конец (часть после текущего элемента).
Текущий элемент списка лежит на вершине первого стека. При необходимости
переместиться к следующему элементу, значение вершины второго стека извлекается
и помещается на вершину первого стека. При необходимости переместиться к
предыдущему элементу, значение вершины первого стека извлекается и помещается
на вершину второго стека.
Данная реализация активно применялась,
например, при создании текстовых редакторов. Текстовый редактор представляет
собой двунаправленный список строк. Работа с каждой строкой может быть
представлена как работа с простым вектором символов. Операции вставки,
редактирования, удаления символов в строке могут быть реализованы за время =
O(N), где N – количество символов в строке.
Список строк реализуется в виде двух стеков,
каждый из которых может быть реализован в виде временного файла. Текущая строка
(и, возможно несколько соседних строк) хранятся в оперативной памяти, начало
файла – в виде одного временного файла, конец (в обратном порядке) – в виде
второго временного файла.
Реализация L2-списка с обеспечением
выделения/освобождения памяти
При работе со списками может оказаться, что
работа функции malloc требует слишком много времени. К тому же, эта функция
реально выделяет памяти больше, чем запрошено, что делает ее применение слишком
дорогим. Возможна реализация списка, в которой память под весь список
выделяется сразу как массив элементов списка. На основе данного массива
строятся два списка – основной список и список свободного места. В начальный
момент список свободного места объединяет все элементы созданного массива.
Теперь для добавления элемента в список
требуется взять его из списка свободного места и добавить в основной список.
Для извлечения элемента из списка элемент извлекается из основного списка и
добавляется в список свободного места.
Если при добавлении элементов в список место
в списке свободного места закончилось, то можно либо выдать сообщение об
ошибке, либо выделить еще некоторое количество ячеек памяти для хранения дополнительных
свободных элементов и добавить их к списку свободного места.
Итак, для хранения всех данных, относящихся
к подобному списку можно использовать следующую структуру typedef struct
Мда, прямое копирование иногда приводит к
недоразумениям. Последняя фраза – бред. Формально
оценка снижена именно за это.
2). Функция - это самостоятельная единица
программы, созданная для решения конкретной задачи. Функция в языке С играет ту
же роль, что и подпрограммы или процедуры в других языках. Функциями удобно пользоваться,
например, если необходимо обработать один и тот же код программы. Как и
переменные, функции надо объявлять. Функцию необходимо объявить до её
использования. Запомните это простое правило - сначала объяви, а потом
используй.
Спасибо. Я постараюсь запомнить
Каждая функция языка С имеет имя и список
аргументов.
Функции могут возвращать значение. Это
значение может быть использовано далее в программе. Так как функция может вернуть какое-нибудь значение,
то обязательно нужно указать тип данных возвращаемого значения. Если тип не
указан, то по умолчанию предполагается, что функция возвращает целое значение.
После имени функции принято ставить круглые скобки (это касается вызова функции
её объявления и описания). В этих скобках перечисляются параметры функции, если
они есть. Если у функции нет параметров, то при объявлении и при описании
функции вместо списка параметров надо поставить void - пусто.
Основная форма описания функции имеет вид:
1)Вызов функции делается следующим
образом:"имя функции" или "переменная" = "имя
функции".
2)При вызове функции так же ставиться точка
с запятой.Для правильной работы кода функции машине надо знать тип
возвращаемого значения, количество и типы аргументов. При вызове какой-либо
функции копии значений фактических параметров записываются в стек, в
соответствии с типами указанными в ее прототипе. Затем происходит переход в
вызываемую функцию.Приведем пример вызова функции, которая будет печатать
строку "Вызвали функцию" на экран.
Опять же, прямое копирование иногда приводит
к недоразумениям. Надо хотя бы читать, что копируете. Где пример?
Функции возвращающие значение.
В списке параметров для каждого параметра
должен быть указан тип.
Пример правильного списка параметров: function(int x, char a, float z)
Пример неправильного списка параметров: function(int x, a, float z)
В языке С функция может возвращать несколько
значений. Чтобы функция могла вернуть несколько значений необходимо
пользоваться указателями. Этот механизм называется - передача параметров по
ссылке.
07_08
Задача:
#include <stdio.h>
#include <stdlib.h>
#include "07_08_task.h"
int main(int arg, char* argum[])
{
float
x1;
char
file_1;
char
file_2;
printf("Vvedite x\n");
scanf("%f", &x1);
printf("Vvedite im`a vhodnogo faila\n");
scanf("%s",
file_1 );
printf("Vvedite im`a vihodnogo faila\n");
scanf("%s", file_2 );
task(x1, file_1, file_2);
return
0;
}
Уже все неправильно.
Программа упадет даже на этих строках.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct list
{
int
chis, znam;
struct
list *next;
};
int task(float x, const char* fin, const char*
fout)
{
FILE
*f1 = fopen(fin, "r");
FILE
*f2 = fopen(fout, "w");
int
i=1, j, k=50, m, n;
struct
list *mn, *firstlink, *curlink;
f1=fopen(fin,
"r");
long
double tmp, tmp2;
if
(f1!=NULL)
{
if (f2!=NULL)
{
mn=(list*)malloc(k*sizeof(list));
fscanf(f1, "%d", &m);
fscanf(f1,
"%d", &n);
mn[0].chis=m;
mn[0].znam=n;
while (fscanf(f1, "%d", &m) == 1)
{
fscanf(f1,
"%d", &n);
mn[i].chis=m;
mn[i].znam=n;
mn[i-1].next=&mn[i];
i++;
if (i==k)//выход за границу массива уже произошел
{
k*=2;
mn=(list*)realloc(mn,k);
//при этом переотведении памяти все ссылки, заданные
ранее, станут некорректными
}
}
mn[i-1].next=&mn[0];
//----------------------------
firstlink
= curlink = &(mn[0]);
tmp
= 1/(long double)i;
do
{
tmp2
= (long double)(curlink->chis)/(curlink->znam);
tmp2
= fabsl(x-tmp2);
if
(tmp2<=tmp)
{
fprintf(f2,
"%d %d ", curlink->chis, curlink->znam);
}
curlink
= curlink->next;
}
while
(firstlink != curlink);
//----------------------------
fclose(f1);
fclose(f2);
}
else
return -2;
}
else
return -1;
return
0;
}
Вагапов
Рашид. Билет №8
Вопрос
№1
Структура - это набор данных, предполагается
что данные имеют некую логическую связь, но необязательно быть одного типа.
Например: Если нужно записать список работников, о которых известны некоторые
данные, например имя, фамилия и год рождения. В такой задаче очень удобно будет
использовать структуры.
Описание на языке С:
struct [имя структуры]
{
[тип
переменной] [переменная 1];
[тип
переменной] [переменная 2];
................................
[тип
переменной] [переменная n];
};
В данном примере можно создать структуру
вида:
struct Worker
{
char[50] Name;//неверный синтаксис
char[50] SurName;
int Year;
};
описание структуры еще не инициализирует
переменных, для этого необходимо инициализовать переменные вручную:
srtruct [имя структуры] [имя переменной];
В нашем случае:
struct worker Human;
Либо объявить ее можно было еще в описании
структуры:
struct [имя структуры]
{
[тип
переменной] [переменная 1];
[тип
переменной] [переменная 2];
................................
[тип
переменной] [переменная n];
} [переменная 1], [переменная 2], ... ,
[переменная n];
Ну и в данном примере:
struct Worker
{
char[50] Name;
char[50] SurName;
int Year;
} Human;
При объявлении переменной структурного типа выделяется
память сразу для всех элементов структуры.
Обращение к переменным структурного типа:
[Имя переменной].[имя из структуры]
То есть в примере можно задать значения:
Human.Name = "Ivanov";//так делать нельзя
Human.SurName = "Ivan";
Human.Year = 1990;
Очередь - это набор данных, доступ к которым
реализуется по принципу First in, First out. При добавлении данных индекс конца сдвигается влево. При
извлечении сдвигается влево индекс
начала. Если один из индекстов стание <0 делаем его равным n-1
В очереди должны быть реализованы сл.
функции:
1)Инициализация
2)Проверка, пуста ли очередь.
3)Добавление элемента в конец
4)Извлечение элемента из начала
5)Очистка очереди
Дек - это редкая реализация доступа к набору
данных, в котором можно извлечь элемент и из начала, и из конца(первый или
последний);
В деке должны быть реализованы сл. функции:
1) Инициализация.
2) Проверка, пуст ли, дек
3) Добавление элемента в конец/начало
4) Извлечение элемента из начала/конца
5) Очистка
вопрос
№2
Область видимости переменной:
Доступ к переменной возможен только внутри
того блока, в котором она объявлена. Исклюдение составляют глобальные
переменные. Они описываются вне каких либо функций и блоков кода. Доступ к ним
возможен из любой части программы в любой момент. Также в любое время можно
обратиться к статическим переменным(static)
Время жизни переменной:
Все переменные, кроме глобальных и
статических "живут" только то время, пока выполняется функция, в
которой она была объявлена.
Нет. Не функция, а блок.
Как
только функция выполнена, переменная уничтожается. Время "жизни"
глобальных и статических переменных совпадает со временем выполнения программы.
09_13
Задача:
#include <stdio.h>
#include <stdlib.h>
int main_09_13 ()
{
char
nameinf[256], nameoutf[256];
scanf( "%s", nameinf );
scanf( "%s", nameoutf );
FILE
*inf = fopen( nameinf, "r" );
FILE
*outf = fopen( nameoutf, "w" );
int
**arr, strings = 1, sum = 0, count, i = 0, j = 0, n = 0;
if(
fscanf( inf, "%d", &count ) != 1 )
{
fprintf(
stderr, "EMPTY FILE\n" );
return
-2;
}
//подсчета количества
строк нет; перехода в начало файла нет
while ( sum < count
)
sum
+= strings++;
strings--;
arr=(
int** ) malloc ( strings * sizeof( int* ) + sum * sizeof( int ) );
arr[0]
= ( int* )( arr + strings );
for(
i = 1; i < strings; i++ )
arr[i]
= ( int* )( arr[i-1] + i );
for(
i = 0; i < strings; i++)
for(
j = 0; j < i + 1; j++ )
if(
fscanf( inf, "%d", &n ) == 1 )
arr[i][j]
= n;
for(
i = 0; i < strings; i++ )
for(
j=0; j < i + 1; j++ )
fprintf(
outf, "%d ", arr[i][j] );
free(
arr );
return 0;
}
Билет
13.
1. Сбалансированные бинарные деревья поиска.
Поиск, добавление, удаление элемента.
Прежде чем сказать, что такое
сбалансированные бинарные деревья поиска, нужно сказать, что такое
бинарное дерево: это такое дерево, у
которого для каждой вершины заданы не более 2 потомков.
Значение текущей вершины называется ключом.
Если для каждой вершины дерева ключи всех
вершин правого поддерева этой вершины больше или
равны ключа текущего, а в левом, наоборот,
меньше или равны, то такое дерево - это дерево поиска.
Теперь скажем, что такое сбалансированное
бинарное дерево - это такое, что для любой его вершины высоты левого
и правого поддерева вершины отличаются не
более чем на 1.
Правым и левым поддеревьями вершины дерева
head называются поддеревья c ответвлениями head->left и head->right.
Балансом head называется разность высот
левого и правого поддеревьев.
Для сбалансированного дерева состоящего из N
вершин, существует теорема, гласящая, что высота этого
дерева h имеет оценку:
h =
О( log2 N ).
Доказательство.
Пусть mN - минимальное количество элементов
в сбалансированном дереве высоты N.
Тогда рекурсивная формула mN = m(N - 1) +
m(N - 2) + 1 верна.
То есть для дерева с высотой n и минимальным
количеством вершин одно из поддеревьев,
дочерних корневому элементу, должно быть
сбалансированным деревом высоты N - 1 с минимальным количеством вершин,
а другое - сбалансированным деревом высоты N
- 2.
Уравнение mN - m(N - 1) - m(N - 2) = 1 имеет решение:
mN = с1(a1)^n + с1(a2)^n - 1,
где ai
являются решениями уравнения a^2-a-1=0. =>
mN=а( ( ( 1 + sqrt( 5 ) ) / 2 ) ^ n ) + a( ( (
sqrt( 5 ) - 1 ) / 2 ) ^ n ) = a( ( ( sqrt( 5 ) - 1 ) / 2) ^ n )
=> log2 mN ? log2 C + N log2 ( ( sqrt ( 5 ) - 1 ) / 2 )
N ? ( log2 mN - log2 C) / log2 ( ( sqrt( 5 )
- 1 ) / 2 ), для некоторого C>0.
Поиск элемента в дереве.
Допустим, необходимо найти элемент, равный
элементу var1.
Пусть cur - текущая вершина дерева.
В начале выберем текущей вершиной основание
дерева, то есть его корень.
Далее рекурсивно вызовем функцию:
tree *find( tree *arr, int var1 )
{
if( arr == NULL )
return NULL;
if( arr -> value == var1 )
return arr;
if( arr -> value >= var1 )
return Find( arr ->
right, var1 );
else
return Find( arr ->
left, var1 );
}
Удаление элемента из дерева.
Если вершина имеет всего одного потомка то
операция по ее удалению очевидна.
В противном случае нужно изъять минимальный
элемент, например, из правого поддерева и переместить на место
удаленного.
2. Строки в языке С. Функции работы со
строками.
В отличии от паскаля в языке си нет
определенного типа строк, они реализованы через массивы.
А именно массивы типа char, которые
оканчиваются нулем.
Обратно - обычный одномерный массив можно
представлять как строку символов.
Также в языке С существуют строковые константы,
хотя для нит нет специального типа.
Функции работы со строками:
int getchar()
возвращает значение символа, который
пользователь ввел с клавиатуры.
char *gets ( char *st )
функция ожидает ввода строки от
пользователя, которую она помещает в массив st,
пока последний не нажмет Enter.
int putchar ( int t )
печатает символ кода t.
char *strcpy ( char *string1, char string2 )
Копирует строку string2 в строку string1,
возвращает значение полученной строки string1.
char *strncpy ( char *string1, char string2, int n )
Аналогична предыдущей функции, позволяет
задавать количество копируемых символов.
int sprintf ( char *st, char *format, ... )
Аналогична функции printf за тем
исключением, что данные записываются в массив st.
char *strcat ( char *string1, char string2 )
Функция добавляет в строку string1 строку
string2.
int puts ( char *st )
печатает строку st, а затем переводит курсор
на новую строку.
char *strncat ( char *string1, char string2, int n )
Добавляет к первой строке ровно n символов
из второй строки.
int sscanf ( char *st, char *format, ... )
значения вводятся не с клавиатуры, а из
массива st.
10_02
Задача:
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <ctype.h>
int task_10_02(char *filename1,char *filename2)
{
FILE *fileread, *filewrite;
int i, j, k, g = 0;
char string_1[256];
char string_2[256];
fileread = fopen( filename1,"r" );
if (fileread != NULL)
{
filewrite = fopen( filename2, "w");
if
(filewrite != NULL)
{
while
(fscanf(fileread, "%s", string_1) == 1)
{
for (i
= 1; i < strlen(string_1); i++)
{
if (string_1[i] == toupper(string_1[i]))
g = 1;
}
j = 1;
i = 1;
if (g == 1)
{ string_2[0] = tolower(string_1[0]);
while (i < strlen(string_1))
{
if
(isalpha(string_1[i]) == 1 || string_1[i] == toupper(string_1[i]))
{
string_2[j] = '_';
j++;
string_2[j] = tolower(string_1[i]);
j++;
i++;
}
else
{
string_2[j] =
string_1[i];
j++;
i++;
}
}
for
(i = 0; i < j; i++)
fprintf(filewrite,
"%c", string_2[i]);
}
if (g
!= 1)
{
if (
strstr( string_2, ";") != NULL )
fprintf( filewrite,
"%s\n", string_2 );
else
if ( strstr( string_2,
"#") != NULL )
fprintf( filewrite,
"\n%s ", string_1 );
else
if (
strstr(string_1, "}") != NULL || strstr(string_1, "{") !=
NULL )
fprintf(
filewrite, "\n%s\n", string_1 );
else
fprintf(
filewrite, "%s ", string_1 );
}
g =
0;
}
}
else
return -2;
}
else
return -1;
fclose(fileread);
fclose(filewrite);
return 0;
}
В целом, на правду похоже, но fscanf(f,”%s”…) игнорирует пробелы после считанного слова, а это в ряде случаев приведет к проблемам. Для считывания строк использование этой ф-ции нежелательно. Вообще, программа сильно покорежится (переход на следующую строку в программе делается произвольным, хотя и приемлемым, способом).
Ибрагимов
Бобур. Билет № 2.
вопрос 1. Сортировка пузырьком имеет
следующий вид:
int BSort(kol-vo,m[])
int i,j,temp;
for (i=0; i<kol-vo-1; i++)
for (j=0;j<kol-vo-1; j++)
{
if(m[j]>m[j+1])
{
temp=m[j+1]; m[j+1]=m[j]; m[j]=temp;
}
}
Использование сортировки пузырьком
оптимально при небольшом количестве элементов в массиве.
верхняя оценка времени:O(N log2 N).
нижняя оценка времени: O(N2).
Не верно ни то, ни другое.
Сортировка слиянием.
Смысл данной сортировки заключается в
следующем:
Пусть задан неосортированный массив. Мы
делим его пополам,после чего сортируем по-отдельности обе его половины(любым
способом).
Затем сравниваем минимальные значения обеих
половин и записываем в массив.
Абсолютно бессмысленные действия.
Сортировка слиянием имеет следующий вид:
int SSort(kol-vo,c[])
m = kol-vo/2;
for(i=0;i<m;i++)
a[i]=c[i];
for(j=m;j<kol-vo;j++)
b[j]=c[j];
сортируем массивы а и в
while(i<m && j<(kol-vo-m))
{
if(a[i]<b[j])
c[k]=a[i]; k++;i++;
else
c[k]=b[j]; k++;j++;
}
Последнего цикла недостаточно.
верхняя оценка времени:
нижняя оценка времени:
Сортировка слиянием с рекурсией.
int SSort(kol-vo,c[])
m = kol-vo/2;
for(i=0;i<m;i++)
a[i]=c[i];
for(j=m;j<kol-vo;j++)
b[j]=c[j];
для сортировки а и в мы вновь используем
функцию SSort.
while(i<m && j<(kol-vo-m))
{
if(a[i]<b[j])
c[k]=a[i]; k++;i++;
else
c[k]=b[j]; k++;j++;
}
От предыдущего, вроде, не отличается.
вопрос
2.
В языке С есть две основные разновидности
базовых типов: целые и вещественные. К целым типам относятся типы
Char
short
int
long
Перед каждым каждым из них может стоять
слово signed или unsigned. signed указывает на то, что переменная имеет знак, а
unsigned - что переменная не имеет знак. По умолчанию, все переменные имеют
знак. Исключением является переменная типа char.
Известно, что в данном списке указанные типы
располагаются по неубыванию их размеров. Если требуется узнать конкретный
размер переменной в байтах, то он может быть получен с помощью оператора
sizeof(): sizeof(char).
К вещественным типам относятся
float
double
Кроме базовых типов, существуют производные
типы, задающиеся с помощью понятий массив, указатель, функция, структура,
объединение.
Базовые понятия
описание
и определение
время жизни
область видимости или область действия
Одними из основных понятий программирования
являются описание и определение объектов.
Описание переменной задает ее тип и
указывает на то, что переменная где-то определена.
Определение переменной указывает место в
программе, задающее время рождения переменной. Определение переменной всегда
является ее описанием.
Время жизни переменной задается интервалом
между моментом рождения переменной и моментом ее смерти. Внутри этого интервала
гарантируется сохранность значения переменной. С точки зрения времени жизни, в
языке С бывает два вида переменных:
статические и автоматические.
Автоматические переменные всегда
определяются внутри некоторого блока. Блоком называется часть тела некоторой
функции, заключенная в фигурные скобки. Телом функции называется набор
операторов, задающих действия, совершаемые функцией. Автоматические переменные
всегда являются локальными, т.е. их область видимости ограничивается их блоком.
Автоматические переменные рождаются в момент входа выполнения программы в
данный блок и умирают в момент выхода из блока.
Статически созданные переменные рождаются в
момент запуска программы и умирают в момент прекращения работы программы.
Память под них отводится в общей куче (heap), т.е. в обще-используемой памяти.
Ее размер ограничивается размером памяти, доступной программе. Статически
созданные переменные это - либо глобальные переменные (т.е. переменные,
определенные вне всех блоков программы), либо локальные.
Ну, нельзя же так откровенно копировать мои
лекции…
12_14
Задача:
Билет
14.
1 . Сбалансированные бинарные деревья
поиска. Поиск минимального и максимального элемента в дереве. Поиск
следующего/предыдущего элемента в дереве.
Бинарные деревьями называют деревья где
задан корень, т.е. корневой элемент и для каждой вершины существует не более
двух потомков (ответвлений).
Бинарное дерево называется деревом поиска,
если для любой вершины дерева <а> значения всех вершин в правом поддереве
больше или равно <а>, а в левом меньше.
Ветвью дерева называется последовательность
вершин дерева, в котором каждый следующий элемент дерева является ответвлением
предыдущего.
Длина ветви это количество элементов дерева
в ветви.
Высотой дерева называется максимальная ветвь
(длина).
Поиск минимального и максимального элемента
в дереве. Поиск минимального элемента осуществляется по левой ветви, доходя до
последнего элемента. Поиск максимального элемента осуществляется по правой
ветви, доходя до последнего элемента.
Если у текущего элемента есть правый
потомок, то следующим элементом будет минимальный элемент в поддереве, иначе мы
поднимаемся наверх до текущего элемента, являющиеся левым потомком
<родителя>. Этот родитель будет след. элементом дерева.
2.
Типы базовых переменных. Их описание, определение, инициализация.
На языке Си существуют две основные типы
переменных: целые и вещественные.
целые: int, char, long, short
Перед каждым типом можно поставить слова
signed - переменная имеет знак, unsigned - переменная не имеет знак. по
умолчанию все переменные имеют знак, кроме char.
Если требуется узнать размер переменной в
байтах, то можно получить с помощью оператора sizeof().
вещественные: float, double
Известно что sizeof(float)<sizeof(double).
кроме этих базовых типов существуют
производные типы, которые задаются с помощью массива, объединения, указатель,
структура.
Описание переменной задает ее тип и
указывает на то, что переменная где-то определена. Определение переменной
указывает место в нашей программе, задающая время рождения переменной.
Время жизни переменной задается интервалом
между моментом рождения и смерти переменной. В си время жизни бывает переменные
автоматическим и статическим. Автоматические переменные всегда определяются
внутри некоторого блока. Блок это часть тела функции в фигурных скобках. Тело
функции это набор операторов, которые задают действия совершаемые функцией.
Автоматические переменные ограничиваются их блоком.
Статические переменные рождаются в момент
запуска программы и умирают после прекращения работы программы. Память для них
отводится в общеиспользумой памяти. Ее размер ограничивается памятью программы.
Статически созданные переменные это либо переменные определенные вне всех
блоков либо локальные
13_06
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#pragma warning(disable: 4996)
struct list
{
int x;
struct
list *next, *prev;
};
int task_13_06(float x, char* filename_in,
char* filename_out)
{
FILE
*in,*out;
int
i=1,j,n,m,k=50;
struct
list *mn,*firstlink,*xlink;
in=fopen(filename_in,"r");
if
(in!=NULL)
{
out=fopen(filename_out, "w");
if
(out!=NULL)
{
mn=(list*)malloc(k*sizeof(list));
fscanf(in,
"%d", &m);
mn[0].x=m;
while
(fscanf(in, "%d", &m)==1)
{
mn[i].x=m;
if (i==1)
{
mn[0].next=&mn[1];
}
else
{
mn[i-1].prev=&mn[i-2];
mn[i-1].next=&mn[i];
}
i++;
if (i==k)//выход за границу массива уже произошел
{
k*=2;
mn=(list*)realloc(mn,k);//неправильное переотведение памяти
//переотведение
памяти делает некорректными все созданные ссылки
}
}
mn[0].prev=&mn[i-1];
mn[i-1].prev=&mn[i-2];
mn[i-1].next=&mn[0];
firstlink=xlink=&(mn[0]);
do
{
if
(abs(x-(xlink->x))<=1)
fprintf(out, "%d ", xlink->x);
xlink=xlink->next;
}
while
(firstlink!=xlink);
fclose(in);
fclose(out);
}
return
-2;
}
return -1;
}
Билет
6
1) Сортировка подсчетом
Пусть мы хотим отсортировать N целых чисел,
каждое из которых не превосходит K, при этом K=O(N). Тогда мы можем создать
временный массив А размером K, в который можно поместить для каждого i количество чисел в массиве AВ не
превосходящих i. Тогда для каждого 1
<= i <= N: в отсортированном
массиве в элементе с индексом А[В[i]]
лежит элемент, равный В[i] .
Приведем реализацию данного алгоритма.
Результат поместим в третий массив C
CountingSort (В,C,N,K, А)
Для всех i от 1 до K с шагом 1 выполнить:
А[i]=0
Для всех i от 1 до N с шагом 1 выполнить:
А[В[i]] ++
Для всех i от 1 до K с шагом 1 выполнить:
А[i]= А[i]+ А[i-1]
Для всех i от N до 1 с шагом -1 выполнить:
C[А[В[i]]] = В[i]; А[В[i]]- -
Поэтому данная сортировка сохраняет взаимное
расположение равных элементов. Этой свойство сортировки называется
устойчивостью. Это свойство имеет смысл, когда равенство элементов в смысле
сравнения не влечет тождественного равенства элементов. Например, это
происходит если сортировка идет по ключу.
Цифровая сортировка
Пусть требуется отсортировать массив целых
чисел, записанных в некоторой системе исчисления. Мы сортируем массив
устойчивым методом по младшей цифре. Потом - по второй, и т.д. Новая сортировка
не меняет порядок уже отсортированных элементов, поэтому в конце мы получим
отсортированный массив.
Алгоритм цифровой сортировки требует O(nd)
операций, где n - максимальное количество операций для одной внутренней
сортировки, d - количество цифр.
Этот алгоритм облегчает использование
сортировки подсчетом. Действительно, если есть большой массив 32-битных целых
чисел без приемлемых ограничений на их величину, то можно разбить их на 2 либо 4 части и
рассмотреть каждую часть как одну цифру в алгоритме цифровой сортировки.
Ну нельзя же так откровенно копировать
лекции
2) Логическиоперации
"&&","||","!"
операция "&&" - "и" , эквивалентна операции
умножения, результатом будет истина
только в случае, когда оба утверждеия истина.
А В А*В
0 0 0
0 1 0
1 0 0
1 1 1
операция "//" - "или",
эквивалентна операции сложения, результатом будет истина в случае когда хотябы
одно утверждение истина.
А В А+В
0 0 0
0 1 1
1 0 1
1 1 1
операция "!" отрицание
А !А
0 1
1 0
14_07
Задача:
#include <stdio.h>
#include <stdlib.h>
#include "14_07.h"
int task_14_07(char *filename)
{
char
c[10];
int i,
j, k, n, set=0;
FILE
* f1=fopen(filename , "rb");
if(sizeof(int) != 4 )
return
0;
if(f1==NULL)
return
0;
FILE *
f2=fopen("14_07out.bmp" , "wb");
if(f2==NULL)
return
1;
if(fread(c, 1, 10, f1) != 10) {
fclose(f1);
fclose(f2);
return
0; }
fwrite(c, 1, 10, f2);
if(fread(&set, sizeof(int), 1, f1) != 1) {
fclose(f1);
fclose(f2);
return
0; }
fwrite(&set, sizeof(int), 1, f2);
for(i=0; i<set-10-sizeof(int); i++) {
fread(c, 1, 1, f1);
fwrite(c, 1, 1, f2); }
unsigned
char s[32];
for(i=0;
i<32; i++)
{
fread(s,
1, 32, f1);
for(j=0; j<32;j++)
{
n=0;
for(k=0; k<8; k++)
if(s[j] & 1<<k)
n++;
if
(n>4)
n=255;
else
if(n<4)
n=0;
else
n=128;
s[j] = n;
}
fwrite(s, 1, 32, f2);
}
fclose(f1);
fclose(f2);
return
1;
}
Билет
7.
1) Структурой данных является реализация,
понятия множества элементов определенного типа. Под реализацией понимается
способ хранения данных. Вместе со способом хранения задается набор операций
(алгоритмов) по добавлению поиску, удалению элементов множества.
Массив в С является точной реализацией
структуры данных вектор. Вектором называется структура данных, в которой к
каждому элементу множества можно обратится по целочисленному индексу. В
структуре данных вектор значение индекса может быть ограничено некоторой
наперед заданной величиной- длиной вектора(массива).
СОздание
вектора требует следующих функций:
1. Создать вектор длины n;
2. Положить вектор по индексу i;
3. Взять элемент из вектора по индексу i;
4. Уничтожить вектор;
При
использовании массивов для реализации структуры данных вектор,
создание/уничтожение объекта происходит автоматически, если же этим процессом
надо управлять, то следует использовать такие функции как malloc/free.
Стеком
называется струтура данных, организованная по принципу LIFO(last-in, first-out)
или другими словами элемент попавшим в множество последним, должен первым его
покинуть. При практическом использовании часто налагаются ограничение на длину
стека, т.е требуется чтобы кол-во элементов не превосходило N для некоторого
целого числа N.
Создание
стек предполагает наличие следующих функций:
1. Инициализация;
2. Добавление элемента на вершину стека;
3. Взятие/извлечение элемента с вершины
стека;
4. Проверка на пустоту стека;
5. Очистка стека;
Реализация
стека.
Для
реализации стека целых чисел состоящего не более чем из 100 чисел, на базе
массива в языке С, следует определить массив целых, состоящий из 100 чисел и
целую переменную, указывающую на вершину стека(ее значение также будет равно
числу элементов в стеке).
int stack[100], i=0;
Ну нельзя же так откровенно копировать
лекции.
2)Указатель - это переменная, значением
которой является адресс другой переменной. Так как указатель может ссылаться на
переменные разных типов, с указателем в языке Си связывается тип того объекта,
на который он ссылается. Для описания указателей используется операция
косвенной адресации *. Например, указатель целого типа uk описывается так : int
*uk. Унарная операция &, примененная к некоторой переменной, показывает,
что нам нужен адресс этой переменной, а не ее текущее значение. Если переменная
uk объявлена как указатель, то оператор присваивания uk=&x означает:
"взять адресс переменной x и присвоить его значение переменной-указателю
uk".
Указатели на функции
Указатели на функции - очень важное средство
языка С. Функция располагается в памяти по определенному адресу, который можно
присвоить указателю в качестве его значения. Адресом функции является ее точка
входа. Именно этот адрес используется при вызове функции. Так как указатель хранит
адрес функции, то она может быть вызвана с помощью этого указателя. Он
позволяет также передавать ее другим функциям в качестве аргумента. В программе
на С адресом функции служит ее имя без скобок и аргументов (это похоже на адрес
массива, который равен имени массива без индексов).
Указатели на функции
Указатели на функции[1] - очень мощное
средство языка С. Хотя нельзя не отметить, что это весьма трудный для понимания
термин. Функция располагается в памяти по определенному адресу, который можно
присвоить указателю в качестве его значения. Адресом функции является ее точка
входа. Именно этот адрес используется при вызове функции. Так как указатель
хранит адрес функции, то она может быть вызвана с помощью этого указателя. Он
позволяет также передавать ее другим функциям в качестве аргумента.
В программе на С адресом функции служит ее
имя без скобок и аргументов (это похоже на адрес массива, который равен имени
массива без индексов). Рассмотрим следующую программу, в которой сравниваются
две строки, введенные пользователем. Обратите внимание на объявление функции
check() и указатель p внутри main(). Указатель p, как вы увидите, является
указателем на функцию.
5.11. Указатели на функции
В Си сама функция не является переменной, но
можно определить указатель на функцию и работать с ним, как с обычной
переменной: присваивать, размещать в массиве, передавать в качестве параметра
функции, возвращать как результат из функции и т.д. Для иллюстрации этих
возможностей воспользуемся программой сортировки, которая уже встречалась в
этой главе. Изменим ее так, чтобы при задании необязательного аргумента -n
вводимые строки упорядочивались по их числовому значению, а не в
лексикографическом порядке.
Сортировка, как правило, распадается на три
части: на сравнение, определяющее упорядоченность пары объектов; перестановку,
меняющую местами пару объектов, и сортирующий алгоритм, который осуществляет
сравнения и перестановки до тех пор, пока все объекты не будут упорядочены.
Алгоритм сортировки не зависит от операций сравнения и перестановки, так что
передавая ему в качестве параметров различные функции сравнения и перестановки,
его можно настроить на различные критерии сортировки.
16_11
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int task(char *file_in, char *file_out)
{
FILE
*fin, *fout;
fin =
fopen(file_in, "rb");
fout =
fopen(file_out, "wb");
if(fin!=
NULL && fout != NULL)
{
unsigned char buffer;//Смещение
unsigned long temp;
int
i=0, k=0, j=0, res = 0;
for(i=0; i<10; i++)//Пробегаемся по смещению(=10)
{
fread(&buffer, 1, 1, fin);
fwrite(&buffer, 1, 1, fout);
}
fread(&temp, sizeof(temp), 1, fin);
fwrite(&temp, sizeof(temp), 1, fout);
for(i=0; i<temp-10-sizeof(temp); i++)//Считываем остальное
{
fread(&buffer, 1, 1, fin);
fwrite(&buffer, 1, 1, fout);
}
for(i=0; i<32; i++)
{
fread(&temp, 4, 1, fin);
for(j=0; j<32; j++)
if
(temp & (1 << j))
res++;
}
if (res
>= 16*32)
buffer
= 255;
else
buffer
= 0;
for(i=0; i<32; i++)
{
for(j=0; j<4; j++)
fwrite(&buffer, 1, 1, fout);
}
}
fclose(fin);
fclose(fout);
return
0;
}
int main()
{
char
A[256],B[256];
scanf("%s",A);
printf("\n");
scanf("%s",B);
task(A,B);
return
0;
}
М1-12 Кодиров Улугбек Билет №10
--------------------------
ВОПРОС
№1
Бинарное дерево - дерево, в котором задан
корневой элемент и для каждой вершины существует не более двух потомков.
Бинарное дерево называется деревом поиска,
если для каждой вершины справедливы следующие свойства:
а)
ключ любой вершины правого поддерева больше либо равен ключу данной вершины
б)
ключ любой вершины левого поддерева меньше ключа данной вершины
Для задания вершины дерева в языке С можно
написать следующую структуру:
typedef struct Tree_
{
int num;
struct Tree_ *prev;
struct Tree_
*right,*left;
}Tree;
В данной структуре указатель prev указывает
на родительский элемент, указатель left - на левый элемент,а right - на правый.
Число num (мы взяли целое число) - это ключ вершины. Если левого(правого)
потомка нет, то ключ левого(правого) элемента равен нулю.
Ветвь дерева - последовательность вершин
дерева, каждый последующий элемент в котором является потомком предыдущего.
Длина ветви - количество элементов ветви.
Высота дерева - максимальная длина среди
всех вершин дерева.
Поиск
минимального и максимального элемента в дереве.
Данная функция дойдет до самого левого
элемента дерева поиска(следовательно, до минимального):
Tree *FindMin(Tree *root)
{
return root.left==NULL?
root: FindMin(root.left);
}
Аналогично, нахождением самого правого
нижнего элемента дерева мы определим максимальный
элемент:
Tree *FindMax(Tree
*root)
{
return
root.right==NULL? root: FindMax(root.right);
}
Поиск
следующего и предыдущего элемента:
Если у текущего элемента есть правый
потомок, то следующим элементом будет минимальный элемент
в правом поддереве. Иначе мы должны
подниматься вверх по дереву, пока не встретиться вершина,
являющаяся левым потомком своего родителя. В
таком случае родитель этой вершины будет
следующим элементом дерева.
Tree
*FindNext()
{
if(curr==NULL) return
NULL;
if(curr.right!=NULL)
return FindMin(curr.right);
while (curr.prev
&& curr!=prev.left) curr=curr.prev;
return
curr.prev;
}
Таким же образом ищется предыдущий элемент.
ВОПРОС №2
Функция malloc принимает в качестве
аргумента размер выделяемой области в байтах, возвращает
указатель (void*) на область памяти
заявленного размера или NULL(если выделить не удалось).
Функция realloc изменяет выделение памяти
для блока до заданного количества байт. Если невозможно расширить текущий блок,
то будет выделен новый,в который будет скопировано содержимое старого блока,а
сам старый блок будет освобожден.Cодержимое блока памяти, превышающее объем
старого будет не определено.
Функция free - функция стандартной
библиотеки языка Си, предназначенна для освобождения ранее выделенной
динамической памяти.Функция возвращаемого значения не имеет. free() не
проверяет указатель на правильность, и может освободить невыделенную область
памяти, что может привести к повреждению кучи. Вызов функции с NULL безопасен.
Для избежания повреждения кучи рекомендуются
обнулять каждый освобождаемый указатель.
Вызов вышеописанных функций осуществляется
так:
void free (void *ptr);
void *malloc (size_t size);
void *realloc (void *block, size_t size);
17_04
Задача:
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <string.h>
# include "17_04.h"
int task17_04 ( char *vxodnoy, char *vixodnoy)
{ char
mas1[400],mas2[400],el;
const char pr='\'';
int
i=0,j=0,t=0,k=0,dlina=0;
FILE
*fin,*fout;
fin=fopen(vxodnoy,"r");
fout=fopen(vixodnoy,"w");
if
((fin==NULL) && (fout==NULL)) return 0;
while
(fscanf(fin,"%c",&el)==1)
{
mas1[i]=el; i++;dlina=i;}
//не будет работать
для больших файлов; это - принципиально
while(j<dlina)
{
if
(mas1[j]==pr) { t=j+1; // esli
vstretim odinarnie kavichki,nachinaem zapisivat
while((t<dlina)
&& (mas1[t]!=pr))// zapisivaem poka ne vstretim snova odinarnie
kavichki
{ mas2[k]=mas1[t];
k++;
t++;}
mas2[k++]=' ';};
j=t;
j++; }
for(i=0;i<k;i++)
fprintf(fout,"%c",mas2[i]);
fclose(fin);
fclose(fout);
return
0;
}
Билет
№4.
1. Сортировка алгоритмом HeapSort или
сортировка с помощью пирамиды.
Пусть нам дан массив A длины N.Массив будем считать пирамидально
упорядоченным, если для всех элементов i выполняется соотношение: A[i/2]
>=A[i] . То есть : A[i]>=A[2i] и
A[i]>=A[2i+1](1)( представим
бинарное дерево: если у вершины индекс i,то у ее сыновей индексы будут 2i и
2i+1,а у родителя - i/2 ).
Этапы алгоритма:
1.Cначала выстроим элементы массива где
выполнены отношения A[i]>=A[2i] и
A[i]>=A[2i+1];
2.Будем удалять по одному элементу и
изменять дерево ( сначала переставим первый и последний элемент ,и массив A[i],
где i= от 1 до n-1,преобразуем так, чтобы там выполнялись отношения(1); потом
переставим первый и последний элемент в получившемся массиве и перестроим массив
А[i],где i=от 1 до n-2,чтобы там снова выполнялось отношение (1);и т.д,пока не
останется один элемент).
Функция Heapyfy(A,i,N) проверяет выполнение
условия (1)- если оно выполнено, то ничего не происходит. Если нет-выбираем
максимальный элемент из A[i], A[2i],
A[2i+1] и выбранный элемент меняем местами с A[i].
Heapsort(a,N)
for (i=N-1;i>=1;i--)
Heapyfy(A,i,N);
for (i=1;i<=N-1;i++)
{ swap(A[i],A[N-i+1]);
Heapyfy(A,1,N-i);}
2. Структуры и объединения. Описания и
определения.
Струтура-это некоторый набор однотипных или
разнотипных данных и он рассматривается как новый тип данных. Структура
объявляется с помощью ключевого слова struct,затем следует имя
структуры и шаблон,указываемый в фигурных скобках,по которому будет создаваться
структура.
Так как структура новый тип данных, то ее
надо объявить.
struct New
{
<тип1> < имя1>- это поля структуры с различными типами
<тип2> <имя2>
<тип3> <имя3>
<тип 4> <имя4>
};
Синтаксис описания заканчивается точкой с
запятой.
struct Students
{ char name[40];
int cource;
};
При этом никакая память не выделилась, мы
лишь сказали, что такие элементы в будущем могут присутствовать.
Students A;
Students A; - мы выделили память под структуру и дали ей
имя.
Чтобы обратиться к структуре,используем имя
структуры, а для доступа к полю используем имя поля через точку.
A.course=2;
Если адрес структуры записан в указатель, то
для обращения к полю будем использовать
->. Например:
Students A;
Student *pS;
p=&A;
p->course=3;
Объединение служит для размещения в одной и
той ж области памяти данных различных типов.
Объявление начинается с ключевого слова union,за которым следует идентификатор и блок описания элеменов
различного типа:
union Objects
{ int houses;
float prices[12];
};
При этом в памяти резервируется место для
для размещения самого большого элемента объединения, в вышеперечисленном
случае- для вещественного массива.
Доступ к элементаам объединения
осуществляется также через точку. В отличие от структур, переменная типа
объединения может быть приоинциализирована только значением первого
объявленного члена( в данном случаем переменной houses типа int).
18_12
Задача:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "18_12.h"
int comp(const void *i, const void *j)
{
return
*(int *)i - *(int *)j;
}
int 18_12task(const char* s1, const char* s2)
{
int *a,
n, k, i;//a- din massiv, n - chislo elementov v massive, k - kolichestvo naib
chisel kot zadaet user
FILE
*f1, *f2;//f1- vh, f2 - vih
f1=
fopen(s1, "r");
if(f1
== NULL)
return 1;
fscanf(f1, "%d", &n);//obschee k-vo el
a =
(int*)malloc(n * sizeof(int));//create array
if(a
== NULL)
{
fclose(f1);
return
3;
}
for(i=
0; i< n; i++)
fscanf(f1, "%d", &a[i]);
fclose(f1);
qsort(a, n, sizeof(int), comp);
scanf("%d", &k);
f2=
fopen(s2, "w");
if(f2 == NULL)
return 2;
for(i= 0; i< (n-k); i++)
fprintf(f2, " %d", a[i]);
fclose(f2);
free(a);
return
0;
}
Лернер В
Б№12
2)Программа в С - набор процедур и функций.
В программе обязательно должна присутствовать основная функция, которая
называется main().
Хорошим тоном в программировании считается
тот факт, когда функция возвращает лишь одно нулевое значение.
Это непонятно о чем.
Если предположить, что программа исполняется
начиная с основной функции, то говорим, что во время этого процесса она
вызывает уже вспомогательные функции.
Перед работает основной функции включается
препроцессор
Он работает перед компиляцией, а не перед
выполнением main()
, он исполняет такие команды как:
#define - директива работает с макросами,
простейшее - замена текста в программе
#pragma -
#error - здесь можно задать текст при
возникновение ошибок
#include - подключение заголовков
#if - условия обработки директив
b т.п.
Все команды должны начинаться с символа '#'
и находиться в начале кода.
Это непонятно о чем.
В языке C существуют лишь целые и
вещественные переменные.Для вывода используются не операторы, а функции.
1)Дерево называется сбалансированным если
высота его левого и правого поддерева отличается не более чем на 1.
Дерево будет называться идеально сбалансированным, если длины всех
ветвей, начинающихся с корня дерева и заканчивающиеся в узле хотя бы с одним
нулевым указателем отличаются не более чем на 1.
Высота идеально сбалансированного дерева
лежит в интервале от log_2(n) < h < 1+ log_2(n), где h - высота такого
дерева, а n - количество элементов.
Для сбалансированного дерева, которое имеет
n вершин, высота дерева h должна оцениваться как h =Q( log_2(n) ).
Бинарное дерево будет называется деревом
поиска, если для любой вершины дерева ключи всех вершин в правом поддереве
больше или равны ключа a, а в левом - меньше.
19_14
Задача:
#include <stdio.h>
#include "19_14h.h"
void seek(FILE *fin, FILE *fout, int offsetPos)
{
int i=0;
char c;
for(i=0;
i<offsetPos; i++)
{
fread(&c,1,1,fin);
fwrite(&c,1,1,fout);
}
}
int getOffset(FILE *fin, FILE *fout)
{
int
offset=0;
seek(fin, fout, OFFSET_POS);
if(fread(&offset,
sizeof(int), 1, fin) != 1)
{
fclose(fin);
fclose(fin);
return
0;
}
else
fwrite(&offset, sizeof(int), 1, fin);
return
offset;
}
void invertColour(FILE *fin, FILE *fout, int
offset)
{
int i=0,
j=0;
unsigned
char s[4];
seek(fin,
fout, offset);
for(i=0;
i<32; i++)
{
fread(s, 1, sizeof(s), fin);
for(j=0;j<sizeof(s);j++)
s[j] = ~s[j];
fwrite(s, 1, sizeof(s), fout);
}
}
int getSize(FILE *file)
{
fseek(file, 0, 2);
return
ftell(file);
}
int task_19_14(FILE *fin, FILE *fout)
{
int
offset = getOffset(fin, fout);
if(offset == 0)
{
printf("Maybe empty file\n");
return
1;
}
invertColour(fin, fout, offset-14);
if(getSize(fout) != getSize(fout))
{
printf("Incorrect file size\n");
return
1;
}
printf("Good luck :)");
return
1;
}
1) Бинарное дерево называется
сбалансированным , если для всех его вершин высоты правого и левого поддерева
отличается не больше чем на еденичку.
Правым и левым поддеревьями вершины дерева,
например cur, называются поддеревья с корнями cur->left и cur->right
Балансом вершины дерева называется разность
высот левого и правого поддеревьев.
Поиск мин. и макс. элемента.
Если
cur текущая вершина, тогда для поиска минимального элемента надо пройтись по
левой ветке до последнего элемента
Stree *findmin(Stree *cur){
return cur->left
==NULL?cur:findmin(cur->left);
}
Для поиска максимального элемента идём по
правой ветке до последнего элемента
Stree *findmax(Stree *cur){
return cur->right
==NULL?cur:findmax(cur->right);
}
Поиск следующего или предыдущего элемента:
Если у текущего элемента cur есть правый
потомок, то следующим элементом будет самый левый элемент в поддереве, которое
имеет корень cur->right. Если такого элемента нет, то надо подниматься вверх
по дереву, пока не дойдём до вершины, являющейся левым потомком своего
родителя. Родитель этой вершины будет следующим элементом дерева.
Stree *findnext(Stree *cur)
{
If(cur==NULL) return
NULL;
If(cur->right!=NULL)
return findmin(cur->right);
While(cur->back &&
cur!=cur->back->left) cur=cur->back;
Return
cur->back;
}
Если у текущего элемента cur есть левый
потомок, то следующим элементом будет самый
правый элемент в поддереве, которое имеет корень cur->left. Если
такого элемента нет, то надо подниматься вверх по дереву, пока не встретится
вершина cur, являющаяся правым потомком своего родителя. В этом случае родитель
этой вершины будет предыдущим элементом дерева.
Stree *findprev(Stree *cur)
{
If(cur==NULL) return
NULL;
If(cur->left!=NULL) return findmax(cur->left);
While(cur->back && cur!=cur->back->right)
cur=cur->back;
Return cur->back;
}
2) Типы базовых переменных. Их описание,
определение и т.д.
В языке C есть две основные разновидности
типов: целые и вещественные.
Целые: char, short, int, long.
Перед каждым типом можно поставить слово
signed или unsigned.
Signed указывает, что переменная имеет знак.
Unsigned-не имеет знака.
По умолчанию все типы имеют знак, кроме
char.
Если требуется узнать размер переменной в
байтах, то можно воспользоваться функциями sizeof()
К вещественным типам относятся float double.
Кроме базовых типов есть ещё массивы,
указатели, функции, структуры, объединения.
Описание переменной задаёт её тип и
указывает на то, что она где-то определенна.
В программе может быть сколько угодно
описаний одной и той же переменной, но определенна может быть только один раз.
Внутри одного блока могут быть другие блоки
и если во внутренних блоках определить переменные с именами, совпадающими с
именами переменных во внешних блоках, то внутренние имена переменных перекроют
видимость для внешних переменных. Перекрытие области видимости не сказывается
на времени жизни переменных.
Автоматические переменные разрешается
определять только в начале блока, перед выполняемыми операторами.
Автоматические переменные используют память,
выделяемые в системном стеке, что делает процедуру отведения/очистки памяти под
них весьма быстрой
Статически созданные переменные рождаются в
момент запуска программы и умирают в момент прекращения работы программы.
Память под них отводится в общей куче (heap), т.е. в обще-используемой памяти.
Ее размер ограничивается размером памяти, доступной программе. Статически
созданные переменные это - либо глобальные переменные (т.е. переменные,
определенные вне всех блоков программы), либо локальные
Если есть несколько переменных с одинаковым
именем, то внешние статические переменные перекрывают область видимости
соответствующих глобальных переменных, а локальные переменные перекрывают
область видимости соответствующих внешних статических переменных.
20_02
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "20_02_3.h"
int task (char* file_in, char* file_out)
{
FILE
*f_in, *f_out;
char
data_1[256], data_2[256];
int f =
0, i, j, k;
f_in =
fopen(file_in, "r");
if (f_in
!= NULL)
{
f_out =
fopen(file_out, "w");
if
(f_out != NULL)
{
while
(fscanf(f_in, "%s", data_1) == 1) //Цикл пока мы считываем значения из файла
//Считывать с помощью
fscanf() здесь не очень правильно
{
for
(i = 1; i < strlen(data_1); i++) //Запускаем цикл до длины строки
{
if
(data_1[i] == toupper(data_1[i])) f = 1; //Проверяем, большая буква или нет
}
j = 1; i = 1;
if (f == 1) //Если буква большая
{
data_2[0] = tolower(data_1[0]); //... то
делаем её маленькой и ищем следующую большую
while (i < strlen(data_1))
{
if (isalpha(data_1[i]) == 1 &&
data_1[i] == toupper(data_1[i])) //Проверяем, буква ли вообще и большая ли,
ищем следующую такую букву
// Как только нашли - делаем маленькой, и
ставим перед ней _. Точнее, ставим во 2 массив _, увеличиваем индекс
{
data_2[j] = '_';
j++;
data_2[j] = tolower(data_1[i]);
j++;
i++;
}
else
{
data_2[j]
= data_1[i];
j++;
i++;
}
}
for
(i = 0; i < j; i++) fprintf(f_out, "%c", data_2[i]);
}
if (f
!= 1)
{
if
(strstr(data_1, ";") != NULL) fprintf(f_out, "%s\n",
data_1);
else
if (strstr(data_1, "#") != NULL) fprintf(f_out, "\n%s ",
data_1);
else
if (strstr(data_1, "}") != NULL || strstr(data_1, "{") !=
NULL) fprintf(f_out, "\n%s\n", data_1);
else
fprintf(f_out, "%s ", data_1); //Ищем в строках #, }, { . При нахождение переходим на новую строку
}
f = 0;
}
}
else return -2;
}
else return -1;
fclose(f_in); fclose(f_out);
return
0;
}
1.
Сортировка пузырьком
Алгоритм оптимален, если на обмен элементов
тратится O(N) времени.
Сортировка в худшем случае работает не менее
чем за O(N^2) времени. Пусть у нас есть n элементов.
for (i = 0; i < (n - 1); i++)
for (j = 1; j < n; j++)
if (arr[i]
> arr[j]) swap (arr[i],arr[j])
Это вообще не сортировка
Худший случай - это когда нам дан обратно
упорядоченный массив. В там случае, чтобы поменять местами 1 и последний
элемент, нужно n-1 операций. Для второго
и опять же последнего - n-2 и так далее.
Легко видеть, что в итоге число перестановок больше чем N^2.
Сортировка слиянием.
Проводится для двух упорядоченных массив
длинной m и n. В худшем случае работает за n+m операций. Суть состоит в
следующем. Мы последовательно сравниваем
элементы в двух массивах.
arr[n+m], arr_i[n], arr_j[m];
i = 0, j = 0;
while (i < n || j < m)
{
if (arr_i[i] <
arr_j[j])
{
arr[i+j] =
arr[i];
i++;
} else {
arr[i+j] =
arr[j];
j++;
}
}
Это не сортировка, а алгоритм слияния
упорядоченных массивов
Если от какого-либо массива останется
непройденная часть, то просто приклеиваем её в конец нашего.
Алгоритм с рекурсией. Пусть нам дана
неупорядоченная последовательность элементов длины n. Если число элементов
равно 1 - то выход.
Если их два - то просто сравниваем их и
упорядочиваем.
Для более чем 2 элементов.
(1) Определяем длины двух массивов как n1 =
[n/2] и n2 = n - n1.
(2) Вызываем функцию (1) до тех пор, пока не
останется один элемент
(3) Массив из одного элемента считается
упорядоченным. Сливаем 2 массива из 1 элемента в 1 упорядоченный массив из
двух.Получаем снова упорядоченный массив.
Снова вызываем функцию (3) до тех пор, пока
не сольём весь массив.
Это тоже не сортировка
Данный алгоритм можно реализовать без
рекурский, циклом while.
2. Типы базовых переменных.
Целочисленные типы: int, char, short и long.
int - integer. занимает 4 байта, то есть
принимает 2^32 значений. из них первые 2^31 - это отризацательные, оставшиеся
(2^31) - 1 - положительные.
Это верно не на всех машинах и компиляторах
Опредяют в программе следующим образом:
int x;
int x = 1000;
int a, b, ...;
int a = 100, b = 2, c, d = 4, ...;
char. хранит 256 значений, от -128 до 127.
Каждое из значений совпадает с номером в таблице ASCII. Хранит в себе число, а
не символ!
объявление сходно с типом int.
char a;
char a = -1;
char a = 'a';
при этом, объявления char = 1 и char = '1'
не равы друг другу. во втором случае в переменной будет хранится номер символа
'1'.
short и long - конкретные размеры
устанавливаются аритектурой и средой. Чаще всего short занимает 2 байта, а тип
long совпадает с int.
Все вышеперечисленные типы - со знаком.
Существует специальный беззнаковый модификатор - unsigned. Добавляется перед
типом, например unsigned int
Вещественные типы.
float - вещественное число с одинарной
точностью. Занимает 4 байта. В настощее время мало используется, т.к.
современные ПК при работе с float сначала переводят
их в double, потом производят вычисления и
переводят обратно.
double - вещественное число с двойной
точностью. Занимает 8 байтов.
Так же существует тип void, для создания
функции которая ничего не возвращает.
23_08
Задача:
#include <stdio.h>
#include <stdlib.h>
struct list
{
int
chis, znam;
struct
list * next;
};
int task_23_08(float x, char* filename_in,
char* filename_out)
{
FILE
*f1, *f2;
int i=1,
j, k=50, m, n;
struct
list *mn, *firstlink, *curlink;
f1=fopen(filename_in, "r");
long
double tmp, tmp2;
if
(f1!=NULL)
{
f2=fopen(filename_out, "w");
if (f2!=NULL)
{
mn=(list*)malloc(k*sizeof(list));
fscanf(f1, "%d", &m);
fscanf(f1, "%d", &n);
mn[0].chis=m;
mn[0].znam=n;
while (fscanf(f1, "%d", &m) == 1)
{
fscanf(f1, "%d", &n);
mn[i].chis=m;
mn[i].znam=n;
mn[i-1].next=&mn[i];
i++;
if (i==k)//выход за границы
массива уже произошел
{
k*=2;
mn=(list*)realloc(mn,k);
//переотведение
памяти делает неверными все созданные ссылки
}
}
mn[i-1].next=&mn[0];
//----------------------------
firstlink = curlink = &(mn[0]);
tmp = 1/(long double)i;
do
{
tmp2
= (long double)(curlink->chis)/(curlink->znam);
tmp2
= fabsl(x-tmp2);
if
(tmp2<=tmp)
{
fprintf(f2, "%d %d ", curlink->chis, curlink->znam);
}
curlink = curlink->next;
}
while
(firstlink != curlink);
//----------------------------
fclose(f1);
fclose(f2);
}
else
return -2;
}
else return -1;
return 0;
}
1)Структура данных это реализация понятия
множества элементов определенного типа.
Вместе со способом хранения задается набор
операций по добавлению, поиску, удалению элементов множества.
Дек это структура данных, представляющих
собой упорядоченное множество элементов,
в котором элементы можно добавлять в начало и конец множества и
извлекать их можно с обеих сторон. Создние дэка предполагает наличие следующих
функций: инициализация, добавление
элемента в начало дека, добавление элемента в конец дека
,взятие/извлечение элемента из начала, дека,
взятие/извлечение элемента с конца дека, проверка: пуст ли дек?очистка дека.
Циклические реализации дэка
используются аналогично очереди.
В данном случае перемена местами пары слов
из лекций лишило фразу смысла
Очередью называется структура
данных,организованных по принципу first-in, first-out , т.е. элемент, попавшим
в множество первым, должен первым его покинуть. При практическом использовании
часто налагается ограничение на длину очереди, т.е. требуется, чтобы количество
элементов не превосходило N для некоторого целого N.
Создание очереди предполагает наличие
следующих функций: инициализация,
добавление элемента в конец очереди,
взятие/извлечение элемента с начала очереди, проверка: пуста ли очередь?
, очистка очереди.
Обычно, используется реализация
циклической очереди. Т.е. под очередь отводится некоторый непрерывный кусок памяти (массив) и при подходе хвоста очереди к
концу массива хвост автоматически перебрасывается на противоположный конец
массива.
Очередь и дэк это различные реализации
структур данных
Ну нельзя же так откровенно списывать
лекции.
2) Область видимости переменных и время
жизни переменных.
Переменные
Основные типы
В языке С есть две основные разновидности
базовых типов: целые и вещественные. К целым типам относятся типы: char, short,
int, long.
Перед каждым вышеупомянутым типом может
присутствовать слово signed или unsigned. Идентификатор signed указывает на то,
что переменная имеет знак, а unsigned - на отсутствие знака у переменной. По
умолчанию, все переменные имеют знак. Исключением является переменная типа
char. Полагаться на наличие/отсутствие знака у переменной данного типа нельзя,
т.к. данное свойство может быть изменено с помощью ключей компилятора.
К вещественным типам относятся: float,
double.
Кроме базовых типов, существуют производные
типы, задающиеся с помощью понятий массив, указатель, функция, структура,
объединение. Одними из основных понятий программирования являются описание и
определение объектов.
Описание переменной задает ее тип и
указывает на то, что переменная где-то определена. Признаком описания
переменной служит наличие ключевого слова extern перед оператором, ее задающим.
Отсутствие ключевого слова extern говорит об определении переменной.Определение
переменной указывает место в программе, задающее время рождения переменной. При
определении переменной можно задать инициализирующее ее значение. Определение
переменной всегда является ее описанием.В программе может быть сколько угодно
согласующихся описаний одной и той же переменной, но должно быть ровно одно ее
определение.Время жизни переменной задается интервалом между моментом рождения
переменной и моментом ее смерти. Внутри этого интервала гарантируется
сохранность значения переменной, т.е. значение переменной может быть изменено
только с помощью соответствующих операторов программы.С точки зрения времени
жизни, в языке С бывает два вида
переменных: статические и автоматические.
Автоматические переменные всегда
определяются внутри некоторого блока. Автоматические переменные всегда являются
локальными, т.е. их область видимости ограничивается их блоком. Автоматические
переменные рождаются в момент входа выполнения программы в данный блок и
умирают в момент выхода из блока.Внутри одного блока могут быть другие блоки и
если во внутренних блоках определить переменные с именами, совпадающими с
именами переменных во внешних блоках, то внутренние имена переменных перекроют
видимость для внешних переменных. Перекрытие области видимости не сказывается
на времени жизни переменных.Автоматические переменные разрешается определять
только в начале блока, перед выполняемыми операторами.Автоматические переменные
используют память, выделяемые в системном стеке.Статически созданные переменные
рождаются в момент запуска программы и умирают в момент прекращения работы
программы. Память под них отводится в общей куче (heap). Статически созданные
переменные это - либо глобальные переменные, либо локальные.
Осталось упомянуть о внешних статических
переменных - глобальных переменных, область видимости которых ограничена данным
файлом. Как и все глобальные переменные, эти переменные определяются вне всех
блоков программы, но перед их определением написано ключевое слово static.
Если есть несколько переменных с одинаковым
именем, то внешние статические переменные перекрывают область видимости
соответствующих глобальных переменных, а локальные переменные перекрывают
область видимости соответствующих внешних статических переменных.
Изначально в языке С присутствуют
регистровые переменные. Наличие ключевого слова register перед определением
переменной служит указанием компилятору использовать внутренние машинные
регистры для хранения данной переменной. На данный момент, при использовании
оптимизирующих компиляторов наличие данного типа, как правило, не может служить
для ускорения работы программы. Более того, обязательное использование регистра
для хранения данной переменной запрещает его использование для других целей,
что может послужить поводом к замедлению работы программы.
Ну нельзя же так откровенно списывать
лекции.
24_10
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "24_10.h"
int task(char *fRead, char *fWrite)
{
FILE
*f1,*f2;
f1=fopen(fRead,"r");
f2=fopen(fWrite,"w");
if(f1
!=NULL && f2 !=NULL)
{
int
n=0, i=0, sum=0, temp=0, j=0, index=0;
int
*a=NULL, **p=NULL;
fscanf(f1, "%d", &n);
a=(int*)malloc(sizeof(int)*n);
for(i=0; i<n; i++){
fscanf(f1, "%d", &a[i]);
sum
+=a[i];
if(a[i]>temp){
temp=a[i];
index=i;
}
}
p=(int**)malloc(n*sizeof(int*)+sum*sizeof(int));
p[0]=(int*)(p+n);
for(i=1;
i<n; i++)
p[i]=(int*)(p[i-1]+a[i-1]);
for(i=0;
i<n; i++)
for(j=0; j<a[i]; j++)
fscanf(f1,"%d", &p[i][j]);
for(i=0;
i<temp; i++)
fprintf(f2, "%d ", p[index][i]);
}
fclose(f1);
fclose(f2);
return 0;
}
M1.
10 БИЛЕТ.
Пак Илья.
Вопросы:
1. Бинарные деревья поиска. Поиск, добавление,
удаление элемента.
2. Потоковый ввод/вывод для бинарных файлов.
Открытие файла, ввод/данных с помощью функций fread/fwrite, закрытие файла.
3. Во входном текстовом файле задан
двумерный массив целых чисел. Число строк массива задается первым числом в
файле. Далее для
Ответы:
1. Бинарным деревом поиска называется дерево
из каждой вершины которого выходит две ветви, причем все элементы правого
поддерева больше вершины из которой они выходят, а элементы левого порядка -
меньше.
Поиск элемента делается следующим образом: мы двигаемся от корня дерева
вниз по вершинам, каждый раз проводя операцию сравнения.
Если значение вершины меньше требуемого, то
переходим в левое поддерево, а если больше то в правое. Если значение равно
искомому, то элемент найден.
Добавление элемента осуществляется с помощью операции "поиск
элемента". Элементы добавляют, как правило, в конец. Сравниваем текущую
вершину с "вставляемой" и переходим в правый дочерний уровень если
элемент больше и в левый если меньше.
Удаление элемента. При удалении элемента у нас остается "пустая
вершина", которую нужно заполнить элементом. Он (элемент) берется из
дочерних поддеревьев. Мы спускаемся на самый нижний уровень левого поддерева и
берем его самый правый элемент А
если его нет? . В этом случае мы
будем иметь наибольший элемент из левого поддерева. При этом все элементы из
правого поддерева будут больше нашего элемента. Можно также взять самый левый
нижний элемент из правого поддерева. Он будет большего любого элемента из
левого поддерева и меньше любого элемента из правого поддерева.
2. Для открытия файла и создания указателя
используются зарезервированные слова FILE и команду fopen.
FILE *f1; // f1-название потока.
f1=fopen("filename","r");
//в потоке содержится файл filename. "r"-файл открыт для чтения.
Для
бинарных файлов используются "rb","wb" соответственно.
Для
считывание элементов используется команда fread.
fread(void*
буфер, size_t кол-во байт, size_t счетчик, FILE* файл);
void*
буфер - указатель на место в памяти куда будет считываеться данные
size_t
кол-во бай - кол-во считываемых байт
size_t
счетчик - счетчик считанных байт
FILE*
файл - сам поток
Для
записи элементов используются команда fwrite.
const
void* буфер - указатель на место в
памяти куда будет производиться запись
size_t
кол-во бай - кол-во считываемых байт
size_t
счетчик - счетчик считанных байт
FILE*
файл - сам поток
25_01
Задача:
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <ctype.h>
void task_25_1(char *filename1, char
*filename2) {
FILE
*f1, *f2;
int
count = 0;
char
cherta = '_', first, a, previous;
f1 =
fopen(filename1, "r");
f2 =
fopen(filename2, "w");
if(fscanf(f1, "%c", &first) != cherta) {
first = first - 32;
fprintf(f2, "%c", first);
}//Зачем
сравнивать код возврата fscanf () и cherta ???
while(fscanf(f1, "%c",
&a) == 1) {
if(a != cherta) {
previous = a;//это же не
используется
fprintf(f2,
"%c", a);
}
else {
if(fscanf(f1, "%c", &a) == 1) {
a = a - 32;//откуда
взялось 32???
fprintf(f2, "%c", a);
}
}
}
fclose(f1);
fclose(f2);
//оставшийся
кусок кода, конечно, ясно, зачем присутствует, но как-то это не спортивно…
f1 = fopen(filename1,
"r");
while(fscanf(f1, "%c", &a) == 1) {
if(a == cherta)
++count;
}
fclose(f1);
if(count == 0) {
f1 = fopen(filename1, "r");
f2 = fopen(filename2, "w");
while(fscanf(f1, "%c", &a) == 1) {
fprintf(f2, "%c", a);
}
fclose(f1);
fclose(f2);
}
}
26_15
Задача:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "26_15h.h"
int First=1;
typedef
struct
sItem_
{
double
v;
struct
sItem_ *next, *prev;
} sItem;
typedef
struct
sList2_
{
sItem
*head, *tail;
sItem
*cur;
}
sList2;
sList2* InitEmpty()
{
sList2
*L;
L =
(sList2*)calloc(1, sizeof(sList2));
L->head=(sItem *)calloc(1,sizeof(sItem));//какая-то странная реализация
L->tail=(sItem *)calloc(1,sizeof(sItem)); //какая-то странная реализация
L->cur=L->head;
L->cur->prev=L->head;
L->cur->next=L->tail;//тогда уже надо L->tail->prev задавать
if (L == NULL) return NULL;//бессмысленно
return
L;
}
int AddAfter(sList2 *L2, double value)
{
sItem *newItem;
if (!First)
{
newItem = (sItem*)calloc(1,sizeof(sItem));
if
(newItem == NULL) return -1;
newItem->v
= value;
newItem
-> prev = L2 -> cur;
newItem
-> next = L2 -> cur -> next;
L2
-> cur -> next = newItem;
newItem
-> next -> prev = newItem;
L2->cur=newItem;
} else {
L2->cur=L2->head;
L2->cur->v=value;
First = 0;
L2->cur->next=L2->tail;
}
return
0;
}
int AddBefore(sList2 *L2, double value)
{
sItem
*newItem;
if
(!First) {
newItem
= (sItem*)calloc(1,sizeof(sItem));
if
(newItem == NULL) return -1;
newItem->v = value;
newItem->prev=L2->cur->prev;
newItem->next=L2->cur;
L2->cur->prev->next=newItem;
L2->cur->prev=newItem;
L2->cur=newItem;
} else {
L2->cur=L2->head; L2->cur->v=value; First = 0;
L2->cur->next=L2->tail; }
return
0;
}
int CurNext(sList2 *L2)
{
if (L2
== NULL) return -1;
L2 ->
cur = L2 -> cur -> next;
return 0;
}
int CurPrev(sList2 *L2)
{
if (L2
== NULL) return -1;
L2 -> cur = L2 -> cur -> prev;
return
0;
}
double GetVal(sList2 *L2)
{
return
L2->cur->v;
}
int GoFirst(sList2 *L2)
{
while
(L2->cur!=L2->head) CurPrev(L2);
return
0;
}
int DelCur(sList2 *L2)
{
sItem
*Cur=L2->cur;
if
(L2->cur!=L2->head || L2->cur!=L2->tail) {
L2->cur->next->prev=L2->cur->prev->next;
free(Cur);
}
return
0;
}
int Destroy(sList2 *L2)
{
while
(L2->cur!=L2->head) DelCur(L2);
//у Вас же после
первого добавления: L2->cur=L2->head;
//т.е. удаление в
этом случае не произойдет
free(L2);
return
0;
}
int task_26_15(char *inf,char *of,double x)
{
FILE
*fin=fopen(inf,"r"),*fout=fopen(of,"w");
if((fin==0) || (fout==0)) return 1;
int
n=0,i;
double
k,xmin,xmax;
sList2 *List = InitEmpty();
while
(fscanf(fin,"%lf ",&k)==1) { AddAfter(List,k); n++;}
for
(i=0;i<n;i++) {
k=GetVal(List);
CurPrev(List);
xmin=(x-(double)((double)1/(double)n));
xmax=(x+(double)((double)1/(double)n));
if ((k
>= xmin) && (k <= xmax)) fprintf(fout,"%lf ",k);
}
Destroy(List);
fclose(fin);fclose(fout);
return
0;
}
Реализация сильно неправильная
Пономаренко
Бронеслава.
Группа
М1-12, Билет - 15.
1)Нижние оценки. Теорема о связи нижних
оценок времени решения задач на принятие решения и количества
линейно-разделимых компонент множества точек, на которых решением задачи будет
<да>. Пример задачи поиска всех различных элементов множества.
На входе таких задач выдается всего одни бит
информации, т.е. <да> или <нет>.
На входе?
Будем рассматривать алгоритмы решения задач
о принятии решений, которое сводится к бинарному дереву принятия решений. Под
деревом принятия решения имеется в виду следующее. Пусть на входе нашего
алгоритма находится вектор входных данных (a принадлежит R). Рассмотрим
бинарное дерево, в каждой вершине которого вычисляется некоторая функция от
вектора <а> и в зависимости от знака этой функции происходит на правую
или левую ветвь дерева. Каждая конечная вершина дерева будет называться либо
принимающей, либо отвергающей, в зависимости от приписанного ей
соответствующего атрибута. Достижение принимающей вершины означает выдачу
алгоритмом ответа <да>, а отвергающей соответственно - <нет>.
Дерево принятия решения называется
алгебраическим деревом степени n. Если функции в вершинах дерева являются
многочленами степени не выше n.
Далее рассмотрим алгоритмы, представимые в
виде алгебраического дерева принятия решений степени 1. Будем предполагать, что
время вычисления каждой функции в вершине дерева есть О(1). Приведенная далее
теорема верна и для деревьев высшей степени, но для ее доказательства требуется
весьма серьезные факты из теории
функций, которые здесь привести не сможем.
Введем два определения.
Разделимые множества. Множества А, B принадлежащие
R наз. Раздельными (линейно раздельными) если для любых а принадлежащих А, b
принадлежащих В найдется с принадлежащее [a,b], такое, что с не принадлежит ни
А и ни В.
Связное множество. Связным множеством наз.
Такое множество, что при любом его разбиении на два непересекающихся непустых
подмножества одно из них содержит точку, предельную для другого. В евклидовом
пространстве открытое множество связано тогда и только тогда, когда любые две
его точки можно соединить целиком лежащей в нем ломаной.
Пусть множество W содержится во множестве R
- множество точек, на которых решением задачи будет <да>. Пусть #W -
количество разделимых связных компонент множества W. Тогда в рамках алгоритмов,
описывающихся алгебраическими деревьями степени 1. Время решения задачи есть
(log(2)#N)
Очередные скопированные лекции…
2) Константы (целые, вещественные,
строковые, символьные).
Подобно переменным, константы представляют
собой ячейки памяти, предназначенные для хранения данных. Но в отличии от переменных, константы не изменяются.
Литеральная константа - это значение,
непосредственно вводимое в самой программе (например: int x=28;//28 -
литеральная константа)
Списано с адреса http://www.tinlib.ru/kompyutery_i_internet/osvoi_samostojatelno_s_za_21_den/p6.php
Символьные константы заключаются в одинарные
кавычки. В языке с определены многобайтовые (состоящие из одного или более
байт) и широкие (обычно длиной 16 бит) символы. Они используются для
представления символов языков, имеющих в своем алфавите много букв.
Многобайтовый символ записывается в одинарных кавычках, например 'xy'.
Целые числа определяются как числа без
дробной части. Например, 10 и -100 - это целые константы. Константы в плавающем
формате записываются как числа с десятичной точной, например, 11.123.
Допускается также экспоненциальное представление чисел ( в виде мантиссы и
порядка): 111.23е-1.
Шестнадцатеричные и восьмеричные константы.
Иногда удобнее использовать не десятичную, а
восьмеричную или шестнадцатеричную
систему. Шестнадцатеричная константа начинается с 0х, а восьмеричная с 0.
Строковые константы.
Язык С поддерживает тип констант - строковые
константы. Строка - это последовательность символов, заключенных в двойные
кавычки.
Не следует путать понятия строки и символа.
Символьная константа заключается в одинарные кавычки.
Списано с адреса
http://cpp.com.ru/shildt_spr_po_c/02/0209.html
27_03
Задача:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "27_3.h"
#define MAX 256
char line[MAX];
int task_27_3(char *infilename, char*
outfilename)
{
FILE
*fin=fopen(infilename,"r");
FILE
*fout=fopen(outfilename,"w");
if(fin==NULL)
return
1;
else
if(fout==NULL)
return
2;
else
{
char*
match=NULL;
while(
fgets(line, MAX, fin) != NULL )
{
if( (match = strstr(line, "#define" )) != NULL )
{
fprintf( fout, "%s", match + sizeof("#define") );
fprintf( fout, "\n" );
}
}
return
0;
}
fclose(fin);
fclose(fout);
}
Сагатов Шухрат, М1-12
1
Вопрос.
Quicksort
(с английского <Быстрая сортировка>) - алгоритм сортировки с
использованием рекурсии. Идея алгоритма состоит в следующем:
- выбирается опорный элемент m (обычно
медиана)
- Меняем элементы в массиве по принципу: все
меньшие или равные опорному слева, остальные справа; для этого обозначаем через
I и R минимальный и максимальный индексы элементов. (1) Пока a[i]<a[m]
вып-ем i++, a[r]>a[m] вып-ем r--; (2) Если i<=r меняем элементы a[i] и
a[r] местами затем снова (1);
-рекурсивно сортируем подмассивы
Время работы.
Пусть мы сможем найти медиану за ~N. На
k-том шаге у нас получится порядка 2k частей, в каждой из которых середина
ищется за ~N/2k, т.е на каждый шаг уходит около ~N. Чтобы прийти к частям длины
1 нам понадобится ~logN. Следовательно сортировку можно выполнить за ~O(NlogN).
2
Вопрос.
Константы в языке C представляют собой
неизменяемые численные величины.
Целая константа - это десятичное,
восьмеричное или шестнадцатеричное целое число (тип int).
Вещественные константы (с плавающей точкой)
- это действительные числа. Содержат целую часть, дробную часть и экспоненту. Эти константы
символизируют всегда положительное число. Знак <-> означает операцию
вычитания. (тип double).
Символьная константа - это любой символ,
заключенный в одинарные кавычки. По сути, символьная константа - число,
значение ASCII - кода, соответствующего данному символу. К примеру, '0'=0. (тип
char).Это не верно
В языке С строковая константа - это лишь
массив из символьных констант. Концом строки-массива служит символ '\0'. (тип )
29_04
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "29_04task.h"
int task(char *file_in, char *file_out)
{
FILE
*f1, *f2;
int i=0,
j=0, k=0, length=0;
char
string_old[3000], string_new[3000], c;
f1 =
fopen(file_in, "r");
if(f1 ==
NULL)
{
fclose(f1);
return
0;
}
f2 =
fopen(file_out, "w");
if(f2 ==
NULL)
{
fclose(f1);
fclose(f2);
return
0;
}
while(fscanf(f1, "%c", &c)==1)
string_old[i++] = c;
//это не будет
работать для больших файлов
length = i;
for(i=0;
i<length; i++)
{
if(string_old[i] == '\'')
{
i++;
while(i < length && string_old[i] != '\'')
string_new[k++] = string_old[i++];
string_new[k++] = ' ';
}
}
for(i=0;
i<k; i++)
fprintf(f2, "%c", string_new[i]);
fclose(f1);
fclose(f2);
return
0;
}
Бехзод Солиев. 29_04
Сортировка алгоритмом heapsort
Пусть дан массив
A[1…n], состоящий из n элементов. Мы будем его называть
пирамидально-упорядоченным, если выполняются следующие условия:
A[i] >= A[2*i] и
A[i] >= A[2*i+1] (для всех таких i, чтобы эти выражения имели смысл. То есть
нельзя выходить за пределы массива)
Отсюда очевидно, что
данный массив будет представлять древообразную структуру. Дерево будет
бинарным. Оно также будет либо полным, либо почти полным. Узлы дерева (вершины)
представляют собой значения элементов массива. Каждый узел имеет два ребра, то
есть два потомка. Другими словами, A[i] – это предок, A[2*i] и A[2*i+1] –
дочерние элементы. Заполнение дерева идет слева направо. Понятно, что, если и
будут незаполненные узлы, то они будут снизу и справа. (то есть на самом нижнем
уровне дерева) Такая структура называется пирамидой. При помощи неё работает
алгоритм heapsort.
Заметим также, что
глубина такого дерева будет [logN] + 1.
Заметим, что если
массив пирамидально-упорядочен, то его первый элемент будет максимальным. Если
мы возьмем этот элемент и “отрежем” его из дерева, а затем новое полученное
дерево снова приведем к пирамидально-упорядоченному виду, то снова в новом
дереве (или в массиве) первый элемент будет максимальным. То есть, как бы
говоря, отрезая первые элементы, мы получим отсортированный массив. В этом и
суть пирамидальной сортировки.
В данном алгоритме мы
будем использовать структуры heapify(A, i , n).
При помощи неё мы
будем массив приводить к пирамидально-упорядоченному виду.
A – это массив,
который необходимо обработать. C индекса i начинается рассматриваемое
поддерево, а n – это количество
элементов во всем дереве.
Процедура heapify(A,
I, n) проверяет следующие условия:
A[i] >= A[2*i] и
A[i] >= A[2*i+1]
Если они выполняются,
то процедура продолжает работу, оставив эти элементы без изменений. Если же нет, то она выбирает
максимальный из них и меняет его местами с A[i], что логично, так как предком
должен быть наибольший элемент. Далее, вызываем процедуру heapify(A, I, n) для
нового предка. Заметим, что свойство пирамидально-упорядоченности останется для
третьего элемента верным. (Это тот элемент, который мы не трогали)
Теперь приведем сам
алгоритм heapsort:
Heapsort(A, n) {
I = n – 1
while (I >= 1) {
heapify(A, I, n); I = I – 1 }
I = 1
while (I <= n – 1)
{ swap (A[1] , A[n-i+1]) ; heapify(A, 1, n-i); I = I + 1 }
}
В первом цикле
создается пирамида. Потом мы получаем, массив с максимальным первым элементов.
Используя это свойство, мы получаем упорядоченный массив.
Сложность процедуры
Heapify(A, I, N) – O(log(K)), где K – это глубина поддерева.
Сложность всего
алгоритма – O(N*log (N)).
Структуры, объединения.
Структуры – это наборы
логически связанных переменных, объединенных под одним названием. Иногда их
называют агрегатами. Структуры создаются из объектов других данных.
Описание структуры
выглядит следующим образом:
struct info {
char name[100];
int grade;
};
Ключевое слово
определяет структуру. “info” – это
имя-этикетка структуры. Элементами
структуры являются массив из символов name[100] и целочисленная переменная
grade.
Имя этикета является
вообще необязательным при определении структуры. Но используется при объявлении
переменных. Стоит сказать, что написав вышеприведенный код, мы лишь указываем
новый тип данных. То есть ничего в данном случае не объявляется. И память
соответственно не отводится. Элементами структуры не могут быть объекты тог же
типа, что и сама структура.
Объявлять переменные
типа структуры можно следующим образом:
1)
struct info {
char name[100];
int grade;
} a, b;
2) struct
info a, b;
В обоих случаях были объявлены
переменные a и b типа struct info.
Обращение к элементам
структуры могут осуществляться двумя способами: через операцию элемента
структуры “.” (её также называют операцией точка) и через операцию указателя
структуры “->” (также известную, как операция стрелка).
Например, если
объявлены переменная temp типа struct info, то обращение имеет следующий
вид: temp.grade.
Рассмотрим следующую
программу:
#include <stdio.h>
#include <stdlib.h>
struct info {
char name[100];
int grade;
};
struct info a;
int main()
{
struct info *ptr;
ptr
= &a;
a.grade
= 0;
printf("%d\n", ptr->grade);
return 0;
}
Мы присваиваем
переменной a.grade значение нуль. Далее, с помощью указателя обращаемся к этой
переменной и выводим её значение.
Если структура
содержит в качестве своего элемента указатель, который ссылается на тип
структуры, в которой она объявлена, то она называется структурой, ссылающейся
на себя. С помощью таких структур можно создавать разные динамические структуры
данных, такие как связанные списки, очереди, стеки и т.д.
Объединения – это
произвольный тип данных, элементы которого разделяют одну и ту же область
памяти. Они объявляются с помощью ключевого слова union. Оно происходит так же,
как и при объявлении структур.
union number {
int x;
double y;
}
Память, которое
отводится для объединения, должна быть
достаточной для хранения его самого большого (в плане занимаемой памяти)
элемента. (в случае struct number это тип double)
Объединение содержит несколько типов данных. Но в
определенный момент времени можно ссылаться только на один элемент, то есть на
один тип данных.
Доступ к элементам
производится аналогично структурам.
Объединения могут быть объявлены внутри
структур.
30_16
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "30_16_header.h"
int main( void )
{
char
instr[255], outstr[255];
//
Ввод названий входного и выходного файла
printf( " Vvedite nazvanie
vxodnogo fayla \n" );
if(
scanf( "%s", instr ) == 0 ) printf("Oshibka schitivaniya"
);
//ошибку так
проверять нельзя
printf(
" Vvedite nazvanie vixodnogo fayla \n" );
if(
scanf( "%s", outstr ) == 0 ) printf("Oshibka schitivaniya"
);
task(
instr, outstr );
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int qsort( int *main_array, int left, int right
)
{
int
middle = main_array[ (left + right)/2 ];
int i =
left, j = right, temp = 0;
while
( i < j )
{
// поиск элементов для последующей
переброски
while ( main_array[i] < middle )
i++;
while ( main_array[j] > middle )
j--;
// замена элементов местами
if ( i <= j )
{
temp
= main_array[i];
main_array[i] = main_array[j];
main_array[j] = temp;
i++;
j--;
}
}
// рекурсивно применяем алгоритм для обоих
частей ( если там они еще остались )
if ( j > left )
qsort(main_array, left, j);
if ( i
< right )
qsort(main_array, i, right);
return
0;
}
int task( char * filein, char * fileout )
{
int
*main_array, i = 0, numb = 0;
// заполнение массива из файла
FILE *
fileopen = fopen( filein, "r" );
if(
fscanf( fileopen, "%d", &numb ) == 0 ) printf("fayl
pust");
main_array = ( int* )malloc( (sizeof( int )) * numb );
for( i
= 0; i < numb; i ++ )
fscanf( fileopen, "%d", &(main_array[i]));
fclose(
fileopen );
//////////////////////////////////////////////////
qsort(
main_array, 0, numb - 1);
int k =
0, j = 0, temp_el = 0, q = 0;
for( i
= 0; i < numb - 1; i ++ )
{
if(
main_array[i] == main_array[i + 1] )
{
k =
k + 1;
for( j
= i + 1; j < numb - 1; j ++ )
{
temp_el = main_array[j + 1];
main_array[j] = main_array[j + 1];
main_array[j + 1] = temp_el;
}
}
}
/////////////////////////////////////////////////
// вывод отсортированного массива в файл
FILE *
filewrite = fopen( fileout, "w" );
for( i
= 0; i < numb - k + 1; i ++ )
fprintf( filewrite, "%d ", main_array[i] );
fclose(
filewrite );
return 0;
}
Билет 16. Фазлыев Руслан М2-12.
1.
Нижняя оценка - минимально возможное время
работы алгоритма.
Это абсолютно не верно.
Два множества А и Б называются
линейно-разделимыми, если для любых элементов а из А и б из Б Есть отрезок
[а,б] который ни содержится ни в одном из множеств А и Б. Это не верно.
Связным множество - множество, что при любом
его разбиении на два непересекающихся непустых подмножества одно из них
содержит точку, предельную для другого.
Теорема.
Пусть задано некотрое множество точек W, на
которых решением задачи будет "да". Пусть n - количество разделимых
связных компонентов множества W. Тогда, в рамках алгоритмов, описывающихся
алгебраическими деревьями степени 1, время решения задачи есть o(log2(n)).
Док-во.
Установим, что количество принимающих вершин
дерева принятия решений не меньше
n. Для этого докажем, что все
элементы, относящиеся к одной принимающей вершине дерева решений, находятся
внутри одной разделимой связной компоненты W.
Предположим противное: существует принимающая вершина дерева принятия решений,
в которую попадает алгоритм при использовании двух различных a,b из W , таких что a и b принадлежат различным
разделимым связным компонентам Va , Vb из W,
соответственно. Рассмотрим [a,b]. Линейные функции от N переменных
обладают свойством монотонности на отрезке, поэтому все функции, вычисляющиеся
в вершинах дерева принятия решений, сохраняют свой знак на [a,b]. Т.е. весь отрезок [a,b] из W (т.к. все точки
из отрезка обязаны попасть в одно и ту же принимающую вершину). Это противоречит
предположению о принадлежности a и b различным разделимым компонентам.
Из предположение следует, что количество
вершин бинарного дерева принятия решений не меньше n, из чего сразу следует,
что высота дерева не меньше log2(n).
Задача о проверки все ли элементы
различаются, относится к классу задач о принятии решения. Это значит, что на
выходе таких задач выдается всего один бит информации (да или нет). Все
алгоритмы решения задач о принятии решений можно свести к бинарному дереву
принятия решений. Пусть на входе нашего алгоритма находится вектор входных
данных. Рассмотрим бинарное дерево, в каждой вершине которого вычисляется
некоторая функция от вектора и в зависимости от знака этой функции происходит
переход на правую или левую ветвь дерева.
Дерево принятия решений называется алгебраическим
деревом принятия решений степени n, если функции в вершинах дерева являются
многочленами степени не выше n.
Очередная копия лекций.
2.
Структуры данных - это способ хранения
обьедененных одним типом элементов. В зависимости от использования, имеются
разные реализации.
Как правило, элементы структуры связаны друг
с другом по смыслу.
Способ задания:
struct НАЗВАНИЕ
{
переменные
....
....
};
Например:
struct point_
{
double x;
double y;
};
point A;
Эта структура задает точку с координатами
А(х,у). На самом деле не каких переменных не создается, а описывается ТИП. Т.е
пока мы не обьявим переменную типа Point, пременная существовать не будет.
Доступ осуществляется следующим образом:
имя_объекта.имя_элемента. В нашем случае это A.x ( A.y ).
Объединение - это место в памяти, которое
используется для хранения переменных, разных типов.
Способ задания (похож на обьявление
стурктуры):
union example {
int i;
char a;
};
Доступ осуществляется так же, как и в
структурах.
Когда переменная объявляется как union,
компилятор автоматически выделяет память, равную самому большому элементу
нового объединения.
Объединения часто используются тогда, когда
нужно выполнить необычное преобразование типов. ( Например необычное округление
числа типа double ).
31_17
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include"31_17.h"
int task_31_17(char *file_in, char *file_out,
int m)
{
FILE
*f1, *f2;
f1 =
fopen(file_in, "r");
f2 =
fopen(file_out, "w");
if(f1 !=
NULL && f2 != NULL)
{
int
n=0, i=0, sum=0, row=0, j=0, index=0;
int
*a=NULL, **p=NULL;
fscanf(f1, "%d", &n);
while
(sum<n){
sum +=
row%m + 1;
row++;
}
p =
(int**)malloc(row*sizeof(int*)+sum*sizeof(int));
p[0] =
(int*)(p+row);
for(i=1; i<n; i++)
{
p[i] = (int*)(p[i-1]+i);//длина строки не
равная i
}
sum =
0;
for(i=0; i<row; i++)
for(j=0; j<i%m + 1 && sum<n; j++, sum++)
fscanf(f1, "%d", &p[i][j]);
sum =
0;
for(j=0; j<row; j++){
if
(sum < n)
fprintf(f2, "%d ", p[j][0]);
sum +=
j%m + 1;
}
}
fclose(f1);
fclose(f2);
return 0;
}
Вопрос
№1
Нижней оценкой времени решения задачи z называется такая функция j(N), что для любого
алгоритма, решающего данную задачу, j(N)
будет нижней оценкой времени работы данного алгоритма.
Теорема: Пусть W лежит в R в степени N - это
множество точек, на которых решением задачи будет `да'. Пусть #W - количество
разделимых связных компонент множества W. Тогда, в рамках алгоритмов,
описывающихся алгебраическими деревьями степени 1, время решения задачи есть
омега(log 2 #W).
Доказательство: Докажем, что количество
принимающих вершин дерева принятия решений не меньше #W.
Для этого докажем, что все элементы R в степени N, относящиеся к одной
принимающей вершине дерева решений находятся внутри одной разделимой связной
компоненты W.
Предположим противное: существует принимающая вершина дерева принятия решений,
в которую попадает алгоритм при использовании двух различных a,b из W , таких что a и b принадлежат различным
разделимым связным компонентам Va , Vb лежащих в W,
соответственно. Рассмотрим [a,b]. Линейные функции от N переменных
обладают свойством монотонности на отрезке, поэтому все функции, вычисляющиеся
в вершинах дерева принятия решений, сохраняют свой знак на [a,b]. Т.о. весь отрезок [a,b] лежащий в W (т.к. все
точки из отрезка обязаны попасть в одно и ту же принимающую вершину). Это
противоречит предположению о принадлежности a и b различным разделимым
компонентам.
Итак, мы получили, что количество концевых
вершин бинарного дерева принятия решений не меньше #W, из чего сразу следует,
что высота дерева не меньше [log 2 #W].
Нижней оценкой времени выполнения алгоритма
m называется такая функция j(N), что для
любого N найдется такой
набор входных данных алгоритма размером N,
что время работы данного алгоритма на указанных данных будет не меньше j(N).
Если задача z1 сводится к задаче z2 за время
g(N) и задача z1 имеет нижнюю оценку времени решения j1(N), то задача z2 имеет нижнюю оценку времени решения j2(N) =
j1(N) - g(N).
Очередная копия лекций.
Вопрос
№2
в языке С используются следующие
арифметические операции
a + b Сложение.
Возвращает сумму двух операндов.
a - b Вычитание.
Возвращает разность от вычитания правого операнда из левого.
a * b Умножение.
Возвращает произведение двух операндов.
a / b Деление.
Возвращает частное от деления левого операнда на правый.
a += b значит прибавить к переменной a
значение переменной b.
a -= b значит отнять от переменной a
значение переменной b.
a *= b эквивалентно a = a * b.
a /= b эквивалентно a = a / b.
a++ эквивалентно a=a+1. Есть отличия
a-- эквивалентно a=a-1.
32_16
Задача:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include "32.h"
#pragma warning(disable:4996)
void qSort(int down, int up, float *a)
{
int
i = down;
int
j = up;
float x = a[(down+up)/2];
do
{
while(a[i] < x)
++i;
while(a[j] > x)
--j;
if(i <= j)
{
float temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
while(i < j);
if(down < j) qSort(down, j, a);
if(i < up) qSort(i, up, a);
}
int task32_16(char * path)
{
int
n,i=0;
float *
a;
FILE *f=fopen(path, "r");
FILE *g=fopen("32out.txt",
"w");
if
(fscanf(f,"%d",&n)==0)
fprintf(g,"The file is empty");
fprintf(g,"%d ",n);
a =
(float*)malloc(n * sizeof(float));
for(i =
0; i<n; i++)
fscanf(f,"%f",&a[i]);
qSort(0,(n-1),a);
for(i=0;
i<n; i++)
fprintf(g,"%f ", a[i]);
fclose(f);
fclose(g);
return
0;
}
1) Нижние оценки.
Теорема о связи нижних оценок времени
решения задач на принятие решения количества линейно-разделимых компонент
множества на которых решением задачи будет "да".
Пример задачи на определение все ли элементы
в множестве различаются.
2) Структуры и объединения .Описания и
определения.
1. Задача: Определить, все ли элементы в
множестве A={A1,:,AN } различаются, где - Ai , например, целые или вещественные
числа
Задача
относится к классу задач о принятии решения. Это значит, что на выходе
таких задач выдается всего один бит информации, т.е. ответ `да' или `нет'. Мы
будем рассматривать алгоритмы решения задач о принятии решений, которые
сводятся к бинарному дереву принятия решений.
Под деревом принятия решений имеется в виду
следующее. Пусть на входе нашего алгоритма находится вектор входных данных
aeIR N.
Рассмотрим бинарное дерево, в каждой вершине
которого вычисляется некоторая функция от вектора a и в зависимости от знака
этой функции происходит переход на правую или левую ветвь дерева.
Каждая конечная вершина дерева будет
называться либо принимающей либо отвергающей, в зависимости от приписанного ей
соответствующего атрибута. Достижение принимающей вершины означает выдачу
алгоритмом ответа `да', а отвергающей,
соответственно, - `нет'.
Дерево принятия решений называется
алгебраическим деревом принятия решений степени n, если функции в вершинах
дерева являются многочленами степени не выше n.
Далее мы рассмотрим лишь алгоритмы,
представимые в виде алгебраического дерева принятия решений степени 1.
Мы будем предполагать, что время вычисления
каждой функции в вершине дерева.Приведенная далее теорема верна и для деревьев
высшей степени, но для ее доказательства потребуются весьма серьезные факты из
теории функций,
которые мы здесь привести не сможем.
Введем два определения.
Разделимые множества. Множества A, B <
IR в степени N называются
разделимыми (линейно-разделимыми) если для
любых aеA, bеB найдется c e[a,b], такое что с не пренадлежит A, с не
пренадлежит B.
Связное множество. Связным множеством называется такое множество, что при любом его
разбиении на два непересекающихся непустых подмножества одно из них содержит
точку, предельную для другого.
В евклидовом пространстве открытое множество
связно тогда и только тогда, когда любые две его точки можно соединить целиком
лежащей в нём ломаной.
Теорема. Пусть W c IR N - множество точек, на которых решением
задачи будет `да'. Пусть #W - количество разделимых связных компонент множества
W.
Тогда, в рамках алгоритмов, описывающихся
алгебраическими деревьями степени 1, время решения задачи есть ^(log 2 #W).
Доказательство. Докажем, что количество
принимающих вершин дерева принятия решений не меньше #W.
Для этого докажем, что все элементы R
N, относящиеся к одной принимающей вершине дерева решений находятся
внутри одной разделимой связной компоненты W.
Предположим противное: существует принимающая вершина дерева принятия решений,
в которую попадает алгоритм при использовании двух различных a,b c W , таких что a и b принадлежат различным
разделимым связным компонентам Va , Vb c W,
соответственно. Рассмотрим [a,b]
Линейные функции от N переменных обладают
свойством монотонности на отрезке, поэтому все функции, вычисляющиеся в
вершинах дерева принятия решений, сохраняют свой знак на [a,b].
Т.о. весь отрезок [a,b] c W (т.к. все точки
из отрезка обязаны попасть в одно и ту же принимающую вершину).
Это противоречит предположению о принадлежности
a и b различным разделимым компонентам.
Итак, мы получили, что количество концевых
вершин бинарного дерева принятия решений не меньше #W, из чего сразу следует,
что высота дерева не меньше [log 2 #W].
Вернемся к решению задачи Определить, все ли
элементы в множестве A={A1,:,AN } различаются, где - Ai , например, целые или
вещественные числа.
Рассмотрим в качестве различных вариантов
входных данных задачи все перестановки последовательности {1,2,:,N}. Т.е.
Ap= {p(1), p(2),:, p(N)}, где p - некоторая
перестановка.Докажем, что каждая последовательность Ap принадлежит своей
связной разделимой компоненте множества W, на котором решением Задачи 2 будет
`да'.
Действительно, допустим противное, т.е.
пусть две различные последовательности Ap1
и Ap2 принадлежат одной
компоненте W. Тогда найдутся 1 <= i, j <= N,такие что (p1(i)- p1(j))
(p2(i)- p2(j))<0, т.е. (p1(i)- p1(j)) и (p2(i)- p2(j)) имеют разные знаки.
Но тогда для любой ломаной S, соединяющей
точки Ap1 и Ap2 е IR в степени N , найдется x е S такая,
что xi = xj , что противоречит принадлежности Ap1 и Ap2
одной связной компоненте множества W.
В приведенном доказательстве требует
объяснения следующий факт: для двух различных перестановок множества
{1,2,:,N} всегда найдутся 1 <= i, j
<= N, такие что (p1(i)- p1(j)) и (p2(i)- p2(j)) имеют разные знаки.
Пусть для каждой перестановки p: tk - количество чисел p(i) больших p(k) для
i>k. Легко увидеть, что p и t однозначно задают друг друга (действительно,
для p(i)=N имеем t(i)=0,
поэтому если мы найдем такое i, что t(i)=0,
то сразу получим, что p(i)=N; далее мы ищем такое i, что t(i)=1, и получаем,
что p(i)=N-1, и т.д.). Т.о. для двух различных перестановок p1 и p2
мы получим различные соответствующие t1 и t2 . Выберем i: t1(i) !=
t2(i).
Пусть, например, t1(i) > t2(i), но тогда найдется j>i, такое
что p1(j)> p1(i), но p2(j)< p2(i).
Получили требуемое.
Очередная копия лекций.
2.Структуры
и объединения. Описания и определения.
Структура - это совокупность переменных,
объединенных под одним именем. С помощью структур удобно размещать в смежных
полях связанные между собой элементы информации. Объявление структуры создает
шаблон,
который можно использовать для создания ее
объектов (то есть экземпляров этой структуры).
Переменные, из которых состоит структура,
называются членами. (Члены структуры еще называются элементами или полями.)
Как правило, члены структуры связаны друг с
другом по смыслу. Например, элемент списка рассылки, состоящий из имени и
адреса логично представить в виде структуры. В следующем фрагменте кода
показано, как объявить структуру,
в которой определены поля имени и адреса.
Ключевое слово struct сообщает компилятору, что объявляется (еще говорят,
"декларируется") структура.
struct addr
{
char name[30];
char street[40];
char city[20];
char state[3];
unsigned long int zip;
};
Скопировано с http://xn----9sbcmrygis2b.xn--p1ai/C++/6/07/0701.htm
Объявление завершается точкой с запятой,
потому что объявление структуры является оператором. Кроме того, тег структуры
addr идентифицирует эту конкретную структуру данных и является спецификатором
ее типа.
В данном случае на самом деле никакая
переменная не создается. Всего лишь определяется вид данных. Когда вы объявляете
структуру, то определяете агрегатный тип, а не переменную. И пока вы не
объявите переменную этого типа, то существовать она не будет.
Чтобы объявить переменную (то есть
физический объект) типа addr, напишите следующее:
struct addr addr_info;
В этом операторе объявлена переменная типа
addr, которая называется addr_info. Таким образом, addr описывает вид структуры
(ее тип), a addr_info является экземпляром (объектом) этой структуры.
Когда объявляется переменная-структура,
компилятор автоматически выделяет количество памяти, достаточное, чтобы
разместить все ее члены. Одновременно с объявлением структуры можно объявить
одну или несколько переменных. Например,
struct addr {
char name[30];
char street[40];
char city[20];
char state[3];
unsigned long int zip;
} addr_info, binfo, cinfo;
определяет тип структуры, называемый addr, и
объявляет переменные этого типа addr_info, binfo и cinfo.
Доступ к членам структуры
Доступ к отдельным членам структуры
осуществляется с помощью оператора . (который обычно называют оператором точка
или оператором доступа к члену структуры).
Этот отдельный член определяется именем
объекта, за которым следует точка, а затем именем самого этого члена. В общем
виде использование оператора точка для доступа к члену структуры выглядит таким
образом:
имя-объекта.имя-члена
Объединение - это место в памяти, которое
используется для хранения переменных, разных типов. Объединение дает
возможность интерпретировать один и тот же набор битов не менее, чем двумя
разными способами. Объявление объединения (начинается с ключевого слова union)
похоже на объявление структуры и в общем виде выглядит так:
union тег {
тип
имя-члена;
тип
имя-члена;
тип
имя-члена;
переменные-этого-объединения
.
.
.
}
34_15
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "34_15.h"
int First=1;
typedef
struct
sItem_
{
double
v;
struct
sItem_ *next, *prev;
} sItem;
typedef
struct
List2_
{
sItem
*head, *tail;
sItem
*cur;
} List2;
List2* InitEmpty()
{
List2
*L;
L =
(List2*)calloc(1, sizeof(List2));
L->head=(sItem *)calloc(1,sizeof(sItem));
L->tail=(sItem *)calloc(1,sizeof(sItem));
L->cur=L->head;
L->cur->prev=L->head;
L->cur->next=L->tail;
if (L ==
NULL) return NULL;
return
L;
}
int AddAfter(List2 *L2, double value)
{
sItem
*newItem;
if
(!First)
{
newItem = (sItem*)calloc(1,sizeof(sItem));
if
(newItem == NULL) return -1;
newItem->v = value;
newItem
-> prev = L2 -> cur;
newItem
-> next = L2 -> cur -> next;
L2
-> cur -> next = newItem;
newItem
-> next -> prev = newItem;
L2->cur=newItem;
} else {
L2->cur=L2->head;
L2->cur->v=value;
First = 0;
L2->cur->next=L2->tail;
}
return
0;
}
int AddBefore(List2 *L2, double value)
{
sItem
*newItem;
if
(!First) {
newItem
= (sItem*)calloc(1,sizeof(sItem));
if
(newItem == NULL) return -1;
newItem->v = value;
newItem->prev=L2->cur->prev;
newItem->next=L2->cur;
L2->cur->prev->next=newItem;
L2->cur->prev=newItem;
L2->cur=newItem;
} else {
L2->cur=L2->head; L2->cur->v=value; First = 0;
L2->cur->next=L2->tail; }
return
0;
}
int CurNext(List2 *L2)
{
if (L2
== NULL) return -1;
L2 ->
cur = L2 -> cur -> next;
return
0;
}
int CurPrev(List2 *L2)
{
if (L2
== NULL) return -1;
L2 ->
cur = L2 -> cur -> prev;
return
0;
}
double GetVal(List2 *L2)
{
return
L2->cur->v;
}
int GoFirst(List2 *L2)
{
while
(L2->cur!=L2->head) CurPrev(L2);
return
0;
}
int DelCur(List2 *L2)
{
sItem
*Cur=L2->cur;
if
(L2->cur!=L2->head || L2->cur!=L2->tail) {
L2->cur->next->prev=L2->cur->prev->next;
free(Cur);
}
return
0;
}
int Destroy(List2 *L2)
{
while
(L2->cur!=L2->head) DelCur(L2);
free(L2);
return
0;
}
int task_15(char *inf,char *of,double x)
{
FILE
*fin=fopen(inf,"r"),*fout=fopen(of,"w");
int
n=0,i;
double
k,xmin,xmax;
List2
*List = InitEmpty();
while
(fscanf(fin,"%lf ",&k)==1) { AddAfter(List,k); n++;}
for
(i=0;i<n;i++) {
k=GetVal(List);
CurPrev(List);
xmin=(x-(double)((double)1/(double)n));
xmax=(x+(double)((double)1/(double)n));
if ((k
>= xmin) && (k <= xmax)) fprintf(fout,"%lf ",k);
}
Destroy(List);
fclose(fin);fclose(fout);
return
0;
}
См. 26_15
Ходжабекова Шахноза М2-12
Билет 15
1. Нижние оценки.
Теорема о связи нижних оценок времени решения задач на принятия решения и
количества линейно-разделимых компонент множества точек, на которых решением
задачи будет 'да'
Разделимые множества.
Множества A, B IR N называются
разделимыми (линейно-разделимыми) если
a A, b B найдется c [a,b], такое что с
A, с B.
Связное множество.
Связным множеством называется такое
множество, что при любом его разбиении на два непересекающихся непустых
подмножества одно из них содержит
точку, предельную для
другого. В евклидовом пространстве открытое множество связно тогда и только
тогда, когда любые две его точки можно соединить целиком лежащей в
нём ломаной.
Теорема
Пусть W lR N - множество точек на
которых решением задачи будет 'да', и
пусть #W - количество разделимых связаных компрнент множества W, тогда в рамках
алгоритмов,
описывающихся алгебраическими деревьями степени 1, нижняя оценка времени
решения задачи равна W(log2#W).
Д-во
Докажем, что кол-во принимающих
вершин дерева принятия решений, не меньше #W, для этого докажем что вс е
элементы R N, относящихся к одной
принимающей
вершине дерева решений
ноходятся внутри одной разделимой связаной компаненты W.
Предположим противное существует
принимающая вершина дерева принятия решений, в которую попадает алгоритм при
использавании 2х различных а, bl W, таких что а
и b пренадлежат
различным разделимым связным копонентам Va Vb l W соответственно.
Рассмотрим [a,b] линейные ф-ии от N
переменных обладают свойством монотонности на отрезке, поэтому все ф-ции,
вычисляющихся в вершинах дерева принятия
решений, сохроняют
свой знак на [a,b]
Т.е. весь отрезок [a,b] l W(т.к. все
точки из отрезка обязаны попасть в одну и туже принимающую вершину ) Это
противоречит предположению о принадлежности а и b
разделимым
компонентам.
Следует количество концевых вершин
бинарного дерева принятия решений не меньше #W, из чего сразу следует что
высота дерева не меньше [log2#W].
Скопировано из лекций вплоть до
некопируемых символов
2. Константы (целые,
вещественные, строковые, символьные)
Константа — это фиксированное
значение, которое не может быть изменено программой. Константа может относиться
к любому базовому типу. Способ представления
константы определяется
ее типом. Константы также называются литералами.
Символьные константы заключаются в
одинарные кавычки. В языке С определены многобайтовые (состоящие из одного или
более байт) и широкие (обычно длиной 16 бит)
символы. Они
используются для представления символов языков, имеющих в своем алфавите много
букв. Многобайтовый символ записывается в одинарных кавычках, например,
'ху', а широкий — с
предшествующим символом L.
Целые константы определяются как
числа без дробной части. Например, 10 и -100 — это целые константы. Константы в
плавающем формате записываются как числа с
десятичной точкой,
например, 11.123. Допускается также экспоненциальное представление чисел (в
виде мантиссы и порядка): 111.23е— 1.
По умолчанию
компилятор приписывает константе тип наименьшего размера, в ячейку которого
может уместиться константа. Но это правило имеет исключение: всем
константам в плавающем
формате, даже самым маленьким, приписывается тип double (если, конечно, они
сюда помещаются).
Определение типов констант по умолчанию
является вполне удовлетворительным при разработке большинства программ. Однако,
используя суффикс, можно явно указать тип числовой константы. Если после числа
в плавающем формате стоит суффикс F, то считается, что константа имеет тип
float, а если L, то long double. Для целых типов суффикс
Списано
с адреса
http://cpp.com.ru/shildt_spr_po_c/02/0209.html
U означает unsigned, a L — long.
Тип суффикса не зависит от регистра, например, как F, так и f определяют
константы типа float.
Шестнадцатеричные и
восьмеричные константы. Иногда удобнее использовать не десятичную, а
восьмеричную или шестнадцатеричную систему. Шестнадцатеричная константа
начинается с 0х, а
восьмеричная — с 0.
Строковые константы.
Язык С поддерживает еще один тип констант, а именно — строковые. Строка — это
последовательность символов, заключенных в двойные кавычки.
Не следует путать
понятия строки и символа. Символьная константа заключается в одинарные кавычки.
Специальные символьные
константы
В языке С определены
специальные символьные константы:
\n новая строка
\b удаление предыдущего символа
\f подача бумаги
\r возврат каретки
\t горизонтальная табуляция
\" двойные кавычки
\' одинарная кавычка
\\ обратный слэш
\v вертикальная табуляция
\a сигнал
\? знак вопроса
\N восьмеричная константа (N - восьмеричное
представление)
\xN шеснадцатеричная
константа (N - шеснадцатеричное представление)
35_09
Задача:
#include <stdio.h>
#include <stdlib.h>
void task_35_09_sort(float *m,int x,int y,int
z,int n)// это кто???
{
int
a,b,c,i;
x=n/2;
while
((x<n/2)&&(y<n/2))
if (m[x]<m[y])
c[z++]=a[i++];// a – не массив!!!
else
c[z++]=b[i++];
while
(x<n/2)
c[z++]=a[i++];
while
(y<n/2)
c[z++]=b[i++];
task_35_09_sort
( m, x, z );
task_35_09_sort ( m, y, n );
}
int task_35_(char * filename);
{
int c,i,j,k;
float m;
FILE *f1=fopen(filename,"r");
FILE
*f2=fopen("35_9out","w");
fscanf(f1,"%d",&a);
m=(float*)malloc(a*sizeof(float));
for (i=0;i<n;i++)
fscanf (f1,"%f",&m[i]);
task_35_09_sort(m,x,y,z);
fprintf(f2,"%d\n",a);
for (c=0;c<a;c++)
fprintf(f2,"%f",m[c]);
fclose(f1);
fclose(f2);
return 0;
}
При всей моей лояльности в плане принятия
задач, это – перебор…
Цветиков
Евгений.Билет №9.
2)
Описание и определение функций.
В функции переменным задаются
значения,которые могут быть вызванны в основном блоке программы. Полная бессмыслица.
Function [имя функции]; Это не имеет никакого отношения к языку С
{ [тип значения] [переменная 1];
...........................
[тип
значения] [переменная n];
Тело
функции в котором выполняются действия.
return;
}
В основном блоке программы переменные
обращаются к функции, в которой происходят действия заданные в ней, а затем
возвращают результат.Таким образом можно избежать повторения одних и тех же
действий в основном блоке программы (т.е.не писать один и тот же код несколько
раз).
1)
Структуры данных.Определния.Различные реализации.L1 и L2 списки.
Структуры - это некоторая область (или набор
данных) которая объединяет переменные различных типов.
struct [имя структуры];{[тип переменной]
[переменная 1],...,[тип переменной] [переменная 2];} Синтаксиси неверный
Например:
struct[spisok];
{ char[20] Imya;
int telefon;
} Ситаксис неверный даже приблизительно
L1- односвязные списки предполагают:
-инициализация.
-установка текущего элемента в начало
списка.
-очистка списка.
-проверка на наличие элементов в списке. Список
директив принципиально неполный
L2-двусвязные списки имеют дополнительные
функции
-перемещение текущего элемента списка к
предыдущему.
-проверка текущий элемент в начале списка.
-вставка нового элемента перед текущим.
36_17
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int func(int m, char * input_filename, char*output_filename)
{
int i=0,
temp=0,k=0, p=0,c=0, n=0, cn=0, strnum=0;
int**arr;
FILE *
in = fopen(input_filename, "r");
FILE *
out = fopen(output_filename,"w");
if(in
==NULL)
return
-1;
fscanf(in, "%d",&n);
for (cn
=0; cn<n; cn++)
if (cn ==((strnum % m) + 1))
strnum++; //бессмыслица какая-то
arr=(int**)malloc(strnum*n*sizeof(int));
fscanf(in,"%d", &temp);
while
(fscanf(in, "%d",&arr[i][k])==1)
{
k++;
if(k==((i%m)+1))
{
k = 0;
i++;
}
}
for(c=0; c<3; c++) //почему до 3?
{
fprintf(out,"%d\n", arr[c][0]);
}
fclose(in);
fclose(out);
free(arr);
return 0;
}
билет
17
1. Нижние оценки. теорема о связи нижних
оценок времени решения задач и количества линейно -разделимых
компонет множества точек, на которых
решением задачи будет "да"ю пример задачи на определение, совпадают
ли два множества?
2. Арифметические операции `+’, `-’, `*’, `/’, `+=’, `-=’, `*=’, `/=’,
`++’, `--’.
Вопрос
2
Арифметические
операции -, +, *, /, %, ++, --,
В
языке С к арифметическим операциям относятся следующие операции:
-
вычитание или унарный минус
+
сложение;
*
умножение;
/
деление;
%
деление по модулю;
++
увеличение на единицу;
--
уменьшение на единицу;
Операции сложения, вычитания, умножения и деления действуют так же, как
в большинстве алгоритмических языков программирования.
операции выполняются так: сначала
вычисляется значение левого выражения (операнда), затем вычисляется значение
выражения,
стоящего справа от знака действия. Далее, в
том случае, когда операнды имеют общий тип данных, этот же тип имеет и
результат.
Поэтому, если применяется деление
"/" к целым числам, например, 11/3, то результат тоже будет целым, то
есть в данном случае 3.
В
выражении x++ значение переменной x сначала используется и только вслед за этим
оно увеличивается на 1.
Напротив в выражении ++x переменная x
сначала увеличивается на 1, а потом ее значение используется в вычислениях.
В
выражениях с операциями `--` аналогично операции `++`
Составное присваивание `+=`
Составное присваивание — это разновидность
оператора присваивания, в которой запись сокращается и становится более удобной
в написании.
Например, оператор
x = x+y;
можно записать как
x += y;
Оператор "+=" сообщает
компилятору, что к переменной х нужно прибавить 10.
"Составные" операторы присваивания
существуют для всех бинарных операций, имеющих два операнда. Любой оператор
вида
переменная = переменная оператор выражение;
можно записать как
переменная оператор = выражение;
Соответственно, если `-=` `*=` `/=`
это означает, что
х=х-y;
х=х*y;
х=х/y;
Арифметические операции применяются к
числовым операндам и возвращают числовое значение, означающее результат
операции. Если типы операндов различны, то делается попытка преобразовать их к
числовому типу. При этом:
Операция
"сложение" выполняется только тогда, когда оба операнда являются
числами или логическими значениями. Если хотя бы один операнд является строкой,
то производится конкатенация строк.
• Остальные
операции преобразуют операнды в числа, а затем выполняют операцию.
• Операции
"инкремент" и "декремент" применяются только к переменным.
Арифметические операции
Операция Название Описание
a + b Сложение Возвращает сумму двух операндов.
a - b Вычитание Возвращает разность от вычитания правого операнда
из левого.
a * b Умножение Возвращает произведение двух операндов.
a / b Деление Возвращает частное от деления левого
операнда на правый.
a % b Остаток
по модулю Возвращает целый
остаток от деления левого операнда на правый. Плавающие числа перед операцией
округляются до целых.
++ Инкремент Унарная операция. Увеличивает значение
переменной на 1.
Если используется как префикс (++a),
возвращает значение операнда после увеличения его на 1.
Если используется как постфикс (a++),
возвращает значение операнда перед увеличением его на 1.
-- Декремент Унарная операция. Уменьшает значение
переменной на 1.
Если используется как префикс (--a),
возвращает значение операнда после уменьшения его на 1. Если используется как
постфикс (a--), возвращает значение операнда перед уменьшением его на 1.
-a Смена
знака Унарная операция. Возвращает
арифметическое отрицание операнда.
Скопировано с сайта http://cpp.com.ru/shildt_spr_po_c/02/0210.html
Вопрос
1
Введем два определения.
Разделимые множества. Множества A, B
принадлежащие множеству IR. N называются разделимыми (линейно-разделимыми) если ? a принадлежит A,
bпринадлежит
B найдется c которое принадлежит отрезку [a,b],
такое что с не принадлежит A, с не
принадлежит B.
Связное множество. Связным множеством называется такое множество, что при любом его
разбиении на два непересекающихся непустых
подмножества одно из них содержит точку,
предельную для другого. Открытое множество связно
тогда и только тогда, когда любые две его
точки можно соединить целиком лежащей в нём ломаной.
Теорема.
Пусть W принадлежит IR N – множество точек, на которых решением
задачи будет `да’. Пусть #W – количество
разделимых связных компонент множества W.
Тогда, в рамках алгоритмов, описывающихся алгебраическими деревьями степени 1,
время решения задачи есть (log 2 #W).
Доказательство. Докажем, что количество
принимающих вершин дерева принятия решений не меньше #W.
Для этого докажем, что все элементы
R N,
относящиеся к одной принимающей вершине дерева решений находятся внутри одной
разделимой связной компоненты W.
Предположим противное: существует принимающая вершина дерева принятия решений,
в которую попадает алгоритм при
использовании двух различных a,b принадлежит W ,
таких
что a и b принадлежат различным разделимым связным компонентам Va , Vb
принадлежит W,
соответственно. Рассмотрим [a,b]. Линейные
функции от N переменных обладают свойством монотонности на отрезке,
поэтому все функции, вычисляющиеся в
вершинах дерева принятия решений, сохраняют свой знак на [a,b].
Т.е. весь отрезок [a,b] принадлежит W (т.к.
все точки из отрезка обязаны попасть в одно и ту же принимающую вершину).
Это противоречит предположению о
принадлежности a и b различным разделимым компонентам.
Итак, мы получили, что количество концевых
вершин бинарного дерева принятия решений не меньше #W, из чего сразу следует,
что высота дерева не меньше [log 2 #W].
Скопировано из моих лекций. С учетом того,
что многие символы в текст перенесены быть не могут, текст стал абсолютно
бессмысленным.
37_11
Задача:
#include <stdio.h>
#include <stdlib.h>
#include "37_11.h"
int 37_11_task(const char* file_in, const char*
file_out)
{
unsigned
long a;
int i=0,
k=0, j=0;
int ost
= 0;
unsigned
char offset;
FILE *f1
= fopen(file_in, "rb");
FILE *f2
= fopen(file_out, "wb");
if(f1)
if(f2)
{
while(i<10)
{
fread(&offset, 1, 1, f1);
fwrite(&offset, 1, 1, f2);
i++;
}
fread(&a, sizeof(a), 1, f1);
fwrite(&a, sizeof(a), 1, f2);
for(i=0; i<a-10-sizeof(a); i++)
{
fread(&offset, 1, 1, f1);
fwrite(&offset, 1, 1, f2);
}
i=0;
while(i<32)
{
fread(&a, 4, 1, f1);
for(j=0; j<32; j++)
if (a
& (1 << j))ost++;
i++;
}
if (ost
>= 16*32)
offset
= 255;// (1111 1111)
else
offset
= 0;// (0000 0000)
for(i=0; i<32; i++)
for(j=0; j<4; j++) fwrite(&offset, 1, 1, f2);
}
fclose(f1);
fclose(f2);
return
0;
}
Шабанова
Юлия. М2-12.
Билет
11.
1 вопрос: Бинарные деревья поиска, поиск
элемента в дереве.
Ответ:
Бинарными деревьями называются деревья у
которых для каждой вершины задано не более двух потомков.
Основные операции которые мы может совершать
с бинарными деревьями:
добавлять, либо удалять какой либо элемент
из дерева;
поиск элемента в дереве по заданному ключу;
поиск максимального и минимального элемента
в дереве;
для данной вершины дерева можно разбить
дерево поиска на два дерева поиска таких, что все элементы первого дерева
меньше или равны данной нам вершины,
и все элементы второго дерева больше или
равны данной нам вершины;
для двух деревьев поиска таких, что все
элементы первого дерева меньше или равны всех элементов второго дерева;
слияние в одно дерево поиска;
Поиск элемента в дереве осуществляется по
следующей схеме:
tree *search(tree *current, int svalue)
{
if(current==NULL)
return NULL;
if(current->value == svalue)
return current;
if(current->value >=
svalue)
return
search(current->childright, svalue);
else
return
search(current->childleft, svalue);
}
//
current это данная вершина.
Value - это значение текущей вершины,
указатель parent - это родительская вершина, childleft и childright - левый и
правый потомки.
Отсутствие потомка у вершины обозначается
нулевым значением соответствующего указателя.
Сравнением двух элементов является сравнение
ключей этих элементов.
Последовательность вершин дерева, для
которой каждый последующий элемент является потомком предыдущего, называется
ветвью дерева.
Количество элементов в ветви составляет
длину ветви.
Максимальная длина из всех длин ветвей дерева
называется высотой дерева.
Листом дерева называется вершина, у которой
нет потомков.
Если для любой данной вершины бинарного
дерева ключи всех вершин в правом поддереве этой вершины больше или равны ключа
данной вершины,
а в левом поддереве меньше или равны ключа
данной вершины,
то такое дерево называется деревом поиска.
Для добавление элемента в дерево нужно для
начала найти лист, после которого следует вставить новый элемент допустим в
нашем случае new,
и вставляем new после листа.
Удаление элемента из дерева:
Если данная вершина является листом, то ее
можно просто удалить.
Если она имеет всего одного потомка, то на
место данной вершины записываем её потомка. Либо можно из правого поддерева
элемента,
который нам нужно удалить, изъять
минимальный элемент, он будет самым левым, и поместить его на место удаленного
элемента.
Поиск следующего, предыдущего элемента в
дереве:
Если у текущего элемента cur есть правый
потомок, то следующим элементом будет самый левый элемент в поддереве, которое
имеет корень cur->right.
Если
такого элемента нет, то надо подниматься вверх по дереву, пока не встретиться
вершина cur, являющаяся левым потомком своего родителя.
В
этом случае родитель этой вершины будет следующим элементом дерева.
Stree *findnext(Stree *cur)
{
if(cur==NULL)return NULL;
if(cur -> right!=NULL)
return findmin(cur
-> right);
while (cur -> back &&
cur!=cur -> back -> left)
cur = cur -> back;
return (cur -> back);
}
Если у текущего элемента cur есть левый
потомок, то следующим элементом будет самый правый элемент в поддереве, которое
имеет корень cur->left.
Если
такого элемента нет, то надо подниматься вверх по дереву, пока не встретиться
вершина cur, являющаяся правым потомком своего родителя.
В этом случае родитель этой вершины будет
предыдущим элементом дерева.
2
вопрос: Отведение, очистка памяти с помощью malloc/ realloc/ free.
Ответ:
malloc в переводе с английского означает
выделение памяти.
calloc переводится с английского как чистое
выделение памяти.
realloc означает перевыделение памяти -
функции выделения динамической памяти, входящие в стандартную библиотеку языка
Си.
вызвать данные функции можно следующим
образом:
void *malloc (size_t size);
void *calloc (size_t num, size_t size);
void *realloc (void *block, size_t size);
malloc
Принимает в качестве аргумента размер
выделяемой области в байтах, возвращает указатель (void*) на область памяти
заявленного размера или NULL в случае,
если
выделить память невозможно. Содержимое выделяемой области памяти не определено.
calloc
Принимает в качестве аргумента количество
элементов и размер каждого элемента в байтах;
возвращает указатель (void*) на область памяти
заявленного размера или NULL в случае, если выделить память невозможно.
Значения элементов устанавливаются в ноль.
malloc работает быстрее, чем calloc, в связи
с отсутствием функции обнуления выделяемой памяти.
realloc
Изменяет выделение памяти для блока до size
байт. Если невозможно расширить текущий блок, то будет выделен новый,
в который будет скопировано содержимое
старого блока, а сам старый блок будет освобожден.
Cодержимое блока памяти, превышающее объем
старого будет не определено.
free в переводе с английского освобождение -
функция стандартной библиотеки языка Си, предназначенна для освобождения ранее
выделенной динамической памяти.
Вызвать эту функцию мы можем следующим
образом:
void free (void *ptr);
Функция возвращаемого значения не имеет. free()
не проверяет указатель на правильность, и может освободить невыделенную область
памяти,
что может привести к повреждению кучи. Вызов
функции с NULL безопасен.
Для избежания повреждения кучи рекомендуются
обнулять каждый освобождаемый указатель.
38_07
Задача:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int task38_07(char *file_in, char *file_out)
{
FILE
*f1, *f2;
f1 =
fopen(file_in, "rb");
f2 =
fopen(file_out, "wb");
if(f1 !=
NULL && f2 != NULL)
{
unsigned char buffer;
unsigned long temp;
int
i=0, k=0, j=0;
int res
= 0;
for(i=0; i<10; i++)
{
fread(&buffer, 1, 1, f1);
fwrite(&buffer, 1, 1, f2);
}
fread(&temp, sizeof(temp), 1, f1);
fwrite(&temp, sizeof(temp), 1, f2);
for(i=0; i<temp-10-sizeof(temp); i++)
{
fread(&buffer, 1, 1, f1);
fwrite(&buffer, 1, 1, f2);
}
for(i=0; i<32; i++)
for(k=0; k<32; k++)
{
fread(&buffer, 1, 1, f1);
res =
0;
for(j=0; j<8; j++)
if(buffer & (1 << j))
res++;
if(res >= 4)
buffer = 255;
else
buffer = 0;
fwrite(&buffer, 1, 1, f2);
}
}
fclose(f1);
fclose(f2);
return
0;
}
Билет
7.
1.
Структуры данных. Определения. Различные реализации. Вектор. Стек.
Структура данных это способ хранения данных
определённого типа. Вместе со способом хранения так же задаётся набор операций
по добавлению, поиску и удалению элементов множества.
Стек - это такая структура данных, которая
организована по принципу last - in, first - out. Это означает, что элемент,
который попал в множество последним, должен первым его покинуть. Создание
стукруты Стек имеет следующие различные функции: создание структуры, добавление
элемента на вершину стека, взятие элемента с вершины стека, потом проверка на
пустоту стека и очистка стека.
Есть несколько реализаций Стека.
К примеру реализация на основе массива. Для
реализации стека целых чисел, состоящего не более чем из 100 чисел, на базе
массива следует определить массив из 100 целых чисел и целую переменную,
указывающую на вершину стека, значеник которой будет равно числу элементов в
стеке.
Еще есть реализация на основе массива с
использованием общей струтуры. Чтобы сгруппировать различные элементы в один
объект, следует использовать стуктуру.
Структуры нельзя передавать в качестве
параметров функций, их нельзя возвращать как результат работы функций, но во
всех этих случаях можно использовать указатели на структуры.
Есть еще одна реализация, которая основана
на указателях. Если размер стека можно выяснить только после написания
программы, то память под стек можно выделить динамически, то есть используя
функцию malloc. При этом, вершину стека можно указывать не индексом в массиве,
а указателем на вершину.
Еще есть реализация на основе массива из
двух указателей, на основе указателя на указатель.
Массив в С является точной реализацией
структуры данных под названием Вектор. Вектором называется структура данных, в
которой к каждому элементу множества можно обратиться по индексу, как и в
массиве. В структуре данных Вектор значение индекса может быть ограничено
некоторой наперед заданной величиной. Длиной вектора. Так же как и длина
массива.
Создание Вектор предполагает наличие такиех
функций, как:
создать вектор определённой длины, положить
элемент в вектор по индексу, взять элемент из вектора по индексу и уничтожить
вектор.
При использовании массивов для реализации
структуры данных Вектор, создание или уничтожение объекта происходит в
соответствующие моменты автоматически. Если же этим процессом надо управлять,
то следует использовать функции malloc и free.
2.
Указатели. Указатели на функции.
Указатель, от английского pointer -
переменная, у которой диапазон значений состоит из адресов ячеек памяти и
специального значения - нулевого адреса. Значение нулевого адреса не является
реальным адресом и используется только для обозначения того, что указатель в
данный момент не может использоваться для обращения ни к какой ячейке памяти.
Указатели применяются в двух различных
сферах. Во-первых, они позволяют использовать некоторые выгоды косвенной адресации,
широко применяемой в программировании на языках ассемблера. Во-вторых,
указатели предлагают метод динамического управления памятью: их можно
использовать для доступа к области с динамическим размещением памяти, обычно
называемой кучей, или динамической памятью.
Переменные, размещаемые в куче, называются
динамическими. Часто они не содержат связанных с ними идентификаторов, и
ссылаться на них можно только с помощью указателей и ссылок.
Языки программирования, в которых
предусмотрен тип указателей, содержат, как правило, две основные операции над
ними: присваивание и разыменование. Первая из этих операций присваивает
указателю некоторый адрес. Вторая служит для обращения к значению в памяти, на
которое указывает указатель. Разыменование может быть явным и неявным. В
большинстве современных языков программирования разыменование происходит только
при явном указании.
В случае, если указатель хранит адрес
какого-либо объекта, то говорят, что указатель ссылается или указывает на этот
объект.
Языки, которые предусматривают использование
указателей для управления динамической памятью, должны содержать оператор
явного размещения переменных в памяти. В некоторых языках помимо этого
оператора предусмотрен ещё и оператор явного удаления переменных из памяти. Обе
эти операции часто принимают форму встроенных подпрограмм.
Мда… Круто… Так круто, что просто не может
быть написано самостоятельно. А вообще, я сильно не рекомендую копировать
ответы из Википедии. Там статьи часто пишут не совсем адекватные люди. Кстати,
никакого отношения к языку С эта статья не имеет.
39_05
Задача:
#include <stdio.h>
#include <stdlib.h>
int func (char *way1, char *way2)
{
char
c[10];
int
offset,i,j;
unsigned char s[4];
FILE *
f1 , * f2;
if
(sizeof(int)!=4) return 1;
if ((f1
= fopen (way1,"rb"))==NULL) return 1;
if ((f2
= fopen (way2,"wb"))==NULL) return 1;
if
(fread (c,1,10,f1) == 0)
{
fclose
(f1);
fclose
(f2);
return
1;
}
fwrite
(c,1,10,f2);
if
(fread(&offset,sizeof(int),1,f1)!=1)
{
fclose
(f1);
fclose
(f2);
return
1;
}
fwrite
(&offset,4,1,f2);
for
(i=0;i<offset-14;i++)
{
fread(&c,1,1,f1);
fwrite
(&c,1,1,f2);
}
for
(i=0;i<32;i++)
{
fread
(s,1,4,f1);
if
(i%2==0)
for (j=0;j<4;j++)
s[j]=~s[j];
fwrite(s,1,4,f2);
}
fclose
(f1);
fclose
(f2);
return
0;
}
Яковлев Тимур М2-12
Билет 5.
1.Алгоритмы сортировки за время
O(N).Сортировка подсчетом. Цифровая сортировка.
Сортировка подсчетом.
Пусть мы хотим отсортировать N целых чисел
A={A1,…, AN}, каждое из которых не превосходит K. Для реализации алгоритма нам
понадобится дополнительных
2 массива B и С. Размер массива В будет
равен K, а размер массива С - N. В массиве будут хранится числа для каждого i
количество чисел в массиве A,
не превосходящих i. Результат будем помещать
в третий массив C.
Для всех i от 1 до K с шагом 1 выполнить:
B[i]=0
Для всех i от 1 до N с шагом 1 выполнить:
B[A[i]] ++
Для всех i от 2 до K с шагом 1 выполнить:
B[i]= B[i]+ B[i-1]
Для всех i от N до 1 с шагом -1 выполнить:
C[B[A[i]]] = A[i]; B[A[i]]--
Lобавка `B[A[i]]- -’гарантирует, что если в
массиве A есть элементы с равными значениями, то они будут положены в различные
ячейки массива C.
Более того,каждый следующий элемент со
значением, равным некоторому x (при обратном проходе!), будет помещаться в
ячейку левее предыдущей.
Поэтому данная сортировка сохраняет взаимное
расположение равных элементов. Этой свойство сортировки называется
устойчивостью. Это свойство имеет
смысл, когда равенство элементов в смысле
сравнения не влечет тождественного равенства элементов.
Цифровая сортировка
Идея весьма проста. Пусть требуется
отсортировать массив целых чисел, записанных в некоторой позиционной системе
исчисления. Сначала мы сортируем массив
устойчивым методом по младшей цифре. Потом –
по второй, и т.д. Очередная сортировка не меняет порядок уже отсортированных
элементов, поэтому в конце мы
получим отсортированный массив.
Действительно, если есть большой массив 32-битных целых чисел без приемлемых
ограничений на их величину,
то можно разбить их на 2 либо 4 части и
рассмотреть каждую часть как одну цифру в алгоритме цифровой сортировки.
2.Арифметические операции
'+','-','*','/','+=','-=','*=','/=','++','--'.
Пусть даны числа int a,b,c и float d,g
сложение а=b+c
Вычитание a=b-c
Умножение a=b*c
Если в предыдущих операциях нет ни каких
условий, то для деления есь ограничения. Если целое число делить на
целое(например 7/3), то в результате получится
целое число (2). А при делении вещественое
на вещественное(целое), то резальтатом будет вещественное (7/3=2.5)
a+=b эквивалентно a=a+b
a-=b эквивалентно a=a-b
a*=b эквивалентно a=a*b
d/=g эквивалентно d=d/g
a++ эквивалентно a=a+1
a-- эквивалентно a=a-1
02_01
Задача:
02_01
Задача:
02_01
Задача:
02_01
Задача: