|
锁定老帖子 主题：写个算法
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-02-26
最后修改：2011-02-26
搞定了，貌似和楼主实例的算法不太一样，而且还是用了递归，昨天想的有些简单了。。。
首先得到最长的标准数列+自由因子 例如10就是 1+2+3+4 + 0 11 1+2+3+4 + 1 14 1+2+3+4 + 4 然后将自由因子按规则依次向前放置， 遍历完4个数字的数列后，将最大的数累加到自由因子上，继续前面的过程。
public class abcerer {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int i = 1;
int j = 0;
int count = 0;
//n is the input number
if(n <3)
{
System.out.println("num is too small to get result");
}
for(; count < n; j++,i++)
{
num[j] = i;
count += i;
}
j--;
i--;
if(count != n)
{
num[j -1] += n -(count - i);
j--;
}
int freedom = 0;
int test = 1;
while(true)
{
if( count == n && test == 1)
{
for(int sss = 0; sss<= j; sss++)
{
if( num[sss] != 0)
{
System.out.print(num[sss]);
if(sss != j)
System.out.print(" + ");
}
}
System.out.println(" = " + n);
}
if( test == 1)
{
freedom += num[j] - (j+1);
test = 0;
}
else
freedom += num[j+1];
num[j] = (j+1);
if(j == 0)
break;
mycall(0, j, freedom);
j--;
}
}
public static void mycall(int i, int j, int freedom)
{
//int save = freedom;
if(i < j)
{
while(freedom >= j-i-1)
{
mycall(i + 1, j, freedom);
int t = i;
newnum[t]++;
freedom --;
t++;
while (t <= j )
{
newnum[t]++;
freedom--;
t++;
}
}
newnum = new int[100];
}
else
{
for(int sss = 0; sss<= j; sss++)
{
if( num[sss] != 0)
{
if(sss != j)
{
System.out.print(num[sss]+newnum[sss]);
System.out.print(" + ");
}
else
{
System.out.print(num[sss] + newnum[sss] + freedom);
}
}
}
System.out.println(" = " + n);
}
}
static int[] num = new int[100];
static int[] newnum = new int [100];
static int n = 10;//what is you need change
}
|
| 返回顶楼 | |
|
发表时间：2011-02-26
最后修改：2011-02-26
这是树的遍历问题。可以这样构造树，子节点的值都大于父节点的值。若分支的节点之和为n,则为可行解。可以用栈来记录遍历路径。以下是树的3个处理方式：
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
depthFirstSolve(Node.createFirstNode(), 10);
breadthFirstSolve(10);
multiThreadSolve(10);
}
/**
* 深度优先
* @param preNode
* @param n
*/
public static void depthFirstSolve(Node preNode, int n) {
for (int i = preNode.value + 1; i + preNode.sum <= n; i++) {
Node node = new Node(i, preNode);
if (node.sum == n) {
solveOK(node);
} else {
depthFirstSolve(node, n);
}
}
}
/**
* 广度优先
* @param n
*/
public static void breadthFirstSolve(int n) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(Node.createFirstNode());
Node node;
while ((node = queue.poll()) != null) {
if (node.sum == n) {
solveOK(node);
} else {
for (int i = node.value + 1; i + node.sum <= n; i++) {
queue.add(new Node(i, node));
}
}
}
}
/**
* 多线程 + 广度
* @param n
*/
public static void multiThreadSolve(final int n) {
int count = Runtime.getRuntime().availableProcessors();
final ExecutorService exe = Executors.newFixedThreadPool(count);
Node node = Node.createFirstNode();
final AtomicInteger exeCount = new AtomicInteger(0); //统计活动线程
class SolverTask implements Runnable {
final Node node;
public SolverTask(Node node) {
exeCount.incrementAndGet();
this.node = node;
}
@Override
public void run() {
if (node.sum == n) {
solveOK(node);
} else {
for (int i = node.value + 1; i + node.sum <= n; i++) {
exe.execute(new SolverTask(new Node(i, node)));
}
}
if (exeCount.decrementAndGet() == 0) {
exe.shutdown();
}
}
} // class
exe.execute(new SolverTask(node));
}
private synchronized static void solveOK(Node node) {
LinkedList<Integer> l = new LinkedList<Integer>();
while (node != null) {
l.add(0, node.value);
node = node.pre;
}
l.remove(0);
for (Integer t : l) {
System.out.print(t + " ");
}
System.out.println();
}
static class Node {
final int value;
final int sum; //分支节点值之和
final Node pre; //父节点
public static Node createFirstNode() {
return new Node();
}
private Node() {
this.value = 0;
this.sum = 0;
this.pre = null;
}
public Node(int value, Node pre) {
this.value = value;
this.sum = pre.sum + value;
this.pre = pre;
}
}
}
|
| 返回顶楼 | |
|
发表时间：2011-02-26
楼主，我做出来了，你应聘的什么公司啊，给我介绍介绍啊，可怜的我找不到工作啊!
|
| 返回顶楼 | |
|
发表时间：2011-02-26
这个算法叫正整数拆分，具体google之
|
| 返回顶楼 | |
|
发表时间：2011-02-28
巧克力的算法很快,但是结果不正确...
例如50 部分结果 2 + 3 + 15 = 50 2 + 4 + 14 = 50 2 + 5 + 13 = 50 2 + 6 + 12 = 50 2 + 7 + 11 = 50 2 + 8 + 10 = 50 2 + 3 + 12 = 50 2 + 4 + 11 = 50 2 + 5 + 10 = 50 这和50差太多了... |
| 返回顶楼 | |
|
发表时间：2011-02-28
代码更新一下，之前的确实是错了。。。不过这个版本内存空间浪费比较严重，无奈。。
import java.io.IOException;
public class abcerer {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
while(true)
{
/*try {
n = System.in.read();
if( n > 5 && n <= 500)
test(n);
else
break;
mycount = 0;
num = new int[100];
}
catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}*/
test(n);
break;
}
}
public static void test( int n)
{
int i = 1;
int j = 0;
long count = 0;
if(n <3)
{
System.out.println("num is too small to get result");
}
for(; count < n; j++,i++)
{
num[j] = i;
count += i;
}
j--;
i--;
if(count != n)
{
num[j -1] += n -(count - i);
j--;
}
int freedom = 0;
int test = 1;
while(true)
{ if( test == 1)
{
freedom += num[j] - (j+1);
test = 0;
}
else
freedom += num[j+1];
num[j] = (j+1);
if(j == 0)
break;
mycall(0, j, freedom);
j--;
}
System.out.println(mycount);
}
public static void mycall(int i, int j, int freedom)
{
//int save = freedom;
if(i < j)
{
int save = 0;
//while(freedom >= j-i-1)
while(freedom >= 0)
{
mycall(i + 1, j, freedom);
int t = i;
while( t <= j && i != j - 1)
{
newnum[i][t] = save;
t++;
}
t = i;
while (t <= j )
{
//newnum[t] = save;
//freedom --;
newnum[i][t]++;
freedom--;
t++;
}
save++;
}
newnum[i] = new int[100];
}
else
{
for(int sss = 0; sss<= j; sss++)
{
if( num[sss] != 0)
{
int count = j+1;
if(sss != j)
{
int temp = 0;
temp += num[sss];
while(count >= 0)
{
temp += newnum[count][sss];
count--;
}
System.out.print(temp);
System.out.print(" + ");
}
else
{
int temp = 0;
temp += num[sss];
while(count >= 0)
{
temp += newnum[count][sss];
count--;
}
System.out.print(temp+freedom);
}
}
}
System.out.println(" = " + n);
mycount ++;
}
}
static int[] num = new int[100];
static int n = 28;
static int[][] newnum = new int [n][100];
static long mycount = 0;
}
|
| 返回顶楼 | |
|
发表时间：2011-03-01
好无聊啊，没事我也算了一下。
public static void main(String[] args) throws Exception {
int m = 21;//待求和整数
int n = (m +1)/2; //循环次数，待求和整数的1/2
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int k = 0;
for(int i=1; i<n; i++) {
int j = i;
int total = 0;
while(true) {//求出最小整数序列： 1+2+3+4=10
total += j;
if(total > m) {
map.remove(k);
total -= (j + k);
continue;
} else if(total == m) {
map.put(j, j);
break;
}
map.put(j, j);
k = j;
j++;
}
if(!map.isEmpty()) {//输出最小整数序列
print(map, m);
}
if(map.size() > 2) {//对最小整数序列进行两两以上相加
Integer num[] = map.values().toArray(new Integer[0]);
int len = num.length;
int mm = 2;
for(j=len-1; j>0; j--) {
while(mm <= j) {
map.clear();
total = 0;
for(k=0; k<=j-mm; k++) {
map.put(num[k].intValue(), num[k].intValue());
}
for(k=j; k>j-mm; k--) {
total += num[k].intValue();
}
map.put(total, total);
print(map, m);
mm ++;
}
}
}
map.clear();
}
}
// 输出函数
static void print(TreeMap<Integer, Integer> m, int total) {
StringBuffer str = new StringBuffer();
for(Object i : m.keySet()) {
str.append(m.get(i));
str.append(" + ");
}
System.out.println(str.substring(0, str.length() - 2) + " = " + total);
}
|
| 返回顶楼 | |
|
发表时间：2011-03-11
静夜思春 写道 好无聊啊，没事我也算了一下。
public static void main(String[] args) throws Exception {
int m = 21;//待求和整数
int n = (m +1)/2; //循环次数，待求和整数的1/2
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int k = 0;
for(int i=1; i<n; i++) {
int j = i;
int total = 0;
while(true) {//求出最小整数序列： 1+2+3+4=10
total += j;
if(total > m) {
map.remove(k);
total -= (j + k);
continue;
} else if(total == m) {
map.put(j, j);
break;
}
map.put(j, j);
k = j;
j++;
}
if(!map.isEmpty()) {//输出最小整数序列
print(map, m);
}
if(map.size() > 2) {//对最小整数序列进行两两以上相加
Integer num[] = map.values().toArray(new Integer[0]);
int len = num.length;
int mm = 2;
for(j=len-1; j>0; j--) {
while(mm <= j) {
map.clear();
total = 0;
for(k=0; k<=j-mm; k++) {
map.put(num[k].intValue(), num[k].intValue());
}
for(k=j; k>j-mm; k--) {
total += num[k].intValue();
}
map.put(total, total);
print(map, m);
mm ++;
}
}
}
map.clear();
}
}
// 输出函数
static void print(TreeMap<Integer, Integer> m, int total) {
StringBuffer str = new StringBuffer();
for(Object i : m.keySet()) {
str.append(m.get(i));
str.append(" + ");
}
System.out.println(str.substring(0, str.length() - 2) + " = " + total);
}
不完全正确。 |
| 返回顶楼 | |
|
发表时间：2011-03-13
最后修改：2012-02-15
采用OO的方式实现了一个版本，内存占的也很多，见如下链接：
http://freejvm.iteye.com/blog/960626 |
| 返回顶楼 | |
|
发表时间：2011-03-14
最后修改：2011-03-14
"哎，这个所谓的算法题又被挖出来了；你们不觉得你们的解法，无论观感、数据结构与算法，还是抽象、java特性，和若干楼上BackShadow的解法都有不少差距吗?"道格李如是说(其实是BackShadow剽窃道格李的，大神的作品，能差吗?)。
|
| 返回顶楼 | |
