Question
Transcribed Text
Dynamic Programming
Problem Statement
For this assignment, you will develop a program to demonstrate your understanding of
the use of dynamic programming as an algorithm design technique.
We want to create a long paper chain of triangles for the king of Algroland. This
king requires that the various supply of grey colored paper of triangles be connected
together such that the shades of grey increase from light (white has value 0.0) to dark
(black has value 1.0). Each triangle can be fastened together with one or two other
triangles along sides with equal length. To increase flair, each triangle of the chain must
be a different shade of grey. For example, for the triangles shown in the figure below,
we can connect together four of them to make a chain.
3
4
4
4
4
2
2
2
2
3
6
5
3
4
4
4 4
7
g = 0
g = 0.4
g = 0.6
g = 0.6
g = 0.7
g = 1.0
Input
The input consists of a first line containing an integer 1 ≤ n ≤ 10000 denoting the
number of triangles available. This is then followed by a n lines containing three positive
integers l1, l2, l3 that denote the triangle side lengths and a real value 0.000 ≤ g ≤ 1.000
that denotes the grey scale color.
Output
For each test case output a single positive integer that represents the longest chain
(number of triangles) that could be made.
Taken from the earlier pictorial example we have the following sample input and
expected output.
Sample Input Sample Output
6
3 4 4 0.4
4 4 2 0.0
4 7 4 0.6
2 2 2 0.6
3 5 6 0.7
3 4 4 1.0
4
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
import java.io.BufferedReader;import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Algroland {
private static ArrayList<Triangle [] > readFile(String fileName) throws FileNotFoundException, Exception{
Scanner scanner = new Scanner( new File(fileName) );
ArrayList<Triangle [] > list = new ArrayList<Triangle []>();
int i = 0;
int number;
while (scanner.hasNext()) {
number = Integer.parseInt( scanner.nextLine() );
if (number <= 0)
break;
Triangle [] triangles = new Triangle[number];
for (int j = 0; j < number; j++) {
String next = scanner.nextLine();
triangles[j] = new Triangle(next);
}
list.add(triangles);
}
return list;
}...
By purchasing this solution you'll be able to access the following files:
Solution.java.
Return to homework library