ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

自然数 n に対して、次の等式を考えます。

    □1□2□3□4…□n = 0

四角の部分には、プラス(+)またはマイナス(-)の記号が入ります。

等式を成立させるような記号の入れ方を考えましょう。

例えば、n = 7 のとき、次の 8 通りの入れ方が可能です。

+1+2-3+4-5-6+7 = 0
+1+2-3-4+5+6-7 = 0
+1-2+3+4-5+6-7 = 0
+1-2-3-4-5+6+7 = 0
-1+2+3+4+5-6-7 = 0
-1+2-3-4+5-6+7 = 0
-1-2+3+4-5-6+7 = 0
-1-2+3-4+5+6-7 = 0

自然数 n に対し、等式を成立させる記号の入れ方の数を F(n) と定義します。

例えば F(7) = 8 です。

同様に、F(3) = 2、F(8) = 14 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 50)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針

等式を成立させる記号の入れ方の数を求める問題です。

ぱっと思いつく解法は、記号の入れ方の全てのパターンを列挙して、左辺がゼロになるかどうかを確かめるというものです。しかし、本問では n の上限が 50 ですから、全ての組み合わせは 250 ≒ 1015 通りです。あまりに膨大な数ですので、他のアプローチをとらねばなりません。

そこで、次の G(n, s) を新たに定義しましょう。

  G(n, s) : □1□2□3□4…□n = s となる記号の入れ方の数.

G(n, s) は、F(n) をより一般化したものです。s = 0 とした G(n, 0) が、求めるべき F(n) です。

さて、G(n, s) を求めるにはどうすればよいでしょうか。ここで役に立つ考え方が、一つ手前の状態を考えることです。ここでいう一つ手前の状態とは、n の一つ前、つまり n-1 までの部分を指します。すべての s に対する G(n-1, s) の値が分かっていたとして、これらの値を用いて G(n, s) を表せないだろうか? と考えてみましょう。要するに、G(n, s) の漸化式を導出することが、本問を解くポイントです。

そこで、G(n, s) の値を、□1□2□3□4…□(n-1)□n の最後の□にプラスとマイナスのどちらが入るかで場合分けしてみましょう。プラスの場合は、n-1 までの部分 □1□2□3□4…□(n-1) が s-n に等しければ、全体は s に等しくなります。そのような記号の入れ方は G(n-1, s-n) 通りです。一方、最後の□がマイナスの場合は、n-1 までの部分が s+n に等しければ、全体は s に等しくなります。そのような記号の入れ方は G(n-1, s+n) 通りです。結局のところ、G(n, s) とはこのいずれかですから、G(n, s) = G(n-1, s-n) + G(n-1, s+n) という漸化式が導き出せます。

あとは、漸化式を解くコードを書けばOKです。さまざまな s に対する G(n, s) の値を保存するためのデータ構造を用意します。n = 0 の場合の G(n, s) の値は、s = 0 のときのみ 1、それ以外では 0 です。これらを初期値として、n についてのループ文を書き、保存された値を次々と更新していきましょう。

コード例は以下です(C++)。G(n, s) の値を std::map で保存しています。s の正負がひっくり返っても G(n, s) の値が変わらないことを利用し、s が負のときの計算を省いています。

#include <iostream>
#include <map>
#include <cstdlib>
using namespace std;

int main()
{
int n;
cin >> n;
map<int, long long> d, d_new;
d[0] = 1;
for (int i = 1; i

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP