Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
ЗВІТ
З лабораторних робіт №1-4
З дисципліни: «Програмування ч.4»
Мета:
1) Дано натуральне n, обчислити
1/1! + 1/2! + … + 1/n!
2) Дано два зростаючих масиви, знайти спільні елементи в масивах
3) Вивести всі підмножини множини {1..k}
4) Перерахувати всі способи розстановки n ферзів на шахівниці n на n, при яких вони не б'ють один одного.
Блок-схеми:
1)
2)
3) 4)
Лістінги програм:
/****************************************************************\
FILE..........: main.cpp
AUTHOR........: Kuzyk Galja
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-03-10 Created - Galja
04-03-10 Modified - Galja
\****************************************************************/
/*===============================[ PUBLIC DECLARATIONS ]========*/
#include <iostream>
#include <cstdlib>
#include "main.h"
using namespace std;
int main ()
{
/*===============================[ OBJECT DECLARATIONS ]========*/
CFactorial* factorial; // pointer by CFactorial
CSimilar* similar; // pointer by CSimilar
CSubset* sub; // pointer by CSubset
CQueen* queen; // pointer by CQueen
/*===============================[ PRIVATE DECLARATIONS]=======*/
int labs;
while(true)
{
system("cls");
cout << "Select number of labs: ";
cin >> labs;
switch(labs)
{
case 1:
cout << "Object-oriented method" << endl;
int iN;
cout << "n = ";
cin >> iN;
factorial = new CFactorial(iN);
factorial->result();
system("PAUSE");
system("cls");
cout << "Procedure-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
factorial_(iN);
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:
cout << "Object-oriented method" << endl;
cout << "k = ";
cin >> iK;
sub = new CSubset(iK);
sub->Generate();
system("PAUSE");
system("cls");
cout << "Procedure-oriented method" << endl;
cout << "k = ";
cin >> iK;
Generate(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:
break;
default:
system("PAUSE");
return 0;
}
}
}
/*===============================[ LABA #1 ]===================*/
/****************************************************************\
METHOD........: CFactorial
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: void
\****************************************************************/
CFactorial::CFactorial(int iN)
{
m_iN = iN;
}
/****************************************************************\
METHOD........: show_result
DESCRIPTION...: Calculate number 1 / 0! + 1 / 1! + 1 / 2! + ... + 1 / n!
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: void
NOTES.........: Example:
m_iN Result
---- ------
1 1
2 1.5
3 1.66667
\****************************************************************/
void CFactorial::result()
{
float fltSum = 0; //sum of row
int iFact = 1;
//Formation of Factorial and summation line
for(int i = 1; i <= m_iN; i++)
{
iFact *= i; //Calculated factorial
fltSum += 1.0 / iFact; //Calculated sum of row
}
cout << "Result: " << fltSum << endl;
}
/****************************************************************\
FUNCTION......: factorial
DESCRIPTION...: Calculate number 1 / 0! + 1 / 1! + 1 / 2! + ... + 1 / n!
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - number of iteration
RETURNS.......: void
NOTES.........: Example:
iN Result
---- ------
1 1
2 1.5
3 1.66667
\****************************************************************/
void factorial_ (int iN){
float fltSum = 0; //sum of row
int iFact = 1;
//Formation of Factorial and summation line
for(int i = 1; i <= iN; i++)
{
iFact *= i; //Calculated factorial
fltSum += 1.0 / iFact; //Calculated sum of row
}
cout << "Result: " << fltSum << endl;
}
/*===============================[ END LABA #1 ]===================*/
/*===============================[ LABA #2 ]===================*/
/****************************************************************\
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;
}
/*===============================[ END LABA #2 ]===================*/
/*===============================[ LABA #3 ]===================*/
/****************************************************************\
METHOD........: CSubset
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iK - size of set
RETURNS.......: none
\****************************************************************/
CSubset::CSubset(int iK)
{
m_iK = iK;
}
/****************************************************************\
METHOD........: Generate
DESCRIPTION...: Generate all subset
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CSubset::Generate()
{
m_iK++;
int* iArrB = new int[m_iK];
int i;
while (iArrB[m_iK-1]!=0)
{
i=1;
while (iArrB[i]==1)
{
iArrB[i]=0;
i++;
}
iArrB[i]=1;
cout << "{";
for(i=0; i<m_iK;i++)
{
if(iArrB[i]==1)
{
cout << i;
}
}
cout << "} ";
}
cout << endl;
}
/****************************************************************\
METHOD........: Generate
DESCRIPTION...: Generate all subset
ATTRIBUTES....: Public
ARGUMENTS.....:
iK - size of set
RETURNS.......: void
\****************************************************************/
void Generate(int iK)
{
iK++;
int* iArrB = new int[iK];
int i;
while (iArrB[iK-1]!=0)
{
i=1;
while (iArrB[i]==1)
{
iArrB[i]=0;
i++;
}
iArrB[i]=1;
cout << "{";
for(i=0; i<iK;i++)
{
if(iArrB[i]==1)
{
cout << i;
}
}
cout << "} ";
}
cout << endl;
}
/*===============================[ END LABA #3 ]===================*/
/*===============================[ 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........: 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);
}
}
}
/*===============================[ END LABA #4 ]===================*/
/** (END OF FILE : main.cpp)*********************************/
/****************************************************************\
FILE..........: main.h
AUTHOR........: Kuzyk Galja
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-03-10 Created - Galja
04-03-10 Modified - Galja
\****************************************************************/
/****************************************************************\
CLASS…......: CFactorial.
DESCRIPTION…: Calculate number 1 / 0! + 1 / 1! + 1 / 2! + ... + 1 / n!.
\****************************************************************/
class CFactorial
{
private:
int m_iN; // variable n
public:
CFactorial(int iN);
void result();
};
void factorial_(int iN);
/****************************************************************\
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
{
private:
int m_iK;
public:
CSubset(int iK);
void Generate();
};
void Generate (int iK);
/****************************************************************\
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();
};
void Create_arr(int** ppiArr, int iN);
void show_arr(int** ppiArr, int iN);
void mod_arr(int** ppiArr, int i, int j);
bool Exit(int* piArrX, int iK, int j);
void Backtracking(int iK, int** ppiArr, int iN, int* piArrX, int* piCount);
/** (END OF FILE : main.h)*********************************/
Висновки і результати роботи програм:
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора