Перейти до вмісту

Гарна демонстраційна програма на С++


Повідомлень в темі: 4

#1 GENTOR

    Постійний житель

  • На перевірці
  • PipPipPipPipPip
  • 153 повідомлень
  • Місто:Київська область

Відправлено 05.01.2007 – 02:54

  • 4
Програма написана на С++


Будемо фантазерами: маємо гарне широке поле, але не просте, а казкова двохвимірна матриця! Ось таке чудове поле! А на ньому ростуть - одинички! Так от: якийсь фермер (дядько програмер наприклад) сіяв одинички. Але сіяв з закритими очима і не у всі комірочки потрпили одинички! Уявіть собі таке горе! :D Що ж дядько програмер був лидачий і не хотів виправляти своїх помилок, але ми ж не такі. Ми знайдемо найбільшу прямокутну ділянку, куди потрібно досіяти наші одинички!
Суть проста: написати програму, яка випадково заповняє матрицю одиницями і нулями, а потім знаходе найбільшу прямокутну ділянку нулів.
Я дядько щедрий :D тому за даром поділюся з усіма результатом своєї(!) інтелектуальної праці. Програма з усим фаршом, навіть малює поле в окремий txt файл.

Якщо хтось може надати простіший алгоритм або, можливо, красивіший варіант програми з тими ж функціями, будь-ласка повідомте :cool2:

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <fstream.h>

ofstream F("Field.txt");

const int width=100;
const int length=100;

int vegetables=0; //Total vegetables

int field[width][length];
void growing(); //This function initialize and fills the field
int cells(int arr[][length]);//This one shows how many empty sells
int check(int arr[][length]);

int main()
{
cout<<"_____________________________Field___________________________"<<endl;
F<<"________________________________Field___________________________"<<endl;
growing();
cout<<endl;
cout<<"The area of our field is "<<(length*width)<<"."<<endl;
F<<endl;
F<<"The area of our field is "<<(length*width)<<"."<<endl;
cout<<"Empty cells: "<<cells(field)<<"."<<endl;
F<<"Empty cells: "<<cells(field)<<"."<<endl;
cout<<"The biggest area is "<<check(field)<<"."<<endl;
F<<"The biggest area is "<<check(field)<<"."<<endl;
cout<<"Good by..."<<endl;
F<<"Good by..."<<endl;
return 0;
}
void growing()
{
int limit;
time_t t;
srand((unsigned) time(&t));
//Initialization
for(int i=0;i<=width;i++)
{
for(int j=0;j<=length;j++)
{
limit=rand()%2;
field[i][j]=limit;
}
}
//Field display
for(i=0;i<=width;i++)
{
cout<<"| ";
F<<"| ";
for(int j=0;j<=length;j++)
{
cout<<field[i][j]<<' ';
F<<field[i][j]<<' ';
}
cout<<"|"<<endl;
F<<"|"<<endl;
}
cout<<"-";
F<<"-";
for(i=0;i<=width;i++)
{
cout<<"---";
F<<"---";
}
}

int cells(int arr[][length])
{
int a=0;
for(int i=0;i<=width;i++)
{
for(int j=0;j<=length;j++)
{
if(arr[i][j]==0)
{
a++;
}
}
}
return a;
}

int check(int arr[][length])
{
int n,p,Scur;
int Smax=0;
int l=0;
int h=0;
int lp=31;
for(int i=0; i<=width; i++)
{
for(int j=0; j<length; j++)
{
if(arr[i][j]==0)
{
n=i;
p=j;
do
{
h++;n++;
while((arr[n-1][p]==0) && (p<=length))
{
l++;p++;
} p=j;

if(lp>=l)
{
lp=l;
}
l=0;

Scur=lp*h;
if((lp==1) || (h==1));
else
if(Scur>Smax)
{
Smax=Scur;
}
}while((arr[n][j]==0) && (n<=width));
h=0;
lp=length+1;
}
}
}
return Smax;
}

#2 Xobb

    Doctor What'son

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 1481 повідомлень
  • Стать:Чоловік

Відправлено 05.01.2007 – 03:07

GENTOR
а користуватися [ code ] [ /code ] релігія не позволяє?

В свою чергу тривіальна задачка про коняку. Є шахматна дошка розміру 8х8. Потрібно обійти коньом всю шахматну дошку не наступаючи двічі на одну клітинку. Вот, задача ясна, тому приступимо до реалізації. Є два виходи: евристика і перебор (я назвав цей метод в лоб через жопу).

метод перебору. Якщо повезе, то програма рахуватиметься відносно недовго. В залежності від початкової клітинки. Нажаль ця програма "плужить" на 28 ході, якщо починати з клітинки A1. Красіво зроблена рекурсія, ручная работа.
//---------------------------------------------------------------------------
#pragma hdrstop
#pragma argsused
//---------------------------------------------------------------------------
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
//---------------------------------------------------------------------------
int cb[8][8];
void printArray( int A[8][8]);
void horse( int x, int y, int n );

int main(int argc, char* argv[])
{
	int X, Y, y_temp;
	char x_temp[1];
	cout << "Knight v.1 (algorithm \"trudnyj\")" << endl;
	cout << "Please enter the start position of the horse: " << endl;
	cout << "X [1;8]: ";
	cin >> X;
	cout << endl;
	cout << "Y [1;8]: ";
	cin  >> Y;
	cout << endl << "Thanks. :) Already counting;)" << endl;

	horse(X - 1, Y - 1, 1);
	printArray(cb);

	getch();
	return 0;
}

void horse( int x, int y, int n )
//bool horse( int x, int y, int n )
{
	static int i;
	if ( n == 64 ) {
		//wheather board is filled the function exits
		printArray(cb);
		return;
	}
	// inserting the step num.
	cb[x][y] = n;

// debug
	cout << "Step no. " << n << " | Iteration: " << i << endl;
	printArray(cb);
	i++;
// steps start here
	// probable step 1: up right 1
	if ( x < 7 && y > 1 && cb[x+1][y-2] == 0) {
		horse(x+1, y-2, n+1);
	}
	// probable step 2:  down right 1
	if ( x < 7 && y < 6 && cb[x+1][y+2] == 0) {
		horse(x+1, y+2, n+1);
	}
	// probable step 3:  right down 2
	if ( x < 6 && y < 7 && cb[x+2][y+1] == 0) {
		horse(x+2, y+1, n+1);
	}
	// probable step 4:  left down 2
	if ( x > 1 && y < 7 && cb[x-2][y+1] == 0) {
		horse(x-2, y+1, n+1);
	}
	// probable step 5:  left down 1
	if ( x > 0 && y < 6 && cb[x-1][y+2] == 0) {
		horse(x-1, y+2, n+1);
	}
	// probable step 6:  left up 1
	if ( x > 0 && y > 1 && cb[x-1][y-2] == 0) {
		horse(x-1, y-2, n+1);
	}
	// probable step 7:  left up 2
	if ( x > 1 && y > 0 && cb[x-2][y-1] == 0) {
		horse(x-2, y-1, n+1);
	}
	// probable step 8:  right up 2
	if ( x < 6 && y > 0 && cb[x+2][y-1] == 0) {
		horse(x+2, y-1, n+1);
	}
// steps end here
	cb[x][y] = 0;
}

void printArray( int A[8][8])
{
	char delimiter[25] = "-------------------------";
	cout << "Chess board with steps highlighted:" << endl << delimiter << endl;
	for(int i=0; i<8; i++) {
		for(int j=0; j<8; j++) {
			printf("|%02d", A[i][j]);
		}
		cout << "|" << endl << delimiter << endl;
	}
	getch();
}
//---------------------------------------------------------------------------


Евристика ше цікавіше. Є правило якогось німця спєцом для цієї задачі (забув прізвище німця), яка говорить, що потрібно ходити в ту клітинку, з якої найменше є доступних наступних ходів, а якщо є дві клітинки з однаковою кількістю наступних доступних ходів, то немає різниці як ходити. Вот евристичним правилом і скористалися. лістінг знизу:
//---------------------------------------------------------------------------
#pragma hdrstop
#pragma argsused
//---------------------------------------------------------------------------
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#define M 8

int numberNewOfSteps(int x, int y, int A[M][M]);
void printArray(int A[M][M]);
int offset[8][2];
int main()
{
	int A[M][M];
	int steps[8];
	int x, y, count=1, idx=0;
	offset[0][0]= 2; offset[0][1]= 1;
	offset[1][0]= 2; offset[1][1]=-1;
	offset[2][0]= 1; offset[2][1]= 2;
	offset[3][0]= 1; offset[3][1]=-2;
	offset[4][0]=-1; offset[4][1]= 2;
	offset[5][0]=-1; offset[5][1]=-2;
	offset[6][0]=-2; offset[6][1]= 1;
	offset[7][0]=-2; offset[7][1]=-1;

	cout << "Knight step v.2 (algorithm bystryj)" << endl;
	cout << "Please enter the start position of the knight: " << endl;
	cout << "X [1;8]: ";
	cin >> x;
	cout << endl;
	cout << "Y [1;8]: ";
	cin  >> y;
	cout << endl << "Thanks. :) Already counting;)" << endl;

	x = x -1; y = y -1;

	for(int i=0;i<M;i++) {
		for(int j=0;j<M;j++) {
			A[i][j]=0;
		}
	}
	A[x][y]=count;

	do {
		for(int k=0; k<8; k++) {
			steps[k]=numberNewOfSteps(x+offset[k][0], y+offset[k][1], A);
		}
		for(int k=0; k<8; k++) {
			if(steps[k]>0) {
				idx = k;
				break;
			}
			if(k==7) {
				for(int i=0; i<8; i++) {
					if(steps[i]==0) {
						A[x+offset[i][0]][y+offset[i][1]]=++count;
					}
				}
				printArray(A);
				return 0;
			}
		}
		for(int k=0; k<8; k++) {
			if(steps[k]<steps[idx] && steps[k]>0) {
				idx = k;
			}
		}

		x += offset[idx][0];
		y += offset[idx][1];
		A[x][y]=++count;

	} while(true);
	return 0;
}
int numberNewOfSteps(int x, int y, int A[M][M])
{
	if((x<0 || x>=M || y<0 || y>=M || A[x][y]!=0)) {
		return -1;
	}
	int count=0;
	for(int k=0; k<8; k++) {
		int xn=x+offset[k][0];
		int yn=y+offset[k][1];
		if(xn>=0 && xn<M && yn>=0 && yn<M && A[xn][yn]==0) {
			count++;
		}
	}

	return count;
}
void printArray(int A[M][M])
{
	char delimiter[25] = "-------------------------";
	cout << "Chess board with steps highlighted:" << endl << delimiter << endl;
	for(int i=0;i<M;i++) {
		for(int j=0;j<M;j++) {
			printf("|%02d", A[i][j]);
		}
		cout << "|" << endl << delimiter << endl;
	}
	cout << "Hit Enter to exit.";
	getch();
}


//---------------------------------------------------------------------------

  • 0

#3 Evol

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 1846 повідомлень
  • Стать:Чоловік

Відправлено 05.01.2007 – 03:12

і чим сіє диво компілюєш?
  • 0

#4 Xobb

    Doctor What'son

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 1481 повідомлень
  • Стать:Чоловік

Відправлено 05.01.2007 – 11:59

Evol
трубо Ци плюз плюз.Я не Ци пишу, на Ци тільки приколююсь, птаму ні сільон в тому яка різниця між віжуаль ци і дапустім бульдіром бордельоуським.
  • 0

#5 GENTOR

    Постійний житель

  • На перевірці
  • PipPipPipPipPip
  • 153 повідомлень
  • Місто:Київська область

Відправлено 06.01.2007 – 00:24

Дякую за пораду з
 
і розумні алгоритми розв'язання цікавих задач! :) Ну блін, не знав, що поробиш ;)
  • 0



Кількість користувачів, що читають цю тему: 1

0 користувачів, 1 гостей, 0 анонімних