JAVA Consider the following relation: Given an integer n > 4 the Collatz success
ID: 3856681 • Letter: J
Question
JAVA
Consider the following relation: Given an integer n > 4 the Collatz successors of n are defined to be: C(n) = {n is even AND ((n - 1) mod 3 = 0) {2 times n, (n - 1)/3} Otherwise {2 times n} Given an integer n > 4 the Collatz graph G_n(V, E) where V is the set of vertices of G_n, and E is the set of edges of G_n, is constructed by: 1. Set n to be a vertex in V 2. For each vertex j elementof V add C(n), the Collatz successor[s] of j, to V. Add the edges from j to its successors to E. It can be shown that under the assumption that the conjecture holds, and by definition of the graph, G_B(V, E) is an infinite tree that spans all the positive integers except for 1, 2, and 4. Consider the following tree construction (enumeration) algorithm: 1. Given the integer n = 8 and an empty queue, Q, insert n into Q. 2. Do forever: a. Remove the head element from Q (assume it is the integer j). b. Print j to a file c. Insert the successor[s] of j to Q. Assignment Instructions: Your assignment is to write a Java program that implements the above algorithm using a Queue Abstract Data Type. The program terminates the tree construction after 20 iteration of the given algorithm.Explanation / Answer
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Edge implements Comparable<Edge> {
int from;
int to;
Edge() {
from = to = -1;
}
Edge(int f, int t) {
from = f;
to = t;
}
@Override
public int compareTo(Edge e2) {
if (from == e2.from && to == e2.to)
return 0;
else
return -1;
}
}
class Vertex {
int vertex;
Vertex(int v) {
vertex = v;
}
int getVertex() {
return vertex;
}
}
class Graph {
Graph() {
List<Vertex> vlist = new ArrayList<Vertex>();
List<Edge> elist = new ArrayList<Edge>();
}
List<Vertex> vlist;
List<Edge> elist;
void insertEdge(Edge e) {
if (!elist.contains(e))
elist.add(e);
}
}
class CollatzSeq {
public static int[] succ(Vertex v) {
int n = v.getVertex();
if (n % 2 == 0 && (n - 1) % 3 == 0)
return new int[] { 2 * n, (n - 1) / 3 };
else
return new int[] { 2 * n };
}
public static void main(String[] args) {
Graph g = new Graph();
Queue<Vertex> q = new LinkedList();
q.add(new Vertex(8));
for (int i = 0; i < 20; i++) {
Vertex v = q.remove();
if (v == null)
return;
System.out.print(v.getVertex() + " ");
int[] arr = succ(v);
for (int j = 0; j < arr.length; j++)
q.add(new Vertex(arr[j]));
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.