1. Programación procedimental
1.1. Entrada y salida
1.2. Expresiones y condicionales
1.2.1. Índice de masa corporal
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106 import java.util.Scanner;
/**
* Calculate the body mass index and the nutritional category for a set of data
*/
class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Repetir mientras hayan datos
while ( this.input.hasNextDouble() )
{
// Leer la masa (en kilogramos)
final double mass = this.input.nextDouble();
// Leer la altura (en centimetros)
final double height = this.input.nextDouble();
// Si la masa y la altura son validos
// Si masa es positiva y menor o igual a 1000kg
// Si altura es positiva y menor o igual a 300cm
if ( (mass > 0 && mass <= 1000) && (height > 0 && height <= 300) )
{
// Crear bmi como masa entre la altura al cuadrado
// convirtiendo altura de centimetros a metros (bmi = peso / (altura/100)^2)
final double bmi = mass / ((height / 100) * (height / 100));
// Crear estado nutricional resultado de clasificar bmi
String state = null;// clasifyBmi(bmi);
if (bmi < 18.5)
state = "underweight";
else if (bmi < 25)
state = "normal";
else if (bmi < 30)
state = "overweight";
else
state = "obese";
// Imprimir masa, altura, bmi, estado nutricional
System.out.printf("%6.2f %6.2f %5.2f %s%n", mass, height, bmi, state);
}
else
{
// Imprimir "invalid data"
System.out.printf("%6.2f %6.2f invalid data%n", mass, height);
}
} // while
// Close the standard input
this.input.close();
}
// Clasificar bmi:
public String clasifyBmi(double bmi)
{
// Si bmi < 18.5
if ( bmi < 18.5 )
// Responder underweight
return "underweight";
// Si 18.5 ≤ bmi < 25
if ( bmi < 25 )
// Responder normal
return "normal";
// Si 25 ≤ bmi < 30
if ( bmi < 30 )
// Responder overweight
return "overweight";
// Si 30 ≤ bmi
// Responder obese
return "obese";
}
// Es masa valida:
// Si peso es positivo y menor o igual a 1000kg
// Responder peso es valido
// Sino
// Responder que el peso no es valido
// Es altura valida:
// Si altura es positiva y menor o igual a 300cm
// Responder que altura es valida
// Sino
// Responder que la altura no es valida
} // class Solution
1.2.2. Convertidor de temperatura
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 import java.util.Scanner;
/**
* Convert temperatures from Fahrenheit to Celsius
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Read all real values from standard input
while ( this.input.hasNextDouble() )
{
// Read the temperature in Fahrenheit degrees
final double fahrenheit = this.input.nextDouble();
// Convert to Celsius
final double celsius = 5.0 / 9.0 * (fahrenheit - 32.0);
if ( celsius >= -273.15 )
System.out.printf("%.2f%n", celsius);
else
System.out.printf("invalid temperature%n");
}
// Close the standard input
1.2.3. Años bisiestos
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 import java.util.Scanner;
/**
* Indicates whether given years are leap or not
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Mientras hayan años en la entrada estándar
while ( this.input.hasNextLong() )
{
// Leer el año
final long year = this.input.nextLong();
System.out.printf("%d: ", year);
// Si el año es divisible por 4 y no es divisible por 100, o es divisible por 400
// if ( year % 4 == 0 && year % 100 != 0 || year % 400 == 0 )
if ( year % 4 == 0 ^ year % 100 == 0 )
{
// Imprimir que es bisiesto
System.out.println("leap year");
}
else
{
if ( year % 400 == 0 )
System.out.println("leap year");
else
// Imprimir que NO es bisiesto
System.out.println("normal year");
}
}
// Close the standard input
1.3. Repetición: ciclos
1.4. Subrutinas
1.4.1. Combinaciones y permutaciones
Solución 1: artimética de precisión fija (desbordamiento)
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154 import java.util.Scanner;
/**
* Replace this JavaDoc comment for the purpose of this class
*/
public class CombPermOriginal
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
CombPermOriginal solution = new CombPermOriginal();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Read n
final long n = this.input.nextLong();
// Read r
final long r = this.input.nextLong();
printHeader();
printPermutations(n, r);
printCombinations(n, r);
// Close the standard input
this.input.close();
}
/**
* Print table header without repetition and with repetition
*/
public static void printHeader()
{
System.out.println(" No repetitions With repetitions");
}
/**
* Calculates and prints the permutations row of the table
*/
public static void printPermutations(final long n, final long r)
{
// Print text "Permutations"
System.out.print("Permutations ");
// Create permutations without repetition as the result of calculate permutations without repetition
final long permutationsWithoutRepetition = calculatePermutationsWithoutRepetition(n, r);
// Print permutations without repetition
System.out.printf("%20d ", permutationsWithoutRepetition);
// Create permutations with repetition as the result of calculate permutations with repetition
// Print permutations with repetition
System.out.printf("%20d%n", calculatePermutationsWithRepetition(n, r));
}
/**
* Calculate permutations without repetition
* @param n Size of the set of members to arrange. It must be greather than r.
* @param r Size of the arrangements (subsets) of n. It must be 0 or greater.
* @return The number of k-permutations of n without repetition, or zero if n or r are invalid.
*/
public static long calculatePermutationsWithoutRepetition(final long n, final long r)
{
// Return n! / (n - r)!
if ( n > r && r >= 0 )
return factorial(n) / factorial(n - r);
else
return 0;
}
public static long factorial(final long value)
{
// Create result as 1
long result = 1;
// Repeat current from 1 to n
for ( long current = 1; current <= value; ++current )
{
// Assign result as result * current
result *= current;
}
// Return result
return result;
}
// Calculate permutations with repetition:
public static long calculatePermutationsWithRepetition(final long n, final long r)
{
// Create result as 1
long result = 1;
// Repeat current from 1 to r
for ( long current = 1; current <= r; ++current )
{
// Assign result as result * n
result *= n;
}
// Return result
return result;
}
/**
* Calculates and prints the combinations row of the table
*/
public static void printCombinations(final long n, final long r) {
// Print text "Combinations"
System.out.print("Combinations ");
// Create combinations without repetition as the result of calculate
// combinations without repetition
final long combinationsWithoutRepetition = calculateCombinationsWithoutRepetition(n, r);
// Print combinations without repetition
System.out.printf("%20d ", combinationsWithoutRepetition);
// Create combinations with repetition as the result of calculate combinations
// with repetition
// Print combinations with repetition
System.out.printf("%20d%n", calculateCombinationsWithRepetition(n, r));
}
// Calculate combinations without repetition:
public static long calculateCombinationsWithoutRepetition(final long n, final long r)
{
// Return n! / ( r! * (n - r)! )
return factorial(n) / ( factorial(r) * factorial(n - r) );
}
// Calculate combinations with repetition:
public static long calculateCombinationsWithRepetition(final long n, final long r)
{
// Return (n + r - 1)! / ( r! * (n - 1)! )
return factorial(n + r - 1) / ( factorial(r) * factorial(n - 1) );
}
} // class
Solución 2: artimética de precisión fija optimizada
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173 import java.util.Scanner;
/**
* Replace this JavaDoc comment for the purpose of this class
*/
class CombPermOptimized
{
/**
* Gets data from standard input
*/
private Scanner input;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
CombPermOptimized solution = new CombPermOptimized();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Read n
final long n = this.input.nextLong();
// Read r
final long r = this.input.nextLong();
printHeader();
printPermutations(n, r);
printCombinations(n, r);
// Close the standard input
this.input.close();
}
/**
* Print table header without repetition and with repetition
*/
public static void printHeader()
{
System.out.println(" No repetitions With repetitions");
}
/**
* Calculates and prints the permutations row of the table
*/
public static void printPermutations(final long n, final long r)
{
// Print text "Permutations"
System.out.print("Permutations ");
// Create permutations without repetition as the result of calculate permutations without repetition
final long permutationsWithoutRepetition = calculatePermutationsWithoutRepetition(n, r);
// Print permutations without repetition
System.out.printf("%20d ", permutationsWithoutRepetition);
// Create permutations with repetition as the result of calculate permutations with repetition
// Print permutations with repetition
System.out.printf("%20d%n", calculatePermutationsWithRepetition(n, r));
}
/**
* Calculate permutations without repetition
* @param n Size of the set of members to arrange. It must be greather than r.
* @param r Size of the arrangements (subsets) of n. It must be 0 or greater.
* @return The number of k-permutations of n without repetition, or zero if n or r are invalid.
*/
public static long calculatePermutationsWithoutRepetition(final long n, final long r)
{
// Return n! / (n - r)!
if ( n > r && r >= 0 )
return factorialDivision(n, n - r);
else
return 0;
}
public static long factorialDivision(final long numerator, final long denominator)
{
if ( numerator >= denominator && denominator > 0 )
{
long result = 1;
for ( long current = numerator; current > denominator; --current )
result *= current;
return result;
}
else
return 0;
}
public static long factorial(final long value)
{
// Create result as 1
long result = 1;
// Repeat current from 1 to n
for ( long current = 1; current <= value; ++current )
{
// Assign result as result * current
result *= current;
}
// Return result
return result;
}
// Calculate permutations with repetition:
public static long calculatePermutationsWithRepetition(final long n, final long r)
{
// Create result as 1
long result = 1;
// Repeat current from 1 to r
for ( long current = 1; current <= r; ++current )
{
// Assign result as result * n
result *= n;
}
// Return result
return result;
}
/**
* Calculates and prints the combinations row of the table
*/
public static void printCombinations(final long n, final long r) {
// Print text "Combinations"
System.out.print("Combinations ");
// Create combinations without repetition as the result of calculate
// combinations without repetition
final long combinationsWithoutRepetition = calculateCombinationsWithoutRepetition(n, r);
// Print combinations without repetition
System.out.printf("%20d ", combinationsWithoutRepetition);
// Create combinations with repetition as the result of calculate combinations
// with repetition
// Print combinations with repetition
System.out.printf("%20d%n", calculateCombinationsWithRepetition(n, r));
}
// Calculate combinations without repetition:
public static long calculateCombinationsWithoutRepetition(final long n, final long r)
{
// Return n! / ( r! * (n - r)! )
final long min = Math.min(r, n - r);
final long max = Math.max(r, n - r);
return factorialDivision(n, max) / factorial(min);
}
// Calculate combinations with repetition:
public static long calculateCombinationsWithRepetition(final long n, final long r)
{
// Return (n + r - 1)! / ( r! * (n - 1)! )
final long min = Math.min(r, n - 1);
final long max = Math.max(r, n - 1);
return factorialDivision(n + r - 1, max) / factorial(min);
}
} // class
Solución 3: artimética de precisión arbitraria (ineficiente)
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175 import java.util.Scanner;
/**
* Replace this JavaDoc comment for the purpose of this class
*/
class CombPermArbitrary
{
/**
* Gets data from standard input
*/
private Scanner input;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
CombPermArbitrary solution = new CombPermArbitrary();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Read n
final long n = this.input.nextLong();
// Read r
final long r = this.input.nextLong();
printHeader();
printPermutations(n, r);
printCombinations(n, r);
// Close the standard input
this.input.close();
}
/**
* Print table header without repetition and with repetition
*/
public static void printHeader()
{
System.out.println(" No repetitions With repetitions");
}
/**
* Calculates and prints the permutations row of the table
*/
public static void printPermutations(final long n, final long r)
{
// Print text "Permutations"
System.out.print("Permutations ");
// Create permutations without repetition as the result of calculate permutations without repetition
final long permutationsWithoutRepetition = calculatePermutationsWithoutRepetition(n, r);
// Print permutations without repetition
System.out.printf("%20d ", permutationsWithoutRepetition);
// Create permutations with repetition as the result of calculate permutations with repetition
// Print permutations with repetition
System.out.printf("%20d%n", calculatePermutationsWithRepetition(n, r));
}
/**
* Calculate permutations without repetition
* @param n Size of the set of members to arrange. It must be greather than r.
* @param r Size of the arrangements (subsets) of n. It must be 0 or greater.
* @return The number of k-permutations of n without repetition, or zero if n or r are invalid.
*/
public static long calculatePermutationsWithoutRepetition(final long n, final long r)
{
// Return n! / (n - r)!
if ( n > r && r >= 0 )
return factorial(java.math.BigInteger.valueOf(n)).divide(
factorial(java.math.BigInteger.valueOf(n - r)) ).longValue();
else
return 0;
}
public static java.math.BigInteger factorial(final java.math.BigInteger value) {
// Create result as 1
java.math.BigInteger result = new java.math.BigInteger("1");
// Repeat current from 1 to n
for (long current = 1; current <= value.longValue(); ++current) {
// Assign result as result * current
result = result.multiply( java.math.BigInteger.valueOf(current) );
}
// Return result
return result;
}
public static long factorial(final long value)
{
// Create result as 1
long result = 1;
// Repeat current from 1 to n
for ( long current = 1; current <= value; ++current )
{
// Assign result as result * current
result *= current;
}
// Return result
return result;
}
// Calculate permutations with repetition:
public static long calculatePermutationsWithRepetition(final long n, final long r)
{
// Create result as 1
long result = 1;
// Repeat current from 1 to r
for ( long current = 1; current <= r; ++current )
{
// Assign result as result * n
result *= n;
}
// Return result
return result;
}
/**
* Calculates and prints the combinations row of the table
*/
public static void printCombinations(final long n, final long r) {
// Print text "Combinations"
System.out.print("Combinations ");
// Create combinations without repetition as the result of calculate
// combinations without repetition
final long combinationsWithoutRepetition = calculateCombinationsWithoutRepetition(n, r);
// Print combinations without repetition
System.out.printf("%20d ", combinationsWithoutRepetition);
// Create combinations with repetition as the result of calculate combinations
// with repetition
// Print combinations with repetition
System.out.printf("%20d%n", calculateCombinationsWithRepetition(n, r));
}
// Calculate combinations without repetition:
public static long calculateCombinationsWithoutRepetition(final long n, final long r)
{
// Return n! / ( r! * (n - r)! )
return factorial(java.math.BigInteger.valueOf(n)).divide(
factorial(java.math.BigInteger.valueOf(r)).multiply(
factorial(java.math.BigInteger.valueOf(n - r)))
).longValue();
}
// Calculate combinations with repetition:
public static long calculateCombinationsWithRepetition(final long n, final long r)
{
// Return (n + r - 1)! / ( r! * (n - 1)! )
//return factorial(n + r - 1) / ( factorial(r) * factorial(n - 1) );
return factorial(java.math.BigInteger.valueOf(n + r - 1)).divide(
factorial(java.math.BigInteger.valueOf(r)).multiply(factorial(java.math.BigInteger.valueOf(n - 1))))
.longValue();
}
} // class
1.5. Arreglos y matrices
1.5.1. Mediana estadística
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 import java.util.Scanner;
/**
* Calculates the median of a set of real values
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Leer la cantidad de elementos
final int elementCount = this.input.nextInt();
// Crear un arreglo de la cantidad de elementos
double elements[] = new double[ elementCount ];
// Repetir posicion desde 0 hasta la cantidad de elementos
for ( int position = 0; position < elements.length; ++position )
{
// Leer un valor en la posicion del arreglo
elements[position] = this.input.nextDouble();
}
// Ordenar el arreglo
java.util.Arrays.sort( elements );
// Si la cantidad de elementos es impar
if ( elements.length % 2 != 0 )
{
// Crear mediana como el valor en la posicion cantidad de elementos entre dos
final double median = elements[ elements.length / 2 ];
// Imprimir la mediana
System.out.printf("%.2f%n", median);
}
else
{
// Crear mediana como el promedio de los dos valores en el centro
final double value1 = elements[elements.length / 2 - 1];
final double value2 = elements[elements.length / 2];
final double median = (value1 + value2) / 2.0;
// Imprimir la mediana
System.out.printf("%.2f%n", median);
}
// Close the standard input
this.input.close();
}
}
1.5.2. Formatear el mes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 import java.util.Scanner;
public class PrintDate
{
public static void main(String args[])
{
Scanner input = new Scanner(System.in);
int year = input.nextInt();
int month = input.nextInt();
int day = input.nextInt();
System.out.printf("%04d-%s-%02d\n", year, formatMonth(month), day);
}
public static String formatMonth(final int month)
{
// final String monthNames[] = new String[]{ "Ene", "Feb" };
final String monthNames[] = { "Ene", "Feb", "Mar", "Abr", "May"
, "Jun", "Jul", "Ago", "Set", "Oct", "Nov", "Dic" };
return monthNames[month - 1];
}
}
1.5.3. Leer e imprimir la matriz
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 import java.util.Scanner;
public class Matrix
{
public static void main(String args[])
{
Scanner input = new Scanner(System.in);
final int rowCount = input.nextInt();
final int colCount = input.nextInt();
double matrix[][][] = new double[rowCount][colCount];
read(matrix, input);
print(matrix);
}
public static void read(double matrix[][], Scanner input)
{
for ( int row = 0; row < matrix.length; ++row )
for ( int col = 0; col < matrix[row].length; ++col )
matrix[row][col] = input.nextDouble();
}
public static void print(final double matrix[][])
{
for ( int row = 0; row < matrix.length; ++row )
{
for ( int col = 0; col < matrix[row].length; ++col )
{
System.out.printf("%.1f ", matrix[row][col]);
}
System.out.println();
}
}
}
1.6. Recursión
1.6.1. Imprimir argumentos en línea de comandos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 public class Args
{
public static void main(String args[])
{
// for ( int index = 0; index < args.length; ++index )
// System.out.printf("%d[%s]%n", index, args[index]);
printArguments(args, 0);
}
public static void printArguments(String args[], int index)
{
if ( index < args.length )
{
System.out.printf("%d[%s]%n", index, args[index]);
printArguments(args, index + 1);
}
else
{
// Do nothing
}
}
}
1.6.2. Factorial
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 public class Factorial
{
public static void main(String args[])
{
for ( int index = 0; index < args.length; ++index )
{
long number = Long.parseLong(args[index]);
//System.out.printf("%d! = %d%n", number, iterativeFactorial(number));
System.out.printf("%d! = %d%n", number, tailRecursiveFactorial(number));
}
}
public static long iterativeFactorial(final long number)
{
long result = 1;
for ( int counter = 2; counter <= number; ++counter )
result *= counter;
return result;
}
public static long pureRecursiveFactorial(final long number)
{
if ( number == 0 )
return 1;
else
return number * pureRecursiveFactorial(number - 1);
}
public static long tailRecursiveFactorial(final long number)
{
return tailRecursiveFactorial(number, 1);
}
public static long tailRecursiveFactorial(final long number, final long result)
{
if ( number == 0 )
return result;
else
return tailRecursiveFactorial(number - 1, number * result);
}
}
1.6.3. Potencia entera (aritmética flotante)
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 public class IntPower
{
private static long iterations = 0;
private static long recursions = 0;
public static void main(String args[])
{
if ( args.length == 2 )
{
double base = Double.parseDouble(args[0]);
long exponent = Long.parseLong(args[1]);
System.out.printf("%f^%d = %f%n%n", base, exponent
// , iterativePower(base, exponent) );
// , pureRecursivePower(base, exponent) );
, optmimizedPureRecursivePower(base, exponent) );
System.out.printf("iterations: %d%n", iterations);
System.out.printf("recursions: %d%n", recursions);
}
else
System.err.println("Usage: IntPower <base> <exponent>");
}
public static double iterativePower(final double base, final long exponent)
{
double result = 1.0;
for ( long counter = 1; counter <= exponent; ++counter )
{
result *= base;
++iterations;
}
return result;
}
public static double pureRecursivePower(final double base, final long exponent)
{
++recursions;
if ( exponent == 0 )
return 1.0;
else if ( exponent == 1 )
return base;
else
return base * pureRecursivePower(base, exponent - 1);
}
public static double optmimizedPureRecursivePower(final double base, final long exponent)
{
++recursions;
if ( exponent == 0 )
return 1.0;
else if ( exponent == 1 )
return base;
else if ( exponent % 2 == 0 )
{
double mid = optmimizedPureRecursivePower(base, exponent / 2);
return mid * mid;
}
else
return base * optmimizedPureRecursivePower(base, exponent - 1);
}
}
1.6.4. Islas inundadas (backtracking)
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221 import java.util.Scanner;
enum FloodState
{
nonVisited,
nonFlooded,
flooded,
}
/**
* Calculates percent of floated island terrain by water
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String[] args)
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Leer el mapa
final double[][] map = this.readMap();
// Si se pudo leer un mapa
if ( map != null )
{
// Repetir mientras hayan años
while ( this.input.hasNextInt() )
{
// Leer el año
final int year = this.input.nextInt();
// Leer el nivel del mar proyectado
final double projectedLevel = this.input.nextDouble();
// Calcular el porcentaje de inundacion
final double floodPercent = this.calculateFloodPercent(map, projectedLevel);
// Imprimir el año, el nivel proyectado, y el porcentaje de inundación
System.out.printf("%d: %.1f %.1f%%%n", year, projectedLevel, floodPercent);
}
}
else
{
System.out.println("Invalid data");
}
// Close the standard input
this.input.close();
}
// Leer mapa:
public double[][] readMap()
{
// Leer filas y columnas
int rows = this.input.nextInt();
int columns = this.input.nextInt();
// Check rows and columns are valid
if ( rows <= 0 || columns <= 0 )
return null;
// Crear matriz de reales de tamano filas por columnas
double[][] map = new double[rows][columns];
// Leer la matriz
for ( int row = 0; row < map.length; ++row )
for ( int column = 0; column < map[row].length; ++column )
map[row][column] = this.input.nextDouble();
return map;
}
// Calcular el porcentaje de inundacion:
public double calculateFloodPercent(double[][] map, double projectedLevel)
{
// Crear una matriz de estados, uno por celda, inicialmente no visitados
FloodState[][] cellStates = new FloodState[ map.length ][ map[0].length ];
// Inundar el borde del mapa
this.floodBorder(map, projectedLevel, cellStates);
// Calcular el porcentaje de inundacion con la matriz de estados
return this.calculateFloodPercent(cellStates);
}
// Inundar el borde del mapa:
public void floodBorder(double[][] map, double projectedLevel, FloodState[][] cellStates)
{
// Inundar la primera fila
this.floodRow(0, map, projectedLevel, cellStates);
// Inundar la última fila
this.floodRow(map.length - 1, map, projectedLevel, cellStates);
// Inundar la primera columna
this.floodColumn(0, map, projectedLevel, cellStates);
// Inundar la última columna
this.floodColumn(map[0].length - 1, map, projectedLevel, cellStates);
}
// Inundar una fila:
public void floodRow(int row, double[][] map, double projectedLevel, FloodState[][] cellStates)
{
// Repetir por cada columna
for ( int column = 0; column < map[row].length; ++column )
{
// Inundar la celda
this.floodCell(row, column, map, projectedLevel, cellStates);
}
}
// Inundar una columna:
public void floodColumn(int column, double[][] map, double projectedLevel, FloodState[][] cellStates)
{
// Repetir por cada fila
for ( int row = 0; row < map.length; ++row )
{
// Inundar la celda
this.floodCell(row, column, map, projectedLevel, cellStates);
}
}
// Inundar celda:
public void floodCell(int row, int column, double[][] map, double projectedLevel, FloodState[][] cellStates)
{
// Si la celda no existe
if ( ! this.isValidCell(row, column, map) )
{
// Retornar (no continuar, condicion de parada)
return ;
}
// Si la celda ya esta visitada en la matriz de estados
if ( cellStates[row][column] != null /*FloodState.nonVisited*/ )
{
// Retornar (no continuar, condicion de parada)
return ;
}
// Si el nivel en la celda en el mapa es mayor que el nivel proyectado
if ( map[row][column] > projectedLevel )
{
// Asignar en el estado de la celda visitado no inundado
cellStates[row][column] = FloodState.nonFlooded;
// Retornar (no continuar, condicion de parada)
return ;
}
// Asignar en el estado de la celda visitado inundado
cellStates[row][column] = FloodState.flooded;
// Inundar la celda en el norte
this.floodCell(row - 1, column + 0, map, projectedLevel, cellStates);
// Inundar la celda en el noreste
this.floodCell(row - 1, column + 1, map, projectedLevel, cellStates);
// Inundar la celda en el este
this.floodCell(row + 0, column + 1, map, projectedLevel, cellStates);
// Inundar la celda en el sureste
this.floodCell(row + 1, column + 1, map, projectedLevel, cellStates);
// Inundar la celda en el sur
this.floodCell(row + 1, column + 0, map, projectedLevel, cellStates);
// Inundar la celda en el suroeste
this.floodCell(row + 1, column - 1, map, projectedLevel, cellStates);
// Inundar la celda en el oeste
this.floodCell(row + 0, column - 1, map, projectedLevel, cellStates);
// Inundar la celda en el noroeste
this.floodCell(row - 1, column - 1, map, projectedLevel, cellStates);
}
// La celda es valida:
public boolean isValidCell(int row, int column, double[][] map)
{
return row >= 0 && row < map.length && column >= 0 && column < map[0].length;
}
// Calcular el porcentaje de inundacion con la matriz de estados:
public double calculateFloodPercent(FloodState[][] cellStates)
{
// Contar la cantidad de celdas inundadas en la matriz de estados
long floodedCount = this.countState(cellStates, FloodState.flooded);
// Retornar cantidad de celdas inundadas entre la cantidad de celdas por cien
return 100.0 * floodedCount / (cellStates.length * cellStates[0].length);
}
// Contar la cantidad de celdas que tienen un estado
public long countState(FloodState[][] cellStates, FloodState state)
{
// Crear contador en cero
long count = 0;
// Repetir por cada fila
for ( int row = 0; row < cellStates.length; ++row )
{
// Repetir por cada columna
for ( int column = 0; column < cellStates[row].length; ++column )
{
// Si la la celda tiene el estado
if ( cellStates[row][column] == state )
{
// Incrementar el contador
++count;
}
}
}
// Retornar el contador
return count;
}
}
2. Programación orientada a objetos
2.1. Potencia entera (aritmética arbitraria)
Este ejemplo utiliza objetos existentes en la biblioteca estándar de Java (java.lang.BigInteger), y sirve para hacer explícita la diferencia entre la sintaxis arimética procedimental (infija), contra la notación de los objetos (el operador punto).
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 import java.math.BigInteger;
public class IntPowerArbitrary
{
private static long iterations = 0;
private static long recursions = 0;
public static void main(String args[])
{
if ( args.length == 2 )
{
BigInteger base = new BigInteger(args[0]);
long exponent = Long.parseLong(args[1]);
System.out.printf("%d^%d = %d%n%n", base, exponent
// , iterativePower(base, exponent) );
// , pureRecursivePower(base, exponent) );
, optmimizedPureRecursivePower(base, exponent) );
System.out.printf("iterations: %d%n", iterations);
System.out.printf("recursions: %d%n", recursions);
}
else
System.err.println("Usage: IntPowerArbitrary <base> <exponent>");
}
public static BigInteger optmimizedPureRecursivePower(final BigInteger base, final long exponent)
{
++recursions;
if ( exponent == 0 )
return new BigInteger("1");
else if ( exponent == 1 )
return base;
else if ( exponent % 2 == 0 )
{
BigInteger mid = optmimizedPureRecursivePower(base, exponent / 2);
return mid.multiply(mid);
}
else
return base.multiply( optmimizedPureRecursivePower(base, exponent - 1) );
}
public static double iterativePower(final double base, final long exponent)
{
double result = 1.0;
for ( long counter = 1; counter <= exponent; ++counter )
{
result *= base;
++iterations;
}
return result;
}
public static double pureRecursivePower(final double base, final long exponent)
{
++recursions;
if ( exponent == 0 )
return 1.0;
else if ( exponent == 1 )
return base;
else
return base * pureRecursivePower(base, exponent - 1);
}
public static double optmimizedPureRecursivePower(final double base, final long exponent)
{
++recursions;
if ( exponent == 0 )
return 1.0;
else if ( exponent == 1 )
return base;
else if ( exponent % 2 == 0 )
{
double mid = optmimizedPureRecursivePower(base, exponent / 2);
return mid * mid;
}
else
return base * optmimizedPureRecursivePower(base, exponent - 1);
}
}
2.2. Analizador de argumentos
2.2.1. Clase controladora Renamer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 public class Renamer
{
private Arguments arguments = null;
public static void main(String args[])
{
final Renamer renamer = new Renamer();
renamer.run(args);
}
public void run(String args[])
{
// ERROR: Arguments arguments = new Arguments();
this.arguments = new Arguments();
if ( this.arguments.analyze(args) )
{
if ( this.arguments.helpAsked() )
this.arguments.printHelp();
}
}
}
2.2.2. Clase modelo Arguments
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 public class Arguments
{
private String action = null;
private String filename = "";
private String pattern = null;
private String directory = null;
private boolean dryRunAsked = false;
private boolean quietAsked = false;
private boolean helpAsked = false;
public Arguments()
{
}
public boolean analyze(String[] args)
{
//this.printArguments(args);
//return args.length > 0;
for ( int index = 0; index < args.length; ++index )
{
switch ( args[index] )
{
case "-n": this.dryRunAsked = true; break;
case "--help": this.helpAsked = true; break;
default:
break;
}
}
return true;
}
public void printHelp()
{
System.out.println("Usage: Renamer [-nq] <action>");
}
public boolean helpAsked()
{
return this.helpAsked;
}
private static void printArguments(String args[])
{
for ( int index = 0; index < args.length; ++index )
System.out.printf("%d[%s]%n", index, args[index]);
}
}
2.3. Calculadora fraccional
2.3.1. Enunciado del problema (en Markdown)
En el análisis orientado a objetos se identifican los sustantivos y verbos involucrados en la tarea de traducir la entrada en la salida del programa. Se sugiere marcarlos con resaltadores (por ejemplo, azul para sustantivos y rojo para verbos).
El diseño inicia identificando entre los sustantivos resaltados a los objetos candidatos, llamados conceptos, los cuales simplemente se listan. También se identifican relaciones entre los sustantivos, por ejemplo, el numerador es un atributo del concepto fracción, y una calculadora tiene una fracción resultado.
Luego se recorre la lista de verbos resaltados, y se ubica cuáles objetos candidatos deben realizarlas. Por ejemplo, la calculadora debe simplificar las fracciones, pero la experta en simplificar es la clase fracción, por tanto tiene sentido decir "una fracción debe ser capaz de simplificarse". Otro ejemplo, la calculadora debe ser capaz de sumar fracciones. Ambas clases pueden cooperar para realizar esta acción. La calculadora reconoce la acción de sumar (sum = fr1 + fr2), la cual involucra tres fracciones (dos operandos y el resultado), el operador de suma (+) y la asignación en la fracción resultado (con el operador =). La clase calculadora puede encargarse de administrar las fracciones y reconocer la operación de suma, mientras que la clase fracción puede encargarse de sumarse con otra y producir el resultado, de forma análoga como un objeto BigInteger es capaz de sumarse con otro.
# Calculadora fraccional
Casi todo el mundo tiene una calculadora, hasta en su celular. Pero no todos tienen una calculadora fraccional, y pocos una con precisión arbitraria... Se necesita una calculadora fraccional estándar de precisión arbitraria que permita calcular las cuatro operaciones básicas: suma (`+`), resta (`-`), multiplicación (`*`), y división (`/`) de fracciones. En esta versión no es necesaria la prioridad de operaciones.
En matemática, una fracción es un número representado de la forma `a/b`, donde `a`, `b` son enteros y `b` nunca es cero. Conceptualmente, `a` recibe el nombre de `numerador` y `b` el de `denominador`.
Su calculadora debe ser interactiva. Debe leer las fracciones y operaciones de la entrada estándar e imprimir los resultados en la salida estándar, siempre simplificados. Cuando la calculadora está lista para leer una fracción muestra el indicador `fr> ` para avisar al usuario de que espera una fracción. Cuando está lista para leer un operador, mostrará el indicador `op> `.
```sh
./frcalc
fr> 12/-8
op> =
-3/2
```
En el ejemplo anterior se introdujo la fracción `12 / -8` y el operador `=`, que muestra el último resultado de una operación. En este caso, la fracción se imprime, y como puede verse, la calculadora la imprime en forma simplificada `-3/2`. Nótese además que la calculadora ajustó los negativos, dado que por convención, no se escriben denominadores negativos en las fracciones.
La calculadora debe realizar las cuatro operaciones básicas. Si el usuario ingresa uno de los operadores cuando se presenta el indicador `op> `, la calculadora esperará por otra fracción. Una vez ingresada, se presenta el resultado de la operación. Por ejemplo:
```sh
./frcalc
fr> 12/8
op> +
fr> 1/4
-3/2
```
Ingrese fracción 1 en formato a b: 12 8
Ingrese fracción 2 en formato a b: 1 4
3/2 + 1/4 = 7/4
Para simplificar la fracción, implemente el [algoritmo de Euclides](http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Simplificar_fracciones), el cual consiste en encontrar el máximo común divisor (`mcd`) entre el numerador y denominador, y si este es diferente de cero, se divide tanto el numerador como el denominador por el `mcd` encontrado. Para calcular el máximo común divisor, implemente un método estático que recibe dos enteros `a` y `b` por parámetro, y retorna el máximo común divisor entre
ellos ó 0 si no hay, utilizando el algoritmo de Euclides, el cual se resume en el siguiente pseudocódigo:
```java
función maximoComunDivisor(a, b):
mientras ( b != 0 )
t = b
b = a modulo b
a = t
El resultado es a
```Pendiente: diagrama de clases UML del diseño anterior.
2.3.2. Clase controladora FractionalCalculator
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 import java.math.BigInteger;
import java.util.Scanner;
public class FractionalCalculator
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
Fraction fr1 = new Fraction( new BigInteger("1") );
// fr1.print();
// System.out.println();
System.out.println(fr1.toString());
Fraction fr2 = new Fraction();
if ( fr2.read(input) )
// fr2.print();
System.out.printf("%s%n", fr2);
else
System.err.println("invalid fraction");
Fraction sum = fr1.add(fr2);
System.out.printf("%s + %s = %s%n", fr1, fr2, sum);
}
}
2.3.3. Clase modelo Fraction
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117 import java.math.BigInteger;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Fraction
{
private BigInteger numerator = BigInteger.ZERO;
private BigInteger denominator = BigInteger.ONE;
public Fraction()
{
this(new BigInteger("0"));
}
public Fraction(BigInteger numerator)
{
this(numerator, new BigInteger("1"));
}
public Fraction(BigInteger numerator, BigInteger denominator)
{
this.numerator = numerator;
this.denominator = denominator;
this.simplify();
}
public void print()
{
System.out.print( this.toString() );
}
@Override
public String toString()
{
return String.format("%d/%d", this.numerator, this.denominator);
}
public boolean read(Scanner input)
{
boolean ok = true;
Pattern originalDelimiter = input.delimiter();
input.useDelimiter("[\\s/]+");
if ( input.hasNextBigInteger() )
{
numerator = input.nextBigInteger();
if ( input.hasNextBigInteger() )
{
denominator = input.nextBigInteger();
if ( denominator.compareTo(BigInteger.ZERO) == 0 )
{
denominator = BigInteger.ONE;
ok = false;
}
}
else
ok = false;
}
else
ok = false;
if ( ok )
this.simplify();
input.useDelimiter(originalDelimiter);
return ok;
}
private void simplify()
{
//this.numerator /= this.gcd();
BigInteger gcd = this.gcd();
this.numerator = this.numerator.divide( gcd );
this.denominator = this.denominator.divide( gcd );
if ( this.denominator.compareTo(BigInteger.ZERO) < 0 )
{
this.numerator = this.numerator.multiply( new BigInteger("-1") );
this.denominator = this.denominator.multiply( new BigInteger("-1") );
}
}
public BigInteger gcd()
{
return gcd( this.numerator.abs(), this.denominator.abs() );
}
/**
* Adapted from http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Simplificar_fracciones
* @param a . The value given must be positive or zero, otherwise it may generate an infinite loop.
*/
public static BigInteger gcd(BigInteger a, BigInteger b)
{
while ( b.compareTo(BigInteger.ZERO) != 0 )
{
BigInteger t = b; // new BigInteger( b.toString() ); // b.clone();
b = a.mod(b);
a = t;
}
return a;
}
public Fraction add(Fraction other)
{
Fraction result = new Fraction();
result.numerator = this.numerator.multiply(other.denominator).add( this.denominator.multiply(other.numerator) );
result.denominator = this.denominator.multiply(other.denominator);
result.simplify();
return result;
}
public Fraction multiply(Fraction other)
{
return new Fraction(this.numerator.multiply(other.numerator), this.denominator.multiply(other.denominator));
}
}
3. Estructuras de datos (¿programación genérica?)
La máquina provee cuatro (realmente tres) formas de usar el almacenamiento (memoria):
-
Variable: un espacio para almacenar un único valor.
-
Indirección: un espacio para almacenar un número entero sin signo que es la dirección de algo almacenado en la memoria. Realmente es un caso especial de la forma anterior.
-
Arreglo: una región continua de la memoria para almacenar varios valores (variables) del mismo tipo.
-
Registro: una región continua de la memoria para almacenar varios valores (variables) que pueden tener tipos distintos.
Para almacenar varios valores se usan colecciones, que son estructuras de datos. Las estructuras pueden clasificarse en:
-
De memoria continua: arreglos, matrices, arreglos multimensionales.
-
De memoria discontinua: pilas, colas, listas, árboles, grafos.
-
Híbridos de las dos anteriores.
3.1. Arreglo dinámico (java.util.ArrayList<E>)
Es un objeto que internamente controla un arreglo, y puede cambiarlo por otro cuando se necesita más o menos elementos. El siguiente ejemplo encuentra la mediana de valores dados en la entrada estándar sin conocer la cantidad de ellos:
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 import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
* Calculates the median of a set of real values
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
// Crear un arreglo de la cantidad de elementos
ArrayList<Double> elements = new ArrayList<Double>();
// Repetir posicion desde 0 hasta la cantidad de elementos
while ( this.input.hasNextDouble() )
{
// Leer un valor en la posicion del arreglo
elements.add( this.input.nextDouble() );
}
// Ordenar el arreglo
Collections.sort( elements );
// Si la cantidad de elementos es impar
if ( elements.size() % 2 != 0 )
{
// Crear mediana como el valor en la posicion cantidad de elementos entre dos
final double median = elements.get( elements.size() / 2 );
// Imprimir la mediana
System.out.printf("%.2f%n", median);
}
else
{
// Crear mediana como el promedio de los dos valores en el centro
final double value1 = elements.get( elements.size() / 2 - 1 );
final double value2 = elements.get( elements.size() / 2 );
final double median = (value1 + value2) / 2.0;
// Imprimir la mediana
System.out.printf("%.2f%n", median);
}
// Close the standard input
this.input.close();
}
}
La mayoría de contenedores, como ocurre con java.util.ArrayList<E>, usa el paradigma de programación genérica para pasar tipos de datos por parámetro. En Java se usa la notación <T> para indicar que T se reemplaza por un tipo de datos cualquiera (en Java restringido a no primitivos).
3.2. Lista doblemente enlazada
Las estructuras de datos de memoria discontinua usan registros, para combinar los valores que se quieren almacenar, junto con variables de indirección (referencias) para saber cuáles otros valores están relacionados. A estos registros se les llaman nodos. La cantidad de valores de indirección en cada nodo distinguen el tipo de estructura:
-
1 referencia por nodo: pila, cola, lista.
-
2 referencias por nodo: árboles binarios.
-
n referencias por nodo: árboles n-arios.
El siguiente ejemplo permite almacenar nombres en una lista doblemente enlazada:
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 import java.util.Scanner;
/**
* Calculates the median of a set of real values
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
try
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
List names = new List();
while ( this.input.hasNextLine() )
names.append( this.input.nextLine() );
// System.out.print( names.map( toupper ) );
// System.out.print( names.reduce( tieneDosNombres ), count );
names.reversePrint();
System.out.println();
names.recursivePrint();
System.out.println();
long count = 0;
while ( ! names.isEmpty() )
{
String name = names.removeFirst();
System.out.printf("%d: %s%n", ++count, name);
}
// Close the standard input
this.input.close();
}
catch ( Exception exception )
{
System.err.println( exception );
}
}
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 public class List
{
private Node first = null;
private Node last = null;
private long count = 0;
private class Node
{
private Node previous = null;
private String data = null;
private Node next = null;
public Node(String data)
{
//this.data = data;
this(data, null);
}
public Node(String data, Node previous)
{
this.data = data;
this.previous = previous;
}
public String getData()
{
return this.data;
}
public Node getPrevious()
{
return this.previous;
}
public Node setPrevious(Node previous)
{
return this.previous = previous;
}
public Node getNext()
{
return this.next;
}
public Node setNext(Node next)
{
return this.next = next;
}
}
public List()
{
}
public void append(String element)
{
if ( this.isEmpty() )
this.last = this.first = new Node(element);
else
this.last = this.last.setNext( new Node(element, this.last) );
// {
// Node newNode = new Node(element, this.last);
// this.last.setNext( newNode );
// this.last = newNode;
// }
++this.count;
}
public boolean isEmpty()
{
return this.first == null;
}
public String removeFirst() throws Exception
{
if ( this.isEmpty() )
throw new Exception("cannot remove from empty list");
String data = this.first.getData();
if ( this.first.getNext() != null )
this.first.getNext().setPrevious(null);
else
this.last = null;
this.first = this.first.getNext();
--this.count;
return data;
}
public void reversePrint()
{
Node current = this.last;
while ( current != null )
{
System.out.printf("%s, ", current.getData());
current = current.getPrevious();
}
}
public void recursivePrint()
{
this.recursivePrint( this.first );
}
public void recursivePrint(Node node)
{
if ( node == null )
return;
System.out.printf("%s, ", node.getData() );
this.recursivePrint( node.getNext() );
}
}
3.3. Árbol binario de búsqueda
Es un árbol con dos valores de indirección en cada nodo (árbol n-ario con n=2). Para asegurar que el acceso y la inserción/eliminación de los elementos sea en tiempo logarítmico impone una restricción: ordenamiento de acuerdo a algún criterio (típicamente la función matemática menor-que). La restricción establece que todos los elementos (nodos) que están a la izquierda de un elemento (nodo) E cumplen el criterio de ordenamiento (por ejemplo, ser menores), y todos los elementos que incumplen el criterio (por ejemplo, ser mayores o iguales) estarán a la derecha del elemento E.
Para realmente asegurar el acceso logarítmico, el árbol además debe estar balanceado, lo que es tema de cursos posteriores. El siguiente ejemplo carga líneas de texto de la entrada estándar, las almacena en un árbol binario de búsqueda, y la imprime con diferentes recorridos por el árbol.
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 import java.util.Scanner;
/**
* Calculates the median of a set of real values
*/
public class Solution
{
/**
* Gets data from standard input
*/
private Scanner input = null;
/**
* Start the execution of the solution
* @param args Command line arguments
*/
public static void main(String args[])
{
Solution solution = new Solution();
solution.run();
}
/**
* Run the solution. This method is called from main()
*/
public void run()
{
try
{
// Create object to read data from standard input
this.input = new Scanner(System.in);
BinarySearchTree names = new BinarySearchTree();
while ( this.input.hasNextLine() )
names.insert( this.input.nextLine() );
// System.out.print( names.map( toupper ) );
// System.out.print( names.reduce( tieneDosNombres ), count );
System.out.printf("Preorder (NLR): ");
names.recursivePreorderPrint();
System.out.printf("%nInorder (LNR): ");
names.recursiveInorderPrint();
System.out.printf("%nOutorder (RNL): ");
names.recursiveOutorderPrint();
System.out.printf("%nPostorder (LRN): ");
names.recursivePostorderPrint();
System.out.println();
// names.recursivePrint();
// System.out.println();
// long count = 0;
// while ( ! names.isEmpty() )
// {
// String name = names.removeFirst();
// System.out.printf("%d: %s%n", ++count, name);
// }
// Close the standard input
this.input.close();
}
catch ( Exception exception )
{
System.err.println( exception );
}
}
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165 public class BinarySearchTree
{
private Node root = null;
private long count = 0;
private class Node
{
//private Node parent = null;
private String data = null;
// private String key = null; // Set or Key
// private String value = null; // Map
//private ArrayList<Node> children = new ArrayList<Node>();
private Node left = null;
private Node right = null;
public Node(String data)
{
this.data = data;
}
public String getData()
{
return this.data;
}
public Node getLeft()
{
return this.left;
}
public Node getRight()
{
return this.right;
}
public Node setLeft(Node left)
{
return this.left = left;
}
public Node setRight(Node right)
{
return this.right = right;
}
// Pre-order (NLR)
public void recursivePreorderPrint()
{
System.out.printf("%s, ", this.data );
if ( this.left != null )
this.left.recursivePreorderPrint();
if ( this.right != null )
this.right.recursivePreorderPrint();
}
// In-order (LNR)
public void recursiveInorderPrint()
{
if ( this.left != null )
this.left.recursiveInorderPrint();
System.out.printf("%s, ", this.data );
if ( this.right != null )
this.right.recursiveInorderPrint();
}
// Out-order (RNL)
public void recursiveOutorderPrint()
{
if ( this.right != null )
this.right.recursiveOutorderPrint();
System.out.printf("%s, ", this.data );
if ( this.left != null )
this.left.recursiveOutorderPrint();
}
// Post-order (LRN)
public void recursivePostorderPrint()
{
if ( this.left != null )
this.left.recursivePostorderPrint();
if ( this.right != null )
this.right.recursivePostorderPrint();
System.out.printf("%s, ", this.data );
}
}
public BinarySearchTree()
{
}
public void insert(String element)
{
if ( this.isEmpty() )
this.root = new Node(element);
else
{
Node current = this.root;
while ( current != null )
{
if ( element.compareTo( current.getData() ) < 0 )
{
if ( current.getLeft() == null )
{
current.setLeft( new Node(element) );
break ;
}
else
current = current.getLeft();
}
else // if ( element.compareTo( current.getData() ) > 0 )
{
if ( current.getRight() == null )
{
current.setRight( new Node(element) );
break ;
}
else
current = current.getRight();
}
// else
// return false;
}
}
++this.count;
}
public boolean isEmpty()
{
return this.root == null;
}
public void recursivePreorderPrint()
{
if ( ! this.isEmpty() )
this.root.recursivePreorderPrint();
}
public void recursiveInorderPrint()
{
if ( ! this.isEmpty() )
this.root.recursiveInorderPrint();
}
public void recursiveOutorderPrint()
{
if ( ! this.isEmpty() )
this.root.recursiveOutorderPrint();
}
public void recursivePostorderPrint()
{
if ( ! this.isEmpty() )
this.root.recursivePostorderPrint();
}
}
4. Herencia y polimorfismo (OOP)
La herencia es un mecanismo de la programación orientada a objetos que permite representar la relación "es un(a)" entre entidades, y reutilizar código. Se implementa en la máquina con redundancia controlada de registros.
El polimorfismo permite que un tipo de datos (llamado supertipo) pueda representar diferentes tipos de datos (subtipos) y que una operación en el supertipo se realice acorde a los subtipos de las entidades representadas. Se implementa en la máquina con tablas de refencias a subrutinas polimórficas.
4.1. Universidad
El reto de este ejemplo es leer un archivo de registros de diferente naturaleza, e imprimir los registros acorde a su tipo y en formato de objetos de JavaScript (JSON, JavaScript Object Notation).
4.1.1. Archivos de datos
El siguiente es un ejemplo de universidad.txt con cuatro registros:
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 estudiante
Pancracio Vega Mora
24/05/2000
1-1111-2222
B89918
5
9.65
administrativo
Flor Mena Mora
17/11/1958
2-0178-7171
7585000
32.19
Decana de medicina
estudiante
Ana Li Rodríguez
18/3/1999
3-1081-1881
991867
0
7.77
profesor
Mario Mortadela
31/04/1955
9-0182-0288
3500000
15.3
Profesor de música
La siguiente es la salida generada (universidad.json) por el programa en notación JSON:
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 [
{
tipo: 'Estudiante',
nombre: 'Pancracio Vega Mora',
fechaNacimiento: 24-05-2000,
cedula: '1-1111-2222',
carnet: 'B89918',
beca: '5',
promedioMatricula: '9.65',
},
{
tipo: 'Administrativo',
nombre: 'Flor Mena Mora',
fechaNacimiento: 17-11-1958,
cedula: '2-0178-7171',
salario: '7,585,000.00',
antigüedad: '32.19',
puesto: 'Decana de medicina',
},
{
tipo: 'Estudiante',
nombre: 'Ana Li Rodríguez',
fechaNacimiento: 18-03-1999,
cedula: '3-1081-1881',
carnet: '991867',
beca: '0',
promedioMatricula: '7.77',
},
{
tipo: 'Profesor',
nombre: 'Mario Mortadela',
fechaNacimiento: 31-04-1955,
cedula: '9-0182-0288',
salario: '3,500,000.00',
antigüedad: '15.30',
titulo: 'Profesor de música',
},
]
4.1.2. Clase Universidad
La clase Universidad se responsabiliza de leer el archivo y crear los objetos polimórficos:
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 import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class Universidad
{
private ArrayList<Persona> poblacionUniversitaria = new ArrayList<Persona>();
public static final String FILE_NAME = "universidad.txt";
public static void main(String args[])
{
Universidad universidad = new Universidad();
universidad.run();
}
public void run()
{
try
{
if ( this.cargarPoblacionUniversitaria() )
this.imprimirPoblacionUniversitaria();
else
System.err.println("Error cargando la población universitaria");
}
catch ( FileNotFoundException exception )
{
System.err.printf("Archivo no encontrado: %s%n", FILE_NAME);
}
}
public boolean cargarPoblacionUniversitaria() throws FileNotFoundException
{
Scanner input = new Scanner( new File(FILE_NAME) );
boolean ok = true;
while ( input.hasNext() && ok )
{
final String tipoPersona = input.next();
input.nextLine();
Persona persona = crearPersona(tipoPersona);
if ( persona != null )
{
persona.cargar(input);
this.poblacionUniversitaria.add( persona );
}
else
ok = false;
}
input.close();
return ok;
}
public static Persona crearPersona(String tipoPersona)
{
switch ( tipoPersona )
{
case "estudiante": return new Estudiante();
//case "funcionario": return new Funcionario();
case "administrativo": return new Administrativo();
case "profesor": return new Profesor();
default: return null;
}
}
public void imprimirPoblacionUniversitaria()
{
System.out.println("[");
for ( Persona persona : this.poblacionUniversitaria )
persona.imprimir(true);
System.out.println("]");
}
}
4.1.3. Clase Persona
La clase Persona es la clase base de la población universitaria. Representa cualquier persona de la universidad: estudiante, profesor, administrativo, misceláneo:
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 import java.util.Scanner;
public class Persona /*extends Object*/
{
protected String nombre = null;
protected FechaNacimiento fechaNacimiento = new FechaNacimiento();
protected String cedula = null;
public void cargar(Scanner entrada)
{
this.nombre = entrada.nextLine();
this.fechaNacimiento.cargar(entrada);
entrada.nextLine();
this.cedula = entrada.nextLine();
}
public void imprimir(boolean cerrarLlave)
{
System.out.printf("{%n");
System.out.printf("\ttipo: '%s',%n", this.getClass().getSimpleName());
System.out.printf("\tnombre: '%s',%n", this.nombre);
System.out.printf("\tfechaNacimiento: ");
this.fechaNacimiento.imprimir();
System.out.printf(",%n\tcedula: '%s',%n", this.cedula);
this.cerrarLlave(cerrarLlave);
}
public void cerrarLlave(boolean debeCerrarLaLlave)
{
if ( debeCerrarLaLlave )
System.out.println("},");
}
}
Una persona tiene una fecha de nacimiento, que se representa con la clase FechaNacimiento. La relación tiene crea composición de registros, a diferencia de la relación es un(a) que crea herencia de registros.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 import java.util.Scanner;
public class FechaNacimiento
{
private int dia = 0;
private int mes = 0;
private int año = 0;
public void cargar(Scanner entrada)
{
// todo: save and restore delimiter
entrada.useDelimiter("[/\\s]+");
this.dia = entrada.nextInt();
this.mes = entrada.nextInt();
this.año = entrada.nextInt();
}
public void imprimir()
{
System.out.printf("%02d-%02d-%04d"
, this.dia, this.mes, this.año);
}
}
4.1.4. Clase Estudiante
Un Estudiante es una Persona. Se responsabiliza de cargar sus campos del archivo e imprimirlos acorde.
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 import java.util.Scanner;
public class Estudiante extends Persona
{
protected String carnet = null;
protected byte beca = 0;
protected double promedioMatricula = 0.0;
// public Estudiante()
// {
// super(arg1, arg2, ...);
// }
@Override
public void cargar(Scanner entrada)
{
super.cargar(entrada);
this.carnet = entrada.nextLine();
this.beca = entrada.nextByte();
this.promedioMatricula = entrada.nextDouble();
}
@Override
public void imprimir(boolean cerrarLlave)
{
super.imprimir(false);
System.out.printf("\tcarnet: '%s',%n", this.carnet);
System.out.printf("\tbeca: '%d',%n", this.beca);
System.out.printf("\tpromedioMatricula: '%.2f',%n", this.promedioMatricula);
this.cerrarLlave(cerrarLlave);
}
}
4.1.5. Clase Funcionario
Un Funcionario es una Persona y es clase base para todas las personas que laboran en la universidad.
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 import java.util.Scanner;
public abstract class Funcionario extends Persona
{
protected double salario = 0.0; // colones
protected double antigüedad = 0.0; // años
@Override
public void cargar(Scanner entrada)
{
super.cargar(entrada);
this.salario = entrada.nextDouble();
this.antigüedad = entrada.nextDouble();
entrada.nextLine();
}
@Override
public void imprimir(boolean cerrarLlave)
{
super.imprimir(false);
System.out.printf("\tsalario: '%,.2f',%n", this.salario);
System.out.printf("\tantigüedad: '%,.2f',%n", this.antigüedad);
this.cerrarLlave(cerrarLlave);
}
}
4.1.6. Clase Profesor
Un Profesor es un Funcionario. Aunque existen profesores que también son estudiantes, la relación de herencia múltiple en Java no es permitida.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 import java.util.Scanner;
public class Profesor extends Funcionario
{
protected String titulo = "";
@Override
public void cargar(Scanner entrada)
{
super.cargar(entrada);
this.titulo = entrada.nextLine();
}
@Override
public void imprimir(boolean cerrarLlave)
{
super.imprimir(false);
System.out.printf("\ttitulo: '%s',%n", this.titulo);
this.cerrarLlave(cerrarLlave);
}
}
4.1.7. Clase Administrativo
Un Administrativo es un Funcionario.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 import java.util.Scanner;
public class Administrativo extends Funcionario
{
protected String puesto = "";
@Override
public void cargar(Scanner entrada)
{
super.cargar(entrada);
this.puesto = entrada.nextLine();
}
@Override
public void imprimir(boolean cerrarLlave)
{
super.imprimir(false);
System.out.printf("\tpuesto: '%s',%n", this.puesto);
this.cerrarLlave(cerrarLlave);
}
}
4.2. Distancia de Levenshtein
Utiliza herencia y polimorfismo de la programación de interfaces gráficas en Java para crear una aplicación que permite al usuario comparar dos textos y encontrar la distancia de edición entre ellos.
4.2.1. Clase controladora LevenshteinDistance
Crea la ventana principal y la muestra.
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 /**
*
*/
/**
* @author jeisson.hidalgo@ecci.ucr.ac.cr
*
*/
public class LevenshteinDistance
{
/**
* @param args
*/
public static void main(String[] args)
{
LevenshteinDistance levenshteinDistance = new LevenshteinDistance();
levenshteinDistance.run();
}
public void run()
{
MainWindow mainWindow = new MainWindow();
mainWindow.setVisible(true);
}
}
4.2.2. Clase vista MainWindow
Tiene dos retos principales:
-
Construir la interfaz gráfica usando controles gráficos (widgets) y maquetadores (layouts).
-
Reaccionar a eventos del usuario o del sistema (listeners). El
MainWindowpor tanto implementa todas las interfaces para poder reaccionar a los eventos que le interesan.
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 import java.awt.BorderLayout;
import java.awt.Font;
import java.awt.GridLayout;
import java.awt.event.TextEvent;
import java.awt.event.TextListener;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextArea;
import javax.swing.event.DocumentEvent;
import javax.swing.event.DocumentListener;
/**
* @author jeisson.hidalgo@ecci.ucr.ac.cr
*
*/
public class MainWindow extends JFrame implements DocumentListener
{
private JTextArea text1 = new JTextArea();
private JTextArea text2 = new JTextArea();
public MainWindow()
{
super("Levenshtein Distance");
this.setSize(640, 480);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
BorderLayout generalLayout = new BorderLayout();
this.setLayout( generalLayout );
JPanel centralPanel = new JPanel();
centralPanel.setLayout( new GridLayout(2,1) );
centralPanel.add(this.text1);
centralPanel.add(this.text2);
this.add(centralPanel, BorderLayout.CENTER);
JLabel distanceLabel = new JLabel("Distance:");
Font font = new Font("Sans", Font.BOLD, 18);
distanceLabel.setFont(font);
this.add( distanceLabel, BorderLayout.SOUTH );
this.text1.getDocument().addDocumentListener(this);
}
// @Override
// public void textValueChanged(TextEvent event)
// {
// System.err.println( event );
// }
// Gives notification that an attribute or set of attributes changed.
public void changedUpdate(DocumentEvent event)
{
System.err.println( event );
}
// Gives notification that there was an insert into the document.
public void insertUpdate(DocumentEvent event)
{
System.err.println( "insertUpdate()" );
this.text2.setText( this.text1.getText() );
}
// Gives notification that a portion of the document has been removed.
public void removeUpdate(DocumentEvent event)
{
System.err.println( "removeUpdate()" );
this.text2.setText( this.text1.getText() );
}
}
