回答編集履歴
2
加筆
test
CHANGED
|
@@ -8,10 +8,10 @@
|
|
|
8
8
|
|
|
9
9
|
そして、最初に集合S = {0}を考えます。
|
|
10
10
|
|
|
11
|
-
一番~~小さい~~**大きい**数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
11
|
+
一番~~小さい~~**大きい**数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。**このとき、TにSの要素とUの要素を追加して、Sと置き換えます。**この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
12
12
|
|
|
13
13
|
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
17
|
-
4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一とな
|
|
17
|
+
4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一となる、という致命的な欠陥に気がつきましたので、該当箇所を修正しました。
|
1
アルゴリズムの修正
test
CHANGED
|
@@ -4,8 +4,14 @@
|
|
|
4
4
|
|
|
5
5
|
しかし、計算量を減らす工夫はできます。
|
|
6
6
|
|
|
7
|
-
まず、入力された数字を小さい順に並べ替えます。
|
|
7
|
+
まず、入力された数字を~~小さい順~~**大きい順**に並べ替えます。
|
|
8
8
|
|
|
9
9
|
そして、最初に集合S = {0}を考えます。
|
|
10
10
|
|
|
11
|
-
一番小さい数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
11
|
+
一番~~小さい~~**大きい**数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
|
|
16
|
+
|
|
17
|
+
4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一となり、深さが2^nに比例する、という致命的な欠陥に気がつきましたので、該当箇所を修正しました。
|