飴ちゃん分配問題
某所で問題出されたので解いてみた。
効率とか出力形式とかはきにしなくていい、というので、まずは思いついたまま
「M個の飴を余りがないようにN人の参加者に分配する。
このとき、飴を1つも貰わない参加者が居てもいい。
参加者名のリストと M, N が与えられたとき、分配のしかたを全て求めよ」例
M=3, N=2
参加者名 ["A", "B"]出力
A=3, B=0
A=2, B=1
A=1, B=2
A=0, B=3
using System; using System.Collections.Generic; namespace candydistribute { class Program { const int MEMBER_NUM = 3; //人数 const int CANDY_NUM = 10; //飴の数 static void Main(string[] args) { //分ける人のリスト作成 List<string> inputnames = new List<string>(); for (int i = 1; i<= MEMBER_NUM; i++) { inputnames.Add("member" + i.ToString()); } destribute(inputnames, CANDY_NUM, ""); } static void destribute(List<string> names, int amount, string for_output) { if(names == null) { Console.WriteLine("ぬるぽ"); } else { int count = names.Count; if (count == 0) { Console.WriteLine("いない人に配れません"); } else { string member = names[0]; if (count == 1) { Console.WriteLine(for_output + string.Format("({0}: {1})", member, amount)); } else { for (int i = 0; i <= amount; i++) { List<string> tmplist = remove_first(names); destribute(tmplist, amount - i, for_output + string.Format("({0}: {1}), ", member, i)); } } } } } //一番前の要素を削除して返す。元のリストからそのままremoveしたらたぶん再帰で呼び出したときに元のリスト変わってしまうのでコピーして返す static List<string> remove_first(List<string> src) { int count = src.Count; string[] tmparr = new string[count - 1]; src.CopyTo(1, tmparr, 0, count - 1); return new List<string>(tmparr); } } }
リストをコピーしてるのでメモリ効率的にとても悪いがとりあえずいいことにする。
直すとしたら、現在何人目の処理してるかを引数とかでとってくるんかな。あとで気が向いたらなおしてみよう。
再帰使って書いたけど、使わないやり方でよさげな方法が思い浮かばん。