Задачаи ВМК-2015 (УМК ВМК)
Описание файла
Файл "Задачаи ВМК-2015" внутри архива находится в папке "УМК ВМК". Документ из архива "УМК ВМК", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Задачаи ВМК-2015"
Текст из документа "Задачаи ВМК-2015"
1. Алгори́тм Де́йкстры
void Djecstra(int st)
{
int **w= new int*[n];
for (int i=0;i<n;i++)
*(w+i)=new int[n];
bool visited[n];
int D[n];
for(int i=0;i<n;i++)
{
D[i]=*(*(w+st)+i);
visited[i]=false;
}
D[st]=0;
int index=0,u=0;
for (int i=0;i<n;i++)
{
int min=INT_MAX;
for (int j=0;j<n;j++)
{
if (!visited[j] && D[j]<min)
{
min=D[j];
index=i;
}
}
u=index;
visited[u]=true;
for(int j=0;j<n;j++)
{
if (!visited[j] && *(*(w+u)+j)!=INT_MAX && D[u]!=INT_MAX && (D[u]+*(*(w+u)+j)<D[j]))
{
D[j]=D[u]+*(*(w+u)+j);
}
}
}
for(int j=0;i<n;j++)
delete *(w+j);
delete w;
}
2. Алгоритм Кнута – Морриса – Пратта
int seek_substring_KMP (char s[], char p[])
{
int i, j, N, M;
N = strlen(s);
M = strlen(p);
int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
/* Вычисление префикс-функции */
d[0]=0;
for(i=1,j=0;i<M;i++)
{
while(j>0 && p[j]!=p[i])
j = d[j-1];
if(p[j]==p[i])
j++;
d[i]=j;
}
/* поиск */
for(i=0,j=0;i<N; i++)
{
while(j>0 && p[j]!=s[i])
j=d[j-1];
if(p[j]==s[i])
j++;
if (j==M)
{
free (d); /* освобождение памяти массива d */
return i-j+1;
}
{
free (d); /* освобождение памяти массива d */
return -1;
}
}
3. Быстаря сортировка
int n, a[n]; //n - количество элементов
void qs(int* s_arr, int first, int last) { int i = first, j = last, x = s_arr[(first + last) / 2]; do { while (s_arr[i] < x) i++; while (s_arr[j] > x) j--; if(i <= j) { if (s_arr[i] > s_arr[j]) swap(&s_arr[i], &s_arr[j]); i++; j--; } } while (i <= j); if (i < last) qs(s_arr, i, last); if (first < j) qs(s_arr, first, j); } 4. Сортировка вставками int i, j, temp; for (i = 1; i < size; i++) { temp = array[i]; for (j = i - 1; j >= 0; j--) { if (array[j] < temp) break; array[j + 1] = array[j]; array[j] = temp; } } 5. Сортировка выбором for (int i = 0; i < size - 1; i++) { /* устанавливаем начальное значение минимального индекса */ int min_i = i; /* находим индекс минимального элемента */ for (int j = i + 1; j < size; j++) { if (array[j] < array[min_i]) { min_i = j; } } /* меняем значения местами */ int temp = array[i]; array[i] = array[min_i]; array[min_i] = temp; } 6. Сортировка перемешиванием #define SWAP(A,B) {(A)=(A)^(B); (B)=(A)^(B); (A)=(A)^(B);} void m_sheker(int mas[], int n) { int last = n-1, left = 1, right = n-1, j; do { for(j = right; j >= left; j--) { if(mas[j-1] > mas[j]) { SWAP(mas[j-1], mas[j]); last = j; } } left = last + 1; for(j = left; j <= right; j++) { if(mas[j-1] > mas[j]) { SWAP(mas[j-1], mas[j]); last = j; } } right = last-1; } while(left < right); } 7. Пирамидальная сортировка #define MAXL 1000 void swap (int *a, int *b) { int t = *a; *a = *b; *b = t; } int main() { int a[MAXL], n, i, sh = 0, b = 0; for (i = 0; i < n; ++i) while (1) { b = 0; for (i = 0; i < n; ++i) { if (i*2 + 2 + sh < n) { if (a[i+sh] > a[i*2 + 1 + sh] || a[i + sh] > a[i*2 + 2 + sh]) { if (a[i*2+1+sh] < a[i*2+2+sh]) { swap (&a[i+sh], &a[i*2+1+sh]); b = 1; } else if (a[i*2+2+sh] < a[i*2+1+sh]) { swap (&a[i+sh],&a[i*2+2+sh]); b = 1; } } } else if (i * 2 + 1 + sh < n) { if (a[i+sh] > a[i*2+1+sh]) { swap (&a[i+sh], &a[i*2+1+sh]); b=1; } } } if (!b) sh++; if (sh+2==n) break; } return 0; } 8. Пузырьковая сортировка #define SWAP(A, B) { int t = A; A = B; B = t; } void bubblesort(int *a, int n) { int i, j; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) SWAP( a[j], a[j + 1] ); } } } 9. Сортировка Шелла void shell(char *items, int count) { register int i, j, gap, k; char x, a[5]; a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1; for(k=0; k < 5; k++) { gap = a[k]; for(i=gap; i < count; ++i) { x = items[i]; for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap) items[j+gap] = items[j]; items[j+gap] = x; } } }