EvbCFfp1XB

problem and my answer.

January 2014


import java.util.Arrays;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 36 Arithmetic<br>
* Problem2<br>
* 非ゼロ要素に対応する節点からなるリンクによるリストを用いて疎な多項式の積を計算するプログラムを書け。
*/
public class Chapter36ArithmeticProblem2 {
public static void main(String[] args) {
Chapter36ArithmeticProblem2 o = new Chapter36ArithmeticProblem2();
o.run();
}

private class Node {
int c;
int j;
Node next;
}

private void run() {
Node t = new Node();
Node i = insert(t, 1, 0);
i = insert(i, 1, 10);
i = insert(i, -1, 100);

Node mult = t;
for (int k = 0; k < 10; k++) {
mult = mult(t, mult);

mult = simple(mult);

for (Node l = mult.next; l != null; l = l.next) {
System.out.format(" + %d*x^%d", l.c, l.j);
}
System.out.format("\n");
}
}

private Node mult(Node t, Node t2) {
Node m = new Node();
Node n = m;
for (Node i = t.next; i != null; i = i.next) {
for (Node j = t2.next; j != null; j = j.next) {
n = insert(n, i.c * j.c, i.j + j.j);
}
}
return m;
}

private Node simple(Node t) {
Node s = new Node();
Node n = s;
for (Node i = t.next; i != null; i = i.next) {
boolean exists = false;
for (Node j = s.next; j != null; j = j.next) {
if (j.j == i.j) {
j.c += i.c;
exists = true;
break;
}
}
if (!exists) {
n = insert(n, i.c, i.j);
}
}
for (Node j = s; j != null; j = j.next) {
if (j.next != null && j.next.c == 0) {
j.next = j.next.next;
}
}
for (;;) {
boolean exists = false;
for (Node j = s; j != null; j = j.next) {
if (j.next != null && j.next.next != null && j.next.j > j.next.next.j) {
Node tmp = j.next;
j.next = j.next.next;
Node tmp2 = j.next.next;
j.next.next = tmp;
j.next.next.next = tmp2;
exists = true;
}
}
if (!exists) {
break;
}
}
return s;
}

private Node insert(Node t, int c, int j) {
t.next = new Node();
t.next.c = c;
t.next.j = j;
return t.next;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}



import java.util.Arrays;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 36 Arithmetic<br>
* Problem1<br>
* 多項式はr[0](x-r[1])(x-r[2])...(x-r[n])と表すことも出来る。このような場合乗算はどうなるか?
*/
public class Chapter36ArithmeticProblem1 {
public static void main(String[] args) {
Chapter36ArithmeticProblem1 o = new Chapter36ArithmeticProblem1();
o.run();
}

private void run() {
// 2 * x * x + 4 * x + 2 = 2 * (x - -1) * (x - -1)
double[] a = new double[] { 2, 4, 2, };
double[] r = new double[] { 2, -1, -1, };
for (int x = -100; x < 100; x++) {
double y = x * x * a[0] + x * a[1] + a[2];
double y2 = r[0] * (x - r[1]) * (x - r[2]);
if (y != y2) {
throw new AssertionError();
}
}

double[] mult = mult(a, a);
debug("mult", mult);
double[] mult2 = mult2(r, r);
debug("mult2", mult2);
for (int x = -100; x < 100; x++) {
double y = 0;
for (int i = 0; i < mult.length; i++) {
y = x * y + mult[i];
}
double y2 = mult2[0];
for (int i = 1; i < mult2.length; i++) {
y2 *= (x - mult2[i]);
}
if (y != y2) {
throw new AssertionError();
}
}
}

private double[] mult2(double[] a, double[] b) {
double[] res = new double[a.length + b.length - 1];
int ri = 0;
res[ri++] = a[0] * b[0];
for (int i = 1; i < a.length; i++) {
res[ri++] = a[i];
}
for (int i = 1; i < b.length; i++) {
res[ri++] = b[i];
}
return res;
}

private double[] mult(double[] a, double[] b) {
double[] res = new double[a.length + b.length - 1];
for (int ai = 0; ai < a.length; ai++) {
for (int bi = 0; bi < b.length; bi++) {
res[ai + bi] += a[ai] * b[bi];
}
}
return res;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}


import java.util.Arrays;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 35 Random Numbers<br>
* Problem8<br>
* 加法的合同法で、例えば、b=3,c=6を用いるのが賢明でないのはなぜか?
*/
public class Chapter35RandomNumbersProblem8 {
public static void main(String[] args) {
Chapter35RandomNumbersProblem8 o = new Chapter35RandomNumbersProblem8();
o.run();
}

private void run() {
int b = 3;
int c = 6;
for (int k = 0; k < 10; k++) {
AdditiveCongruentialMethod rng = new AdditiveCongruentialMethod((int) System.nanoTime(), b, c);
rng.a[-b + rng.a.length] = 0;
rng.a[-c + rng.a.length] = 0;

int N = 1000;
int r = 100;
int[] a = new int[N];
int valid = 0;
for (int test = 0; test < 1000; test++) {
for (int i = 0; i < a.length; i++) {
a[i] = rng.nextInt(r);
}
if (simpletest(a, r)) {
valid++;
}
}
System.out.format("%10.5f\n", valid / 1000.0);
}
}

private boolean simpletest(int[] a, int r) {
return Math.abs(chisquare(a, r) - r) <= 2 * Math.sqrt(r);
}

private double chisquare(int[] a, int r) {
int N = a.length;
int[] count = new int[r];
for (int i = 0; i < N; i++) {
count[a[i]]++;
}
double t = 0;
for (int i = 0; i < count.length; i++) {
t += count[i] * count[i];
}
return t / ((double) N / r) - N;
}

private class AdditiveCongruentialMethod {
private int[] a;
private int j = 0;
private int m = 100000000;
private int m2 = 10000;
private int b;
private int c;

public AdditiveCongruentialMethod(int seed, int b, int c) {
this.b = b;
this.c = c;
a = new int[Math.max(b, c)];
seed = Math.abs(seed) % m;
a[0] = seed;
if (seed < 0 || seed >= m) {
debug("seed", seed);
throw new AssertionError();
}
for (int i = 1; i < a.length; i++) {
a[i] = (mult(a[i - 1], 31415821) + 1) % m;
if (a[i] < 0 || a[i] >= m) {
debug("a[i]", a[i], "a[i-1]", a[i - 1]);
throw new AssertionError();
}
}
}

public int nextInt(int r) {
j = (j + 1) % a.length;
a[j] = (a[(j - b + a.length) % a.length] + a[(j - c + a.length) % a.length]) % m;
int res = ((a[j] / m2) * r) / m2;
if (res < 0 || res >= r) {
throw new AssertionError();
}
return res;
}

private int mult(int a, int b) {
if (m != m2 * m2) {
throw new AssertionError();
}
int a1 = a / m2;
int a2 = a % m2;
int b1 = b / m2;
int b2 = b % m2;
if (a * b != (a1 * m2 + a2) * (b1 * m2 + b2)) {
throw new AssertionError();
}
if ((a1 * m2 + a2) * (b1 * m2 + b2) != (a1 * b1) * m + (a2 * b1 + a1 * b2) * m2 + (a2 * b2)) {
throw new AssertionError();
}
int res = (((a2 * b1 + a1 * b2) % m2) * m2 + (a2 * b2)) % m;
if (res < 0 || res >= m) {
debug("a", a, "b", b, "res", res);
throw new AssertionError();
}
return res;
}
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}


import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Random;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 35 Random Numbers<br>
* Problem10<br>
* 計算機の1語のサイズより大きいMを使って乱数を生成する方法を述べよ。
*/
public class Chapter35RandomNumbersProblem10 {
public static void main(String[] args) {
Chapter35RandomNumbersProblem10 o = new Chapter35RandomNumbersProblem10();
o.run();
}

private void run() {
Random rng = new Random();

String M = "";
for (int i = 0; i < 100; i++) {
M += (int) (10 * rng.nextDouble());
}

BigDecimal m = new BigDecimal(M);
debug("M\n", m);
double d = rng.nextDouble();
debug("d", d);
BigDecimal res = m.multiply(new BigDecimal(d));
debug("m multiply d\n", res);

d = 0.1;

BigDecimal res2 = m.multiply(new BigDecimal(d));
debug("m multiply d\n", res2);
BigDecimal res3 = m.divide(new BigDecimal(1 / d));
debug("m divide 1/d\n", res3);
if (!res2.equals(res3)) {
throw new AssertionError("res2 is not equal to res3. I think the problem is BigDecimal.multiply(0.1).");
}
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}


/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 35 Random Numbers<br>
* Problem9<br>
* 常に同じ値を返すような縮退した乱数発生器の場合、χ2乗の値はいくらか?
*/
public class Chapter35RandomNumbersProblem9 {
public static void main(String[] args) {
Chapter35RandomNumbersProblem9 o = new Chapter35RandomNumbersProblem9();
o.run();
}

private void run() {
Random rng = new Random();
int N = 1 + (int) (999 * rng.nextDouble());
int r = 1 + (int) (999 * rng.nextDouble());
int[] a = new int[N];
double chisquare = chisquare(a, r);
double chisquare2 = N * N / ((double) N / r) - N;
double chisquare3 = (double) N * (r - 1);
boolean b = Math.abs(chisquare - chisquare2) < 1e-5;
boolean c = Math.abs(chisquare2 - chisquare3) < 1e-5;
if (!(b && c)) {
debug(N, r);
throw new AssertionError();
}
System.out.format("chisquare\n = N * (r - 1)\n = %d * (%d - 1)\n = %10.5f\n", N, r, chisquare3);
}

private double chisquare(int[] a, int r) {
int N = a.length;
int[] count = new int[r];
for (int i = 0; i < N; i++) {
count[a[i]]++;
}
double t = 0;
for (int i = 0; i < count.length; i++) {
t += count[i] * count[i];
}
return t / ((double) N / r) - N;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}

このページのトップヘ