Контрольная работа по алгоритмам. Отчет по контрольной работе. Отчет по Контрольной работе, Вариант 12 По дисциплине Алгоритмы и структуры данных
 Скачать 111.23 Kb.
|
|
Институт менеджмента и информационных технологий Кафедра информационных технологий и статистики Отчет по Контрольной работе, Вариант 12 По дисциплине «Алгоритмы и структуры данных» Руководитель к.э.н. доцент Студент гр. Задача 4. Вычисление полинома. Постановка задачи В этой задачи необходимо вычислить полином: anxn + anxn + … + a2x2 + a1x1 + a0. Число n может быть велико, поэтому вычисляется полином по модулю. Необходимо сделать это с возможностью ввода нескольких значений аргумента x. Входные данные: первая строка содержит три значения – степень полинома (N), количество вычисляемых значений аргумента (M) и модуль (MOD). Следующие N+1 строк содержат значения коэффициентов полинома. После значений коэффициентов полинома в M строках содержаться значения аргументов. Выходные данные: в выводе должно быть M строк – значений вычисляемого полинома при заданных значений коэффициентов (N+1) и аргументов (M) по модулю (MOD). Ход решения задачи. В начале программы у пользователя запрашиваются входные значения. Программа проверяет введены ли три значения в первой строке или нет. Если нет, программа запрашивает значения снова. После удачного получения значений, они записываются в программу. Далее создается два массива: один для коэффициентов полинома (a[N+1]), второй для аргументов (x[M]). Начиная со второй строки пользователю необходимо заполнить эти два массива: сначала с коэффициентами, потом с аргументами. После получения всех значений программа начинает расчёт полинома. Расчёт осуществляется с помощью рекурсии. Формула рекурсии: P(n, x) = x * P(n-1, x) + a[n]. В рекурсию направляются поочередно значения аргументов M из массива x[M], значения всех коэффициентов a[N+1] и степень полинома N. На каждом уровне глубины рекурсии N снижается на один. Это продолжается до тех пор, пока N не равен 0. Затем рекурсия начинает обратный ход. На самой глубине рекурсии получается следующее выражение: x*0 + a[N], при N = 0. Если подняться на уровень выше: x *(x * 0 + a[N]) + a[N+1]. Когда рекурсия возвращается на начальный уровень, возвращается полученный полином по модулю MOD. После вычислений пользователю выводятся полученные M полиномов по модулю MOD. Код программы. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Diagnostics; using System.Reflection; namespace Вычисление_полинома { class Program { static int N, M, MOD;//переменные степени полинома, количества значений аргумента и модуля static int n;//переменная степени полинома для рекурсии static int[] x;//массив аргументов x static int[] a;//массив коэффициентов полинома a static void Main(string[] args) { //Начало заполнения значений полинома Console.Write("Введите 3 значения через пробел - степень полинома, количество значений аргумента и модуль: "); try//проверка на 3 введенных значения через пробел { string[] arr = Console.ReadLine().Split(' '); N = int.Parse(arr[0]); M = int.Parse(arr[1]); MOD = int.Parse(arr[2]); } catch//если пользователь не ввёл 3 значения через пробел { Console.Write("Вы не ввели 3 значения через пробел"); Console.ReadLine(); Process.Start(Assembly.GetExecutingAssembly().Location);//запуск программы с новой попыткой Environment.Exit(0);//закрытие программы с текущей попыткой } a = new int[N + 1];//установка размера массива a[] с коэффициентами полинома x = new int[M];//установка размера массива x[] с аргументами for (int i = 0; i < a.Length; i++)//заполнение массива a[] с коэффициентами полинома { Console.Write("Введите {0}-й a: ", (i + 1)); a[i] = Convert.ToInt32(Console.ReadLine()); } for (int i = 0; i < x.Length; i++)//заполнение массива x[] с аргументами { Console.Write("Введите {0}-й x: ", (i + 1)); x[i] = Convert.ToInt32(Console.ReadLine()); } //Конец заполнения значений полинома //Начало расчёта полинома Stopwatch stopWatch = new Stopwatch(); stopWatch.Start(); long before = GC.GetTotalMemory(false); for (int i = 0; i < x.Length; i++) { n = N + 1;//обновление переменной степени полинома для рекурсии Console.WriteLine("При {0}-й х полином с остатком {1} равен: {2}", (i + 1), MOD, Polynom(x[i])); } stopWatch.Stop(); Console.WriteLine("RunTime: " + stopWatch.Elapsed); long after = GC.GetTotalMemory(false); long consumedInMegabytes = (after - before) / (1024 * 1024); Console.WriteLine("Memory is {0} Mb.", consumedInMegabytes); //Конец расчёта полинома Console.ReadLine(); } static int Polynom(int x) //Рекурсия { n--; if (n >= 0)//условие окончания рекурсии: степень равна 0 { int k = a[n];//переменная текущего коэффициента полинома для рекурсии return (x * Polynom(x) + k) % MOD;//формула рекурсии: P(n,x) = x * P(n-1,x) + a[n] } return 0; } } } Примеры работы программы.  Рис. 1 – Первый пример программы «Вычисление полинома»  Рис. 2 – Второй пример работы программы «Вычисление полинома» Тестирование программы. Выходные данные: 1 – первая строка с 3-мя значениями, 2 – значения a, 3 – значения х.
|