Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
ЗВІТ
З лабораторних робіт №1-5
З дисципліни: «Програмування ч.4»
Мета:
1) Реалізувати алгоритм знаходження найбільшого спільного дільника D=nsd(a,b) за формулою d = x*a+y*b
2) Дано два зростаючих масиви, знайти спільні елементи в масивах
3) Вивести всі підмножини довжини k множини {1..n}
4) Перерахувати всі способи розстановки n ферзів на шахівниці n на n, при яких вони не б'ють один одного.
5) Є масив цілих чисел a [1] .. a [n], причому всі числа невід'ємні і не перевершують m. Відсортувати цей масив.
Блок-схеми:
1)
2)
3)
4)
5)
Лістінги програм:
/****************************************************************\
FILE..........: main.cpp
AUTHOR........: Andriy Picyk
DESCRIPTION...: The header file contains programming_labs.
METHOD........: result, Similar_elements, get_Count, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking
FUNCTIONS.....: factorial, Similar_elements, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking
SWITCHES......: WIN32 - if defined, 32-bit version is
compiled, otherwise 16-bit edition is compiled.
COPYRIGHT.....: Copyright (c) 2010.
HISTORY.......: DATE COMMENT
-------- --------------------------------------
-
04-14-10 Created - Andriy
\****************************************************************/
/*===============================[ PUBLIC DECLARATIONS ]========*/
#include <iostream>
#include <cstdlib>
#include <conio.h>
#include <ctime>
#include "main.h"
using namespace std;
int main()
{
/*===============================[ OBJECT DECLARATIONS ]=======*/
CEvklid* nsd;
CSimilar* similar;
CSubset* sub;
CQueen* queen;
CSort* OSort;
/*===============================[ PRIVATE DECLARATIONS]=======*/
int labs;
while (1)
{
system("cls");
cout << "Enter number of labs: ";
labs = getch() - 48;
cout << labs << endl;
switch(labs)
{
case 1:
int iA, iB;
cout << "Object-oriented method" << endl;
cout << "a = ";
cin >> iA;
cout << "b = ";
cin >> iB;
nsd = new CEvklid(iA,iB);
cout << nsd->Seek() << endl;
system("PAUSE");
system("cls");
cout << "a = ";
cin >> iA;
cout << "b = ";
cin >> iB;
cout << Evklid(iA,iB) << endl;
cout << "Procedure-oriented method" << endl;
system("PAUSE");
break;
case 2:
cout << "Object-oriented method" << endl;
int iK, iL;
cout << "k = ";
cin >> iK;
cout << "l = ";
cin >> iL;
similar = new CSimilar(iK,iL);
similar->Similar_elements();
cout << "Odnakovuh elementib " << similar->get_Count() << endl;
system("PAUSE");
system("cls");
cout << "Procedure-oriented method" << endl;
cout << "k = ";
cin >> iK;
cout << "l = ";
cin >> iL;
cout << "Odnakovuh elementib " << Similar_elements(iK, iL) << endl;
system("PAUSE");
break;
case 3:
int iN;
cout << "Object-oriented method" << endl;
cout << "n = ";
cin >> iN;
cout << "k = ";
cin >> iK;
sub = new CSubset(iN, iK);
sub->Generate();
system("PAUSE");
system("cls");
cout << "Procedure-oriented method" << endl;
cout << "n = ";
cin >> iN;
cout << "k = ";
cin >> iK;
Generate(iN,iK);
system("PAUSE");
break;
case 4:
int iCount;
cout << "Object-oriented method" << endl;
cout << "n = ";
cin >> iN;
queen = new CQueen(iN);
queen->Create_arr();
queen->Backtracking(1);
queen->Print_Count();
queen->~CQueen();
system("PAUSE");
system("cls");
iCount = 0;
int* piArr;
int** ppiDoshka;
cout << "Procedure-oriented method" << endl;
cout << "n = ";
cin >> iN;
piArr = new int[iN];
ppiDoshka = new int*[iN];
for(int i=0;i<iN;i++)
{
ppiDoshka[i] = new int[iN];
}
Create_arr(ppiDoshka, iN);
cout << "Roztashyvannja " << iN << " ferziv:" << endl;
Backtracking(1, ppiDoshka, iN, piArr, &iCount);
cout << "Vsogo " << iCount << " roztashyvan" << endl;
for (int i = 0; i < iN; i++)
{
delete ppiDoshka[i];
}
delete ppiDoshka;
cout << endl;
system("PAUSE");
break;
case 5:
cout << "Procedure-oriented method" << endl;
int iM;
cout << "n = ";
cin >> iN;
cout << "m = ";
cin >> iM;
sort(iN, iM);
system("PAUSE");
system("cls");
cout << "Object-oriented method" << endl;
cout << "n = ";
cin >> iN;
cout << "m = ";
cin >> iM;
OSort = new CSort(iN,iM);
OSort->Sort();
system("PAUSE");
break;
default:
system("pause");
return 0;
}
}
}
/****************************************************************\
METHOD........: CEvklid
DESCRIPTION...: Inicialization variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iA - first number
iB - second number
RETURNS.......: void
\****************************************************************/
CEvklid::CEvklid(int iA,int iB)
{
m_iA = iA;
m_iB = iB;
}
/****************************************************************\
METHOD........: Seek
DESCRIPTION...: Finding the greatest common multiple.
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: int
\****************************************************************/
int CEvklid::Seek()
{
int iM,iN,iP,iQ,iR,iS,iK,iX,iY;
iM = m_iA;
iN = m_iB;
iP = 1;
iQ = 0;
iR = 0;
iS = 1;
while (!(iM==0||iN==0))
{
if (iM >= iN)
{
iM -= iN;
iP -= iR;
iQ -= iS;
}
else
{
iN -= iM;
iR -= iP;
iS -= iQ;
}
}
if (iM == 0)
{
iK=iN;
iX=iR;
iY=iS;
}
else
{
iK=iM;
iX=iP;
iY=iQ;
}
return m_iA*iX+m_iB*iY;
}
/****************************************************************\
FUNCTION......: Evklid
DESCRIPTION...: Finding the greatest common multiple.
ATTRIBUTES....: Public
ARGUMENTS.....:
iA - first number
iB - second number
RETURNS.......: void
\****************************************************************/
int Evklid(int iA, int iB)
{
int iM,iN,iP,iQ,iR,iS,iK,iX,iY;
iM = iA;
iN = iB;
iP = 1;
iQ = 0;
iR = 0;
iS = 1;
while (!(iM==0||iN==0))
{
if (iM >= iN)
{
iM -= iN;
iP -= iR;
iQ -= iS;
}
else
{
iN -= iM;
iR -= iP;
iS -= iQ;
}
}
if (iM == 0)
{
iK=iN;
iX=iR;
iY=iS;
}
else
{
iK=iM;
iX=iP;
iY=iQ;
}
return iA*iX+iB*iY;
}
/****************************************************************\
METHOD........: CSimilar
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iK - size first array
iL - size second array
RETURNS.......: void
\****************************************************************/
CSimilar::CSimilar(int iK, int iL)
{
m_iCount = 0;
m_piArrX = new int[iK];
m_piArrY = new int[iL];
m_iK = iK;
m_iL = iL;
for(int i=0;i<iK;i++)
{
cout << "x[" << i << "] = ";
cin >> m_piArrX[i];
}
for(int i=0;i<iL;i++)
{
cout << "y[" << i << "] = ";
cin >> m_piArrY[i];
}
}
/****************************************************************\
METHOD........: Similar_elements
DESCRIPTION...: Find similar items.
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CSimilar::Similar_elements()
{
for(int i=0;i<m_iK;i++)
{
for(int j=0;m_piArrY[j]<=m_piArrX[i];j++)
{
if (m_piArrY[j]==m_piArrX[i])
{
cout << m_piArrX[i] << " ";
m_iCount++;
}
}
}
cout << endl;
}
/****************************************************************\
METHOD........: get_Count
DESCRIPTION...: Outpup count of items.
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
int CSimilar::get_Count()
{
return m_iCount;
}
/****************************************************************\
FUNCTION......: Similar_elements
DESCRIPTION...: Find similar items.
ATTRIBUTES....: Public
ARGUMENTS.....:
iK - size first array
iL - size second array
RETURNS.......: void
\****************************************************************/
int Similar_elements(int iK, int iL)
{
int iCount = 0;
int* piArrX = new int[iK];
int* piArrY = new int[iL];
for(int i=0;i<iK;i++)
{
cout << "x[" << i << "] = ";
cin >> piArrX[i];
}
for(int i=0;i<iL;i++)
{
cout << "y[" << i << "] = ";
cin >> piArrY[i];
}
for(int i=0;i<iK;i++)
{
for(int j=0;piArrY[j]<=piArrX[i];j++)
{
if (piArrY[j]==piArrX[i])
{
cout << piArrX[i] << " ";
iCount++;
}
}
}
cout << endl;
return iCount;
}
/****************************************************************\
METHOD........: CSubset
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - size of set
iK - length of sub set
RETURNS.......: none
\****************************************************************/
CSubset::CSubset(int iN,int iK)
{
m_iK = iK;
m_iN = iN;
}
/****************************************************************\
METHOD........: Generate
DESCRIPTION...: Generate all subset
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CSubset::Generate()
{
int iNum=0;
m_iN++;
int* iArrB = new int[m_iN];
int i;
while (iArrB[m_iN-1]!=0)
{
i=1;
while (iArrB[i]==1)
{
iArrB[i]=0;
i++;
}
iArrB[i]=1;
for(i=0; i<m_iN;i++)
{
if(iArrB[i]==1)
{
iNum++;
}
}
if (iNum == m_iK)
{
cout << "{";
for(i=0; i<m_iN;i++)
{
if(iArrB[i]==1)
{
cout << i;
}
}
cout << "} ";
}
iNum = 0;
}
cout << endl;
}
/****************************************************************\
FUNCTION......: Generate
DESCRIPTION...: Generate all subset
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - size of set
iK - length of sub set
RETURNS.......: void
\****************************************************************/
void Generate(int iN, int iK)
{
int iNum=0;
iN++;
int* iArrB = new int[iN];
int i;
while (iArrB[iN-1]!=0)
{
i=1;
while (iArrB[i]==1)
{
iArrB[i]=0;
i++;
}
iArrB[i]=1;
for(i=0; i<iN;i++)
{
if(iArrB[i]==1)
{
iNum++;
}
}
if (iNum == iK)
{
cout << "{";
for(i=0; i<iN;i++)
{
if(iArrB[i]==1)
{
cout << i;
}
}
cout << "} ";
}
iNum = 0;
}
cout << endl;
}
/****************************************************************\
METHOD........: CQueen
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - Size chess board
RETURNS.......: None
\****************************************************************/
CQueen::CQueen(int iN)
{
m_iN = iN;
m_piArr = new int[m_iN];
m_ppiDoshka = new int*[m_iN];
m_iCount = 0;
for(int i=0;i<iN;i++)
{
m_ppiDoshka[i] = new int[m_iN];
}
}
/****************************************************************\
METHOD........: Create_arr
DESCRIPTION...: Fill the array with zeros
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: void
\****************************************************************/
void CQueen::Create_arr()
{
for(int i=0;i<m_iN;i++)
{
for(int j=0;j<m_iN;j++)
{
m_ppiDoshka[i][j] = 0;
}
}
}
/****************************************************************\
METHOD........: show_arr
DESCRIPTION...: Finding chess board
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: void
\****************************************************************/
void CQueen::show_arr()
{
for(int i=0;i<m_iN;i++)
{
for(int j=0;j<m_iN;j++)
{
cout << m_ppiDoshka[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/****************************************************************\
METHOD........: mod_arr
DESCRIPTION...: Change the location of Queens on the board
ATTRIBUTES....: Public
ARGUMENTS.....:
i - colom
j - row
RETURNS.......: void
\****************************************************************/
void CQueen::mod_arr(int i, int j)
{
m_ppiDoshka[i][j]=1;
}
/****************************************************************\
METHOD........: Exit
DESCRIPTION...: Condition out of the recursion
ATTRIBUTES....: Public
ARGUMENTS.....:
iK = 0 - out of the recursion
j - row
RETURNS.......: bool
\****************************************************************/
bool CQueen::Exit(int iK, int j)
{
int i;
for (i=1;(i<iK) && (j!=m_piArr[i]) && (abs(iK-i)!=abs(j-m_piArr[i]));i++);
return i==iK;
}
/****************************************************************\
METHOD........: Backtracking
DESCRIPTION...: Recursive function roztanovky n Queens on the board nxn
ATTRIBUTES....: Public
ARGUMENTS.....:
iK = 0 - out of the recursion
RETURNS.......: bool
\****************************************************************/
void CQueen::Backtracking(int iK)
{
for (int j=1; j<=m_iN; j++)
{
if (Exit(iK,j))
{
m_piArr[iK]=j;
if (iK==m_iN)
{
for (int i=1;i<=m_iN;i++)
{
mod_arr(i-1, m_piArr[i]-1);
}
show_arr();
Create_arr();
m_iCount++;
}
Backtracking(iK+1);
}
}
}
/****************************************************************\
METHOD........: Print_Count
DESCRIPTION...: Show count of combination
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: void
\****************************************************************/
void CQueen::Print_Count()
{
cout << "Vsogo " << m_iCount << " roztashyvan" << endl;
}
/****************************************************************\
METHOD........: ~CQueen
DESCRIPTION...: Delete dynamic variables
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: None
\****************************************************************/
CQueen::~CQueen()
{
for (int i = 0; i < m_iN; i++)
{
delete m_ppiDoshka[i];
}
delete m_ppiDoshka;
}
/****************************************************************\
FUNCTION......: Create_arr
DESCRIPTION...: Fill the array with zeros
ATTRIBUTES....: Public
ARGUMENTS.....:
ppiArr - Chess board
iN - Size chess board
RETURNS.......: void
\****************************************************************/
void Create_arr(int** ppiArr, int iN)
{
for(int i=0;i<iN;i++)
{
for(int j=0;j<iN;j++)
{
ppiArr[i][j] = 0;
}
}
}
/****************************************************************\
FUNCTION......: show_arr
DESCRIPTION...: Finding chess board
ATTRIBUTES....: Public
ARGUMENTS.....:
ppiArr - Chess board
iN - Size chess board
RETURNS.......: void
\****************************************************************/
void show_arr(int** ppiArr, int iN)
{
for(int i=0;i<iN;i++)
{
for(int j=0;j<iN;j++)
{
cout << ppiArr[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/****************************************************************\
FUNCTION......: mod_arr
DESCRIPTION...: Change the location of Queens on the board
ATTRIBUTES....: Public
ARGUMENTS.....:
ppiArr - Chess board
i - colom
j - row
RETURNS.......: void
\****************************************************************/
void mod_arr(int** ppiArr, int i, int j)
{
ppiArr[i][j]=1;
}
/****************************************************************\
FUNCTION......: Exit
DESCRIPTION...: Condition out of the recursion
ATTRIBUTES....: Public
ARGUMENTS.....:
piArrX - Array for storing the line which should stand queen
iK = 0 - out of the recursion
j - row
RETURNS.......: bool
\****************************************************************/
bool Exit(int* piArrX, int iK, int j)
{
int i;
for (i=1;(i<iK) && (j!=piArrX[i]) && (abs(iK-i)!=abs(j-piArrX[i]));i++);
return i==iK;
}
/****************************************************************\
METHOD........: Backtracking
DESCRIPTION...: Recursive function roztanovky n Queens on the board nxn
ATTRIBUTES....: Public
ARGUMENTS.....:
iK = 0 - out of the recursion
ppiArr - Chess board
iN - Size chess board
piArrX - Array for storing the line which should stand queen
piCount - Number of iteration
RETURNS.......: bool
\****************************************************************/
void Backtracking(int iK, int** ppiArr, int iN, int* piArrX, int* piCount)
{
for (int j=1; j<=iN; j++)
{
if (Exit(piArrX,iK,j))
{
piArrX[iK]=j;
if (iK==iN)
{
for (int i=1;i<=iN;i++)
{
mod_arr(ppiArr, i-1, piArrX[i]-1);
}
show_arr(ppiArr, iN);
Create_arr(ppiArr, iN);
*piCount = *piCount+1;
}
Backtracking(iK+1, ppiArr, iN, piArrX, piCount);
}
}
}
/****************************************************************\
METHOD........: CSort
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - Size array
iM - filter
RETURNS.......: None
\****************************************************************/
CSort::CSort(int iN, int iM)
{
m_iN = iN;
m_iM = iM;
}
/****************************************************************\
METHOD........: CSort
DESCRIPTION...: Sort array
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CSort::Sort()
{
int* piArr;
int iJ,iTemp,iS;
piArr = new int[m_iN];
srand((unsigned)time(0));
for(int i=0;i<m_iN;i++)
{
piArr[i] = rand()%m_iM+1;
cout << piArr[i] << " ";
}
cout << endl;
for(int i=1;i<m_iN;i++)
{
iTemp=piArr[i];
iJ=i-1;
while(iJ>=0 && piArr[iJ]>iTemp)
{
piArr[iJ+1]=piArr[iJ];
iJ--;
piArr[iJ+1]=iTemp;
for(int j=0;j<m_iN;j++)
{
cout << piArr[j]<< " ";
}
cout << endl;
}
}
}
/****************************************************************\
FUNCTION......: sort
DESCRIPTION...: Sort array
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - Size array
iM - filter
RETURNS.......: void
\****************************************************************/
void sort (int iN, int iM)
{
int* piArr;
int iJ,iTemp,iS;
piArr = new int[iN];
srand((unsigned)time(0));
for(int i=0;i<iN;i++)
{
piArr[i] = rand()%iM+1;
cout << piArr[i] << " ";
}
cout << endl;
for(int i=1;i<iN;i++)
{
iTemp=piArr[i];
iJ=i-1;
while(iJ>=0 && piArr[iJ]>iTemp)
{
piArr[iJ+1]=piArr[iJ];
iJ--;
piArr[iJ+1]=iTemp;
for(int j=0;j<iN;j++)
{
cout << piArr[j]<< " ";
}
cout << endl;
}
}
}
/** (END OF FILE : main.cpp)*********************************/
/****************************************************************\
FILE..........: main.h
AUTHOR........: Andriy Picyk
DESCRIPTION...: The header file contains programming_labs.
METHOD........: result, Similar_elements, get_Count, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking
FUNCTIONS.....: factorial_, Similar_elements, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking
SWITCHES......: WIN32 - if defined, 32-bit version is
compiled, otherwise 16-bit edition is compiled.
COPYRIGHT.....: Copyright (c) 2010.
HISTORY.......: DATE COMMENT
-------- --------------------------------------
-
04-14-10 Created - Andriy
\****************************************************************/
/****************************************************************\
CLASS…......: CEvklid.
DESCRIPTION…: Finding the greatest common multiple.
\****************************************************************/
class CEvklid
{
private:
int m_iA, m_iB;
public:
CEvklid(int iA,int iB);
int Seek();
};
int Evklid(int iA, int iB);
/****************************************************************\
CLASS…......: CSimilar.
DESCRIPTION…: Find similar items in two different arrays.
\****************************************************************/
class CSimilar
{
private:
int* m_piArrX;
int* m_piArrY;
int m_iCount;
int m_iK;
int m_iL;
public:
CSimilar(int iK, int iL);
void Similar_elements();
int get_Count();
};
int Similar_elements(int iK, int iL);
/****************************************************************\
CLASS…......: CSubset.
DESCRIPTION…: Output all subsets of the set 1 .. k.
\****************************************************************/
class CSubset
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора