EvbCFfp1XB

problem and my answer.

June 2012

public class AYear {
public static void main(String[] args) {
long ayear = 1;
long days = ayear * 365;
long hours = days * 24;
System.out.format("%d hours\n", hours);
long minutes = hours * 60;
System.out.format("%d minutes\n", minutes);
long seconds = minutes * 60;
System.out.format("%d seconds\n", seconds);
}
}


import java.util.PriorityQueue;

/**
* Chapter 14. Elementary Searching - Problem3 - Robert Sedgewick Algorithms in
* C++<br>
* 2分探索法の再帰的なプログラムを示せ。
*/
public class Chapter14ElementarySearchingProblem3 {
public static void main(String[] args) {
long start = System.nanoTime();
int max = 10000;
Dict d = new Dict(max);
for (int i = 0; i < max; i++) {
String key = random(3);
d.insert(key, key + random(10));
}
d.sort();
System.out.format("%s\n", d.search(random(3)));
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

private static class Dict {
int N;
Node[] a;

public Dict(int max) {
N = 0;
a = new Node[max];
}

public void sort() {
PriorityQueue<Node> pq = new PriorityQueue<Node>();
for (int i = 0; i < N; i++) {
pq.add(a[i]);
}
for (int i = 0; i < N; i++) {
a[i] = pq.poll();
}
}

public void insert(String key, String info) {
a[N] = new Node();
a[N].key = key;
a[N].info = info;
N++;
}

public String search(String key) {
return search(key, 0, N - 1);
}

private String search(String key, int l, int r) {
if (r < l) {
return null;
}
int c = (l + r) / 2;
if (a[c].key.compareTo(key) == 0) {
return a[c].info;
} else if (a[c].key.compareTo(key) < 0) {
return search(key, c + 1, r);
} else {
return search(key, l, c - 1);
}
}
}

private static class Node implements Comparable<Node> {
String key;
String info;

@Override
public int compareTo(Node o) {
return key.compareTo(o.key);
}
}

private static String s = "abcdefghijklmnopqrstuvwxyz";

private static String random(int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(s.charAt((int) (s.length() * Math.random())));
}
return sb.toString();
}
}

/**
* Chapter 14. Elementary Searching - Problem2 - Robert Sedgewick Algorithms in
* C++<br>
* 自己組織的探索を用いた”探索・挿入法”で、はじめ空であった表にキーEASYQUESTIONを入力した後のキーの順を示せ。
*/
public class Chapter14ElementarySearchingProblem2 {
public static void main(String[] args) {
long start = System.nanoTime();
String s = "EASYQUESTION";
Dict d = new Dict();
for (int i = 0; i < s.length(); i++) {
String key = s.substring(i, i + 1);
d.insert(key, key);
}
for (Node b = d.a.next; b != null; b = b.next) {
System.out.format("%s", b.key);
}
System.out.println();
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

private static class Dict {
Node a;

public Dict() {
a = new Node();
}

public void insert(String key, String info) {
for (Node b = a.next, c = a; b != null; c = b, b = b.next) {
if (b.key.compareTo(key) == 0) {
c.next = b.next;
b.next = a.next;
a.next = b;
return;
}
}
Node b = new Node();
b.key = key;
b.info = info;
b.next = a.next;
a.next = b;
}
}

private static class Node {
String key;
String info;
Node next;
}
}

/**
* Chapter 14. Elementary Searching - Problem1 - Robert Sedgewick Algorithms in
* C++<br>
* 配列上にレコードを整列した状態に保ち、成功探索と不成功探索が平均N/2ステップである逐次探索アルゴリズムを実現せよ。
*/
public class Chapter14ElementarySearchingProblem1 {
public static void main(String[] args) {
int max = 10000;
Dict d = new Dict(max);
for (int i = 0; i < max; i++) {
String key = random(3);
d.insert(key, key + random(10));
}
System.out.format("");
{
String key = d.a[d.N / 4].key + "a";
long start = System.nanoTime();
for (int i = 0; i < 100; i++) {
d.search(key);
}
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}
{
String key = d.a[d.N / 4].key;
long start = System.nanoTime();
for (int i = 0; i < 100; i++) {
d.search(key);
}
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}
}

private static String s = "abcdefghijklmnopqrstuvwxyz";

private static String random(int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(s.charAt((int) (s.length() * Math.random())));
}
return sb.toString();
}

private static class Dict {
int N;
Node[] a;

public Dict(int max) {
N = 0;
a = new Node[max];
}

public void insert(String key, String info) {
for (int i = 0; i < N; i++) {
if (a[i].key.compareTo(key) >= 0) {
for (int j = N - 1; j >= i; j--) {
a[j + 1] = a[j];
}
a[i] = new Node();
a[i].key = key;
a[i].info = info;
N++;
return;
}
}
a[N] = new Node();
a[N].key = key;
a[N].info = info;
N++;
}

public String search(String key) {
for (int i = 0; i < N; i++) {
if (a[i].key.compareTo(key) < 0) {
continue;
} else if (a[i].key.compareTo(key) == 0) {
return a[i].info;
} else {
return null;
}
}
return null;
}
}

private static class Node {
String key;
String info;
}
}

import java.util.Arrays;
import java.util.HashMap;
import java.util.TreeSet;

/**
* Chapter 9. Quicksort - Problem1 - Robert Sedgewick Algorithms in C++<br>
* カットオフを組み込んだクイックソートをプログラムとして実現せよ. ここで、要素数がM以下の部分ファイルに挿入整列法を使うものとする.
* そして、1000個の要素のランダムなファイルに対して、最も早く走るようにMの値を定めよ.
*/
public class Chapter9QuicksortProblem1 {
public static void main(String[] args) {
HashMap<Double, Integer> map = new HashMap<Double, Integer>();

int[] a = new int[100000];

for (int i = 0; i < 10; i++) {
random(a);
for (int M = 1; M <= 1000; M *= 2) {
int[] b = Arrays.copyOf(a, a.length);
int[] copy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
quicksortRecursiveM(b, 0, b.length - 1, M);
double time = (System.nanoTime() - start) / 1e9;
map.put(time, M);
isSorted(b, copy);
}
}

for (double time : new TreeSet<Double>(map.keySet())) {
System.out.format("%3d : %f\n", map.get(time), time);
}
}

private static void quicksortRecursiveM(int[] a, int l, int r, int M) {
if (r <= l + M) {
insertion(a, l, r);
return;
}
int i = partition(a, l, r);
quicksortRecursiveM(a, l, i - 1, M);
quicksortRecursiveM(a, i + 1, r, M);
}

private static int partition(int[] a, int l, int r) {
int v = a[r];
int i = l - 1;
int j = r;
for (;;) {
for (; a[++i] < v;) {
}
for (; --j >= l && a[j] > v;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r);
return i;
}

private static void insertion(int[] a, int l, int r) {
for (int i = l + 1; i <= r; i++) {
int v = a[i];
int j = i;
for (; j - 1 >= l && a[j - 1] > v; j--) {
a[j] = a[j - 1];
}
a[j] = v;
}
}

private static void swap(int[] a, int i, int j) {
int s = a[i];
a[i] = a[j];
a[j] = s;
}

private static void random(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = (int) (a.length * Math.random());
}
}

private static void isSorted(int[] a, int[] copy) {
Arrays.sort(copy);
for (int i = 0; i < copy.length; i++) {
if (a[i] != copy[i]) {
System.out.println("unsorted");
break;
}
}
}
}

このページのトップヘ