2014年12月21日

C#で自然数をm個の和で表す全パターンを求める

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その58

この問題のオリジナルタイトルは、「自然数の分割」です。

■問題 (出題者:herumiさん)
自然数nとm(n>=m>0)が与えられたとき,nをm個の非負の整数の和で表すやり方を全て出力してください. その際,和の組(x_1, ..., x_m)は大きい順に出力してください. ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)のいずれかが成り立つとき(つまりは辞書的順序)とします.
    
例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する.
以下、C#のコード。
コメントにある通り、再帰処理で解を求めています。
Solveの第3引数は、答えが格納されるリストです。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Solver sol = new Solver();
            sol.Solve(5,2);
            Console.ReadLine();
        }
    }

    // 再帰呼び出しを使ってる。
    class Solver {
        public void  Solve(int n, int m) {
            Solve(n,m, new List<int>());
        }

        public void Solve(int n, int m, List<int> ans) {
            if (m == 0) {
                if (n == 0) {
                    // めんどくさいので、答えが見つかった時点で印刷。
                    // コンソールアプリ専用。
                    ans.ForEach(x => Console.Write("{0}, ", x));
                    Console.WriteLine();
                }
            } else {
                // 大きい順に出力するために、n, n-1, n-2... と処理していく
                for (int k = n; k >= 0; k--) {
                    ans.Add(k);
                    Solve(n-k, m-1, ans);
                    ans.RemoveAt(ans.Count - 1);
                }
            }
        }
    }
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52394335