Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
ЗВІТ
З лабораторних робіт №1-5
З дисципліни: «Програмування ч.4»
Мета:
1) Дано натуральні числа а і b. Обчислити їх суму а + b. Використовувати оператори присвоювання лише виду
<Змінна1>: = <Змінна2>,
< Змінна>: = <число>,
<Змінна1>: = < Змінна 2> + 1.
2) Елементами масиву a [1 .. n] є неспадаючі масиви [1 .. m] цілих чисел:
a: array [1 .. n] of array [1 .. m] of integer;
a [1] [1] ≤ ... ≤ a [1] [m], ..., a [n] [1] ≤ ... ≤ a [n] [m].
Відомо, що існує число, що входить у всі масиви a [i] (існує таке x, що для всякого i з 1 .. n знайдеться j з 1 .. m, для якого a [i] [j] = x). Знайти одне з таких чисел х.
3) Надрукувати всі послідовності додатніх цілих чисел довжини k, у яких i-ий член не перевершує i.
4) Перерахувати всі способи розстановки n ферзів на шахівниці n на n, при яких вони не б'ють один одного.
5) Є масив цілих чисел a [1] .. a [n], причому всі числа невід'ємні і не перевершують m. Відсортувати цей масив; число дій порядку m + n.
Блок-схеми:
1)
2)
3)
4)
5)
Лістінги програм:
/****************************************************************\
FILE..........: main.cpp
AUTHOR........: Toma Gres
DESCRIPTION...: Laboratory work, designed to solve common problems
METHOD........: Add, Seek, Length, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking, Print_Count,Sort
FUNCTIONS.....: Add, Seek_num, Length, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking, Sort
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-29-10 Created - Toma
04-02-10 Modified - Toma
\****************************************************************/
/*===============================[ PUBLIC DECLARATIONS ]========*/
#include <iostream>
#include <conio.h>
#include <cstdlib>
#include <ctime>
#include<clocale>
#include "main.h"
#define N 3
#define M 3
using namespace std;
void main()
{
/*===============================[ OBJECT DECLARATIONS ]========*/
CAdd* add;
CSeek* seek;
CAmount* amount;
CQueen* queen;
CSort* OSort;
/*===============================[ PRIVATE DECLARATIONS]=======*/
int iLab_n;
setlocale(LC_CTYPE, "");
cout << "Введiть номер лабораторної роботи: ";
cin >> iLab_n;
switch(iLab_n)
{
/*=============[Laba 1]=================*/
case 1:
cout << "Procedure-oriented method" << endl;
int iA,iB;
cout << "a = ";
cin >> iA;
cout << "b = ";
cin >> iB;
cout << "sum = " << Add(iA,iB) << endl;
system("PAUSE");
system("cls");
cout << "Object-oriented method" << endl;
cout << "a = ";
cin >> iA;
cout << "b = ";
cin >> iB;
add = new CAdd(iA,iB);
cout << "sum = " << add->Add() << endl;
system("PAUSE");
break;
/*=============[End Laba 1]=================*/
/*=============[Laba 2]=================*/
case 2:
cout << "Procedure-oriented method" << endl;
cout << Seek_num() << endl;
system("PAUSE");
system("cls");
cout << "Object-oriented method" << endl;
seek = new CSeek();
cout << seek->Seek() << endl;
system("PAUSE");
break;
/*=============[End Laba 2]=================*/
/*=============[Laba 3]=================*/
case 3:
cout << "Procedure-oriented method" << endl;
int iK;
cout << "k = ";
cin >> iK;
Generate(iK);
system("PAUSE");
system("cls");
cout << "Object-oriented method" << endl;
cout << "k = ";
cin >> iK;
amount = new CAmount(iK);
amount->Generate();
break;
/*=============[End Laba 3]=================*/
case 4:
/*=============[Laba 4]=================*/
cout << "Procedure-oriented method" << endl;
int iCount,iN;
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 << "Розташування " << iN << " ферзiв:" << endl;
Backtracking(1, ppiDoshka, iN, piArr, &iCount);
cout << "Всього " << iCount << " розташувань" << endl;
for (int i = 0; i < iN; i++)
{
delete ppiDoshka[i];
}
delete ppiDoshka;
system("PAUSE");
system("cls");
cout << "Object-oriented method" << endl;
cout << "n = ";
cin >> iN;
cout << "Розташування " << iN << " ферзiв:" << endl;
queen = new CQueen(iN);
queen->Create_arr();
queen->Backtracking(1);
queen->Print_Count();
queen->~CQueen();
break;
/*=============[End Laba 4]=================*/
case 5:
/*=============[Laba 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();
break;
/*=============[End Laba 5]=================*/
}
}
/*=============[Laba 1]=====================*/
/****************************************************************\
METHOD........: CAdd
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iA - first number
iB - second number
RETURNS.......: None
\****************************************************************/
CAdd::CAdd(int iA, int iB)
{
m_iA = iA;
m_iB = iB;
}
/****************************************************************\
METHOD........: Add
DESCRIPTION...: Add two nambers
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: int
\****************************************************************/
int CAdd::Add()
{
int iC = m_iA;
for(int i=0;i<m_iB;i++)
{
iC++;
}
return iC;
}
/****************************************************************\
FUNCTION......: Add
DESCRIPTION...: Add two nambers
ATTRIBUTES....: Public
ARGUMENTS.....:
iA - first number
iB - second number
RETURNS.......: int
\****************************************************************/
int Add (int iA, int iB)
{
int iC = iA;
for(int i=0;i<iB;i++)
{
iC++;
}
return iC;
}
/*=============[End Laba 1]=================*/
/*=============[Laba 2]=====================*/
/****************************************************************\
METHOD........: CSeek
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: None
\****************************************************************/
CSeek::CSeek()
{
m_bEq = true;
m_iArrA = new int* [N];
for (int i=0;i<N;i++)
{
m_iArrA[i] = new int[M];
}
m_iArrB = new int [N];
for (int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
cout << "a[" << i << "][" << j << "] = ";
cin >> m_iArrA[i][j];
}
}
for (int i=0;i<N;i++)
{
m_iArrB[i] = 0;
}
}
/****************************************************************\
METHOD........: Seek
DESCRIPTION...: Find an identical character in different areas
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: int
\****************************************************************/
int CSeek::Seek()
{
for (int i=0;i<N;i++)
{
m_bEq = m_bEq && m_iArrA[0][m_iArrB[0]] == m_iArrA[i][m_iArrB[i]];
}
while(!m_bEq)
{
m_iS=m_iK=0;
while(m_iK!=N-1)
{
m_iK++;
if(m_iArrA[m_iK][m_iArrB[m_iK]]<m_iArrA[m_iS][m_iArrB[m_iS]])
{
m_iS=m_iK;
}
}
m_iArrB[m_iS] += 1;
for (int i=0;i<N;i++)
{
m_bEq = m_iArrA[0][m_iArrB[0]]== m_iArrA[i][m_iArrB[i]];
}
}
return m_iArrA[0][m_iArrB[0]];
}
/****************************************************************\
FUNCTION......: Seek_num
DESCRIPTION...: Find an identical character in different areas
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: int
\****************************************************************/
int Seek_num()
{
int iArrA[N][M], iArrB[N];
bool bEq = true;
int iS,iK;
for (int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
cout << "a[" << i << "][" << j << "] = ";
cin >> iArrA[i][j];
}
}
for (int i=0;i<N;i++)
{
iArrB[i] = 0;
}
for (int i=0;i<N;i++)
{
bEq = bEq && iArrA[0][iArrB[0]] == iArrA[i][iArrB[i]];
}
while(!bEq)
{
iS=iK=0;
while(iK!=N-1)
{
iK++;
if(iArrA[iK][iArrB[iK]]<iArrA[iS][iArrB[iS]])
{
iS=iK;
}
}
iArrB[iS] += 1;
for (int i=0;i<N;i++)
{
bEq = iArrA[0][iArrB[0]]== iArrA[i][iArrB[i]];
}
}
return iArrA[0][iArrB[0]];
}
/*=============[End Laba 2]=================*/
/*=============[Laba 3]=====================*/
/****************************************************************\
METHOD........: CAmount
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iK - length of amount
RETURNS.......: None
\****************************************************************/
CAmount::CAmount(int iK)
{
m_iK = iK;
m_bBool = false;
}
/****************************************************************\
METHOD........: length
DESCRIPTION...: Check whether the data set are appropriate length
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - data
RETURNS.......:Int
\****************************************************************/
int CAmount::Length(int iN)
{
int i;
for (i=0,iN *= 10;iN/=10;i++);
if (i==m_iK) return 0;
else
if (m_iK<i) return 1;
}
/****************************************************************\
METHOD........: Generate
DESCRIPTION...: Generates a list of numbers corresponding length in which the i-th member
does not exceed i
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: int
\****************************************************************/
int CAmount::Generate()
{
int iN, iTemp,iInx;
int* piArr;
piArr = new int[m_iK];
bool bBool = false;
for(int j=1;j<2147483647;j++)
{
iTemp = j;
switch (Length(iTemp))
{
case 0:
iInx=m_iK;
iN = m_iK-1;
iTemp *= 10;
do
{
iTemp /= 10;
piArr[iN] = iTemp%10;
if (iN+1==iInx && piArr[iN]<=iInx)
{
bBool=true;
}
else
{
bBool = false;
break;
}
iN--;
iInx--;
}while(iTemp/10);
break;
case 1:
return 0;
}
if(bBool)
{
for (int i=0;i<m_iK;i++)
{
cout << piArr[i];
}
cout << endl;
bBool = false;
}
}
}
/****************************************************************\
METHOD........: length
DESCRIPTION...: Check whether the data set are appropriate length
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - data
iK - length of data
RETURNS.......:Int
\****************************************************************/
int Length(int iN, int iK)
{
int i;
for (i=0,iN *= 10;iN/=10;i++);
if (i==iK) return 0;
else
if (iK<i) return 1;
}
/****************************************************************\
FUNCTION......: Generate
DESCRIPTION...: Generates a list of numbers corresponding length in which the i-th member
does not exceed i
ATTRIBUTES....: Public
ARGUMENTS.....:
iK - length of data
RETURNS.......: int
\****************************************************************/
int Generate(int iK)
{
int iN, iTemp,iInx;
int* piArr;
piArr = new int[iK];
bool bBool = false;
for(int j=1;j<2147483647;j++)
{
iTemp = j;
switch (Length(iTemp,iK))
{
case 0:
iInx=iK;
iN = iK-1;
iTemp *= 10;
do
{
iTemp /= 10;
piArr[iN] = iTemp%10;
if (iN+1==iInx && piArr[iN]<=iInx)
{
bBool=true;
}
else
{
bBool = false;
break;
}
iN--;
iInx--;
}while(iTemp/10);
break;
case 1:
return 0;
}
if(bBool)
{
for (int i=0;i<iK;i++)
{
cout << piArr[i];
}
cout << endl;
bBool = false;
}
}
}
/*=============[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........: 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();
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 << "Всього " << m_iCount << " розташувань" << 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]=================*/
/*=============[Laba 5]=====================*/
/****************************************************************\
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 Laba 5]=================*/
/** (END OF FILE : main.cpp)*********************************/
/****************************************************************\
FILE..........: main.h
AUTHOR........: Toma Gres
DESCRIPTION...: The header file contains programming_labs.
METHOD........: Add, Seek, Length, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking, Print_Count,Sort
FUNCTIONS.....: Add, Seek_num, Length, Generate, Create_arr, show_arr, mod_arr, Exit, Backtracking, Sort
SWITCHES......: WIN32 - if defined, 32-bit version is
compiled, otherwise 16-bit edition is compiled.
COPYRIGHT.....: Copyright (c) 2010.
HISTORY.......: DATE COMMENT
-------- --------------------------------------
-
03-29-10 Created - Toma
04-02-10 Modified - Toma
\****************************************************************/
/****************************************************************\
CLASS.......: CAdd.
DESCRIPTION…: Add 2 numbers.
\****************************************************************/
class CAdd
{
private:
int m_iA, m_iB;
public:
CAdd(int iA, int iB);
int Add();
};
int Add (int a, int b);
/****************************************************************\
CLASS…......: CSeek.
DESCRIPTION…: Find an identical character in different areas
\****************************************************************/
class CSeek
{
private:
int** m_iArrA;
int* m_iArrB;
int m_iS;
int m_iK;
bool m_bEq;
public:
CSeek();
int Seek();
};
06.03.2013 23:53
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора