アルゴリズムを考える

アルゴリズムというものについて考えてみる

Twitterでこんなツイートを見つけました。

自然数nに対して操作F「nが偶数ならばnを2で割る。nが奇数ならばnを3倍して1を加える。」を10回行う。10回目で初めて1となる自然数を全て求めよ。（０７京都高校生数学コンテスト）

プログラマとしては、さっとプログラムを書いて結果を出してみたくなるのではないでしょうか。

この解を出すアルゴリズムは大きく分けて２通りあります。
その１．1から1024(2^10)までの全ての数についてチェックして探す
その２．結果の「1」から逆に遡って探す

上記その１のアルゴリズムは２重ループによる処理で、その２は再帰による処理になります。
おそらく、この問題で求められている解き方は２の方法でしょう。

書いてみた

view plainprint?

1. import java.util.ArrayList;  
2. import java.util.Collection;  
3.   
4.   
5. public class Main {  
6.   
7.  /* 
8.   * こいつを呼ぶ 
9.   */  
10.  public static void main(String[] x_args) {  
11.   new Main().start();  
12.  }  
13.   
14.  public void start() {  
15.   exec(new F10To1ImplVer1());  
16.   System.out.println();  
17.   exec(new F10To1ImplVer2());  
18.  }  
19.   
20.  void exec(F10To1 x_f) {  
21.   {  
22.    System.out.println(x_f.getClass().getSimpleName() + ":start.");  
23.    long time_s = System.currentTimeMillis();  
24.    int count = 10;  
25.    int end = (int) Math.pow(2, count);  
26.    Collection＜Integer＞ values = x_f.getF10To1(end, count);  
27.    for (Integer value : values) {  
28.     System.out.print(value + "\t");  
29.    }  
30.    long time_e = System.currentTimeMillis();  
31.    System.out.println();  
32.    System.out.println(":end.");  
33.    System.out.println("time => " + (time_e - time_s) + "ms");  
34.   }  
35.  }  
36.    
37. }  
38.   
39. interface F10To1 {  
40.   
41.  /* 
42.   * 戻り値Collection内の要素の順番は保証しない 
43.   */  
44.  Collection＜Integer＞ getF10To1(int x_end, int x_count);  
45. }  
46.   
47. /** 
48.  * 全ての自然数についてチェックするパターン 
49.  */  
50. class F10To1ImplVer1 implements F10To1 {  
51.   
52.  public Collection＜Integer＞ getF10To1(int x_end, int x_count) {  
53.   Collection＜Integer＞ result = new ArrayList＜Integer＞();  
54.   // 1...最後までのループ  
55.   for (int i = 1 ; i <= x_end ; i++) {  
56.    if (isF10To1(i, x_count)) {  
57.     result.add(Integer.valueOf(i));  
58.    }  
59.   }  
60.   return result;  
61.  }  
62.   
63.  private boolean isF10To1(int x_value, int x_count) {  
64.   int tmp = x_value;  
65.   // 9回処理する  
66.   for (int i = 0 ; i < x_count - 1 ; i++) {  
67.    tmp = f(tmp);  
68.    if (tmp == 1) {  
69.     // 1になったら対象外  
70.     return false;  
71.    }  
72.   }  
73.   // 10回目  
74.   tmp = f(tmp);  
75.   return tmp == 1;  
76.  }  
77.   
78.  /* 
79.   * 1回分の処理 
80.   */  
81.  private int f(int x_value) {  
82.   if (x_value % 2 == 0) {  
83.    return x_value / 2;  
84.   }  
85.   return x_value * 3 + 1;  
86.  }  
87. }  
88.   
89. /** 
90.  * 逆から辿るパターン 
91.  */  
92. class F10To1ImplVer2 implements F10To1 {  
93.   
94.  public Collection＜Integer＞ getF10To1(int x_end, int x_count) {  
95.   int tmp = 1;  
96.   // 再帰処理でチェックします  
97.   Collection＜Integer＞ result = new ArrayList＜Integer＞();  
98.   revF(result, tmp, x_count);  
99.   return result;  
100.  }  
101.   
102.  private void revF(Collection＜Integer＞ x_values, int x_value, int count) {  
103.   boolean can3 = canRevF_3(x_value);  
104.   int v2 = revF_2(x_value);  
105.   int v3 = revF_3(x_value);  
106.   count--;  
107.   if (count < 1) {  
108.    if (can3) {  
109.     x_values.add(Integer.valueOf(v3));  
110.    }  
111.    x_values.add(Integer.valueOf(v2));  
112.    return;  
113.   }  
114.   if (can3 && (1 < v3)) {  
115.    revF(x_values, v3, count);  
116.   }  
117.   if (v2 != 1) {  
118.    revF(x_values, v2, count);  
119.   }  
120.  }  
121.   
122.  /* 
123.   * 引数が2で割った結果だとした場合の元の数を返す 
124.   */  
125.  private int revF_2(int x_value) {  
126.   return x_value * 2;  
127.  }  
128.   
129.  /* 
130.   * 引数が3倍して1を足した結果だとした場合に元の数が存在するか判断する 
131.   */  
132.  private boolean canRevF_3(int x_value) {  
133.   if (x_value < 4) {  
134.    return false;  
135.   }  
136.   if ((x_value - 1) % 3 != 0) {  
137.    return false;  
138.   }  
139.   return (x_value - 1) / 3 % 2 == 1;  
140.  }  
141.   
142.  /* 
143.   * 引数が3倍して1を足した結果だとした場合の元の数を返す 
144.   */  
145.  private int revF_3(int x_value) {  
146.   return (x_value - 1) / 3;  
147.  }  
148. }  

import java.util.ArrayList;
import java.util.Collection;


public class Main {

 /*
  * こいつを呼ぶ
  */
 public static void main(String[] x_args) {
  new Main().start();
 }

 public void start() {
  exec(new F10To1ImplVer1());
  System.out.println();
  exec(new F10To1ImplVer2());
 }

 void exec(F10To1 x_f) {
  {
   System.out.println(x_f.getClass().getSimpleName() + ":start.");
   long time_s = System.currentTimeMillis();
   int count = 10;
   int end = (int) Math.pow(2, count);
   Collection＜Integer＞ values = x_f.getF10To1(end, count);
   for (Integer value : values) {
    System.out.print(value + "\t");
   }
   long time_e = System.currentTimeMillis();
   System.out.println();
   System.out.println(":end.");
   System.out.println("time => " + (time_e - time_s) + "ms");
  }
 }
 
}

interface F10To1 {

 /*
  * 戻り値Collection内の要素の順番は保証しない
  */
 Collection＜Integer＞ getF10To1(int x_end, int x_count);
}

/**
 * 全ての自然数についてチェックするパターン
 */
class F10To1ImplVer1 implements F10To1 {

 public Collection＜Integer＞ getF10To1(int x_end, int x_count) {
  Collection＜Integer＞ result = new ArrayList＜Integer＞();
  // 1...最後までのループ
  for (int i = 1 ; i <= x_end ; i++) {
   if (isF10To1(i, x_count)) {
    result.add(Integer.valueOf(i));
   }
  }
  return result;
 }

 private boolean isF10To1(int x_value, int x_count) {
  int tmp = x_value;
  // 9回処理する
  for (int i = 0 ; i < x_count - 1 ; i++) {
   tmp = f(tmp);
   if (tmp == 1) {
    // 1になったら対象外
    return false;
   }
  }
  // 10回目
  tmp = f(tmp);
  return tmp == 1;
 }

 /*
  * 1回分の処理
  */
 private int f(int x_value) {
  if (x_value % 2 == 0) {
   return x_value / 2;
  }
  return x_value * 3 + 1;
 }
}

/**
 * 逆から辿るパターン
 */
class F10To1ImplVer2 implements F10To1 {

 public Collection＜Integer＞ getF10To1(int x_end, int x_count) {
  int tmp = 1;
  // 再帰処理でチェックします
  Collection＜Integer＞ result = new ArrayList＜Integer＞();
  revF(result, tmp, x_count);
  return result;
 }

 private void revF(Collection＜Integer＞ x_values, int x_value, int count) {
  boolean can3 = canRevF_3(x_value);
  int v2 = revF_2(x_value);
  int v3 = revF_3(x_value);
  count--;
  if (count < 1) {
   if (can3) {
    x_values.add(Integer.valueOf(v3));
   }
   x_values.add(Integer.valueOf(v2));
   return;
  }
  if (can3 && (1 < v3)) {
   revF(x_values, v3, count);
  }
  if (v2 != 1) {
   revF(x_values, v2, count);
  }
 }

 /*
  * 引数が2で割った結果だとした場合の元の数を返す
  */
 private int revF_2(int x_value) {
  return x_value * 2;
 }

 /*
  * 引数が3倍して1を足した結果だとした場合に元の数が存在するか判断する
  */
 private boolean canRevF_3(int x_value) {
  if (x_value < 4) {
   return false;
  }
  if ((x_value - 1) % 3 != 0) {
   return false;
  }
  return (x_value - 1) / 3 % 2 == 1;
 }

 /*
  * 引数が3倍して1を足した結果だとした場合の元の数を返す
  */
 private int revF_3(int x_value) {
  return (x_value - 1) / 3;
 }
}

もしかしたら上記の実装に間違いがあるかもしれません。その場合は、ご指摘いただけるとありがたいです。
F10To1ImplVer1が総当り(その１)で、F10To1ImplVer2が再帰処理を行う(その２)クラスです。
10回程度のループではそれほど差が出ません(マシンにもよります)が、20回程に回数を増やすと極端に処理時間に差が出ます。

上記の２通りのアルゴリズムで、私が先に書いたのは総当り(その１)の方です。
その後、少し考えてその２の方法を書きました。

普段から簡単にプログラムを書こうとしているせいか、「本来はどういうアルゴリズムであるべきか」をあまり考えなくなってしまったようです。

私は細かい実装はあまり気にしないのですが、気にせずともより良いアルゴリズムで書けるのが理想的ですね。