cjf068
- 浏览: 34408 次
- 性别:
- 来自: 北京
-
最新评论
-
cjf068：
LuckYes 写道楼主如果用最小堆的话，最好用调整堆的方式来 ...
求最小的k个数问题 -
LuckYes：
楼主如果用最小堆的话，最好用调整堆的方式来构建堆，这样效率更高 ...
求最小的k个数问题 -
cjf068：
这个算法的基本思路， ...
大数乘法 -
liujunsong：
这个算法的基本思路，是小学3年级的 算法，就是简单的把乘法运算 ...
大数乘法 -
shuidexiongdi：
去年我也写了一个http://shuidexiongdi.it ...
大数乘法
计算n个数的全排列
计算24点，简单表达式计算
package org.jf.alg.stack;
import java.util.List;
import java.util.ArrayList;
public class PermUtil {
/**
* @param args
*/
public static void main(String[] args)
{
List<String[]> list = perm(new String[]{"a","b","c","d"},0,4,null);
List<String> source = new ArrayList<String>();
String ss [] = list.get(0);
for(String s:ss)
{
source.add(s);
}
List<List<String>> container = new ArrayList<List<String>>();
System.out.println(container.size());
// for(String[] ss:list)
// {
// printArray(ss);
// }
System.out.println(list.size());
}
/**
*
* void perm (char *a, const int k，const int n) {
// n 是数组a的元素个数，生成a[k],…,a[n-1]的全排列
int i;
if (k = = n-1) { // 终止条件，输出排列
for ( i=0; i<n; i++) cout << a[i] << “ ”; // 输出包括前
// 缀，以构成整个问题的解
cout << endl;
}
else { // a[k],…,a[n-1] 的排列大于1，递归生成
for ( i = k; i < n; i++) {
char temp = a[k]; a[k] = a[i]; a[i] = temp; // 交换a[k]
// 和 a[i]
perm(a,k+1,n); // 生成 a[k+1],…,a[n-1]的全排列
temp = a[k]; a[k] = a[i]; a[i] = temp; // 再次交换 a[k] 和
// a[i] , 恢复原顺序
}
} // else结束
} // perm结束
* 求全排列
* @param s
* @param start
* @param end
* @return
*/
public static List<String[]> perm(String []s,int k,int n,List<String[]> result)
{
List<String[]> result1= result;
if (k == n-1)
{
String ss [] = new String[s.length];
for( int i = 0;i<=n-1; i++)
{
ss[i] = s[i];
}
if(result1==null)
result1 = new ArrayList<String[]>();
result1.add(ss);
}else
{
for(int i = k;i<n;i++)
{
String tmp = s[k];
s[k] = s[i];
s[i] = tmp;
result1 = perm(s,k+1,n,result1);
tmp = s[k];
s[k] = s[i];
s[i] = tmp;
}
}
return result1;
}
static void printArray(String[] a)
{
for(String s:a)
{
System.out.print(s+" ");
}
System.out.println();
}
}
计算24点，简单表达式计算
package org.jf.alg.stack;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
public class OperationUtil
{
/**
* 中缀表达式转为后缀表达式
* (1)获取下一个输入标记
* (2)如果标记是:
* 左括号:将其压入表达式栈
* 右括号:连续弹出并显示栈中的元素，直到遇到一个左括号
* 一个运算符:如果栈为空，或者标记具有比栈顶元素更高的优先级，则将其压入栈中，否则弹出并显示
* 栈顶元素；接着继续比较标记和新的栈顶元素
* 一个操作数:显示它
* (3)当到到中缀表达式结尾时，弹出并显示栈中的元素直到栈空
* @param middleFixString
* @param fraction
* @return
*/
public static List<String> toPostfixExp(String middleFixString,boolean fraction)
{
Stack<String> opSt = new Stack<String>();
List<String> postExpList = new ArrayList<String>();
List<String> eleList = getElementList(middleFixString,fraction);
for(String ele:eleList)
{
char c = ele.charAt(0);
if(ele.length()==1 && !(c>='0' && c<='9'))
{
switch(c)
{
case '(' :
opSt.push(ele);
break ;
case ')' :
for(;;)
{
if(opSt.isEmpty())
break;
String op = opSt.pop();
if(op .equals("("))
break;
postExpList.add(op);
}
break ;
default:
if(opSt.isEmpty())
opSt.push(ele);
else
{//比较优先级
while(!opSt.isEmpty())
{
char opTop = opSt.peek().charAt(0);
if(opSt.isEmpty()||opTop == '(')
{
opSt.push(ele);
break;
}
if(getPriority(c)>getPriority(opTop))
{
opSt.push(ele);
break;
}
else
{
postExpList.add(opSt.pop());
opSt.push(ele);
break;
}
}
}
}
}
else
{
postExpList.add(ele);
}
}
while(!opSt.isEmpty())
{
postExpList.add(opSt.pop());
}
return postExpList;
}
private static List<String> getElementList(String middleFixExp,boolean fraction)
{
List<String> list = new ArrayList<String>();
char [] seprator = null;
if(fraction)
seprator = new char[]{'+','-','*','(',')'};
else
seprator = new char[]{'+','-','/','*','(',')'};
int opBeginIndx = -1;
boolean isOperator = false;
for(int i=0;i<middleFixExp.length();i++)
{
char curChar = middleFixExp.charAt(i);
isOperator = false;
for(int j=0;j<seprator.length;j++)
{
if(seprator[j] == curChar)
{
if(opBeginIndx != -1)
list.add(middleFixExp.substring(opBeginIndx, i));
list.add(curChar+"");
isOperator = true;
opBeginIndx = -1;
break;
}
}
if(isOperator)
continue;
if(opBeginIndx == -1)
opBeginIndx = i;
}
if(opBeginIndx != -1)
list.add(middleFixExp.substring(opBeginIndx));
return list;
}
public static String evaluate(String exp,boolean fraction) throws Exception
{
Stack<String> sta = new Stack<String>();
List<String> list = toPostfixExp(exp,fraction);
String s ="";
while(list.size()>0)
{
s = list.remove(0);
if(s.length()==1 && !(s.charAt(0)>='0'&&s.charAt(0)<='9'))
{
String y = sta.pop();
String x = sta.pop();
if("+-*/".indexOf(s)>=0)
{
String result = "";
if(fraction)
result =caculateFraction(x,y,s.charAt(0));
else
result =caculateInteger(x,y,s.charAt(0));
sta.push(result);
}
else throw new RuntimeException("not support operator:"+s);
}
else
{
sta.push(s);
}
}
return sta.pop();
}
public static String evaluate(List<String> postfix_exp,boolean fraction) throws Exception
{
Stack<String> sta = new Stack<String>();
String s ="";
while(postfix_exp.size()>0)
{
s = postfix_exp.remove(0);
if(s.length()==1 && !(s.charAt(0)>='0'&&s.charAt(0)<='9'))
{
String y = sta.pop();
String x = sta.pop();
if("+-*/".indexOf(s)>=0)
{
String result = "";
if(fraction)
result =caculateFraction(x,y,s.charAt(0));
else
result =caculateInteger(x,y,s.charAt(0));
sta.push(result);
}
else throw new RuntimeException("not support operator:"+s);
}
else
{
sta.push(s);
}
}
return sta.pop();
}
private static String caculateInteger(String x,String y,char operator)throws Exception
{
int px = Integer.parseInt(x);
int py = Integer.parseInt(y);
int result = 0;
switch(operator)
{
case '+':
result = px + py;
break;
case '-' :
result = px - py ;
break;
case '*' :
result = px * py;
break;
case '/' :
result = px / py;
break;
}
return result+"";
}
private static String caculateFraction(String x,String y,char operator)
{
int dx = 1, dy = 1,nx = 1, ny = 1;
if(x.indexOf("/")>0)
{
dx = Integer.parseInt(x.substring(x.indexOf("/")+1));
nx = Integer.parseInt(x.substring(0,x.indexOf("/")));
}else
{
nx = Integer.parseInt(x);
}
if(y.indexOf("/")>0)
{
dy = Integer.parseInt(y.substring(y.indexOf("/")+1));
ny = Integer.parseInt(y.substring(0,y.indexOf("/")));
}else
{
ny = Integer.parseInt(y);
}
String s = "";
int sn = 0;
int sd = 1;
switch(operator)
{
case '+':
sn = nx*dy+ny*dx;
sd = dx*dy;
break;
case '-':
sn = nx*dy-ny*dx;
sd = dx*dy;
if(sn%sd==0)
s = (sn/sd)+"";
else
s = sn+"/"+sd;
break;
case '*':
sn = nx*ny;
sd = dx*dy;
break;
case '/':
sn = nx*dy;
sd = ny*dx;
break;
}
if(sn%sd==0)
s = (sn/sd)+"";
else
s = sn+"/"+sd;
return s;
}
private static int getPriority(char operator)
{
switch(operator)
{
case '+':
return 0;
case '-':
return 0;
case '*' :
return 1;
case '/' :
return 1;
case '%' :
return 1;
default :
return -1;
}
}
/**
*
* @param source 操作数集合
* @return
*/
public static List<List<String>> getAllPostfixExp(List<String> source)
{
List<List<String>> container = new ArrayList<List<String>>();
Stack<String> st = new Stack<String>();
st.push(source.get(0));
fn2(source,1,true,source.size()-1,st,container);
// fn(source,1,st,container);
return container;
}
/**
*
* @param source
* @param k
* @param st
* @param container
*/
private static void fn(List<String> source,int k,Stack<String> st,List<List<String>> container)
{
if(container == null)
throw new RuntimeException("container is null");
String []operators = new String[]{"+","-","/","*"};
if(k>=source.size())
return;
st.push(source.get(k));
for(String op:operators)
{
st.push(op);
if(k==source.size()-1)
{
List<String> sta = new ArrayList<String>();
sta.addAll(st);
container.add(sta);
}else
{
fn(source,k+1,st,container);
}
st.pop();
}
st.pop();
}
/**
*
* @param source
* @param k 当前插入序号
* @param st
* @param rest_operator_num 还剩几个操作符没有插入
* @param container
*/
private static void fn2(List<String> source,int k,boolean push,
int rest_operator_num,Stack<String> st,List<List<String>> container)
{
if(container == null)
throw new RuntimeException("container is null");
String []operators = new String[]{"+","-","/","*"};
if(k>=source.size())
return;
if(push)
st.push(source.get(k));
//本次最多能插入的操作符个数
int max_num = rest_operator_num-(source.size()-1-k);
if(k == source.size()-1)//将剩余的所有操作符推入
{
for(int j=0;j<max_num;j++)
{
for(String op:operators)
{
st.push(op);
if(j == max_num-1)
{
List<String> sta = new ArrayList<String>();
if(st.size()==source.size()*2-1)//有一bug 计算出来的表达式比实际的多 尚未找到bug出在哪里 尚且在此判断 去除不合法的表达式
{
sta.addAll(st);
container.add(sta);
}
}else
{
fn2(source,k,false,max_num-j-1,st,container);//?
}
st.pop();
}
}
}else
{
for(int i=0;i<=max_num;i++)
{
if(i!=0)//push i 个操作符
pushOperator(i,source,k,false,rest_operator_num-i,st,container);
else if(i ==0)
{
fn2(source,k+1,true,rest_operator_num,st,container);
}
}
}
if(push)
st.pop();
}
private static void pushOperator(int num,
List<String> source,int k,boolean push,
int rest_operator_num,Stack<String> st,List<List<String>> container)
{
String []operators = new String[]{"+","-","/","*"};
if(num<1)
return;
for(String op:operators)
{
st.push(op);
if(num == 1)
{
fn2(source,k+1,true,rest_operator_num,st,container);
}
else
{
pushOperator(num-1,source,k,push,rest_operator_num,st,container);
}
st.pop();
}
}
public static void main(String args[])
{
// System.out.println(Integer.parseInt("4/5"));
List<String> source = new ArrayList<String>();
source.add("2");
source.add("2");
source.add("4");
source.add("8");
// List<List<String>> container = getAllPostfixExp(source);
// System.out.println(container.size());
// String s ="+";
// System.out.println(s.length()==0 && !(s.charAt(0)>='0'&&s.charAt(0)<='9'));
// List<String> list = toPostfixExp("12+((3*(2-4/5))+5)*3",true);
// System.out.println(OperationUtil.evaluate("3+2-9/4", true));
// List<List<String>> all = getAllPostfixExp(source);
// for(int i=0;i<all.size();i++)
// {
//
// for(String s:all.get(i))
// {
// System.out.print(s+" ");
// }
// System.out.println();
// }
// System.out.println(all.size());
long begin = System.currentTimeMillis();
// find24(new String[]{"4","5","5","1","6"});
find24(new String[]{"8","3","8","3"});
long end = System.currentTimeMillis();
System.out.println(end-begin);
// test8383();
}
public static void find24(String [] ops)
{
List<String[]> list = PermUtil.perm(ops, 0, ops.length, null);
for(String ss[]:list)
{
List<String> list1 = new ArrayList<String>();
for(String s:ss)
{
list1.add(s);
}
List<List<String>> expList = getAllPostfixExp(list1);
// System.out.println("exp list size = "+expList.size());
for(List<String> exp:expList)
{
StringBuffer sbu = new StringBuffer();
for(String str:exp)
{
sbu.append(str).append(" ");
}
// System.out.println(sbu.toString());
String result = "";
try {
result = evaluate(exp,true);
} catch (Exception e) {
// TODO Auto-generated catch block
// e.printStackTrace();
continue;
}
if("24".equals(result))
{
System.out.println("find success:"+sbu.toString());
// System.out.println();
}
}
}
}
static void test8383()
{
List<String> source = new ArrayList<String>();
source.add("8");
source.add("3");
source.add("8");
source.add("3");
List<List<String>> all = getAllPostfixExp(source);
for(int i=0;i<all.size();i++)
{
for(String s:all.get(i))
{
System.out.print(s+" ");
}
System.out.println();
}
System.out.println(all.size());
}
}
分享到：
发表评论
-
中文数字到阿拉伯数字转换
2012-04-24 10:18 1874昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 955package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 734插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 862简单日期计算类： 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 2005已知int数组a按升序排列，要求用线性时间复杂的算法，判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1303求最大子数组之和的线性解法：本算法受编程珠玑中提示而得 /** ... -
LRUCache
2012-03-15 14:35 1655MyLRUCache 缓存类 package org.jf ... -
求变位词组合
2012-03-13 22:53 853public class CharComp { ... -
表达式计算
2012-03-10 23:02 906中缀表达式转后缀 后缀表达式计算 支持整型 分数计算，只支持 ... -
Many2One缓冲
2012-03-06 12:35 932多线程并发操作中，为了尽量减少同步锁的开销，一般都会尽可能减少 ... -
红黑树
2012-03-03 21:47 1229红黑树 规则 * 1.每个 ... -
行文件分组统计
2012-03-02 22:57 831有些情况下，对于一个结构化的以行为记录的文本文件，需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1070链表保存键值，由于没有权值策略，简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1419大根堆，可用于优先级队列 package org.jf.a ... -
固定容量二叉堆
2012-02-08 17:26 996固定容量的二叉堆实现，可用于快速求top k 问题。如要求一个 ... -
大数乘法
2012-02-07 00:16 2885论坛看到的一个面试题，实现任意大整数字符串相乘，返回结果字符串 ...
相关推荐
【计算24点的程序】是一款基于Android平台的小游戏，其核心是实现24点算法。24点游戏源于中国，玩家需要从四张1到13的扑克牌中，通过加减乘除以及括号的运算，使得运算结果等于24。这个游戏既锻炼了玩家的逻辑思维，...
"计算24点的一个小代码（C语言）" 本篇资源是一个使用C语言编写的计算24点的代码，能够输出多种不同的结果，适合C语言初学者学习和实践。以下是对该代码的详细解释和知识点总结： 1. 头文件包含：代码中包含了...
在数学的海洋中，存在着这样一类问题：看似简单，却令人绞尽脑汁——计算二十四点便是其中之一。这款游戏，源自于四张扑克牌的奇妙排列组合，要求玩家在限定的运算规则下，达成一个特定的数字目标——24。这不仅是一...
标题 "计算24点源码" 指的是一个编程项目，目的是实现计算24点游戏的算法。24点游戏是一种流行的心算游戏，玩家需要利用四张1到13之间的扑克牌，通过加、减、乘、除以及括号来组合运算，使得结果等于24。这个程序的...
在本项目中，我们探讨的是一个基于Android Studio开发的扑克牌计算24点应用程序。这个APP的目的是通过算法实现从四张随机扑克牌中找出所有可能的运算组合，以求得结果为24的解。这涉及到编程、算法设计、用户界面...
"计算24点"是一个经典的数学游戏，挑战玩家利用加减乘除运算符以及括号，将四张扑克牌上的数字组合成24。在这个问题中，我们要讨论的是实现这个功能的算法，即如何设计一个程序自动找到这些计算公式。 首先，我们...
《C++实现计算24点：深入理解MFC框架》 在编程领域，C++是一种强大的、面向对象的编程语言，常用于系统软件、游戏开发、高性能计算等场景。而"24点"游戏则是一种普及广泛的数学智力游戏，通过四张1到13的扑克牌，...
这是第一个24点，大家可以参考，改进； 大家互相学习，谢谢 作者QQ2051510483
能计算24点，可以加括号，更换运算顺序，更换运算组合，能够算出所有24点组合
此游戏是基于本人在本科时所写...其将日常生活中的“计算24点游戏”以游戏程序的方式来呈现给各位朋友，属于一个智力游戏。虽然，其尚且存在一些不足之处，但还是足以激发大家对计算类的智力游戏的兴趣，希望各位喜欢！
标题"24dianj.rar_24点计算_数字加减24_计算24点"揭示了这个游戏的核心——通过加、减、乘、除四种基本运算，将四个给定的数字组合成24。描述中的“简单的24点计算.选择四个数字,加减乘除计算得24”进一步明确了游戏...
计算24点游戏的目标是利用基本的算术运算（加、减、乘、除以及括号）将四张扑克牌上的数字组合成24。这个问题在编程中通常被用来作为算法设计和递归思想的练习。 描述中提到“输入1~13的4个数”，这代表游戏中的每...
在编程领域，"穷举组合法计算24点"是一个有趣的算法问题，它涉及到数学、逻辑和编程技巧。24点游戏是大家都熟知的一种智力游戏，玩家需要利用四张牌上的数字，通过加减乘除四则运算以及括号来得到结果24。在这个问题...
其将日常生活中的“计算24点游戏”以游戏程序的方式来呈现给各位朋友，属于一个智力游戏。虽然，其尚且存在一些不足之处，但还是足以激发大家对计算类的智力游戏的兴趣，希望各位喜欢！这个资源是此游戏的源代码，以...
在编程领域，"C# 计算24点"是一个基于C#语言的项目，旨在实现一个能够解决经典数学游戏24点的程序。24点游戏通常使用一副扑克牌的四张数字牌（去掉大小王），通过加、减、乘、除、括号等运算，使得结果等于24。这个...
计算24点是一款深受人们喜爱的智力游戏，它要求玩家通过加、减、乘、除运算，将四张扑克牌上的数字组合成24。本篇文章将深入探讨如何利用C++编程语言，结合Microsoft Foundation Classes (MFC)库，来构建一个具有...
输入任意四个整数(0到10)，运算符只有加减乘除，还有括号.每个数只能且必须用一次。要求判断这些表达的结果中是否有24。如果有，输出计算表达式：如输入4，6，1，1 输出 4*6*1*1 =24 （允许有括号）。
【小程序计算24点】是一种基于数学逻辑和计算策略的游戏，玩家需要利用四张牌上的数字，通过加、减、乘、除以及使用括号，使得运算结果为24。这个游戏在编程领域常被用于锻炼算法思维和逻辑能力，尤其在JavaScript...
24点游戏，又称二十四点，是一项广受欢迎的数学智力游戏。它源于中国，挑战玩家在四张扑克牌（数字从1到13）中寻找组合方式，使得通过加、减、乘、除运算得出24这个结果。在编程领域，设计一个计算24点的程序是一项...