Algorithms 4th - 1.1 Basic Programming Model - EXERCISES
28515 ワード
交流を歓迎する
1.1.1
a. 7
b. 200.0000002
c. true
1.1.2
a. 1.618
b. 10.0
c. true
d. 33
1.1.3
1 public class MainApp {
2 public static void main(String[] args) {
3
4 int a = Integer.parseInt(args[0]);
5 int b = Integer.parseInt(args[1]);
6 int c = Integer.parseInt(args[2]);
7
8 if(a == b && b == c) {
9 System.out.println("equal");
10 } else {
11 System.out.println("not equal");
12 }
13 }
14 }1.1.4
a.「then」を取り除く
b.a>b外周に括弧を付ける
c.正しい
d.elseの前にコロンを付ける
1.1.5
public class MainApp {
public static void main(String[] args) {
Double a = Double.parseDouble(args[0]);
Double b = Double.parseDouble(args[1]);
if(a >= 0 && a <= 1 && b >=0 && b <= 1) {
System.out.println("true");
} else {
System.out.println("false");
}
}
}1.1.6
フィボナッチ数列
0 -> 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> 34 -> 55 -> 89 -> 144 -> 233 -> 377 -> 610
1.1.7
a. 3.00009
b. 499500
c. 10000
1.1.8
a. b
b. bc
c. e
1.1.9
int N = 13;
String s = "";
for(int i = N; i > 0; i /= 2) {
s = i % 2 + s;
}1.1.10
配列が初期化されていません
1.1.11
public class TestApp1 {
public static void main(String[] args) {
int N = 10;
boolean ma[][] = new boolean[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
double r = Math.random();
if(r < 0.5)
ma[i][j] = true;
else
ma[i][j] = false;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(ma[i][j] == true)
System.out.print("*");
else
System.out.print(" ");
}
System.out.println();
}
}
}1.1.12
0 1 2 3 4 4 3 2 1 0
1.1.13
public class TestApp1 {
public static void main(String[] args) {
int N = 10;
int M = 15;
boolean ma[][] = new boolean[N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
double r = Math.random();
if(r < 0.5)
ma[i][j] = true;
else
ma[i][j] = false;
}
}
System.out.println("origin matrix:");
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(ma[i][j] == true)
System.out.print("*");
else
System.out.print(" ");
}
System.out.println();
}
System.out.println("transposition matrix:");
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
if(ma[j][i] == true)
System.out.print("*");
else
System.out.print(" ");
}
System.out.println();
}
}
}1.1.14
public class TestApp1 {
public static void main(String[] args) {
System.out.println(lg(15));
System.out.println(lg(16));
System.out.println(lg(17));
}
private static int lg(int N) {
int result = 1;
while(result <= N) {
result *= 2;
}
return result / 2;
}
}1.1.15
public class TestApp1 {
public static void main(String[] args) {
int A[] = {1, 2, 3, 3, 2, 5, 5, 4};
int N = 8;
int M[] = histogram(A, N);
for(int m : M) {
System.out.println(m);
}
}
private static int[] histogram(int[] A, int N) {
int[] M = new int[N];
for(int i = 0; i < N; i++) {
M[A[i]]++;
}
return M;
}
}1.1.16
311461142246
1.1.17
スタックがオーバーフローするまで再帰的に呼び出されるので、スタックがオーバーフローするまで停止しません.
1.1.18
変更前:
mystery(2, 25) = 50
mystery(3, 11) = 33
変更後:
mystery(2, 25) = 33554432
mystery(3, 11) = 177147
1.1.19
public class TestApp1 {
private static long[] list = new long[1000];
public static void main(String[] args) {
F(1000);
for(int i = 0; i < list.length; i++) {
if(i > 0 && list[i] == 0) {
break;
}
StdOut.println(i + " " + list[i]);
}
}
public static void F(int N) {
list[0] = 0;
list[1] = 1;
for(int i = 2; i < N; i++) {
list[i] = list[i - 1] + list[i - 2];
if(list[i] < list[i - 1]) {
list[i] = 0;
System.out.println("MAX : " + list[i - 1]);
break;
}
}
}
}最大値は75401138047446346429
1.1.20
public class TestApp1 {
public static void main(String[] args) {
for(int i = 1; i <= 10; i++) {
System.out.println("log_fact(" + i + "): " + log_fact(i));
}
}
private static double log_fact(int n) {
if(n == 1)
return 0;
else
return log_fact(n - 1) + Math.log(n);
}
}1.1.21
import java.util.ArrayList;
import java.util.List;
public class TestApp1 {
public static void main(String[] args) {
List<Info> list = new ArrayList<Info>();
String line;
while(StdIn.hasNextLine()) {
line = StdIn.readLine();
if(line.isEmpty()) {
break;
}
String[] content = line.split(" ");
Info info = new Info(content[0], Integer.parseInt(content[1]), Integer.parseInt(content[2]));
list.add(info);
}
for(Info info : list) {
StdOut.println(info);
}
}
}
class Info {
private String name;
private int x;
private int y;
public Info(String name, int x, int y) {
this.name = name;
this.x = x;
this.y = y;
}
public String toString(){
return "1: " + name + "2: " + x + "3: " + y + "4: " + x * 1.0 / y;
}
}1.1.22
import java.util.ArrayList;
import java.util.List;
public class TestApp1 {
public static void main(String[] args) {
rank(3, new int[]{1, 3, 5, 6, 8, 11, 25, 78, 345, 7653});
}
private static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1, 0);
}
private static int rank(int key, int[] a, int lo, int hi, int depth) {
if(lo > hi)
return -1;
int mid = (lo + hi) / 2;
int loop = depth;
while(loop != 0) {
System.out.print(" ");
loop--;
}
System.out.println("lo:" + lo + " hi:" + hi);
if(key < a[mid])
return rank(key, a, lo, mid - 1, ++depth);
else if(key > a[mid])
return rank(key, a, mid + 1, hi, ++depth);
else
return mid;
}
}1.1.23
import java.util.ArrayList;
import java.util.Arrays;
public class BinarySearch {
private BinarySearch(){}
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while(lo <= hi) {
int mid = (lo + hi) / 2;
if(key < a[mid])
hi = mid - 1;
if(key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
public static void main(String[] args) {
In in = new In(args[0]);
int[] whitelist = in.readAllInts();
Arrays.sort(whitelist);
String flag = args[1];
if("+".equals(flag)) {
while(!StdIn.isEmpty()) {
int key = StdIn.readInt();
if(rank(key, whitelist) == -1) {
StdOut.println(key);
}
}
}else if("-".equals(flag)) {
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if(rank(key, whitelist) != -1) {
StdOut.println(key);
}
}
} else {
StdOut.println("Error Flag");
}
}
}1.1.24
public class GCD {
public static void main(String[] args) {
StdOut.println(gcd(105, 24));
}
public static int gcd(int a, int b) {
StdOut.println("a: " + a + " b: " + b);
if(b == 0)
return a;
else
return gcd(b, a % b);
}
}1.1.25
2つの数をa,b(b
第2ステップ:前提からr=a-kb=mc-knc=(m-kn)c
ステップ3:ステップ2の結果からcもrの因数であることがわかる
第四歩:m-knとnの互質【そうでなければ、m-kn=xd、n=ydとすることができ、(d>1)、m=kn+xd=kyd+xd=(ky+x)d、a=mc=(ky+x)dc、b=nc=ycdとすることができるため、aとbの最大公約数はcdとなり、cではなく、前の結論と矛盾する】
従って、gcd(b,r)=c、次いでgcd(a,b)=gcd(b,r)であることが分かる.
証明が終わる.