Zadaci

evo jedan simpicantan vezan za dvodimenzionalne nizove koji su mi momci iz elitesecuritija zadali i tad nisam znao resiti, valjda bih sad znao, evo:

Prema navodima Nedeljka iz elitesec foruma ovo su resavala deca osmog razreda :lol:

Kod:
Zid veličine 2mx2m popločan je keramičkim crnim i belim keramičkim pločicama veličine 10cmx10cm. Crne pločice su susedne ako se dodiruju jednom ivicom. Crne pločice A i B su povezane ako postoji niz crnih pločica koji počinje sa A, završava se sa B i svake dve crne pločice koje su susedne u tom nizu su susedne i na zidu. Sve međusobno povezane crne pločice čine jednu figuru. Većom figurom smatramo figuru veće površine.

 U ulaznoj datoteci je dato dvadeset redova od po 20 nula i jedinica, pri čemu 0 predstavlja belu, a 1 crnu pločicu. Odrediti površinu u dm2 najveće figure.
 
evo jedan simpicantan vezan za dvodimenzionalne nizove koji su mi momci iz elitesecuritija zadali i tad nisam znao resiti, valjda bih sad znao, evo:

Prema navodima Nedeljka iz elitesec foruma ovo su resavala deca osmog razreda :lol:

Kod:
Zid veličine 2mx2m popločan je keramičkim crnim i belim keramičkim pločicama veličine 10cmx10cm. Crne pločice su susedne ako se dodiruju jednom ivicom. Crne pločice A i B su povezane ako postoji niz crnih pločica koji počinje sa A, završava se sa B i svake dve crne pločice koje su susedne u tom nizu su susedne i na zidu. Sve međusobno povezane crne pločice čine jednu figuru. Većom figurom smatramo figuru veće površine.

 U ulaznoj datoteci je dato dvadeset redova od po 20 nula i jedinica, pri čemu 0 predstavlja belu, a 1 crnu pločicu. Odrediti površinu u dm2 najveće figure.

Nije savrseno, ali posto si rekao da nisi skontao rekurziju, moze da ti posluzi
Kod:
#include <iostream>
#include <cstdlib>
#define WHITE 0 // Konstanta za bijelo polje
#define BLACK 1 // Logicno

using namespace std;

const int field_size = 4;	// Velicina polja, po zadatku 20, ali koristimo manju zbog lakseg unosa
int field[field_size][field_size];	// Zapravo matrica plocica
int maxCount = 0;	// Rezultat, povrsina najvece figure

// indeks, indeks, povrsina posmatrane figure
void findMaxBlack(int i, int j, int &size){
	// Ukoliko indeksi nisu u okviru dimenzija niza ili ako su manji od 0, te ako je posmatrano polje bijele boje, cao
	if (i < 0 || i >= field_size || j < 0 || j >= field_size || field[i][j] == WHITE) return;
	if (field[i][j] == BLACK){
		// Oznaci trenutno polje kao bijelo, da ga ne bi prelazili vise puta
		field[i][j] = WHITE;
		// Povecavam povrsinu trenutne figure
		size++;
	}
	findMaxBlack(i+1, j, size);	// Dole
	findMaxBlack(i-1, j, size);	// Gore
	findMaxBlack(i, j+1, size);	// Desno
	findMaxBlack(i, j-1, size);	// Lijevo
}

int main(){

	// Boilerplate, ulaz		
	for(int i=0;i<field_size;i++)
		for(int j=0;j<field_size;j++)
			cin >> field[i][j];

	for(int i=0;i<field_size;i++)
		for(int j=0;j<field_size;j++)
			if (field[i][j] == BLACK){	// Ako je polje crne boje, znaci da pocinje figura
				int size = 0;	// Pocetak mjerenja povrsine nove figure, njena velicina je 0
				findMaxBlack(i, j, size);	// Rekurzivno izracunavanje povrsine figure
				if (size > maxCount) maxCount = size;	// Ako je figura do sada maksimalna, sacuvaj njenu povrsinu
			}

	// Izlaz
	cout << "Najveca figura ima povrsinu : " << maxCount << endl;
	return 0;
}
 
Nije savrseno, ali posto si rekao da nisi skontao rekurziju, moze da ti posluzi
Kod:
#include <iostream>
#include <cstdlib>
#define WHITE 0 // Konstanta za bijelo polje
#define BLACK 1 // Logicno

using namespace std;

const int field_size = 4;	// Velicina polja, po zadatku 20, ali koristimo manju zbog lakseg unosa
int field[field_size][field_size];	// Zapravo matrica plocica
int maxCount = 0;	// Rezultat, povrsina najvece figure

// indeks, indeks, povrsina posmatrane figure
void findMaxBlack(int i, int j, int &size){
	// Ukoliko indeksi nisu u okviru dimenzija niza ili ako su manji od 0, te ako je posmatrano polje bijele boje, cao
	if (i < 0 || i >= field_size || j < 0 || j >= field_size || field[i][j] == WHITE) return;
	if (field[i][j] == BLACK){
		// Oznaci trenutno polje kao bijelo, da ga ne bi prelazili vise puta
		field[i][j] = WHITE;
		// Povecavam povrsinu trenutne figure
		size++;
	}
	findMaxBlack(i+1, j, size);	// Dole
	findMaxBlack(i-1, j, size);	// Gore
	findMaxBlack(i, j+1, size);	// Desno
	findMaxBlack(i, j-1, size);	// Lijevo
}

int main(){

	// Boilerplate, ulaz		
	for(int i=0;i<field_size;i++)
		for(int j=0;j<field_size;j++)
			cin >> field[i][j];

	for(int i=0;i<field_size;i++)
		for(int j=0;j<field_size;j++)
			if (field[i][j] == BLACK){	// Ako je polje crne boje, znaci da pocinje figura
				int size = 0;	// Pocetak mjerenja povrsine nove figure, njena velicina je 0
				findMaxBlack(i, j, size);	// Rekurzivno izracunavanje povrsine figure
				if (size > maxCount) maxCount = size;	// Ako je figura do sada maksimalna, sacuvaj njenu povrsinu
			}

	// Izlaz
	cout << "Najveca figura ima povrsinu : " << maxCount << endl;
	return 0;
}

Ma tad rekurziju nisam znao, bra'o. :)

Aj' kad si tu da mi malo docaras ovu malloc() funkciju u C jeziku, pazi kapiram ja da to sluzi za alokaciju odnosno raspodelu memorije, ali kada bi to trebalo koristiti? Meni je nekako logicno da to koristim kad dodje do zasicenja mem lokacie, ali sad nisam siguran, sva objasnjenja su tako konfuzna da to nije zdravo. :lol:
 
Npr. stavis

Kod:
char *nekistr = "Bla bla bla";

Ovaj string je sada konstantan i ne mozes ga mijenjati, znaci da
Kod:
nekistr[2] = 'n';
nece raditi.
Ali zato

Kod:
char *nekistr = (char*)malloc(MAX_BROJ_KARAKTERA * sizeof(char));
nekistr[2] = 'N';

ce raditi.

Ja ne koristim mnogo malloc i C-style alokaciju memorije, a kada je to slucaj malloc koristim za gore navedene stvari i za nizove.Ali opet kazem, rijetko to koristim.
 
Npr. stavis

Kod:
char *nekistr = "Bla bla bla";

Ovaj string je sada konstantan i ne mozes ga mijenjati, znaci da
Kod:
nekistr[2] = 'n';
nece raditi.
Ali zato

Kod:
char *nekistr = (char*)malloc(MAX_BROJ_KARAKTERA * sizeof(char));
nekistr[2] = 'N';

ce raditi.

Ja ne koristim mnogo malloc i C-style alokaciju memorije, a kada je to slucaj malloc koristim za gore navedene stvari i za nizove.Ali opet kazem, rijetko to koristim.

aha, e hvala ti, bas si jasno objasnio :)
 
Не волим задатке у којима су I/O и одржавање већи од решења... пошто сам узео за малу вежбу да решим, ево кода.

Kod:
#include <iostream>
#include <vector>
using namespace std;

class MaxArea;

class Field {
  friend class MaxArea;
private:
  Field(int value, bool visited):
    value(value), visited(visited)
  {}

  int value;
  bool visited;
};

class MaxArea {
private:
  vector<vector<Field*>* > data;
public:
  MaxArea() {
  }
  
  ~MaxArea();
  
  void Load(istream&);
  int Solve();
private:
  int Solve(int, int);
  void Clear();
};

int main()
{
  MaxArea problem;
  problem.Load(cin);
  int value = problem.Solve();
  
  cout << value << endl;
  
  return 0;
}

void MaxArea::Load(istream& in) {
  Clear();
  int rows;
  int cols;
  in >> rows;
  cols = rows;
  for(int row=0; row < rows; row++) {
    vector<Field*>* rowvec = new vector<Field*>();
    for(int col = 0; col < cols; col++) {
      int val;
      in >> val;
      rowvec->push_back(new Field(val, false));
    }
    data.push_back(rowvec);
  }
}

MaxArea::~MaxArea() {
  Clear();
}

void MaxArea::Clear() {
  for(unsigned int i=0; i<data.size(); i++) {
    for(unsigned int j=0; j<data[i]->size(); j++) {
      delete (*data[i])[j];
    }
    delete data[i];
  }
}

#define val(I,J) ((*data[I])[J]->value)
#define vis(I,J) ((*data[I])[J]->visited)
int MaxArea::Solve(int row, int col) {
  if(  row < 0
    || col < 0
    || row >= data.size()
    || col >= data[row]->size()
    || vis(row, col)
    || val(row, col) == 0
  ) {
    return 0;
  }
  vis(row,col) = true;
  int result = 1;
  result += Solve(row - 1, col);
  result += Solve(row + 1, col);
  result += Solve(row, col - 1);
  result += Solve(row, col + 1);
  return result;
}

int MaxArea::Solve() {
  int area = 0;
  for(unsigned int i=0; i<data.size(); i++) {
    for(unsigned int j=0; j<data[i]->size(); j++) {
      if(!vis(i, j)) {
        int newarea = Solve(i, j);
        if(newarea > area) {
          area = newarea;
        }
      }
    }
  }
  return area;
}
#undef val
#undef vis
 
Не волим задатке у којима су I/O и одржавање већи од решења... пошто сам узео за малу вежбу да решим, ево кода.

Kod:
#include <iostream>
#include <vector>
using namespace std;

class MaxArea;

class Field {
  friend class MaxArea;
private:
  Field(int value, bool visited):
    value(value), visited(visited)
  {}

  int value;
  bool visited;
};

class MaxArea {
private:
  vector<vector<Field*>* > data;
public:
  MaxArea() {
  }
  
  ~MaxArea();
  
  void Load(istream&);
  int Solve();
private:
  int Solve(int, int);
  void Clear();
};

int main()
{
  MaxArea problem;
  problem.Load(cin);
  int value = problem.Solve();
  
  cout << value << endl;
  
  return 0;
}

void MaxArea::Load(istream& in) {
  Clear();
  int rows;
  int cols;
  in >> rows;
  cols = rows;
  for(int row=0; row < rows; row++) {
    vector<Field*>* rowvec = new vector<Field*>();
    for(int col = 0; col < cols; col++) {
      int val;
      in >> val;
      rowvec->push_back(new Field(val, false));
    }
    data.push_back(rowvec);
  }
}

MaxArea::~MaxArea() {
  Clear();
}

void MaxArea::Clear() {
  for(unsigned int i=0; i<data.size(); i++) {
    for(unsigned int j=0; j<data[i]->size(); j++) {
      delete (*data[i])[j];
    }
    delete data[i];
  }
}

#define val(I,J) ((*data[I])[J]->value)
#define vis(I,J) ((*data[I])[J]->visited)
int MaxArea::Solve(int row, int col) {
  if(  row < 0
    || col < 0
    || row >= data.size()
    || col >= data[row]->size()
    || vis(row, col)
    || val(row, col) == 0
  ) {
    return 0;
  }
  vis(row,col) = true;
  int result = 1;
  result += Solve(row - 1, col);
  result += Solve(row + 1, col);
  result += Solve(row, col - 1);
  result += Solve(row, col + 1);
  return result;
}

int MaxArea::Solve() {
  int area = 0;
  for(unsigned int i=0; i<data.size(); i++) {
    for(unsigned int j=0; j<data[i]->size(); j++) {
      if(!vis(i, j)) {
        int newarea = Solve(i, j);
        if(newarea > area) {
          area = newarea;
        }
      }
    }
  }
  return area;
}
#undef val
#undef vis


Bespotrebni overhed...zaista...takmicarski zadaci su za takmicenje, a tamo nemas vremena (a ni potrebe) da radis OOP (objektno orijentisano proseravanje).

Sto nisi preklopio operator >> za MaxArea.
Zapravo, ta klasa ne treba da se zove MaxArea nego Area, jer ne sadrzi samo maksimalnu figuru vec i neke druge figure i polja.

Al dobro, nemoj me shvatiti pogresno, nisam imao losih namjera. :D
 
Poslednja izmena:
Bespotrebni overhed...zaista...takmicarski zadaci su za takmicenje, a tamo nemas vremena (a ni potrebe) da radis OOP (objektno orijentisano proseravanje).
Лакше ми је да направим класу са свим елементима, па онда матрицу њених објеката, него да правим по матрицу за сваки параметар. Ти предлажеш уништавање улазног низа, што није нужно лоше али исто тако није ни чување. :) За потребе такмичења уништавање улаза овде није проблем. Назови чување улаза испољавањем навике. Овде сам такође ишао у смеру више тест-примера и динамички подешаване величине проблема, али ми личи да и мом коду треба дорада да би Load-Solve могао да се убаци у петљу.

Sto nisi preklopio operator >> za MaxArea.
Ствар стила.

Zapravo, ta klasa ne treba da se zove MaxArea nego Area, jer ne sadrzi samo maksimalnu figuru vec i neke druge figure i polja.
Класа се назива према проблему... проблем је наћи највећу површину. Има и методу Solve, која не описује нешто карактеристично за било коју површину па не бих оправдао идеју за везивање имена за површину...
 
Ево једног.

Дати су низови целих бројева, који описују дискретизоване вертикалне пресеке терена. Због дискретизованости, пресеци изгледају као низови степеника. Међу тим степеницима могу да се уоче "језера", која су са обе стране оивичена са по два степеника, између којих се налазе нижи степеници. Задатак је написати функцију/методу која као аргумент(е) прима по један такав низ (и податак о његовој дужини), и израчунава површину пресека "језера" на њему. Нпр.:

C/C++-функција:
Kod:
int solve(int* arr, int len)

Јава-метода:
Kod:
public int solve(int[] arr)

Примери:
Улаз: 1, 2, 3, 4, 5, 4, 5, 4, 3, 2, 1
Резултат: 1

Улаз: 100 0 0 0 0 100
Резултат: 400

Улаз: 1, 2, 4, 2, 1, -5, 6, 2, 2, 3
Резултат: 16
 
Poslednja izmena:
Ево једног.

Дати су низови целих бројева, који описују дискретизоване вертикалне пресеке терена. Због дискретизованости, пресеци изгледају као низови степеника. Међу тим степеницима могу да се уоче "језера", која су са обе стране оивичена са по два степеника, између којих се налазе нижи степеници. Задатак је написати функцију/методу која као аргумент(е) прима по један такав низ (и податак о његовој дужини), и израчунава површину пресека "језера" на њему. Нпр.:

C/C++-функција:
Kod:
int solve(int* arr, int len)

Јава-метода:
Kod:
public int solve(int[] arr)

Примери:
Улаз: 1, 2, 3, 4, 5, 4, 5, 4, 3, 2, 1
Резултат: 1

Улаз: 100 0 0 0 0 100
Резултат: 400

Улаз: 1, 2, 4, 2, 1, -5, 6, 2, 2, 3
Резултат: 16

Cek ne kapiram ova "jezera", sta se misli pod "jezera"? O.o
 
Јеси ли пробао да нацрташ "вертикални пресек терена" представљен низом целих бројева? Ако гравитација вуче визуелно надоле, то већ говори где би се у том пресеку могла акумулирати вода. Из једног горњег примера....

1, 2, 4, 2, 1, -5, 6, 2, 2, 3
Kod:
      *
      *
  *   *
  *   *  *
 ***  ****
***** ****
***** ****
***** ****
***** ****
***** ****
***** ****
**********
Када се пресек испуни водом...
Kod:
      *
      *
  *---*
  *---*--*
 ***--****
*****-****
*****-****
*****-****
*****-****
*****-****
*****-****
**********
Поља за воду има 16.
 
Poslednja izmena:
Док чекамо да се неко јави на тај задатак, имам и следећи. Овако нешто бих можда дао на интервјуу. Требало би да је тривијалан за све који су радили са рачунарском графиком, али шта знам... :)

Дат је објекат геометријске фигуре, који садржи њене дужи. Транслација фигуре за вектор v је реализована тако што се итерира по дужима и за сваку дуж се обе њене тачке транслирају за вектор v, који није нула-вектор. Но, након обављене трансформације фигура није била транслирана за вектор v у границама разумних толеранција. Шта може бити грешка?
 
Док чекамо да се неко јави на тај задатак, имам и следећи. Овако нешто бих можда дао на интервјуу. Требало би да је тривијалан за све који су радили са рачунарском графиком, али шта знам... :)

Дат је објекат геометријске фигуре, који садржи њене дужи. Транслација фигуре за вектор v је реализована тако што се итерира по дужима и за сваку дуж се обе њене тачке транслирају за вектор v, који није нула-вектор. Но, након обављене трансформације фигура није била транслирана за вектор v у границама разумних толеранција. Шта може бити грешка?

matiš :zima: 6 godina ja matematike video nisam rode moj, šta ti znači tanslacija?

Ovaj gore sam radio u C i nisam znao neke f-je u C i batalio sam, probaću sutra u C#, verujem da rekurzija dosta pomaže za ovaj gore?
 
Poslednja izmena:
Јеси ли пробао да нацрташ "вертикални пресек терена" представљен низом целих бројева? Ако гравитација вуче визуелно надоле, то већ говори где би се у том пресеку могла акумулирати вода. Из једног горњег примера....

1, 2, 4, 2, 1, -5, 6, 2, 2, 3
Kod:
      *
      *
  *   *
  *   *  *
 ***  ****
***** ****
***** ****
***** ****
***** ****
***** ****
***** ****
**********
Када се пресек испуни водом...
Kod:
      *
      *
  *---*
  *---*--*
 ***--****
*****-****
*****-****
*****-****
*****-****
*****-****
*****-****
**********
Поља за воду има 16.

Možda nešto ovako:
Kod:
<?php 
$arr = array(1, 2, 4, 2, 1, -5, 6, 2, 2, 3);

function solve($arr) {
	$pikovi = array();
	$pik_max = null;
	$pik_flag = false;		
	$totalSum = 0;
	$sumBetweenPiks = 0;	
	$betweenPik = 0;
		
	for ($i = 0; $i < count($arr) - 1; $i++) {
		if (!$pik_flag && $arr[$i+1] < $arr[$i]) {	
			if (end($pikovi) != $arr[$i]) {
				array_push($pikovi, $arr[$i]);
				$pik_max = $arr[$i];				
			}																			
			$pik_flag = true;
		} else 
		if ($pik_flag && $arr[$i+1] > $arr[$i]) {			
			if (end($pikovi) != $arr[$i]){
				array_push($pikovi, $arr[$i+1]);
				$pik_max = $arr[$i+1];
			}				
			$pik_flag = false;
		}
		
		//pik find - start summing
		if ($pik_max != null) {
			$sumBetweenPiks += $pik_max - $arr[$i+1];
					
			$prev = end($pikovi);
			$prev = prev($pikovi);			
			if (($pik_max - $arr[$i+1]) == 0 && $prev > $pik_max) {				
				$sumBetweenPiks -= $betweenPik * ($prev - $pik_max);
			}			
			
			if (($pik_max - $arr[$i+1]) == 0) {
				$betweenPik = 0;
				$totalSum += $sumBetweenPiks;
				$sumBetweenPiks = 0;
			}
			else
				$betweenPik++;								
		}
												
	}
	//var_dump($pikovi);	
	echo "<br> total sum" . $totalSum;
}

solve($arr);

?>

Malo je robusno, al' izgleda da radi. :neutral:
 
Мож` и да објасниш шта ти је идеја. Видим да пуцаш на нерекурзивно решење, што је хај-шот.

Ideja je pronaći pikove, između kojih se nalaze jezera.
Kada se pronađe pik, počinje računanje veličine jezera.
Ako je pik od koga počinje jezero, veći od narednog, koji završava to jezero, oduzeti razliku, imajući u vidu da nivo vode ide do manjeg pika($betweenPik predstavlja dužinu jezera).
 
... Притом мораш бринути о томе да део којег си једном обрадио не обрађујеш опет односно да пре те бриге увек нађеш два "права" врха. :) Мени рекурзија ипак изгледа као "мајка" једноставности и поделе за решење које користи врхове. :) Има и других решења.

Иако не могу да се натерам да ти анализирам метод, изгледало ми је да би ово баш направило проблем као улаз:

1, 8, 2, 7, 2, 4, 2, 6, 2, 9, 1

И збиља, тражени резултат је 31, а види колико код тебе излази.
 
... Притом мораш бринути о томе да део којег си једном обрадио не обрађујеш опет односно да пре те бриге увек нађеш два "права" врха. :) Мени рекурзија ипак изгледа као "мајка" једноставности и поделе за решење које користи врхове. :) Има и других решења.

Иако не могу да се натерам да ти анализирам метод, изгледало ми је да би ово баш направило проблем као улаз:

1, 8, 2, 7, 2, 4, 2, 6, 2, 9, 1

И збиља, тражени резултат је 31, а види колико код тебе излази.

Pa da, problem je kada obradi jezero između dva pika, desi se kasnije da se pojavi pik veći od prethodnih i metod ne računa to što pliva iznad ranije obrađenog jezera i kasnijeg većeg pika.
 
Значи, треба наћи два највећа. Онда се срачуна све између њих. А онда се обради остатак на исти начин.

Рекурзијом, очас посла.
 
Значи, треба наћи два највећа. Онда се срачуна све између њих. А онда се обради остатак на исти начин.

Рекурзијом, очас посла.

Jest', a zamisli teren dugačak 100 kilometara, sa pikovima na svakih par milimetara, koliko bi očas posla bilo pronalaženje jezera rekurzijom? :)
 
Jest', a zamisli teren dugačak 100 kilometara, sa pikovima na svakih par milimetara, koliko bi očas posla bilo pronalaženje jezera rekurzijom? :)
Једино што у рекурзивном позиву кошта више је отварање простора за нови позив. Административни обим је исти.

Ја те наводим да напишеш рекурзију, па је размотај на итеративно ако ти се игра. :) Ако нећеш, можеш да прескочиш тај корак.

Али појави се са кодом који ради.
 
Једино што у рекурзивном позиву кошта више је отварање простора за нови позив. Административни обим је исти.

Ја те наводим да напишеш рекурзију, па је размотај на итеративно ако ти се игра. :) Ако нећеш, можеш да прескочиш тај корак.

Али појави се са кодом који ради.

Aj' postavi svoj primer sa rekurzijom, posto sam slab sa njom totalno?
 

Back
Top