مساله:
دنباله u را در نظر بگیرید که به صورت زیر تعریف می شود:
- عبارت u(0) = 1 است
- برای هر x در u حتما عبارت های y = 2 * x + 1 و y = 3 * x + 1 را خواهیم داشت،
- هیچ عدد دیگری در u نیست
مثال:
u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, …]
شما باید n را به عنوان ورودی از تابع dbl_linear بگیرید و عددی را که در خانه n ام دنباله مرتب شده است برگرداند.
مثال:
dbl_linear(10) should return 22
Description:
Consider a sequence u where u is defined as follows:
The number u(0) = 1 is the first one in u.
For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.
There are no other numbers in u.
Example:
u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, …]
1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on…
Task:
Given parameter n the function dbl_linear (or dblLinear…) returns the element u(n) of the ordered sequence u (ordered with < so there are no duplicates) .
Example:
dbl_linear(10) should return 22
Note:
Focus attention on efficiency
import java.util.*;
class DoubleLinear {
public static int dblLinear(int n) {
if (n == 0) return 1;
SortedSet<Integer> u = new TreeSet<>();
u.add(1);
for(int i=0; i<n; i++) {
int x = u.first();
u.add(x*2+1);
u.add(x*3+1);
u.remove(x);
}
return u.first();
}
}class DoubleLinear {
public static int dblLinear (int n) {
int[] nums = new int[n + 1];
nums[0] = 1;
int i = 0, j = 0, k = 1;
while (k < n + 1) {
int y = 2 * nums[i] + 1;
int z = 3 * nums[j] + 1;
if (y < z) {
nums[k++] = y;
i++;
} else if (z < y) {
nums[k++] = z;
j++;
} else {
nums[k++] = z;
i++;
j++;
}
}
return nums[n];
}
}import java.util.ArrayDeque;
import java.util.Deque;
public class DoubleLinear {
public static int dblLinear (int n) {
Deque<Integer> deque2 = new ArrayDeque<Integer> ((int)n /2);
Deque<Integer> deque3 = new ArrayDeque<Integer> ((int)n /2);
int cnt = 0, h = 1;
while (true) {
if (cnt >= n) return h;
deque2.addLast(2 * h + 1);
deque3.addLast(3 * h + 1);
h = Math.min(deque2.peekFirst(), deque3.peekFirst());
if (h == deque2.peekFirst())
deque2.removeFirst();
if (h == deque3.peekFirst())
deque3.removeFirst();
cnt++;
}
}
}import java.util.*;
class DoubleLinear {
public static int dblLinear (int n) {
int pos = 0;
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
while (pos <= (5*n) ){
list.add(list.get(pos) * 2 + 1);
list.add(list.get(pos) * 3 + 1);
pos++;
}
Set<Integer> temp = new HashSet<>();
temp.addAll(list);
list.clear();
list.addAll(temp);
Collections.sort(list);
return list.get(n);
}
}import java.util.*;
class DoubleLinear {
static List<Integer> done = new ArrayList<>();
static Queue<Integer> result = new PriorityQueue<>(Arrays.asList(1));
public static int dblLinear(int n) {
int size = done.size();
System.out.println(n);
if (size >= n) {
System.out.println("Vorgerechnet");
return done.get(n);
}
int next = 0;
for (int i = 0; i <= n - size; i++) {
next = result.poll();
done.add(next);
int y = 2 * next + 1;
int z = 3 * next + 1;
if (!result.contains(y))
result.add(y);
if (!result.contains(z))
result.add(z);
}
return next;
}
}
