トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
Cマガ電脳クラブ(第015回) 1+2-3=0
問題
1から9までの数字を順に並べ、その8か所の「数字の間」に「+」か「-」をいくつか入れて、
計算結果が100になるものを探した。
その結果、
123-45-67+89=100
1+2+34-5+67-8+9=100
を含め、全部で11種の式が見つかった。
この場合、100を目的としたから11種作れたが、どのように「+」や「-」をいれても、
絶対に作ることのできない正の整数の最小値はいくつか。
ソース (逆ポーランド記法を使って計算する方法)
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
const int Jyougen = 165; //仮の上限
var SuusikiList = new List<string>();
var stk = new Stack<string>();
stk.Push("1□2□3□4□5□6□7□8□9");
while (stk.Count > 0) {
string Popped = stk.Pop();
int Ind = Popped.IndexOf('□');
if (Ind == -1) {
SuusikiList.Add(Popped);
continue;
}
string wkStr = Popped.Remove(Ind, 1);
stk.Push(wkStr);
stk.Push(wkStr.Insert(Ind, "+"));
stk.Push(wkStr.Insert(Ind, "-"));
}
var ResultDict = new Dictionary<string, int>();
foreach (string AnyStr in SuusikiList) {
int wkInt = CalcFromRPN(ToRPN(AnyStr));
if (Jyougen < wkInt) continue;
if (wkInt <= 0) continue;
if (ResultDict.ContainsValue(wkInt)) continue;
ResultDict.Add(AnyStr, wkInt);
}
foreach (var AnyPair in ResultDict.OrderBy(X => X.Value).ThenBy(X => X.Key)) {
Console.WriteLine("{0,17} = {1,3}", AnyPair.Key, AnyPair.Value);
}
Console.WriteLine("上限を{0}として、作成可能な数を列挙しました。", Jyougen);
for (int I = 1; I <= ResultDict.Values.Max() - 1; I++) {
if (ResultDict.Values.Contains(I) == false) {
Console.WriteLine("作成不能な正の整数の最小値={0}", I);
break;
}
}
}
//数式を逆ポーランド記法にしたListジェネリックを返す
static List<string> ToRPN(string pTargetStr)
{
var stk = new Stack<string>();
var RPNList = new List<string>();
string[] WkStrArr = MakeNumAndExpArr(pTargetStr);
foreach (string AnyStr in WkStrArr) {
if (AnyStr == "+" || AnyStr == "-") {
int Priority = DerivePriority(AnyStr);
while (stk.Count > 0 && Priority <= DerivePriority(stk.Peek())) {
RPNList.Add(stk.Pop());
}
stk.Push(AnyStr);
}
else RPNList.Add(AnyStr);
}
while (stk.Count > 0) RPNList.Add(stk.Pop());
return RPNList;
}
//数式から数値と演算子の配列を作成
static string[] MakeNumAndExpArr(string pTargetStr)
{
var wkList = new List<string>();
var sb = new System.Text.StringBuilder();
foreach (Char AnyChar in pTargetStr) {
if (AnyChar == '+' || AnyChar == '-') {
wkList.Add(sb.ToString()); sb.Length = 0;
wkList.Add(AnyChar.ToString());
}
else sb.Append(AnyChar);
}
wkList.Add(sb.ToString());
return wkList.ToArray();
}
//演算子のプライオリティを返す
static int DerivePriority(string pOperator)
{
if (pOperator == "+") return 1;
if (pOperator == "-") return 1;
return 0;
}
//逆ポーランド記法のListジェネリックを計算した結果を返す
static int CalcFromRPN(List<string> pRPNList)
{
var stk = new Stack<int>();
foreach (string AnyStr in pRPNList) {
if (AnyStr == "+" || AnyStr == "-") {
int exp2 = stk.Pop();
int exp1 = stk.Pop();
if (AnyStr == "+") stk.Push(exp1 + exp2);
if (AnyStr == "-") stk.Push(exp1 - exp2);
continue;
}
stk.Push(int.Parse(AnyStr));
}
return stk.Pop();
}
}
ソース (正規表現で各項を抽出する方法)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
class Program
{
static void Main()
{
const int Jyougen = 165; //仮の上限
var SuusikiList = new List<string>();
var stk = new Stack<string>();
stk.Push("1□2□3□4□5□6□7□8□9");
while (stk.Count > 0) {
string Popped = stk.Pop();
int Ind = Popped.IndexOf('□');
if (Ind == -1) {
SuusikiList.Add(Popped);
continue;
}
string wkStr = Popped.Remove(Ind, 1);
stk.Push(wkStr);
stk.Push(wkStr.Insert(Ind, "+"));
stk.Push(wkStr.Insert(Ind, "-"));
}
var ResultDict = new Dictionary<string, int>();
foreach (string AnyStr in SuusikiList) {
int wkInt = CalcFromSuusiki(AnyStr);
if (Jyougen < wkInt) continue;
if (wkInt <= 0) continue;
if (ResultDict.ContainsValue(wkInt)) continue;
ResultDict.Add(AnyStr, wkInt);
}
foreach (var AnyPair in ResultDict.OrderBy(X => X.Value).ThenBy(X => X.Key)) {
Console.WriteLine("{0,17} = {1,3}", AnyPair.Key, AnyPair.Value);
}
Console.WriteLine("上限を{0}として、作成可能な数を列挙しました。", Jyougen);
for (int I = 1; I <= ResultDict.Values.Max() - 1; I++) {
if (ResultDict.Values.Contains(I) == false) {
Console.WriteLine("作成不能な正の整数の最小値={0}", I);
break;
}
}
}
//正規表現を使って各項の和を計算
static int CalcFromSuusiki(string pSuusiki)
{
MatchCollection Matches = Regex.Matches(pSuusiki, "[-+]?[1-9]+");
//return Matches.Cast<Match>().Select(X => int.Parse(X.Value)).Sum();
return Matches.Cast<Match>().Sum(X => int.Parse(X.Value));
}
}
実行結果
省略
1-2-3-4+5+6+7+89 = 99
1+2+3-4+5+6+78+9 = 100
1-2+3+4+5-6+7+89 = 101
1+2-3+4+5+6+78+9 = 102
1-2-34+56-7+89 = 103
1-2-3+45-6+78-9 = 104
1-2+3-4+5+6+7+89 = 105
1-2+34+5+67-8+9 = 106
1-2-3-45+67+89 = 107
1-2-34+56+78+9 = 108
1-2-3+45+67-8+9 = 109
1-2+3+45-6+78-9 = 110
1-23+45+6-7+89 = 111
1-2+34-5+67+8+9 = 112
1-2+3-45+67+89 = 113
1-2+34+5-6-7+89 = 114
1-2+3+45+67-8+9 = 115
1-2-3+45+6+78-9 = 116
1-2-3-4+56+78-9 = 117
1-2+34-5-6+7+89 = 118
1-2+34+5-6+78+9 = 119
1-23+4+56-7+89 = 120
1-2+34-5+6+78+9 = 121
1-2-3+45-6+78+9 = 122
1-2+3-4+56+78-9 = 123
123-4+5-6+7+8-9 = 124
1-2-3+4+56+78-9 = 125
1-2-34+5+67+89 = 126
1+2+3-4+56+78-9 = 127
1-2+3+45-6+78+9 = 128
1-2-3+45+6-7+89 = 129
1-2-3-4+56-7+89 = 130
1-2-3+45-6+7+89 = 131
1+2+3+45-6+78+9 = 132
1-23+4-5+67+89 = 133
1-2-3+45+6+78+9 = 134
1-2-3-4+56+78+9 = 135
1-2+3-4+56-7+89 = 136
1-2+3+45-6+7+89 = 137
1-2-3+4+56-7+89 = 138
1+2-3-4+56+78+9 = 139
1-2+3+45+6+78+9 = 140
1-2+3-4+56+78+9 = 141
1+2-3+4+56-7+89 = 142
1-2-3-4-5+67+89 = 143
1-2-3-4+56+7+89 = 144
1+2+3-4+56+78+9 = 145
1+234-5-67-8-9 = 146
1+2-3-4-5+67+89 = 147
1+2-3-4+56+7+89 = 148
1-2+3-4-5+67+89 = 149
1-2+3-4+56+7+89 = 150
1-2-3+4-5+67+89 = 151
1-2-3+4+56+7+89 = 152
1-2-3-4+5+67+89 = 153
1+2+3-4+56+7+89 = 154
1+2-3+4-5+67+89 = 155
1+2-3+4+56+7+89 = 156
1-2+3+4-5+67+89 = 157
1-2+3+4+56+7+89 = 158
1-2+3-4+5+67+89 = 159
1-2-3+4+5+67+89 = 161
1+2+3+4+56+7+89 = 162
1+2+3-4+5+67+89 = 163
1+234-5-67-8+9 = 164
1+2-3+4+5+67+89 = 165
上限を165として、作成可能な数を列挙しました。
作成不能な正の整数の最小値=160
解説
逆ポーランド記法を使って計算するアルゴリズム問題は、小町算が有名ですね。
8-21 小町算