16_II / Семестровые работы (2,3)
.docxСеместровая работа: Язык булевских операций
< символ > : := < буква > | < код > | < знак > | <разделитель>| < цифра >
< знак > : := | | + | * |
< разделитель > : := ; | : | | =
< код > последовательность из 8 нулей и единиц
< переменная > : := < иден > | < код >
< оператор > : := < иден > := < переменная > | < иден> := < переменная> < знак > < переменная >
Выполнение оператора : вычислить код по правой части (справа от := ) и присвоить его идентификатору левой части. Вычисление кода производится взятием поразрядной операции над двумя кодами (либо простым присваиванием без вычисления). Операции обозначены: “” дизъюнкция, “” конъюнкция, “+” сложение по модулю 2, “” импликация, “*” операция Шеффера (1*1 = 0 и a * b = 1, если a или b равно 0).
Пример языковой программы:
A1 := 11001010; Б18 := 01011111; X := A1 * Б18; Y := Б18 A1;
A1 := X + 11110011;
Дополнительные правила:
з) длина кода равна 8 знакам 0 и 1;
и) в правой части либо ни одного знака, либо один знак операции.
#include <iostream.h>
#include <fstream.h>
void main ()
{
ifstream f("posl.txt");
bool r;
char x;
int q=1, m=0, k=0, zn=0;
r=true;
while ((f.peek()!=EOF)&&r)
{
f>>x;
switch (q)
{
case 1:
if (((x>='A')&&(x<='Z'))||((x>='a')&&(x<='z'))){
q=2;
m=1;
}
else r=false;
break;
case 2:
if (((x>='A')&&(x<='Z'))||((x>='a')&&(x<='z'))||((x>='0')&&(x<='9'))){
q=2;
m++;
}
else
if ((x==':')&&(m<3)){
q=3;
zn=0;
}
else r=false;
break;
case 3:
if (x=='=') q=4;
else r=false;
break;
case 4:
if (((x>='A')&&(x<='Z'))||((x>='a')&&(x<='z'))) {
q=5;
m=1;
}
else
if ((x=='0')||(x=='1')){
q=6;
k=1;
}
else r=false;
break;
case 5:
if (((x>='A')&&(x<='Z'))||((x>='a')&&(x<='z'))||((x>='0')&&(x<='9'))){
q=5;
m++;
}
else
if (m<3){
switch (x){
case '+': {
q=4;
zn++;
}
break;
case '-': {
q=4;
zn++;
}
break;
case '*': {
q=4;
zn++;
}
break;
case 'v': {
q=4;
zn++;
}
break;
case '^': {
q=4;
zn++;
}
break;
case ';':
if ((zn==0)||(zn==1)) q=1;
else r=false;
break;
default: r=false;
}
}
else r=false;
break;
case 6:
if ((x=='0')||(x=='1')) {
q=6;
k++;
}
else
if (k==8){
switch (x){
case '+': {
q=4;
zn++;
}
break;
case '-': {
q=4;
zn++;
}
break;
case '*': {
q=4;
zn++;
}
break;
case 'v': {
q=4;
zn++;
}
break;
case '^': {
q=4;
zn++;
}
break;
case ';':
if ((zn==0)||(zn==1)) q=1;
else r=false;
break;
default: r=false;
}
}
else r=false;
break;
default: r=false;
}
}
if ((q==1)&&r) cout<<"true\n";
else cout<<"NO!!!\n";
cout<<"q="<<q<<endl;
cout<<"r="<<r<<endl;
cout<<"x="<<x<<endl;
cout<<"m="<<m<<endl;
cout<<"zn="<<zn<<endl;
cout<<"k= "<<k<<endl;
}
Семестровая работа: Построение экстремальной части графа.
Графом называется совокупность точек (вершин) A = {a1, … , an} и соединяющих их линий (ребер) V = {v1, v2, … , vm}. Не обязательно, чтобы в графе каждая пара точек соединялась линией. Пусть D – некоторое свойство подмножеств множества A (или множества D); тогда подмножество W называется D-экстремальным (минимальным или максимальным), если W удовлетворяет свойству D и никакое подмножество W (W W, W W) не удовлетворяет свойству D.
Задание. Составить программу для выделения D - экстремального подмножества в заданном графе согласно указанному алгоритму его выделения.
Исходные данные
I. Граф, задаваемый вершинами и ребрами:
б) A = {a1, a2, … , a12};
V = {(a1, a10), (a1, a3), (a1, a12), (a2, a3), (a3, a10), (a4, a10), (a4, a12),
(a5, a6), (a5, a8), (a5, a9), (a6, a8), (a6, a9), (a7, a8), (a8, a9), (a10, a11),
(a10, a12)},
т.е. граф состоит из 12 вершин и 16 ребер.
б) Свойство «независимости» подмножества W A: никакие две вершины из W не соединены в графе ребром.
Алгоритм построения максимального независимого подмножества состоит в выполнении не более n шагов. На первом шаге выбирается вершина a1 и включается в W, в графе помечаются a1 и все те вершины, которые соединены с ней ребрами. На i-ом шаге проверяется, имеются ли в графе непомеченные вершины. Если нет, то процесс построения W закончен. В противном случае выбирается непомеченная вершина xk (с минимальным номером), включается в W, помечаются в графе ak и все вершины, которые соединены с ней ребром. После этого делается переход к (i + 1) –му шагу.
Порядок вершин (их нумерация) должен быть таким, чтобы для всякого i = 1, 2, … , n 1:
а)
#include <fstream.h>
#include <iostream.h>
const n=12;
int a[n][20];
int b[n];
struct Rebro {
int v1;
int v2;
Rebro *next;
};
int i;
int o;
void input_rebra(Rebro *&nach){
ifstream f("inputR1.txt");
Rebro *temp;
nach = NULL;
while (!f.eof()) {
temp = new Rebro;
f>>temp->v1>>temp->v2;
temp->next = nach;
nach = temp;
}
}
void input_Versh(){
ifstream f1("inputV.txt");
for(i=0; i<n; i++){
b[i]=0;
f1>>a[i][0];
a[i][19]=0;
}}
void uporyadochit(Rebro *nachr){
int k=0;
int z0,z1;
while (nachr!=NULL) {
a[nachr->v1-1][1]=a[nachr->v1-1][1]+1;
a[nachr->v2-1][1]=a[nachr->v2-1][1]+1;
nachr = nachr->next;
}
for (i = 0; i < n-1; i++)
for (int j=i+1; j < n-2; j++){
if (a[i][1]>a[j][1]) {
z1=a[i][1]; z0=a[i][0];
a[i][1]=a[j][1]; a[i][0]=a[j][0];
a[j][1]=z1; a[j][0]=z0;
}
}
}
void pokaz_Versh (){
int k=0;
for (i=0; i<n; i++){
cout<<a[i][0]<<" ";
k++;}
cout<<endl<<"Vsego vershin: "<<k<<endl<<endl;
}
void pokaz_Itog (){
int k=0;
for (i=0; i<n; i++)
if (b[i]!=0){
cout<<b[i]<<" ";
k++;}
cout<<endl<<"Vsego chlenov: "<<k<<endl<<endl;
}
void sostavlenie(Rebro *nachr){
Rebro *h;
h=nachr;
i=0;
while (i<n) {
nachr=h;
b[i]=a[i][0];a[i][19]=1;
while (nachr!=NULL) {
if (a[i][0]==nachr->v1)
for (o=0;o<n;o++)
if (a[o][0]==nachr->v2) {a[o][19]=1;}
if (a[i][0]==nachr->v2)
for (o=0;o<n;o++)
if (a[o][0]==nachr->v1) {a[o][19]=1;}
nachr = nachr->next;
}
while ((a[i][19]==1)&&(i<n)) i++;
}
}
void main(){
Rebro *R;
input_rebra(R);
input_Versh();
cout<<"Iznachalnye vershiny:"<<endl;
pokaz_Versh();
uporyadochit(R);
cout<<"Posle uporyadochivaniya:"<<endl;
pokaz_Versh();
cout<<"Itogovoe D-ekstremal'noe:"<<endl;
sostavlenie(R);
pokaz_Itog();
}