代码之家  ›  专栏  ›  技术社区  ›  Sreevathsa Gowru

项目Euler#49 Java

  •  -1
  • Sreevathsa Gowru  · 技术社区  · 8 年前

    问题是-

    算术序列1487、4817、8147,其中每个项 增加3330,在两个方面是不寻常的:(i)三项中的每一项 和(ii)每个4位数字都是 彼此

    没有由三个1、2或3位数字组成的算术序列 素数,显示此属性,但还有一个4位数字 递增序列。

    通过将三个术语串联在一起,您形成了什么样的12位数字 这个序列?

    我已经写了这个代码-

    package Problems;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class Pro49 {
    
        private static boolean isPrime(int n){
            if(n%2 == 0) return false;
    
            for(int i = 3; i<= Math.sqrt(n); i++){
                if(n%i == 0) return false;
            }
    
            return true;
        }
    
        private static boolean isPerm(int m, int n){
            ArrayList<Integer> mArr = new ArrayList<>();
            ArrayList<Integer> nArr = new ArrayList<>();
    
            for(int i = 0; i<4; i++){
                mArr.add(m%10);
                m /= 10;
            }
    
            for(int i = 0; i<4; i++){
                nArr.add(n%10);
                n /= 10;
            }
    
            return mArr.containsAll(nArr);
        }
    
        public static void main(String[] args) {
    
            LinkedList<Integer> primes = new LinkedList<>();
    
            for(int i = 1001; i<10000; i++){
                if(isPrime(i)) primes.add(i);
            }
    
    
            int k = 0;
            boolean breaker = false;
            for(int i = 0; i<primes.size() - 2; i++){
                for(int j = i + 1; j<primes.size() - 1; j++){
                    if(isPerm(primes.get(i), primes.get(j))) {
                        k = primes.get(j) + (primes.get(j) - primes.get(i));
    
                        if(k<10000 && primes.contains(k) && isPerm(primes.get(i), k)) {
                            System.out.println(primes.get(i) + "\n" + primes.get(j) + "\n" + k);
                            breaker = true;
                            break;
                        }
    
                    }
                    if(breaker) break;
                }
                if(breaker) break;
            }
    
    
        }
    
    }
    

    我添加了打印行 System.out.println(primes.get(i) + "\n" + primes.get(j) + "\n" + k); 检查数字。我得到了1049、1499、1949,这些都是错误的。(我猜至少1049是错的)。

    有人能指出我的代码/逻辑哪里错了吗? 感谢任何帮助。

    2 回复  |  直到 8 年前
        1
  •  1
  •   Salem    8 年前

    我认为你的逻辑出错的地方是你的 isPerm 方法您正在使用 AbstractCollection#containsAll 其中, 仅检查参数是否至少在集合中一次 .

    i、 基本上是这样

    for(E e : collection)
        if(!this.contains(e)) return false;
    return true;
    

    因此,例如,4999将是49的置换,因为49包含4和9(虽然它显然不是基于您的示例)。


    您的方法似乎适用于这些值的原因是您循环了固定的时间量-即4。对于49这样的数字,您将得到 {9, 4, 0, 0} 而不是 {9, 4} .像这样做:

    while(n != 0) {
        nArr.add(n%10);
        n /= 10;
    }
    

    你会得到正确的数字 List s(看到了吗 containsAll 这行不通。)

    在其他地方添加4位限制(例如在循环中)


    也许你可以检查每个数字的出现率。 例如:

    int[] occurrencesA = new int[10], occurrencesB = new int[10];
    for(; m != 0; m /= 10)
        occurrencesA[m % 10]++;
    for(; n != 0; n /= 10)
        occurrencesB[n % 10]++;
    for(int i = 0; i < 10; i++)
        if(occurrencesA[i] != occurrencesB[i]) return false;
    return true;
    
        2
  •  0
  •   Sreevathsa Gowru    8 年前

    我找到了一个可能的替代方案 isPerm

    private static boolean isPerm(int m, int n){
            ArrayList<Integer> mArr = new ArrayList<>();
            ArrayList<Integer> nArr = new ArrayList<>();
    
            final String mS = Integer.toString(m);
            final String nS = Integer.toString(n);
    
            if(mS.length() != nS.length()) return false;
    
            for(int i = 0; i<mS.length(); i++){
                mArr.add(m%10);
                m /= 10;
            }
    
            for(int i = 0; i<nS.length(); i++){
                nArr.add(n%10);
                n /= 10;
            }
    
            return (mArr.containsAll(nArr) && nArr.containsAll(mArr));
        }
    

    这给了我正确的答案。另一种选择是由下面的其他人发布的。