48944 (608850), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Глава 3. Тестирование разработанной программы и обсуждение результатов

В этой главе приведем некоторые результаты синтаксического анализа полиномов и их обсуждение. Прежде всего, отметим, что разработанная программа может работать с произвольным количеством переменных в одночлене и одночленов в полиноме. Следует отметить, что программа не допускает размещение коэффициента внутри одночлена: предполагается, что коэффициент может находиться только вначале одночлена. При этом порядок переменных в одночлене может быть произвольным, переменные могут повторяться с разными показателями степеней. Случай обработки таких полиномов представлен на рис. 3. На этом рисунке показаны результаты работы программы по преобразованию полинома к приведенному виду, вычислению значения полинома, определения однородности полинома, нахождения его производной, а также суммы и произведения полиномов.

Рис. 3. Демонстрация корректной работы программы при произвольном порядке переменных в одночленах

А

Б

Рис. 4. Демонстрация работы программы при делении одного полинома на другой (в случае полиномов от одной переменной (а) и от многих переменных (б))

На рис. 4, а показан результат работы программы при определении делимости одного полинома на другой. Полиномы, согласно заданию, предполагаются зависящими от одной переменной. При выполнении операции деления полиномов многих переменных выводится сообщение об ошибке (рис. 4, б)

Глава 4. Дополнительное задание по анализу двоичного кода простых чисел

Передо мной была поставлена дополнительная задача по определению простых чисел, не превосходящих заданного N, в двоичной записи которых содержится максимальное число единиц. Эта программа была реализована в среде MS Visual Studio 2005 на языке C++ в виде консольного приложения.

Алгоритм решения этой задачи включает три этапа:

1. поиск простых чисел, не превышающих заданного N;

2. преобразование десятичного вида простых чисел в бинарный вид;

3. поиск максимального числа единиц в бинарном представлении простых чисел.

Поиск простых чисел, не превышающих заданного N основан на алгоритме, называемом "Решето Эратосфена" [6]. Этот алгоритм заключается в следующем: берем число 2 и выбрасываем все числа кратные 2. Из оставшихся чисел оставляем наименьшее (в данном случае это число 3) и выбрасываем все числа кратные 3, и так далее. Если первое оставшееся число превышает , то работу прекращаем, поскольку все отобранные и оставшиеся числа являются простыми.

Преобразование десятичного вида простых чисел в бинарный вид реализован по следующей схеме. Для каждого простого числа берется строка длиной в 33 символа (размер переменной типа int, равный 4 байтам, умноженный на количество бит в одном байте, т. е. 8, и плюс один символ для "\0"). В нее заносятся нули или единицы. Затем для каждого простого числа выполняется поразрядный сдвиг вправо на количество бит от 31 до 0 с операцией поразрядное "и" (операция наложения маски вида 0x1). Сдвиг целого числа вправо на n разрядов эквивалентен целочисленному делению его на 2ⁿ. Результат этих операций сравнивается с 1 и в зависимости от истинности или ложности этого выражения увеличиваем счетчик единиц и заносим в строку 1 или увеличиваем счетчик нулей и заносим в строку 0 соответственно.

Имея для каждого простого числа количество единиц в его бинарном представлении, находим число или числа с максимальным количеством единиц.

Ниже приведен код программы нахождения простых чисел, не превосходящих заданного N, с максимальным количеством единиц в бинарном представлении.

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int i, j, x;// счетчики

int *a, *b;

//ввод n

int n;

cout<>n;

a = new int [n]; //массив натуральных чисел

b = new int [n]; //массив простых чисел

//массив натуральных чисел

for (i=1; i<=n; i++)

a[i]=i;

//поиск простых чисел

for (i=2; i<=sqrt((float)n); i++)

{

if (i==0) continue;

x=2*i;

while (x <= n)

{

a[x]=0;//зануляем непростые числа

x=x+i;

}

}

//массив простых чисел

for (i=2, j=0; i <= n; i++)

if (a[i] != 0)

{

b[j]=a[i];

j++;

}

//печать простых чисел

int s = j;

for (i=0; i < s; i++) cout<

cout<

int s1,s0;//кол-во единиц и кол-во нулей

//размер массива равен размеру числа, умноженному на кол-во бит в байте,

//т.е. 8, и 1 для закрывающего 0

char* str = new char[sizeof(n)*8+1];

//ставим закрывающий 0

str[sizeof(n)*8]='\0';

int s1max=0;//макс. кол-во единиц в простом числе

int bmax[100]; //массив с простыми числами, сод-щими макс. число единиц

int kmax=0;

j=0;//счетчик

//цикл по простым числам

for (int k = 0; k < s; k++)

{

s1 = 0;

s0 = 0;

//ставим закрывающий 0 в начало,

//чтоб потом можно было цеплять к концу 1 или 0

str[0]='\0';

//цикл по битам числа b[k]

for (int i = sizeof(b[k])*8-1; i >= 0; i--)

{

//b[k]>>i - побитовый сдвиг вправо на i бит

//0x1 - число 1 в бинарном представлении

//((b[k]>>i) & 0x1) == 1 - позволяет определить бинарный вид числа

if (((b[k]>>i) & 0x1) == 1)

{

s1++;//увелич. кол-во единиц

strcat(str,"1");//цепляем "1"

}

else

{

s0++; //увелич. кол-во нулей

strcat(str,"0");//цепляем "0"

}

}

cout<

for (i=jmax; i>jmax-kmax; i--)

cout<

cout<

delete str;

delete a;

delete b;

system("PAUSE");

return 0;

}

Интерфейс программы приведен на рис. 5.

Рис. 5. Интерфейс программы нахождения простых чисел, не превосходящих заданного N, с максимальным количеством единиц в бинарном представлении.

Заключение

За время выполнения курсовой работы я ознакомилась с основами синтаксического анализа (на примере анализа полинома), с основами программирования на языке C#, приобрела опыт разработки визуальных приложений в среде MS Visual Studio 2005. Разработанная мною программа осуществляет синтаксический анализ полиномов, и, в частности, преобразует заданный полином к приведенному виду, вычисляет его значение, определяет, является ли полином однородным, находит его производную по заданной переменной, строит сумму и произведение двух заданных приведенных полиномов, определяет делимость одного полинома на другой без остатка.

Кроме этого мною было выполнено дополнительное задание по определению простых чисел, не превосходящих заданного N, в двоичной записи которых содержится максимальное число единиц. Эта программа была реализована в среде MS Visual Studio 2005 на языке C++ в виде консольного приложения.

Список литературы

1. Ахо, А. В. Компиляторы: принципы, технологии и инструментарий, 2‑е изд./ А. В. Ахо, М. С. Лам, Р. Сети, Д. Д. Ульман. – М.: Издательский дом "Вильямс", 2008.

2. Хантер, Р. Основные концепции компиляторов / Р. Хантер. – М.: Издательский дом "Вильямс" , 2002. – 256 с.

3. Баженова, И.Ю. Введение в программирование: Учебное пособие / И.Ю. Баженова, В.А. Сухомлин. – М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. – 326 с.

4. Харт, Д.М. Системное программирование в среде Windows, 3-е издание: Пер. с англ./ Д.М. Харт. – М.: Издательский дом "Вильямс", 2005. – 592 с.

5. Бронштейн, И.Н. Справочник по математике / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 1980. – 976 с.

6. Черемушкин, А.В. Лекции по арифметическим алгоритмам в криптографии. – М.: МЦНМО, 2002. – 104 с

Характеристики

Список файлов курсовой работы