EDA/Picos.cpp at master · pablma/EDA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>


//FUNCIONES
void divide_vector(std::vector<int>& v, int& pico, int ini, int fin, bool& encontrado);
void es_pico(std::vector<int>& v, int& pico, int ini, int mid, int fin, bool& encontrado);


int main()
{
	int pico = 0;
	std::vector<int> vec;
	int tam;
	bool encontrado = false;

	std::cin >> tam;
	for (int i = 0; i < tam; i++)
	{
		int n;
		std::cin >> n;
		vec.push_back(n);
	}

	divide_vector(vec, pico, 0, vec.size(), encontrado);

	std::cout << "Pico: " << pico << std::endl;

	system("pause");
	return 0;
}


//El coste de esta función es O(logn) siendo n el número de elementos desde ini hasta fin
void divide_vector(std::vector<int>& v, int& pico, int ini, int fin, bool& encontrado)
{
	if (ini < fin - 2)
	{
		int mid = (ini + fin) / 2;
		divide_vector(v, pico, ini, mid, encontrado);
		divide_vector(v, pico, mid, fin, encontrado);
		if(!encontrado)
			es_pico(v, pico, ini, mid, fin, encontrado);
	}
	else if (v.size() == 1)
		pico = v[0];
}


//El coste de esta función es O(1)
void es_pico(std::vector<int>& v, int& pico, int ini, int mid, int fin, bool& encontrado)
{

	if (mid < v.size())
	{
		if (v[mid - 1] >= v[mid])
		{
			pico = v[mid - 1];
			//Solución inmediata (extremo izqdo)
			if (mid - 1 == 0)
				encontrado = true;
		}
		else
		{
			pico = v[mid];
			//Solución inmediata (extremo dcho)
			if (mid == v.size() - 1)
				encontrado = true;
		}
	}
}


//void es_pico(std::vector<int>& v, int& pico, int ini, int mid, int fin, bool& encontrado)
//{
//	if (v[mid] >= v[mid - 1])
//	{
//		if (v[mid] >= v[mid + 1])
//			pico = v[mid];
//		else
//			pico = v[mid + 1];
//	}
//	else
//		pico = v[mid - 1];
//
//	if ((mid - 1) == 0 || (mid + 1) == v.size())
//		encontrado = true;
//
//}