Молодой учёный. Issn молодой учёныйМеждународный научный журналВыходит еженедельно 46 (180) Редакционная коллегия bГлавный редактор
 Скачать 7.12 Mb.
|
|
. № 46 (180) . Ноябрь 2017 г. Информатика 7. Возможность сохранения и загрузки маски варианта. Так как программа может часто использоваться для генерации однотипных задач, удобно хранить шаблон типового варианта, который хранит в себе типы задач, которые необходимо сформировать, с указанием подтипов, текстов условий и диапазонов значений (или случайный выбор параметров). Типы заданий соответствуют заданиям, применяемым преподавателями Брянского государственного технического университета в учебном процессе согласно учебным планами образовательным стандартам Министерства Образования Российской Федерации. За базу для разработки алгоритмов решений задач были взяты методические указания по выполнению расчетно-графической работы по дисциплине Информатика, составленные для студентов первого курса. Для генерации варианта в программе преподавателю необходимо выполнить следующие действия. Отметить типы задач, которые необходимы для типового варианта. По умолчанию все задачи отмечены как необходимые при формировании типового варианта. Выбрать подтип, условие, задать необходимые диапазоны (или оставить отметку использовать случайные значение. Указать количество вариантов и нажать кнопку «Сгенерировать вариант. Сохранить варианты, используя команды главного меню. При необходимости, сохранить маску варианта. На рисунке 1 представлено диалоговое окно про- граммы. Пример документа, полученного в результате генерации заданий, представлен на рисунке Важной особенностью программы является возможность работы с шаблонами вариантов заданий. В шаблоне можно сохранять выбранные типы заданий и их количество, ограничения и подтипы. Использование шаблонов позволяет генерировать различные наборы вариантов ежегодно, без необходимости повторного заполнения информации о структуре самостоятельной работы. Работа с шаблоном продемонстрирована на рисунке Данная программа имеет несколько векторов развития. Расширение тематики задач. Так как алгоритмы решения разных типов задач реализованы модульно, одной из перспектив развития является расширение тематики путем добавления новых модулей, например, задач, связанных с построением графиков, задач по другим дисциплинам (дискретная математика, математическая логика, и т. д. Автоматизированная проверка. Так как программа реализует не только построение задачи и ответа, но и опорных точек для решения, при дальнейшем развитии программы можно реализовать проверку решения, составленного студентом, в соответствии с решением, смоделированным программой. Повышение гибкости составления задач. Алгоритмы составления задач, реализованных в данной программе, имеют статичную структуру, как текстов задач, таки методов решения. Одним из векторов развития программы является разработка алгоритма, позволяющего преподавателю моделировать собственные задачи. При этом это не ограничивается написанием шаблонов текста задачи с подстановкой параметров через специальные символы. Есть возможность внедрить в программу калькулятор формул, который может преобразовывать вве- Рис. 1. Рабочая область программы 25 “Young Scientist” . # 46 (180) . November 2017 Computer денную строку-выражение. Таким образом, преподаватель может не только составить условие задачи, а в качестве сопутствующего материала указать необходимые формулы, по которым программа сможет вычислить искомые промежуточные и конечный результаты на основе генерируемых исходных данных. Литература: 1. Агеева, Е. С, Макарова Е. В. Сетевая система дистанционного обучения Пегас // Молодой ученый. — 2016. — № 21. — с. 847–849. 2. Зорин, Ю. А. Интерпретатор языка построения генераторов тестовых заданий на основе деревьев И/ИЛИ // Доклады Томского государственного университета систем управления и радиоэлектроники, 2013, № 1. с. 75– 79. 3. Кручинин, В. В. Генераторы в компьютерных учебных программах. — Томск Изд-во Том. Унта, 2003. — 200 с. Кручинин, В. В. Генераторы в компьютерных учебных программах. — Томск Изд-во Том. унта, 2003. — 200 с. Рис. 2. Пример документа с сохраненными условиями задач Рис. 3. Сохранение шаблона вариантов Молодой учёный» . № 46 (180) . Ноябрь 2017 г. Информатика Разработка способа представления длинных чисел в памяти компьютера Коптенок Елизавета Викторовна, ассистент Кузин Александр Владимирович, студент Шумилин Тимур Борисович, студент Соколов Максим Дмитриевич, студент Брянский государственный технический университет П од длинной арифметикой понимаются выполняемые с помощью вычислительной машины арифметические операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена только объёмом доступной памяти. Длинная арифметика применяется в различных областях компьютерных технологий. Например, в криптографии большинство систем подписывания и шифрования данных используют целочисленную арифметику по модулю m, где m — очень большое натуральное число, необязательно простое. Например, при реализации метода шифрования RSA, криптосистемы Рабина или схемы Эль-Гамаля требуется обеспечить точность результатов умножения и возведения в степень порядка 10309. В математическое и финансовое ПО результат вычисления на бумаге должен совпадать с результатом работы компьютера с точностью до последнего разряда. Наиболее мощные калькуляторы, реализующие длинную арифметику, имеют ряд недостатков. Стоимость например, калькулятор «eCalc» стоит от 45 евро. Калькуляторы, обладающие широким функционалом и близкой к неограниченной точности вычислений, являются коммерческими продуктами. Ограниченный функционал как правило, бесплатные онлайн калькуляторы имеют ряд существенных ограничений, связанных либо с точностью вычислений, либо с максимальным возможным значением. Например, один из популярных онлайн калькуляторов «web calc», имеющий большой набор действий над числами, строить графики и вычислять значения простых функций, не находит факториалы чисел больше 200. Также данный калькулятор не дает возможности задать точность числа (устанавливается автоматически. Соответственно, если нам нужна более высокая точность, вычисления будут нести погрешность. Большинство бесплатных калькуляторов работают лишь с целыми числами или с ограниченной точностью. Закрытое ПО большинство программ, реализующих вычисления неограниченно больших чисел с любой точностью разрабатываются для шифрования и кодирования и не находятся в открытом доступе. Разработанный программный продукт устраняет большинство недостатков доступных аналогов Работа с числами практически неограниченной длины. В отличие от большинства аналогов, программа способна манипулировать десятичными числами до 10 10^9 ; — Реализация всех базовых арифметических действий над числами, в том числе и деления с остатком необходимой точности Возможность работы с дробными числами Данный продукт способен преобразовать выражение произвольной длины, имеющее до 27 переменных переменные в выражении могут повторяться. Операции, которые могут быть использованы в выражении Повышение приоритета выполнения операций. Таким образом, арифметические действия могут производиться не только между переменными, но и между выражениями сложение/вычитание чисел или выражений Умножение двух чисел с заданной конечной точностью Деление двух чисел. Может быть произведено с заданной точностью, атак же выделение целой части или остатка отделения Возведение в степень, причем показатель степени также может быть длинным числом Факториал числа или выражения; Операции возведения в степень и факториала имеют свои ограничения, так как в данной версии продукта результат не может превышать 10 10^9 . Например, наибольшее число, факториал которого может быть найден — 6000. Среди бесплатных аналогов вычисление факториала такой величины обнаружено не было. Также программа сохраняет результат в текстовый документ для дальнейшего использования и, наоборот, позволяет считать выражение и значение переменных из файла; Хранение числа в памяти Из различных способов представления длинных чисел в памяти компьютера для разработки программного продукта был выбран и доработан принцип поразрядного хранения, так как такие методы, как метод факторизации или разложения на простые модули ограничивают функционал программы (нет возможности работать с дробными числами, производить деление чисел). Так как метод поразрядного хранения может привести к повышенному расходу памяти, а также к ограничению длины числа, было принято решение хранить десятичное число в системе счисления с основанием 10000 (Рис. 1): 27 “Young Scientist” . # 46 (180) . November 2017 Computer Хранение числа реализовано в двусвязном списке, к ссылкам на начало и конец числа была добавлена ссылка на младший разряд целой части. Благодаря этому ест возможность задать любую точность для хранимого числа. Число 10000 было выбрано за размер одной ячейки во избежание перегрузки элемента списка при выполнении промежуточных расчетов. Вовремя вычисления выражения максимальное промежуточное значение должно помещаться в переменную типа int. Максимальное промежуточное значение для числа 9999 будет 9999*9999, что помещается в переменную типа Сложение и вычитание Данные операции следует рассматривать в связке, так как суть их одинакова, асами операции сложения и вычитания сводится к сложению или вычитанию модулей. Стоит отметить, что для ускорения вычислений при вычитании строка выражения преобразуется следующим образом если производится вычитание, то все последующие знаки сложения и вычитания (равного приоритета) инвертируются. Например, при вводе выражения a-b* (c+a) - a+d программа при выполнении первого вычитания фактически изменит выражение и приведет его к виду a-(b* (c+a) - И сложение, и вычитание, выполняется после приведения в соответствие дробной части обоих чисел путем добавления нулевых разрядов в дробную часть числа, у которого она короче. После этого выполняется поразрядное сложение с проверкой переполнения разрядов Рис. Рис Реализация операции сложения Умножение Умножение чисел путем последовательного сложения, с учетом длины чисел, может занять значительное количество времени. В связи с этим был реализован алгоритм поразрядного умножения, который заключается в следу- ющем: Умножить первый множитель на младший разряд второго с проверкой переполнения ячеек; Повторить операция со следующим по старшинству разрядом, добавляя полученное число к результату также со сдвигом в один разряд. Отделить дробную часть путем перемещения нужной ссылки (Рис. 3). Деление Деление чисел путем последовательного вычитания также может занять продолжительное время (например, деление очень большого числа на очень малое. Для увеличения скорости расчетов был реализован алгоритм поразрядного деления. Алгоритм сводится к выполнению следующих действий. Ссылки на младший разряд целой части сдвигаются к младшему разряду до тех пор, пока у одного из чисел Рис Принципиальная схема хранения длинного числа Молодой учёный» . № 46 (180) . Ноябрь 2017 г. Информатика данные ссылки не совпадут (фактически, того же эффекта можно достигнуть, умножая оба числа на 10000, пока одно из них не станет целым, так как 0,16/0,04=16/4); 2. Из делимого выделяется количество разрядов, равное количеству разрядов делителя (если изначально у делимого меньше разрядов, чему делителя, целая часть будет равна нулю. Выполняется деление получившихся чисел. К делимому прибавляем старший из неиспользованных ранее разрядов и повторяем п. 3; 5. Когда число-делитель становится больше делимого, начинаем вычислять остаток к делимому добавляем один пустой разряд (эквивалентно умножению на 10000) и производим деление. Повторяем п. 5 до тех пор, пока не будет достигнута заданная точность или остаток не будет равен 0 (Рис. Рис Реализация операции деления Рис. 3. Реализация операции умножения 29 “Young Scientist” . # 46 (180) . November 2017 Computer Возведение в степень Возведение в степень путем последовательного умножения числа на само себя может привести к большому времени выполнения операции (особенно, если в показателе степени также длинное число. Чтобы этого избежать, был реализован алгоритм разложения показателя степени на множители: Если показатель степени четный, разделить показатель степени на два, выражение представить в виде a 2n =a n *a Если показатель степени нечетный, то представить выражение в виде a 2n+1 =a 2n *a, для a 2n повторить шаг В результате выполнения такого алгоритма получится развернутая запись числа, которая громоздкая на видно дает колоссальный эффект при вычислении выражений типа a n ; Например, число a 10 можно представить как ( (a 2 ) 2 *a) 2 . Программа выполнит фактически 4 операции умножения вместо десяти. В целом сложность такого алгоритма оценивается как О, где n — показатель степени, что гораздо эффективнее последовательного умножения (сложность алгоритма O=n); Факториал Факториал числа вычисляется путем рекурсивного умножения и т. д. Найти более быстрые алгоритмы для длинных чисел пока не удалось. Пример применения алгоритма Результатом проделанной работы стала программа, которая позволяет рассчитать выражение, содержащие до 27 переменных (которые могут повторяться внутри выражения) с расчетом результата, количество разрядов которого в десятичной системе может достигать 10 10^9 . Точность вычисления (количество знаков после запятой) задается пользователем. Над числами могут производиться все базовые арифметические операции (сложение, вычитание, умножение, деление, возведение в степень, факториал. Все функции для записи числа и выполнения расчетов вынесены в библиотеку, которую можно встроить в сторонний проект. Пользователь может вводить выражение и переменные с клавиатуры. Также реализована возможность ввода выражения и переменных из файла, запись результата вычисления в переменную для последующего использования в новых выражениях, изменение выражения и значений переменных, сохранение выражений и переменных в файл. Как уже было написано выше, сложно найти значение факториалов для чисел больших, чем 200. Данная программа позволяет рассчитывать факториал чисел до 6000 Рис. Так как калькуляторов, рассчитывающих такие числа, найдено не было, в Интернете была найдена текстовая запись числа и результат был сверен посимвольно, так как вышло число, количество разрядов которого превышает 20 000 символов. Рис. 5. Реализация возведения в факториал большого числа Данная библиотека функций может послужить фундаментом для разработки более мощного калькулятора с более широкой областью применения. Целью разработки данной программы является возможность производить вычисления с абсолютно любой точностью, ограниченной лишь памятью компьютера, так как на данный момент предельная длина числа ограничена программно (10 10:9 разрядов. Преодоление данного ограничения поможет перейти к арифметике произвольной точности. Главной перспективой развития данного проекта является разработка калькулятора элементарных функций, в частности — тригонометрических. Для точного расчета тригонометрических величин и непериодических констант например, числа Пи) можно использовать уже реализованные функции (сумма, деление, факториал, благодаря которым можно вычислить значение любой функции, составив ее ряд. Следующей перспективой развития является более гибкая обработка выражений, которая позволит исполь- Молодой учёный» . № 46 (180) . Ноябрь 2017 г. Информатика зовать произвольное количество переменных в выражении (на данный момент их количество ограничено буквами латинского алфавита). Таким образом, на базе данной программы можно создать библиотеку функций, реализующих широкий набор математических операций с числами произвольной точности и бесконечной величины. Литература: 1. Электронные средства и системы управления Материалы докладов Международной научно-практической конференции октября 2010 г. — Томск В-Спектр, 2011: В 2 ч. — Ч. 2. — 178 с. ISBN 978–5–91191– 223–6, с. 123–129 2. СМ. Окулов, Длинная арифметика, Информатика, 2016, № 5 (867), режим доступа http://inf. 1september. ru/2000/1/art/okul1. Применение графической библиотеки SDL2.0 для программирования компьютерных игр на языке СИ Коптенок Елизавета Викторовна, ассистент Кустова Дарья Викторовна, студент Полшкова Ирина Владимировна, студент Брянский государственный технический университет О дной из самых распространенных тем курсовых работ по программированию на первом курсе является написание игровой программы. Данная тема позволяет развить алгоритмическое мышление, продемонстрировать умение работать с основными алгоритмическими конструкциями, такими как циклы или условия, а также владение основными приемами программирования. Кроме того, игровые проекты вызывают интерес и повышают мотивацию студентов. Что не менее важно, они связаны с математическими дисциплинами, так как требуют большого числа расчетов. Написание игры связано с программированием графики. Существуют различные библиотеки, например, OpenGl, Qt, SFML, Graphics, SDL. Готовые игровые библиотеки и конструкторы не рассматриваются, так как не позволяют в полной мере продемонстрировать степень владения навыками программирования. В статье рассмотрена библиотека Общий принцип взаимосвязи процедурных блоков и логики игрового проекта представлен на рисунке 1. Запуск любой игры начинается с вывода меню, из которого производится переход к списку рекордов, загрузке игры, новой игре или осуществляется выход из программы. Сама игра содержит такой важный функциональный блок, как игровой цикл. Любая игровая программа основывается на игровом цикле. Общий игровой цикл представлен на рисунке 2. При входе в функцию игры необходимо проинициализи- ровать начальные значения уровня и отрисовать стартовое поле. После этого происходит вход в игровой цикл, условиями выхода из которого могут являться закрытие окна игры, определенные действия пользователя (например, нажатие на кнопку) и достижение определенных значений игровых параметров. Далее рассчитываются параметры, значения которых не зависят от пользовательских действий, например, координаты динамических игровых объектов. Следующим шагом является считывание событий мыши и клавиатуры, на основе которых производится пересчет игровых параметров, зависящих от пользовательских действий. Далее производится отрисовка кадра и возврат в начало цикла. Библиотека SDL позволяет работать с графическими примитивами, такими как точки, прямые и прямоугольники. Средствами библиотеки можно получать графическую информацию из файлов в форматах. bmp, и. png, воспроизводить звуки, выводить текст, работать с контроллерами и манипуляторами. Рассмотрим основные функции библиотеки SDL, применяемые для написания игр. Перед тем как приступить к работе с библиотекой, её нужно проинициализировать. Для этого есть функция int SDL_Init (Uint32 flags), которая принимает параметр, указывающий, какую подсистему инициализировать в SDL. Всего есть несколько подсистем, которые понадобятся для написания игры подсистема таймера, аудио, видео, привод, джойстик. Если необходимо инициализировать все системы, следует использовать константу Первая и основная графическая функция — функция отрисовки окна. Она отрисовывает и выводит на экран окно с заданными размерами и заголовком window = SDL_CreateWindow («HEllo», 100, 100, 800, 600, SDL_WINDOW_SHOWN); |