Решения задач с очного тура 2015, страница 2
Описание файла
PDF-файл из архива "Решения задач с очного тура 2015", который расположен в категории "". Всё это находится в предмете "универсиада" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
Б.Петров В. Г.Сидоров Д. Е.ДолжностьруководительпрограммистпрограммистСотрудникИванов А. Б.Петров В. Г.Сидоров Д. Е.Иванов А. Б.Петров В. Г.Сидоров Д. Е.ПроектПроектПроектПроектПроектПроектПроектXXXYYYДолжностьруководительпрограммистЗарплата2000015000ЗаданиеЯдроЯдроОболочкаЯдроОболочкаОболочка5.Написать программу на языке Си для выполнения в операционной системе семейства Unix(считать, что подключения всех необходимых заголовочных файлов уже выполнены). В аргументахкомандной строки программе передаётся число и имена текстовых файлов.
Каждый текстовыйфайл должен содержать одну строку — имя исполняемого файла. Программа запускает на параллельное исполнение не более чем первые исполняемых файлов и после окончания параллельногоисполнения на последовательное исполнение — оставшиеся исполняемые файлы. По окончании работы процесс-родитель выводит на экран число — количество потомков, которые были успешнозапущены и завершили свою работу с пользовательским кодом возврата 0.H Решение.#include#include#include#include<stdio.h><stdlib.h><ctype.h><string.h>— Универсиада «Ломоносов» 2015 —стр.
8 из 9Решения задач очного тура#include#include#include#include#include<limits.h><sys/types.h><sys/stat.h><unistd.h><sys/wait.h>char *getl(char *buf, size_t size, const char *path){FILE *f = fopen(path, "r");if (!f) return NULL;if (!fgets(buf, size, f)) {fclose(f);return NULL;}fclose(f); f = NULL;int len = strlen(buf);while (len > 0 && isspace(buf[len - 1])) --len;buf[len] = 0;return buf;}intmain(int argc, char *argv[]){int n;sscanf(argv[1], "%d", &n);int arg = 2;int success_count = 0;int r;for (; arg < argc && arg < n + 2; ++arg) {if (!fork()) {char buf[PATH_MAX];if (getl(buf, sizeof(buf), argv[arg])) {execlp(buf, buf, NULL);exit(1);}}}while (wait(&r) > 0) {success_count += (WIFEXITED(r) && !WEXITSTATUS(r));}for (; arg < argc; ++arg) {if (!(r = fork())) {char buf[PATH_MAX];if (getl(buf, sizeof(buf), argv[arg])) {execlp(buf, buf, NULL);exit(1);}} else if (r > 0) {wait(&r);success_count += (WIFEXITED(r) && !WEXITSTATUS(r));}}— Универсиада «Ломоносов» 2015 —стр.
9 из 9Решения задач очного тураprintf("%d\n", success_count);return 0;}NОтвет. Код программы.6. Определить последовательную и параллельную сложность алгоритма, записанного с помощьюследующего фрагмента программы:for( i = 1 ; i <= n ; ++i)for( j = 1 ; j <= m ; ++j)A[i][j] = A[i][j] * A[i-1][j] * A[i][j-1] ;где: последовательная сложность — это число операций умножения в теле цикла; параллельнаясложность — это длина критического пути графа алгоритма (число вершин в критическом пути)данного фрагмента, где каждая вершина представляет отдельное срабатывание оператора телацикла. Ответ обосновать.
Без обоснования ответ не засчитывается.H Решение. Для определения последовательной сложности нужно определить общее число операций: тело данного цикла будет выполнено n*m раз, причем каждому выполнению оператора,стоящему в теле цикла, соответствует две операции умножения, а значит и общее число операций, и последовательная сложность равны 2 * * . Для определения параллельной сложностиалгоритма необходимо построить граф алгоритма, для данного фрагмента он выглядит следующимобразом (см. ответ).
Очевидно, что параллельная сложность, т.е. длина критического пути данногографа (число вершин в критическом пути) равна + − 1.NПоследовательная сложность = 2 * * опеОтвет. раций. Параллельная сложность = + − 1шагов.— Универсиада «Ломоносов» 2015 —.
