数据结构和算法分析

一道有趣的逻辑题

2018-04-21  本文已影响360人  黄某

题目
有两个大于1的正数 x和y,甲知道二者的积,乙知道二者的和。
甲:我不知道这俩数是什么!
乙:我不知道这俩数是什么,我就知道你不知道!
甲:现在我知道了。
乙:现在我也知道了。

分析

首先我们需要将其简化为一个数学问题,即 从甲和乙的对话中筛选出一些条件。

Talk is cheap,show me the code

以下为Java代码实现:

public class findExactNums {

static Map<Integer,String> exactNums = new HashMap();


public static void main(String[] args0){
   findExactNums();
}

//遍历所有数
public static void findExactNums(){
    for(int sum=4;;sum++){
        if(judgeCanSplitToPrime(sum)){
            continue;
        }
        int count=0;
        for(int x=2;x<sum/2+1;x++){
            if(judgeFactorSumCanSplitPrime(x*(sum-x))){
                count+=1;
                int y=sum-x;
                exactNums.put(sum,x+":"+y);
            }
        }
        if(count==1){
            System.out.println(exactNums.get(sum));
        }
    }



}

//判断积的所有因子中是否有且仅有一组因子的和不可分解为两质数
public static boolean judgeFactorSumCanSplitPrime(int product){
    int count=0;
    for(int i=2;i*i<=product;i++){
        if(product%i==0){
            if(!judgeCanSplitToPrime(i+product/i)){
               count+=1;
            }
        }
    }
    if(count==1){
        return true;
    }
    return false;
}

//判断是否能被分解为两个质数
public static boolean judgeCanSplitToPrime(int num){
    for(int i=2;i<num/2+1;i++){
        if(judgePrime(i)&&judgePrime(num-i)){
            return true;
        }
    }
    return false;
}

//判断是否为质数
public  static boolean judgePrime(int num){
    if(num==1){
        return false;
    }
    if(num==2||num==3){
        return true;
    }
    if(num%2==0){
        return false;
    }
    for(int i=3;i*i<=num;i=i+2){
        if(num%i==0){
            return false;
        }
    }
    return true;
}
}
上一篇 下一篇

猜你喜欢

热点阅读