一个很有意思的问题的算法

Question

import java.math.BigInteger;/*
 * Created on 2004/12/07
 *
 * To change the template for this generated file go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 *//**
 * @author Administrator
 *
 * To change the template for this generated type comment go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
public class Fama { public static void main(String[] args) {
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int z = 0;
int th = 0;
boolean Flag = false;
for(a = 1; a <= 40; a++){
for(b = a + 1; b <= 40; b++){
for(c = b + 1; c <= 40; c++){
d = 40 - a - b -c;
if(d > 0){
Fama fma =  new Fama(a, b, c, d);
fma.Four(a, b, c, d);
if(fma.getLn() == 40){

System.out.println("The " + ++th +"th expected are following...");
System.out.println("first is :" + a);
System.out.println("second is :" + b);
System.out.println("third is :" + c);
System.out.println("forth is :" + d);
System.out.println("");
Flag = true;
}
// else{
// System.out.println("first is :" + a +", second is :" + b + ", third is :" + c + ", forth is :" + d);
// System.out.println("is not an excepted team!!");
// }
} }
}

}
if(Flag == false)
{
System.out.println("There are not excepted teams at all!!");

}
}
/**
 * @param a
 * @param b
 * @param c
 * @param d
 */
public Fama(int a, int b, int c, int d) {
this.z = 0;
for(int i=0;i<40;i++)
{
map[i] = 0;
}
}
public void One(int a){
z = a ;
if(0 < z && z <= 40)
{
map[z-1] = 1;
}
}
public void Two(int a, int b){
One(a);
One(b);
z = a + b;
if(0 < z && z <= 40)
{
map[z-1] = 1;
}
z = abs(a - b);
if(0 < z && z <= 40)
{
map[z-1] = 1;
}
}
public void Three(int a, int b, int c)
{
Two(a, b);
Two(a, c);
Two(b, c);
Two(a + b, c);
Two(a + c, b);
Two(b + b, a);
}
public void Four(int a, int b, int c, int d){
Three(a, b, c);
Three(a, b, d);
Three(a, c, d);
Three(b, c, d);
Three(a+b, c, d);
Three(a+c, b, d);
Three(a+d, b, c);
Three(b+c, a, d);
Three(b+d, a, c);
Three(c+c, a, b);
}
public int getLn(){
int len = 0;
for(int i = 0;i<40;i++){
len += map[i];
}
return len;
}
public int abs(int abs){
return abs > 0 ? abs : (-1)*abs;
}
int z;
int [] map = new int[40];
}
小试一把：）

Answer 1

回复人： xiaxuan92021(轩辉) ( ) 信誉：100 
=============================================
你看看你程序的结果中,有没有能测9克的,我经过人工计算没有!

Answer 2

楼主,你40克,不能找到答案吧,我的程序计算出超过27克就没有答案了
public class FindFama 
{
int a ;
int b;
int c;
int d;
int num = 40;
public FindFama()
{
for(a = 0; a < num; a++)
for(b = 0; b < num; b++)
for(c = 0; c < num; c++)
{
d = num - a - b - c;
a = 1; b = 5; c = 16; d = 18;
if(d > 0)
if(find(a,b,c,d))
{
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
System.out.println("d = " + d);
}
else{}
else
break;
}
System.out.println("end");
}
public boolean find(int a,int b, int c,int d)
{
for ( int weight = 1; weight < num + 1 ; weight++)
{
if( oneFama(a,b,c,d,weight)||twoFama(a,b,c,d,weight)
||threeFama(a,b,c,d,weight)||fourFama(a,b,c,d,weight)
){}
else
return false;

}
return true;
}
public boolean oneFama (int a, int b, int c, int d,int weight)
{
if( weight == a || weight == b || weight == c|| weight == d)
return true;
else
return false;
}
public boolean twoFama (int a, int b, int c, int d,int weight)
{
if( weight == a + b || weight == a + c || 
weight == a + d || weight == b + c ||
weight == b + d || 
weight == c + d || weight + a == b ||
weight + a == c || 
weight + a == d || weight + b == a ||
weight + b == c || weight + b == d ||
weight + c == a || weight + c == b ||
weight + c == d || weight + d == a ||
weight + d == b || weight + d == c 
)
return true;
else
return false;
}
public boolean threeFama (int a, int b, int c, int d,int weight)
{
if( weight == a + b + c || weight + a == b + c ||
weight + a == b + d || weight + a == c + d ||
weight + b == a + c || weight + b == a + d ||
weight + b == c + d || weight + c == a + b ||
weight + c == a + d || weight + c == b + d ||
weight + d == a + b || weight + d == a + c ||
weight + d == b + c || weight + b + c == a ||
weight + b + d == a || weight + c + d == a ||
weight + a + c == b || weight + a + d == b ||
weight + c + d == b || weight + a + b == c ||
weight + a + d == c || weight + b + d == c ||
weight + a + b == d || weight + a + c == d ||
weight + b + c == d )
return true;
else
return false;
}
public boolean fourFama (int a, int b, int c, int d,int weight)
{
if(     weight == a + b + c + d || weight + a == b + c + d ||
weight + b == a + c + d || weight + c == a + b + d ||
weight + b + c + d == a || weight + a + c + d == b ||
weight + a + b + d == c || weight + a + b + c == d ||
weight + d == a + b + c || weight + a + b == c + d ||
weight + c + d == a + b || weight + a + c == b + d ||
weight + b + d == a + c || weight + a + d == b + c ||
weight + b + c == a + d
)
return true;
else
return false;
} public static void main(String[] args) 
{
new FindFama();

}
}

Answer 3

不好意思,刚刚发错了
public class FindFama 
{
int a ;
int b;
int c;
int d;
int num = 27;
public FindFama()
{
for(a = 0; a < num; a++)
for(b = 0; b < num; b++)
for(c = 0; c < num; c++)
{
d = num - a - b - c;
if(d > 0)
if(find(a,b,c,d))
{
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
System.out.println("d = " + d);
}
else{}
else
break;
}
System.out.println("end");
}
public boolean find(int a,int b, int c,int d)
{
for ( int weight = 1; weight < num + 1 ; weight++)
{
if( oneFama(a,b,c,d,weight)||twoFama(a,b,c,d,weight)
||threeFama(a,b,c,d,weight)||fourFama(a,b,c,d,weight)
){}
else
return false;

}
return true;
}
public boolean oneFama (int a, int b, int c, int d,int weight)
{
if( weight == a || weight == b || weight == c|| weight == d)
return true;
else
return false;
}
public boolean twoFama (int a, int b, int c, int d,int weight)
{
if( weight == a + b || weight == a + c || 
weight == a + d || weight == b + c ||
weight == b + d || 
weight == c + d || weight + a == b ||
weight + a == c || 
weight + a == d || weight + b == a ||
weight + b == c || weight + b == d ||
weight + c == a || weight + c == b ||
weight + c == d || weight + d == a ||
weight + d == b || weight + d == c 
)
return true;
else
return false;
}
public boolean threeFama (int a, int b, int c, int d,int weight)
{
if( weight == a + b + c || weight + a == b + c ||
weight + a == b + d || weight + a == c + d ||
weight + b == a + c || weight + b == a + d ||
weight + b == c + d || weight + c == a + b ||
weight + c == a + d || weight + c == b + d ||
weight + d == a + b || weight + d == a + c ||
weight + d == b + c || weight + b + c == a ||
weight + b + d == a || weight + c + d == a ||
weight + a + c == b || weight + a + d == b ||
weight + c + d == b || weight + a + b == c ||
weight + a + d == c || weight + b + d == c ||
weight + a + b == d || weight + a + c == d ||
weight + b + c == d )
return true;
else
return false;
}
public boolean fourFama (int a, int b, int c, int d,int weight)
{
if(     weight == a + b + c + d || weight + a == b + c + d ||
weight + b == a + c + d || weight + c == a + b + d ||
weight + b + c + d == a || weight + a + c + d == b ||
weight + a + b + d == c || weight + a + b + c == d ||
weight + d == a + b + c || weight + a + b == c + d ||
weight + c + d == a + b || weight + a + c == b + d ||
weight + b + d == a + c || weight + a + d == b + c ||
weight + b + c == a + d
)
return true;
else
return false;
} public static void main(String[] args) 
{
new FindFama();

}
}

Answer 4

import java.util.HashSet;
import java.util.Set;public class Balance {
    private int a,b,c,d;
    private static Set set;
    
    public Balance(int weight){
        set=new HashSet();
        //System.out.print(set.size());
        for(a=1;a<20;a++){
            for(b=1;b<38;b++){
                for(c=1;c<38;c++){
                    d=weight-a-b-c;
                    if(!set.isEmpty()) set.clear();
                    if(a>0&&b>0&&c>0&&d>0)
                    calculate(a,b,c,d,weight);
                }
            }
        }
    }
    
    private void calculate(int a,int b,int c,int d,int weight){
        //for 1 element
        set.add(new Integer(a));
        set.add(new Integer(b));
        set.add(new Integer(c));
        set.add(new Integer(d));
        
        //for 2 elements
        cal2ele(a,b);
        cal2ele(a,c);
        cal2ele(a,d);
        cal2ele(b,c);
        cal2ele(b,d);
        cal2ele(c,d);
        
        //for 3 elements
        cal3ele(a,b,c);
        cal3ele(a,b,d);
        cal3ele(a,c,d);
        cal3ele(d,b,c);
        
        //for 4 elements
        cal4ele(a,b,c,d);
        
        if(a==1&&b==3&&c==9&&d==27)
        System.out.println(set.size());
        if(set.size()==weight){
            System.out.print("a="+a+", ");
            System.out.print("b="+b+", ");
            System.out.print("c="+c+", ");
            System.out.println("d="+d);
        }
    }
    
    private void cal2ele(int i1,int i2){
        int i=i1-i2;
        if(i<0) set.add(new Integer(0-i));
        else set.add(new Integer(i));
        
        set.add(new Integer(i1+i2));
    }
    
    private void cal3ele(int i1,int i2,int i3){
        set.add(new Integer(i1+i2+i3));
        
        int i=i1+i2-i3;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1-i2-i3;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1-i2+i3;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
    }
    
    private void cal4ele(int i1,int i2,int i3,int i4){
        set.add(new Integer(i1+i2+i3+i4));
        
        int i=i1-i2-i3-i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1+i2-i3-i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1+i2+i3-i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1-i2+i3-i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1-i2+i3+i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1+i2-i3+i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
        
        i=i1-i2-i3+i4;
        if(i>0) set.add(new Integer(i));
        else set.add(new Integer(0-i));
    }
    
    public static void main(String[] args) {
        Balance a=new Balance(40);
    }
}会有重复的结果出来，刚写的，不知道对不对，帮忙测一下吧

Answer 5

刚刚发现程序有点问题,现在改进了一下,能找出正确答案了: 1,3,9,27
public class FindFama 
{
int a ;
int b;
int c;
int d;
int num = 40;
int i = 0;
public FindFama()
{
long start = System.currentTimeMillis();
for(a = 0; a < num; a++)
for(b = 0; b < num - a ; b++)
for(c = 0; c < num - a - b; c++)
{
d = num - a - b - c;
i ++ ;
if (find(a, b, c, d)) 
{
System.out.print("a = " + a + ";");
System.out.print("b = " + b + ";");
System.out.print("c = " + c + ";");
System.out.println("d = " + d);
}
}
System.out.println("time cost " + (System.currentTimeMillis() - start));
System.out.println(i);
}
public boolean find(int a,int b, int c,int d)
{
for ( int weight = 1; weight < num + 1 ; weight++)
{
if( oneFama(a,b,c,d,weight)||twoFama(a,b,c,d,weight)
||threeFama(a,b,c,d,weight)||fourFama(a,b,c,d,weight)
){}
else
return false;

}
return true;
}
public boolean oneFama (int a, int b, int c, int d,int weight)
{
if( weight == a || weight == b || weight == c|| weight == d)
return true;
else
return false;
}
public boolean twoFama (int a, int b, int c, int d,int weight)
{
if( weight == a + b || weight == a + c || 
weight == a + d || weight == b + c ||
weight == b + d || 
weight == c + d || weight + a == b ||
weight + a == c || 
weight + a == d || weight + b == a ||
weight + b == c || weight + b == d ||
weight + c == a || weight + c == b ||
weight + c == d || weight + d == a ||
weight + d == b || weight + d == c 
)
return true;
else
return false;
}
public boolean threeFama (int a, int b, int c, int d,int weight)
{
if( weight == a + b + c || weight == a + b + d ||
weight == b + c + d || weight == a + c + d ||
weight + a == b + c || 
weight + a == b + d || weight + a == c + d ||
weight + b == a + c || weight + b == a + d ||
weight + b == c + d || weight + c == a + b ||
weight + c == a + d || weight + c == b + d ||
weight + d == a + b || weight + d == a + c ||
weight + d == b + c || weight + b + c == a ||
weight + b + d == a || weight + c + d == a ||
weight + a + c == b || weight + a + d == b ||
weight + c + d == b || weight + a + b == c ||
weight + a + d == c || weight + b + d == c ||
weight + a + b == d || weight + a + c == d ||
weight + b + c == d )
return true;
else
return false;
}
public boolean fourFama (int a, int b, int c, int d,int weight)
{
if(     weight == a + b + c + d || weight + a == b + c + d ||
weight + b == a + c + d || weight + c == a + b + d ||
weight + b + c + d == a || weight + a + c + d == b ||
weight + a + b + d == c || weight + a + b + c == d ||
weight + d == a + b + c || weight + a + b == c + d ||
weight + c + d == a + b || weight + a + c == b + d ||
weight + b + d == a + c || weight + a + d == b + c ||
weight + b + c == a + d
)
return true;
else
return false;
} public static void main(String[] args) 
{
new FindFama();

}
}

Answer 6

bigpool(wtj) ( )
=========================
你的答案也正确,但算法复杂度较大,我的为63ms,你的在173左右,呵呵

Answer 7

System.currentTimeMillis()
返回一个long.
你在程序首位和末位转入,作一个减法就出来了

Answer 8

下面这个程序可以计算任何总克数砝码的组合。
import java.util.ArrayList;
public class poise {
    private int count;
    private ArrayList A=new ArrayList();
    private ArrayList B=new ArrayList();
    poise(int count) {
        if (count > 0) {
            this.count = count;
        }
    }
    public void prtGroup(){
        int Left,Inserted,temp;
        Left=count;
        Inserted=0;
        temp=Inserted*2+1;
        int index=0;
        int i;
        while(Left>0){
            temp=Math.min(temp,Left);
            A.add(index,new Integer(temp));
            for(i=Inserted+1;i<=Inserted+temp;i++){
                if(i<temp){
                    B.add(i-1,new String(temp+"-("+B.get(temp-i-1)+")"));
                }else if(i==temp){
                    B.add(i-1,Integer.toString(temp));
                }else if(i>temp){
                    B.add(i-1,new String(temp+"+("+B.get(i-temp-1)+")"));
                }
            }
            Inserted=Inserted+temp;
            Left=Left-temp;
            temp=Inserted*2+1;
            index++;
        }
        for(i=0;i<A.size();i++){
            System.out.println(A.get(i));
        }
        for(i=0;i<B.size();i++){
            System.out.println((i+1)+"="+B.get(i));
        }
    }
    public static void main(String[] args) {
        int count=123;
        poise PS=new poise(count);
        PS.prtGroup();
    }
}

Answer 9

ACM中应该很多这种题目
http://acm.zju.edu.cn/

Answer 10

我也来写一个c的程序。#include<iostream>
#include<iomanip>
#define N 40
using namespace std;
bool isValidate(int,int,int,int);
int main()
{
for(int a = 1; a < N - 3; a++)
for(int b = a + 1; b < N - 2; b++)
for(int c = b + 1; c < N - 1; c++)
for(int d = c + 1; d < N ; d++)
if(isValidate(a,b,c,d))
cout << setw(4) << a << setw(4) <<b << setw(4) << c << setw(4) << d << endl;
return 0;
}
bool isValidate(int a,int b, int c, int d)
{
int arr[N];
for(int i = 0;i < N; i++)
arr[i] = 0;
for(int a1 = -1;a1 <=1; a1++)
for(int b1 = -1;b1 <= 1;b1++)
for(int c1 = -1;c1 <= 1; c1++)
for(int d1 = -1; d1 <=1;d1++)
{
int sum = a * a1 + b * b1 + c * c1 + d * d1;
if(sum > 0 && sum <= N)
arr[sum-1] = 1;
}
for( i = 0;i < N; i++)
if(arr[i] == 0)
return false;
return true;}