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

项目Euler#49 Java

primes permutation 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 年前

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;

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));
    }

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