EvbCFfp1XB

problem and my answer.

March 2012

問題を解いてみました。

/**
* Robert Sedgewick Algorithms in C++
 */

public class Chapter3ElementaryDataStructures {
public static void main(String[] args) {
// problem1();
// problem2();
// problem3();
// problem4();
// problem5();
// problem6();
// problem7();
// problem8();
// problem9();
problem10();
}

/**
* 1. ブール値を要素とする2次元の配列を用いて、iとjの最大公約数が1であればa[i][j]をtrue、
* そうでなければfalseとするプログラムを書け。
*/
static void problem1() {
int n = 100;
boolean[][] a = new boolean[n][n];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
a[i][j] = gcd(i, j) == 1 ? true : false;
}
}

System.out.format("%3s", "");
for (int j = 0; j < n; j++) {
System.out.format("%3d", j);
}
System.out.println();
for (int i = 0; i < a.length; i++) {
System.out.format("%3d", i);
for (int j = 0; j < a[i].length; j++) {
System.out.format("%3d", a[i][j] ? 1 : 0);
}
System.out.println();
}
}

private static int gcd(int a, int b) {
if (a < b) {
int c = a;
a = b;
b = c;
}
for (;;) {
if (b == 0) {
return a;
} else {
a %= b;
}
if (a == 0) {
return b;
} else {
b %= a;
}
}
}

/**
* 2. リンクによるリストに対して、ルーチンmovenexttofront(struct node * t) を実現せよ。
* ここで、この手続きはtがさす節点の次の節点をリストの先頭に移すものである。
*/
static void problem2() {
Node head = new Node("Start");
{
Node a = new Node("A");
head.next = a;
a.next = new Node("L");
a = a.next;
a.next = new Node("I");
a = a.next;
a.next = new Node("S");
a = a.next;
a.next = new Node("T");
a = a.next;
a.next = new Node("End");
a = a.next;
a.next = a;
}

print(head);

movenexttofront(head, "A");

print(head);
}

private static void print(Node head) {
for (Node a = head.next; a.next != a;) {
System.out.print(a.key);
a = a.next;
}
System.out.println();
}

static class Node {
public Node(String string) {
this.key = string;
}

String key;
Node next;
}

private static void movenexttofront(Node head, String s) {
for (Node node = head.next;;) {
if (node.key.equals(s)) {
Node node0 = node.next;
if (node0.key.equals("End")) {
break;
}
node.next = node0.next;
node0.next = head.next;
head.next = node0;
break;
} else {
node = node.next;
}
}
}

/**
* 3. 2つの節点tとuによってさされているとき、その位置を交換するルーチンexchange(struct node * t, struct
* node * u)を実現せよ。
*/
static void problem3() {
Node head = new Node("Start");
{
Node a = new Node("A");
head.next = a;
a.next = new Node("L");
a = a.next;
a.next = new Node("I");
a = a.next;
a.next = new Node("S");
a = a.next;
a.next = new Node("T");
a = a.next;
a.next = new Node("End");
a = a.next;
a.next = a;
}

print(head);
exchange(head, "A", "T");
print(head);
}

private static Node delete(Node head, String s) {
Node n = null;
for (Node node = head; node.next != node; node = node.next) {
if (node.next.key.equals(s)) {
n = node.next;
node.next = node.next.next;
break;
}
}
n.next = null;
return n;
}

private static void insert(Node n, Node insert) {
Node n0 = n.next;
n.next = insert;
insert.next = n0;
}

/**
* ABCDEF -> AECDBF
*/
private static void exchange(Node head, String s0, String s1) {
Node A = null;
Node D = null;
String b = null;
String e = null;
for (Node node = head; node.next != node; node = node.next) {
if (node.next.key.equals(s0)) {
if (A == null) {
A = node;
b = s0;
} else {
D = node;
e = s0;
}
}
if (node.next.key.equals(s1)) {
if (A == null) {
A = node;
b = s1;
} else {
D = node;
e = s1;
}
}
}

Node B;
Node E;
if (A.next == D) {
E = delete(head, e);
insert(A, E);
} else {
B = delete(head, b);
insert(D, B);
E = delete(head, e);
insert(A, E);
}

}

/**
* 4. リストの代わりに配列を用いて、ジョセファス問題を解くプログラムを書け。
*/
static void problem4() {
int n = 9;
int m = 5;
josephus(n, m);
josephusarray(n, m);
}

private static void josephus(int n, int m) {
Node x;
Node t = new Node("1");
x = t;
for (int i = 2; i <= n; i++) {
t.next = new Node("" + i);
t = t.next;
}
t.next = x;
for (; t != t.next;) {
for (int i = 1; i < m; i++) {
t = t.next;
}
System.out.print(t.next.key + " ");
x = t.next;
t.next = x.next;
}
System.out.print(t.key + "\n");
}

private static void josephusarray(int n, int m) {
int count = n;
boolean[] dead = new boolean[n];
for (int i = n - 1; count > 1;) {
for (int c = 0; c < m;) {
i = (i + 1) % n;
if (!dead[i]) {
c++;
}
}
System.out.print((i + 1) + " ");
dead[i] = true;
count--;
}

for (int i = 0; i < dead.length; i++) {
if (!dead[i]) {
System.out.print((i + 1) + "\n");
break;
}
}
}

/**
* 5. 双方向リストに対して挿入と削除の手続きを書け。
*/
static void problem5() {
DNode start = new DNode("[");
DNode end = new DNode("]");
insert(start, end);
DNode A = new DNode("A");
insert(start, A);
DNode B = new DNode("B");
insert(A, B);
DNode C = new DNode("C");
insert(B, C);

remove(B, C);

System.out.println("next:");
for (DNode i = start; i != null; i = i.next) {
System.out.print(i.key + " ");
}
System.out.println();

System.out.println("previous:");
for (DNode i = end; i != null; i = i.previous) {
System.out.print(i.key + " ");
}
System.out.println();
}

static class DNode {
public DNode(String string) {
this.key = string;
}

String key;
DNode previous;
DNode next;
}

private static void insert(DNode node, DNode insert) {
DNode swap = node.next;
node.next = insert;
insert.next = swap;

insert.previous = node;
if (swap != null) {
swap.previous = insert;
}
}

private static void remove(DNode node, DNode remove) {
node.next = remove.next;
if (remove.next != null) {
remove.next.previous = node;
}
}

/**
* 6. 並列的配列を用いて、スタックをリストにより実現する手続きを書け。
*/
static void problem6() {
Listproblem6 list = new Listproblem6();
list.insert(1, "S");
list.print();
list.insert(1, "L");
list.print();
list.insert(1, "A");
list.print();
list.insert(3, "I");
list.print();
list.insert(5, "T");
list.print();
list.delete(3);
list.print();
list.delete(3);
list.print();
list.delete(3);
list.print();
list.delete(2);
list.print();
list.delete(1);
list.print();
list.push("1");
list.print();
list.push("2");
list.print();
list.push("3");
list.print();
System.out.println(list.pop());
list.print();
System.out.println(list.pop());
list.print();
System.out.println(list.pop());
list.print();
System.out.println(list.pop());
list.print();
}

static class Listproblem6 {
String[] key = new String[] { "[", "]", null, null, null, null, null,
null, null, null, };
int[] next = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, };
int index = 2;

public void insert(int i, String s) {
key[index] = s;

int k = 0;
for (int j = 1; j < i; j++) {
k = next[k];
}
int swap = next[k];
next[k] = index;
next[index] = swap;

index++;
}

public void print() {
for (int i = 0; next[i] != i; i = next[i]) {
System.out.format("%s ", key[i]);
}
System.out.println(key[1]);
}

public String delete(int i) {
if (index == 2) {
return null;
}
String delete;
int k = 0;
for (int j = 1; j < i; j++) {
k = next[k];
}
delete = key[next[k]];
key[next[k]] = null;
next[k] = next[next[k]];
index--;
return delete;
}

public void push(String s) {
insert(1, s);
}

public String pop() {
return delete(1);
}

public void put(String s) {
insert(index - 1, s);
}

public String get() {
return delete(index - 2);
}
}

/**
* 7. スタックに対して次の操作列を施したとき、スタックの内容が変化する様子を示せ。 ここで、英字はプッシュ、星印はポップを表す。
* EAS*Y**QUE***ST***I*ON**
*/
static void problem7() {
Listproblem6 stack = new Listproblem6();
stack.push("E");
stack.print();
stack.push("A");
stack.print();
stack.push("S");
stack.print();
stack.pop();
stack.print();
stack.push("Y");
stack.print();
stack.pop();
stack.print();
stack.pop();
stack.print();
stack.push("Q");
stack.print();
stack.push("U");
stack.print();
stack.push("E");
stack.print();
stack.pop();
stack.print();
stack.pop();
stack.print();
stack.pop();
stack.print();
stack.push("S");
stack.print();
stack.push("T");
stack.print();
stack.pop();
stack.print();
stack.pop();
stack.print();
stack.pop();
stack.print();
stack.push("I");
stack.print();
stack.pop();
stack.print();
stack.push("O");
stack.print();
stack.push("N");
stack.print();
stack.pop();
stack.print();
stack.pop();
stack.print();
}

/**
* 8. キューに対して次の操作列を施したとき、キューの内容が変化する様子を示せ。 ここで、英字はput、星印はgetを表す。
* EAS*Y**QUE***ST***I*ON**
*/
static void problem8() {
Listproblem6 queue = new Listproblem6();
queue.put("E");
queue.print();
queue.put("A");
queue.print();
queue.put("S");
queue.print();
queue.get();
queue.print();
queue.put("Y");
queue.print();
queue.get();
queue.print();
queue.get();
queue.print();
queue.put("Q");
queue.print();
queue.put("U");
queue.print();
queue.put("E");
queue.print();
queue.get();
queue.print();
queue.get();
queue.print();
queue.get();
queue.print();
queue.put("S");
queue.print();
queue.put("T");
queue.print();
queue.get();
queue.print();
queue.get();
queue.print();
queue.get();
queue.print();
queue.put("I");
queue.print();
queue.get();
queue.print();
queue.put("O");
queue.print();
queue.put("N");
queue.print();
queue.get();
queue.print();
queue.get();
queue.print();
}

/**
* 9. 図3.5を作り出すようなdeletenextとinsertafterの呼び出しの列を示せ。
*/
static void problem9() {
Listproblem6 list = new Listproblem6();
list.insert(1, "S");
list.insert(1, "L");
list.insert(1, "A");
list.insert(3, "I");
list.insert(5, "T");
list.print();
for (int i = 0; list.key[i] != null; i++) {
System.out.format("%s %d\n", list.key[i], list.next[i]);
}
}

/**
* 10. リンクによるリストを用いて、キューの基本操作を実現せよ。
*/
static void problem10() {
Listproblem10 list = new Listproblem10();
list.put("1");
list.print();
list.put("2");
list.print();
list.put("3");
list.print();
System.out.println(list.get());
list.print();
System.out.println(list.get());
list.print();
System.out.println(list.get());
list.print();
}

static class Listproblem10 {
Node head = new Node("[");
Node z = new Node("]");

public Listproblem10() {
head.next = z;
z.next = z;
}

public void insertafter(String s, String insert) {
for (Node j = head; j != j.next; j = j.next) {
if (j.key.equals(s)) {
Node swap = j.next;
Node node = new Node(insert);
j.next = node;
node.next = swap;
break;
}
}
}

public void print() {
for (Node j = head; j != j.next; j = j.next) {
System.out.format("%s ", j.key);
}
System.out.println(z.key);
}

public String deletenext(String s) {
Node delete = null;
for (Node j = head; j != j.next; j = j.next) {
if (j.next.key.equals(s)) {
delete = j.next;
j.next = j.next.next;
break;
}
}
if (delete != null) {
return delete.key;
}
return null;
}

public void put(String s) {
for (Node j = head; j != j.next; j = j.next) {
if (j.next == z) {
insertafter(j.key, s);
break;
}
}
}

public String get() {
return deletenext(head.next.key);
}
}

}


問題を解いてみました。
/**
* Robert Sedgewick Algorithms in C++
 */

import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;

public class Chapter2C {
public static void main(String[] args) {
// problem1and10();
// problem2();
// problem3();
// problem4();
// problem5();
// problem6();
// problem7();
// problem8();
problem9();
}

/**
* 1. 本文中に説明しているユークリッドのアルゴリズムの変形版をプログラムとして実現せよ。
*/
/**
* 10. ユークリッドのアルゴリズムをJavaで実現せよ。
*/
static void problem1and10() {
for (int x = 1; x <= 10; x++) {
for (int y = 1; y <= 10; y++) {
System.out.format("gcd(%d, %d) = %d\n", x, y, gcd(x, y));
}
}
}

private static int gcd(int x, int y) {
int t;
while (x > 0) {
if (x < y) {
t = x;
x = y;
y = t;
}
x %= y;
}
return y;
}

/**
* 2. u と v が必ずしも正でない場合 u%v の値はどうなるか?
*/
static void problem2() {
System.out.println(-2 % -3);
System.out.println(-2 % 3);
System.out.println(2 % -3);
System.out.println(2 % 3);
}

/**
* 3. 与えられた分数を既約分数に直す手続きを実現せよ。
*/
static void problem3() {
int numerator = (int) (100 * Math.random());
int denominator = (int) (100 * Math.random());
int gcd = gcd(numerator, denominator);
int newnumerator = numerator / gcd;
int newdenominator = denominator / gcd;
System.out.format("%d/%d = %d/%d\n", numerator, denominator,
newnumerator, newdenominator);
}

/**
* 4. 10進数を1文字ずつ読み込み、それを1つの整数に直す関数 int convert()を書け。 ここで、10進数は空白記号で終わるものとする。
*/
static void problem4() {
System.out.format("%d\n", convert());
}

private static int convert() {
int n = 0;
Scanner sc = new Scanner(System.in);
for (;;) {
String s = sc.nextLine();
if (s.equals(" ")) {
break;
}
n = 10 * n + Integer.parseInt(s);
}
return n;
}

/**
* 5. 数を2進数として印刷する手続きbinary(int x)を書け。
*/
static void problem5() {
int n = (int) (Integer.MAX_VALUE * Math.random());
binary(n);
System.out.println(Integer.toString(n, 2));
}

private static void binary(int n) {
StringBuilder sb = new StringBuilder();
for (;;) {
sb.append(n % 2);
n /= 2;
if (n == 0) {
break;
}
}
System.out.println(sb.reverse());
}

/**
* 6. gcd(12345,56789)が呼ばれたとき、uとvがとる値をすべて列挙せよ。
*/
static void problem6() {
gcdproblem6(12345, 56789);
}

private static int gcdproblem6(int x, int y) {
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(x);
set.add(y);
int t;
while (x > 0) {
set.add(x);
set.add(y);
if (x < y) {
t = x;
x = y;
y = t;
}
x %= y;
}
set.add(x);
set.add(y);
for (Integer n : set) {
System.out.println(n);
}
return y;
}

/**
* 7. 問題6で文が実行される回数を正確に数えてみよ。
*/
static void problem7() {
gcdproblem7(12345, 56789);
for (String s : mapproblem7.keySet()) {
System.out.format("\"%s\" : %d\n", s, mapproblem7.get(s));
}
}

static TreeMap<String, Integer> mapproblem7 = new TreeMap<String, Integer>();

private static int gcdproblem7(int x, int y) {
mapproblem7.put("int t;", mapproblem7.get("int t;") == null ? 1
: mapproblem7.get("int t;") + 1);
int t;
mapproblem7.put(
"while (x > 0)",
mapproblem7.get("while (x > 0)") == null ? 1 : mapproblem7
.get("while (x > 0)") + 1);
while (x > 0) {
mapproblem7.put(
"if (x < y)",
mapproblem7.get("if (x < y)") == null ? 1 : mapproblem7
.get("if (x < y)") + 1);
if (x < y) {
mapproblem7.put("t = x;", mapproblem7.get("t = x;") == null ? 1
: mapproblem7.get("t = x;") + 1);
t = x;
mapproblem7.put("x = y;", mapproblem7.get("x = y;") == null ? 1
: mapproblem7.get("x = y;") + 1);
x = y;
mapproblem7.put("y = t;", mapproblem7.get("y = t;") == null ? 1
: mapproblem7.get("y = t;") + 1);
y = t;
}
mapproblem7.put("x %= y;", mapproblem7.get("x %= y;") == null ? 1
: mapproblem7.get("x %= y;") + 1);
x %= y;
}
mapproblem7.put("return y;", mapproblem7.get("return y;") == null ? 1
: mapproblem7.get("return y;") + 1);
return y;
}

/**
* 8. 3つの整数u,v,wの最大公約数を求めるプログラムを書け。
*/
static void problem8() {
for (int u = 1; u <= 10; u++) {
for (int v = 1; v <= 10; v++) {
for (int w = 1; w <= 10; w++) {
System.out.format("gcd(%d %d %d) = %d\n", u, v, w,
gcdproblem8(u, v, w));
}
}
}
}

private static int gcdproblem8(int u, int v, int w) {
return gcd(u, gcd(v, w));
}

/**
* 9. 互いに素な2つの整数でintとして表現できるなるべく大きいものを求めよ。
*/
static void problem9() {
System.out.format("gcd(%d(Integer.MAX_VALUE),%d) = %d\n", Integer.MAX_VALUE,
Integer.MAX_VALUE - 1,
gcd(Integer.MAX_VALUE, Integer.MAX_VALUE - 1));
}


}


formula               number
1 1
2! 2
2^2 4
3! 6
2^3 8
10^1 10
2^4 16
4! 24
2^5 32
2^6 64
10^2 100
5! 120
2^7 128
2^8 256
2^9 512
6! 720
10^3 1000
2^10 1024
2^11 2048
2^12 4096
7! 5040
2^13 8192
10^4 10000
2^14 16384
2^15 32768
8! 40320
2^16 65536
10^5 100000
2^17 131072
2^18 262144
9! 362880
2^19 524288
10^6 1000000
2^20 1048576
2^21 2097152
10! 3628800
2^22 4194304
2^23 8388608
10^7 10000000
2^24 16777216
2^25 33554432
11! 39916800
2^26 67108864
10^8 100000000
2^27 134217728
2^28 268435456
12! 479001600
2^29 536870912
10^9 1000000000
2^30 1073741824
2^31 2147483648
2^32 4294967296
13! 6227020800
2^33 8589934592
10^10 10000000000
2^34 17179869184
2^35 34359738368
2^36 68719476736
14! 87178291200
10^11 100000000000
2^37 137438953472
2^38 274877906944
2^39 549755813888
10^12 1000000000000
2^40 1099511627776
15! 1307674368000
2^41 2199023255552
2^42 4398046511104
2^43 8796093022208
10^13 10000000000000
2^44 17592186044416
16! 20922789888000
2^45 35184372088832
2^46 70368744177664
10^14 100000000000000
2^47 140737488355328
2^48 281474976710656
17! 355687428096000
2^49 562949953421312
10^15 1000000000000000
2^50 1125899906842624
2^51 2251799813685248
2^52 4503599627370496
18! 6402373705728000
2^53 9007199254740992
10^16 10000000000000000
2^54 18014398509481984
2^55 36028797018963968
2^56 72057594037927936
10^17 100000000000000000
19! 121645100408832000
2^57 144115188075855872
2^58 288230376151711744
2^59 576460752303423488
10^18 1000000000000000000
2^60 1152921504606846976
2^61 2305843009213693952
20! 2432902008176640000
2^62 4611686018427387904
2^63 9223372036854775808
10^19 10000000000000000000
2^64 18446744073709551616


source code

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class PrintNumbers {
public static void main(String[] args) {
Map<BigInteger, String> map = new HashMap<BigInteger, String>();

BigInteger[] dp = new BigInteger[65];

BigInteger TWO = new BigInteger("2");
dp[0] = BigInteger.ONE;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1].multiply(TWO);
map.put(dp[i], "2^" + i);
}

BigInteger LIMIT = dp[64];

dp[0] = BigInteger.ONE;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1].multiply(BigInteger.TEN);
if (dp[i].compareTo(LIMIT) > 0) {
break;
}
map.put(dp[i], "10^" + i);
}

dp[0] = BigInteger.ONE;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1].multiply(new BigInteger("" + i));
if (dp[i].compareTo(LIMIT) > 0) {
break;
}
map.put(dp[i], i + "!");
}

map.put(BigInteger.ONE, "1");

System.out.format("%7s %20s\n", "formula", "number");
for (BigInteger bi : new TreeSet<BigInteger>(map.keySet())) {
System.out.format("%7s %20s\n", map.get(bi), bi);
}
}
}



32768KB = (2^15) * (2^10) B = 2^25 B です。
int(4B) の配列なら、 2^25 / 4 = 2^25 * 2^(-2) = 2^23 = 8388608 まで使えます。
ということでしょうか?

このページのトップヘ