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
|
package com.keuin.kbackupfabric;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Random {
public int random(int A, int B) {
return (int) (A + (B - A + 1) * Math.random());
}
public double[] randomArray(int MaxN, int lowA, int highA) {
double[] array = new double[random(1,MaxN)];
for (int i = 0; i < array.length; i++) {
array[i] = lowA + (highA - lowA) * Math.random();
}
return array;
}
public double[] generate(int MaxN, int lowA, int highA) {
double[] testData = randomArray(MaxN,lowA,highA);
double x = testData[random(0,testData.length-1)];
}
public int R(double[] a, double x) {
List<Integer> list = new LinkedList<>();
int k;
for (int i = 0; i < a.length; i++) {
if(Math.abs(a[i] - x) < 1e-6)
list.add(i);
}
assert !list.isEmpty();
k = list.get(list.size() / 2);
return k;
}
public boolean domR(double[] a, double x) {
for (double v : a) {
if(Math.abs(v - x) < 1e-6)
return true;
}
return false;
}
public boolean oracle(double[] a, double x, int k) {
if(!(Math.abs(a[k] - x) < 1e-6))
return false;
int c1=0,c2=0;
for (int i = 0; i < k; i++) {
if(Math.abs(a[i] - x) < 1e-6)
++c1;
}
for (int i = k; i < a.length; i++) {
if(Math.abs(a[i] - x) < 1e-6)
++c2;
}
return c1 - c2 >= -1 && c1 - c2 <= 1;
}
public boolean driver() {
int MaxN = 80, lowA = 20, highA = 50;
double[] a = randomArray(MaxN,lowA,highA);
double x = a[random(0,a.length-1)];
return oracle(a,x,search(a,x));
}
public int search(double[] a, double x) {
int counter = 0;
for (double i : a) {
if(Math.abs(i - x) < 1e-6)
++counter;
}
counter /= 2;
for (int i = 0; i < a.length; i++) {
if(Math.abs(a[i] - x) < 1e-6) {
--counter;
if(counter == 0)
return i;
}
}
return -1;
}
public static void Main() {
int pass = 0, fail = 0;
for (int i = 0; i < 10000; i++) {
if(driver())
pass++;
else
fail++;
}
System.out.println(String.format("pass: %d, fail: %d.",pass,fail));
}
}
|
