Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
ЗВІТ
З лабораторної роботи №4-5
З дисципліни: «Програмування ч.4»
Мета:
4) Вивести всі можливі варіанти розташування N ферзів на дошці NxN
5) Заданий масив цілих чисел a[n], записати ті самі числа в масив b[n] так щоб, цей масив був відсортований.
Блок-схеми:
Лістинг програми 4):
/****************************************************************\
CLASS…......: CQueen.
DESCRIPTION…: Location n Queens on the board nxn.
\****************************************************************/
class CQueen
{
private:
int m_iCount, m_iN;
int* m_piArr;
int** m_ppiDoshka;
public:
void Create_arr(int** arr, int n);
CQueen(int iN);
void Create_arr();
void show_arr();
void mod_arr(int i, int j);
bool Exit(int iK, int j);
void Backtracking(int iK);
void Print_Count();
~CQueen();
};
/****************************************************************\
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);
/****************************************************************\
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);
/****************************************************************\
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);
/****************************************************************\
FUNCTION......: mod_arr
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);
/****************************************************************\
FUNCTION......: 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);
CQueen* queen; // pointer by CQueen
/*===============================[ OBJECT-ORIENTED METHOD ]======*/
case 1:
cout << endl;
cout << "\t\t\t\tObject-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
cout << "Roztashyvannja " << iN << " ferziv:" << endl;
queen = new CQueen(iN);
queen->Create_arr();
queen->Backtracking(1);
queen->Print_Count();
queen->~CQueen();
break;
/*===============================[ PROCEDURE-ORIENTED METHOD ]==*/
case 2:
int iCount;
int* piArr;
int** ppiDoshka;
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);
iCount=0;
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;
cout << "\t\t\tProcedure-oriented method" << endl;
cout << endl;
/*===============================[ LABA #4 ]===================*/
/****************************************************************\
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........: mod_arr
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();
Sleep(500);
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......: mod_arr
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);
Sleep(500);
Create_arr(ppiArr, iN);
*piCount = *piCount+1;
}
Backtracking(iK+1, ppiArr, iN, piArrX, piCount);
}
}
}
Лістинг програми 5):
/****************************************************************\
FILE..........: programming_labs.h
AUTHOR........: Taras Kobernyk
DESCRIPTION...: The header file contains programming_labs.
METHOD........: CFactorial, show_result
FUNCTIONS.....: factorial
SWITCHES......: WIN32 - if defined, 32-bit version is
compiled, otherwise 16-bit edition is compiled.
COPYRIGHT.....: Copyright (c) 2010.
HISTORY.......: DATE COMMENT
-------- --------------------------------------
-
03-17-10 Created - Taras
03-31-10 Modified - Taras
\****************************************************************/
/****************************************************************\
CLASS…......: CSort.
DESCRIPTION…: Sort array.
\****************************************************************/
class CSort
{
int *m_piA;
int *m_piB;
int m_iN,m_iMin;
public:
CSort(int iN);
void Sort();
int Min_elm(int iM);
};
/****************************************************************\
FUNCTION......: Sort
DESCRIPTION...: Sort array
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void Sort();
/****************************************************************\
FUNCTION......: Min_elm
DESCRIPTION...: Search min element of array
ATTRIBUTES....: Public
ARGUMENTS.....:
iArr - array
iN - Size array
iM - pred minimal element
RETURNS.......: int
\****************************************************************/
int Min_elm(int* iArr, int iN, int iM);
/** (END OF FILE : programming_labs.h)*********************************/
/****************************************************************\
FILE..........: programming_labs.cpp
AUTHOR........: Taras Kobernyk
DESCRIPTION...: Laboratory work, designed to solve common problems
METHOD........: CFactorial, show_result
FUNCTIONS.....: factorial
SWITCHES......: WIN32 - if defined, 32-bit version is
compiled, otherwise 16-bit edition is compiled.
COPYRIGHT.....: Copyright (c) 2010, KI-21.
HISTORY.......: DATE COMMENT
-------- --------------------------------------
-
03-17-10 Created - Taras
03-31-10 Modified - Taras
\****************************************************************/
CSort* sort; // pointer by CSort
/*===============================[ LABA #5 ]====================*/
cout << endl;
cout << "\t\t\t\tLaboratory work #1" << endl;
cout << endl;
cout << "Select a method of program\n\t"
"1 - Object-oriented method\n\t"
"2 - Procedure-oriented method" << endl;
iNumber_method = getch() - 48;
switch(iNumber_method)
{
/*===============================[ OBJECT-ORIENTED METHOD ]======*/
case 1:
cout << endl;
cout << "\t\t\t\tObject-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
sort = new CSort(iN);
sort->Sort();
break;
/*===============================[ PROCEDURE-ORIENTED METHOD ]===*/
case 2:
cout << endl;
cout << "\t\t\tProcedure-oriented method" << endl;
cout << endl;
Sort();
break;
}
break;
/*===============================[ END LABA #5 ]================*/
/*===============================[ LABA #5 ]===================*/
/****************************************************************\
METHOD........: CSort
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - Size array
RETURNS.......: None
\****************************************************************/
CSort::CSort(int iN)
{
m_iMin=0;
m_iN = iN;
m_piA = new int[m_iN];
m_piB = new int[m_iN];
srand((unsigned)time(0));
for (int i=0;i<m_iN;i++)
{
m_piA[i] = rand()%(rand()%100)+1;
cout << m_piA[i] << " ";
}
cout << endl;
}
/****************************************************************\
METHOD........: Min_elm
DESCRIPTION...: Search min element of array
ATTRIBUTES....: Public
ARGUMENTS.....:
iM - pred minimal element
RETURNS.......: int
\****************************************************************/
int CSort::Min_elm(int iM)
{
int iMin = 100;
for (int i=0;i<m_iN;i++)
{
if(iMin>m_piA[i]&&m_piA[i]>iM){
iMin=m_piA[i];
}
}
return iMin;
}
/****************************************************************\
METHOD........: Sort
DESCRIPTION...: Sort array
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CSort::Sort()
{
int j=0;
while(j<m_iN)
{
m_iMin = Min_elm(m_iMin);
for(int i=0;i<m_iN;i++)
{
if(m_piA[i]==m_iMin)
{
m_piB[j]=m_iMin;
cout << m_piB[j++] << " ";
}
}
}
cout << endl;
}
/****************************************************************\
FUNCTION......: Sort
DESCRIPTION...: Sort array
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void Sort()
{
int *piA;
int *piB;
int iN,iMin=0;
int j=0;
cout << "n = ";
cin >> iN;
piA = new int[iN];
piB = new int[iN];
srand((unsigned)time(0));
for (int i=0;i<iN;i++)
{
piA[i] = rand()%(rand()%100)+1;
cout << piA[i] << " ";
}
cout << endl;
while(j<iN)
{
iMin = Min_elm(piA,iN,iMin);
for(int i=0;i<iN;i++)
{
if(piA[i]==iMin)
{
piB[j]=iMin;
cout << piB[j++] << " ";
}
}
}
cout << endl;
}
/****************************************************************\
FUNCTION......: Min_elm
DESCRIPTION...: Search min element of array
ATTRIBUTES....: Public
ARGUMENTS.....:
iArr - array
iN - Size array
iM - pred minimal element
RETURNS.......: int
\****************************************************************/
int Min_elm(int* iArr, int iN, int iM)
{
int iMin = 100;
for (int i=0;i<iN;i++)
{
if(iMin>iArr[i]&&iArr[i]>iM){
iMin=iArr[i];
}
}
return iMin;
}
/** (END OF FILE : programming_labs.cpp)*********************************/
Висновок:
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора