EvbCFfp1XB

problem and my answer.

問題を解いてみました。
/**
* 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 まで使えます。
ということでしょうか?

このページのトップヘ