|
发表于 2004-3-1 19:46:50
|
显示全部楼层
/*
* Created on 2003-11-23
*
* 一日,鬼谷子在2--100这99个数字中选了2个数字,然后把它们的和告诉了庞涓,
* 把积告诉了孙膑。当然,庞涓不知道积是多少,孙膑不知道和是多少。 第二日,
* 庞涓遇见孙膑很傲慢的对孙膑说:"虽然我不知道这两个数是多少但是我肯定你
* 也不知道。"孙膑立刻还击道:"本来我不知道的,但是现在我知道这两个数是多
* 少了。"庞涓想了一 会,说道:"现在我也知道这两个数是多少了。"
* 请问这二个数各是多少?
*/
/**
* @author mhx
* @exception Exception
* To change the template for this generated type comment go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
import java.util.*;
class ETwoEqualNumber extends Exception{}
class EInvalidParam extends Exception{}
class IntPair{
public IntPair(int i1,int i2)throws ETwoEqualNumber{
if(i1 == i2)
throw new ETwoEqualNumber();
n1 = i1;
n2 = i2;
}
public String toString(){
return "{"+Integer.toString(n1) +" & " +Integer.toString(n2)+"}";
}
public int hashCode(){
return n1 + n2;
}
public boolean equals(Object o){
boolean res = (o instanceof IntPair) && (
((IntPair)o).n1 == n1 && ((IntPair)o).n2 == n2
||
((IntPair)o).n1 == n2 && ((IntPair)o).n2 == n1
);
return res;
}
public int sum(){
return n1 + n2;
}
public int mult(){
return n1 * n2;
}
int n1;
int n2;
public static void main(String [] args)throws Exception{
HashSet hs = new HashSet();
hs.add(new IntPair(2,3));
hs.add(new IntPair(3,2));
hs.add("x");
hs.add("x");
System.out.println(hs);
}
}
public class Answer {
static HashSet getIntPairsBySum(int sum)throws EInvalidParam{
if (sum < (2*smallNumber + 1)|| sum > (2*bigNumber - 1))
throw new EInvalidParam();
HashSet hs = new HashSet();
int top = Math.min(sum/2,bigNumber);
for (int i = smallNumber; i <= top;i++)
if (i != sum - i)
try{
hs.add(new IntPair(i,sum - i));
}catch(ETwoEqualNumber e){
System.err.println(e);
}
return hs;
}
static HashSet getIntPairsByMult(int mult)throws EInvalidParam{
if(mult <(smallNumber * (smallNumber + 1)) || mult > (bigNumber * (bigNumber - 1)))
throw new EInvalidParam();
HashSet hs = new HashSet();
for(int i = smallNumber;i < bigNumber;i++){
if (mult%i == 0 && i != mult/i && mult/i >= smallNumber && mult/i <= bigNumber)
try{
hs.add(new IntPair(i,mult/i));
}catch(ETwoEqualNumber e){
System.err.println(e);
}
}
return hs;
}
public static void usage(){
System.out.println("USAGE:");
System.out.println("java Answer smallNumber bigNumber");
System.out.println("such as: java Answer 2 100");
System.exit(0);
}
public static void main(String[] args) throws Exception{
//check params
if (args.length != 2)
usage();
try{
smallNumber = Integer.parseInt(args[0]);
bigNumber = Integer.parseInt(args[1]);
if (smallNumber >= bigNumber)
throw new Exception();
}catch(Exception e){
usage();
}
HashSet hs1,hs2;
HashSet sums = new HashSet();
F1:
for (int i = (2*smallNumber + 1);i <= (2*bigNumber - 1);i++){
hs1 = getIntPairsBySum(i);
Iterator it1 = hs1.iterator();
while(it1.hasNext()){
IntPair ip = (IntPair)it1.next();
hs2 = getIntPairsByMult(ip.mult());
if (hs2.size() <= 1)
continue F1;
}
sums.add(new Integer(i));
}
System.out.print("possible sums :" + sums);
System.out.println(" count = "+sums.size());
HashSet mults = new HashSet();
F2:
for (int i = (smallNumber * (smallNumber + 1));i<=(bigNumber * (bigNumber - 1));i++){
hs1 = getIntPairsByMult(i);
Iterator it1 = hs1.iterator();
int count = 0;
while(it1.hasNext()){
IntPair ip = (IntPair)it1.next();
if (sums.contains(new Integer(ip.sum()))){
count++;
}
if (count >=2)
continue F2;
}
if (count == 1){
mults.add(new Integer(i));
}
}
System.out.print("possible multiplies :" +mults);
System.out.println(" count = "+mults.size());
HashSet result = new HashSet();
Iterator it = sums.iterator();
W:
while(it.hasNext()){
int val = ((Integer)it.next()).intValue();
HashSet hs = getIntPairsBySum(val);
Iterator it1 = hs.iterator();
int count = 0;
IntPair ip = null;
IntPair ip2 = null;
while(it1.hasNext()){
ip = (IntPair)it1.next();
if (mults.contains(new Integer(ip.mult()))){
count++;
ip2 = ip;
}
if (count >= 2)
continue W;
}
if (count == 1){
if (ip == null)
throw new Exception("impossible! count is 1,but ip is null!");
result.add(ip2);
}
}
System.out.println("===================================");
if (result.size() != 1){
System.out.println("sorry,i can\'t find out the answer!");
}else{
System.out.println("the Answer is:" + result.iterator().next());
}
}
private static int smallNumber = 0;
private static int bigNumber = 1;
} |
|