Синтаксический анализатор полиномов (стр. 2 из 3)

Определение делимости без остаткаодного полинома (от одной переменной) на другой

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

Нахождение остатка от деления одного полинома на другой, очевидно, основано на операциях сложения и умножения полиномов. Поэтому для выполнения этого задания есть смысл воспользоваться процедурами сложения и умножения, описанных в пунктах 1.5 и 1.6.

Глава 2. Реализация синтаксического анализатора полиномовв среде VisualStudio 2005 на языке C#

Программа "Синтаксический анализатор" была написана на языке C# в среде VisualStudio 2005 [3, 4]. Язык С# - один из современных и широко используемых языков объектно-ориентированного программирования. Для реализации программы использовался шаблон Windows Forms Application, обеспечивающий наиболее удобный способ ввода и отображения информации.Для ввода полиномов использовался визуальный компонент ComboBox. Этот компонент удобен тем, что позволяет не только вводить свою собственную информацию (полином), но и использовать имеющуюся по умолчанию, что предпочтительно для демонстрации возможностей программы.

Для отображения информации в списках, необходимых для реализации процедур обработки полиномов (см. главу 1) , использовался визуальный компонент ListBox.

Для ввода значений переменных, входящих в состав полинома, использовался визуальный компонент TextBox в многострочном режиме.

Интерфейс разработанной программы представлен на рис. 2.

1. Кнопка "Приведенный полином" строит по заданному полиному приведённый. Если это невозможно или полином уже приведенный, программа выдает сообщение.

2. Кнопка "Значение" позволяет по заданному полиному и целым значениям всех его переменных вычислить его значение. При отсутствии хотя бы одного значения переменной выдается сообщение об ошибке.

3. Кнопка "Произведение" позволяет по двум заданным приведённым полиномам построить третий, который является произведением двух первых.

4. Кнопка "Производная" позволяет по заданному приведённому полиному построить новый приведённый полином, который является производной первого полинома по заданной переменной.

5. Кнопка "Сумма" позволяет по двум заданным приведённым полиномам построить третий приведённый полином, который является суммой двух первых.

6. Кнопка "Деление" позволяет по двум заданным приведённым полиномам от одной переменной определить, делится ли первый полином на второй без остатка.

7. Кнопка "Однородность" позволяет по заданному полиному определить его однородность.

Рис. 2. Интерфейс программы "Синтаксический анализатор"

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

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

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

А

Б

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

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

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

Передо мной была поставлена дополнительная задача по определению простых чисел, не превосходящих заданного N, в двоичной записи которых содержится максимальное число единиц. Эта программа была реализована в среде MSVisualStudio 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 <iostream>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

usingnamespace std;

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

{

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

int *a, *b;

//ввод n

int n;

cout<<"Input n: "; cin>>n;

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

b = newint [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<<b[i]<<" ";

cout<<endl;

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

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

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

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

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

str[sizeof(n)*8]='&bsol;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]='&bsol;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<<b[k]<<" "<<str<<" kol-vo '1'="<<s1<<" kol-vo '0'="<<s0<<endl;

//поиск макс. числа единиц

if (s1>s1max)

{

s1max=s1;

//массив bmax заполняется числами по возрастанию кол-ва единиц

//в их двоичной записи

bmax[j]=b[k];

j++;

kmax=0;//кол-во чисел с макс. на текущий момент числом единиц

}

if (s1==s1max)