今天不算二十四
--------------------编程问答--------------------
using System;
using System.Collections;
using System.Diagnostics;
namespace SixtyFour
{
/// <summary>
/// Expression with fraction support
/// </summary>
class Expression
{
int numerator, denominator, precedence;
string oper;
Expression opnd1, opnd2;
public Expression(int val)
{
numerator = val;
denominator = 1;
precedence = 3;
oper = null;
opnd1 = null;
opnd2 = null;
}
public bool Succeed()
{
return (numerator == 64) && (denominator == 1);
}
static int g_c_d(int v1, int v2)
{
v1 = Math.Abs(v1);
v2 = Math.Abs(v2);
while (v1 != 0)
{
int t = v2 % v1;
v2 = v1;
v1 = t;
}
return v2;
}
/// <summary>
/// Creat a new expression to store operation result
/// </summary>
/// <param name="num">Numerator</param>
/// <param name="den">Denominator</param>
/// <param name="op">Operation</param>
/// <param name="pre">Precedence</param>
/// <param name="opnd2">Second operand</param>
/// <returns></returns>
Expression Oper(int num, int den, string op, int pre, Expression opnd2)
{
if ((den == 0) || (num < 0)) // Reject negative number and divide by 0
{
return null;
}
int d = g_c_d(num, den);
Expression exp = new Expression(1);
exp.precedence = pre;
exp.numerator = num / d;
exp.denominator = den / d;
exp.oper = op;
exp.opnd1 = this;
exp.opnd2 = opnd2;
return exp;
}
public Expression Add(Expression v)
{
return Oper(numerator * v.denominator + denominator * v.numerator,
denominator * v.denominator,
"+", 1, v);
}
public Expression Sub(Expression v)
{
return Oper(numerator * v.denominator - denominator * v.numerator,
denominator * v.denominator,
"-", 1, v);
}
public Expression Mul(Expression v)
{
return Oper(numerator * v.numerator,
denominator * v.denominator,
"*", 2, v);
}
public Expression Div(Expression v)
{
return Oper(numerator * v.denominator,
denominator * v.numerator,
"/", 2, v);
}
/// <summary>
/// Full string representation for debugging
/// </summary>
public override string ToString()
{
string exp = null;
if (this.oper == null)
{
Debug.Assert(this.denominator == 1);
exp = numerator.ToString();
}
else
{
string exp1 = this.opnd1.ToString();
string exp2 = this.opnd2.ToString();
if (opnd1.precedence != 3)
{
exp1 = "(" + exp1 + ")";
}
if (opnd2.precedence != 3)
{
exp2 = "(" + exp2 + ")";
}
exp = exp1 + oper + exp2;
}
return exp;
}
/// <summary>
/// Gather terms in a sorted list
/// </summary>
/// <param name="list">Output list</param>
/// <param name="pre">precedence</param>
/// <param name="negative">"-" or "/"</param>
void GatherTerms(ArrayList list, int pre, bool negative)
{
if (this.precedence == pre)
{
this.opnd1.GatherTerms(list, pre, negative);
this.opnd2.GatherTerms(list, pre, negative ^ ((oper == "-") || (oper == "/")));
}
else
{
string term = Exp();
if (precedence < pre)
{
term = "(" + term + ")";
}
if (negative) // add prefix for "-" or "/"
{
if (pre == 1)
{
term = "-" + term;
}
else if (pre == 2)
{
term = "/" + term;
}
}
int pos = list.Count;
for (int i = 0; i < list.Count; i++)
{
string s = list[i] as string;
bool before;
bool neg1 = (s[0] == '-') || (s[0] == '/');
bool neg2 = (term[0] == '-') || (term[0] == '/');
if (neg1 ^ neg2) // not the same
{
before = neg1;
}
else
{
before = String.Compare(term, s) > 0;
}
if (before)
{
pos = i;
break;
}
}
list.Insert(pos, term);
}
}
/// <summary>
/// Normalized string representation
/// </summary>
public string Exp()
{
string exp = null;
if (this.oper == null)
{
Debug.Assert(denominator == 1);
exp = numerator.ToString();
}
else
{
ArrayList terms = new ArrayList();
// Gather all terms of the same precedence in a sorted list
opnd1.GatherTerms(terms, precedence, false);
opnd2.GatherTerms(terms, precedence, (oper == "-") || (oper == "/"));
exp = "";
string op = null;
if (precedence == 1)
{
op = "+";
}
else if (precedence == 2)
{
op = "*";
}
foreach (string s in terms)
{
// Add operator if needed
if ((exp != "") && ((s[0] != '-') && (s[0] != '/')))
{
exp = exp + op + s;
}
else
{
exp = exp + s;
}
}
}
return exp;
}
}
/// Algorithm for solving 64 problem using full search
class SixtyFour
{
private ArrayList solutions = new ArrayList();
void Solve1(Expression[] values, int i, int j, Expression v)
{
if (v != null)
{
Expression[] newv = new Expression[values.Length - 1];
int l = 0;
for (int k = 0; k < values.Length; k++)
if ((k != i) && (k != j))
{
newv[l++] = values[k];
}
newv[l] = v;
Solve(newv);
}
}
--------------------编程问答--------------------
void Solve(Expression[] values)
{
if (values.Length == 1)
{
if (values[0].Succeed())
{
bool dup = false;
string exp = values[0].Exp();
// Remove duplication
foreach (string s in solutions)
{
if (s == exp)
{
dup = true;
break;
}
}
if (!dup)
{
solutions.Add(exp);
Console.WriteLine("{0}: {1} \t {2}", solutions.Count, exp, values[0].ToString());
}
}
return;
}
for (int i = 0; i < values.Length; i++)
for (int j = i + 1; j < values.Length; j++)
{
Solve1(values, i, j, values[i].Add(values[j]));
Solve1(values, i, j, values[i].Sub(values[j]));
Solve1(values, j, i, values[j].Sub(values[i]));
Solve1(values, i, j, values[i].Mul(values[j]));
Solve1(values, i, j, values[i].Div(values[j]));
Solve1(values, j, i, values[j].Div(values[i]));
}
}
static void Solve(int v1, int v2, int v3, int v4)
{
Expression[] values = new Expression[4];
values[0] = new Expression(v1);
values[1] = new Expression(v2);
values[2] = new Expression(v3);
values[3] = new Expression(v4);
Console.WriteLine("{0} {1} {2} {3} ->", v1, v2, v3, v4);
SixtyFour solver = new SixtyFour();
solver.Solve(values);
Console.WriteLine();
}
[STAThread]
static void Main(string[] args)
{
Solve(3, 8, 8, 8);
Solve(3, 3, 8, 8);
Solve(5, 6, 6, 7);
Solve(4, 5, 8, 7);
}
}
}
--------------------编程问答-------------------- mark 原来算64 被骗进来了 --------------------编程问答-------------------- 收藏了 --------------------编程问答-------------------- 关注！！
3 8 8 8 ->
3 3 8 8 ->
1: 8*8+3-3 (3-3)+(8*8)
2: 8*(8+3-3) 8*(8+(3-3))
3: 8*3*3-8 (8*(3*3))-8
4: 8*8*3/3 (3/3)*(8*8)
5 6 6 7 ->
4 5 8 7 ->
1: 8*(7+5-4) 8*(7+(5-4))
2: 8*4*(7-5) (4*8)*(7-5)
--------------------编程问答-------------------- 64是什么玩意？ --------------------编程问答-------------------- 学习 --------------------编程问答--------------------
90后的？
--------------------编程问答-------------------- 完全不明白呀。。
啥玩意。 --------------------编程问答-------------------- ms很好很强大 --------------------编程问答-------------------- 什么东西，讲一下 --------------------编程问答-------------------- 可以收藏啊! --------------------编程问答-------------------- 好快啊， 有到 64 了 --------------------编程问答-------------------- 前还是24。。。怎么这么快。。。呵 --------------------编程问答-------------------- 欢迎袁峰大牛来这里分享。。。
--------------------编程问答--------------------
记录一下
--------------------编程问答--------------------
private const double Precision = 1E-6; // 精度
private bool fSearchExpression(double[] ANumbers, string[] AExpressions,
int ALevel, int ADest, List<string> AResults)
{
bool Result = false;
if ((ALevel <= 1) && (Math.Abs(ANumbers[0] - ADest) <= Precision))
{
AResults.Add(AExpressions[0]);
return true;
}
for (int i = 0; i < ALevel; i++)
for (int j = i + 1; j < ALevel; j++)
{
double A = ANumbers[i];
double B = ANumbers[j];
ANumbers[j] = ANumbers[ALevel - 1];
string vExpA = AExpressions[i];
string vExpB = AExpressions[j];
AExpressions[j] = AExpressions[ALevel - 1];
AExpressions[i] = '(' + vExpA + '+' + vExpB + ')';
ANumbers[i] = A + B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
AExpressions[i] = '(' + vExpA + '-' + vExpB + ')';
ANumbers[i] = A - B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
AExpressions[i] = '(' + vExpB + '-' + vExpA + ')';
ANumbers[i] = B - A;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
AExpressions[i] = '(' + vExpA + '*' + vExpB + ')';
ANumbers[i] = A * B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
if (B != 0)
{
AExpressions[i] = '(' + vExpA + '/' + vExpB + ')';
ANumbers[i] = A / B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
}
if (A != 0)
{
AExpressions[i] = '(' + vExpB + '/' + vExpA + ')';
ANumbers[i] = B / A;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
}
ANumbers[i] = A;
ANumbers[j] = B;
AExpressions[i] = vExpA;
AExpressions[j] = vExpB;
}
return Result;
}
private bool SearchExpression(List<string> AResults, int ADest, params int[] ANumbers)
{
double[] vNumbers = new double[ANumbers.Length];
string[] vExpressions = new string[ANumbers.Length];
for (int i = 0; i < ANumbers.Length; i++)
{
vNumbers[i] = ANumbers[i];
vExpressions[i] = ANumbers[i].ToString();
}
return fSearchExpression(vNumbers, vExpressions, ANumbers.Length, ADest, AResults);
}
private void button1_Click(object sender, EventArgs e)
{
List<string> vExpressions = new List<string>();
SearchExpression(vExpressions, 64, 4, 5, 8, 7);
foreach (string vExpression in vExpressions)
Console.WriteLine(vExpression + "\r\n");
}
表达式不够美观。。。[img=http://p.blog.csdn.net/images/p_blog_csdn_net/zswang/%E5%B7%A5%E4%BD%9C.gif]图[/img] --------------------编程问答-------------------- 为了忘却的记忆 --------------------编程问答-------------------- 下次算128! --------------------编程问答-------------------- 景仰。 --------------------编程问答-------------------- 啥意思？ --------------------编程问答-------------------- 什么东西来的呀？ --------------------编程问答-------------------- 学习 --------------------编程问答-------------------- mark
lz能简单讲个算法不。 --------------------编程问答-------------------- mark时必须的呀~~~ --------------------编程问答-------------------- 规范呀。 ~~ --------------------编程问答-------------------- 不知道在主页上出现的这个“今天不算二十四”是啥子意思？ --------------------编程问答-------------------- 不懂,楼主讲讲吧 --------------------编程问答-------------------- 路过 --------------------编程问答-------------------- 看看！ --------------------编程问答-------------------- 跳大神？ --------------------编程问答-------------------- --------------------编程问答-------------------- 终于看明白了。原来是算64...... --------------------编程问答-------------------- 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=64
=.= --------------------编程问答-------------------- 虽然24以后，但是我们不会忘记 --------------------编程问答-------------------- 大家看清楚啊，是six four，ninteen years ago.....................
补充：.NET技术 , C#
