在Java中比较6个整型数组

Question

在Java中比较6个整型数组

javaarrays

4

我正在尝试通过编程解决一个谜题。我有6个int数组，每个数组都有6个数字。我需要从每个数组中选择一个数字，使它们的总和为419。

我几乎是Java的初学者。我尝试使用if() elseif()语句，例如： if (lock1[i]+lock2[i]+lock4[i]+lock4[i]+lock5[i]+lock6[i] == 419) 但是代码太长了。

我查阅了Java API中的Array和ArrayList类，但是无法确定应该使用哪个方法。

以下是数组：

 class Locks {
        public static void main(String[] args) {
            int [] lock1 = {39,6,75,88,15,57};
            int [] lock2 = {9,2,58,68,48,64};
            int [] lock3 = {29,55,16,67,8,91};
            int [] lock4 = {40,54,66,22,32,25};        
            int [] lock5 = {49,1,17,41,14,30};
            int [] lock6 = {44,63,10,83,46,3};
            int total = 419;
          }
    }

- 0x2bad

另一种方法（不太高效）是使用6个循环（或递归）进行暴力破解，并尝试所有组合。 - jmj

将数组放入ArrayList中，然后使用增强型for循环来迭代它并进行加法操作。 - Ragavan

手动输入的话，很难有高位数... @Ragavan 或 for (int[] a : /int[][]/ locks) - clwhisk

另一种方法（比较复杂）是生成所有可能的6个索引组合，并检查这些值是否加起来等于所需的总和。对于给定索引获取值将是O(1)操作，但我不确定生成所有索引排列的效率如何，以及它是否比暴力方法更好。 - Prateek

4个回答

1

public class Tset {

static int [] lock1 = {39,6,75,88,15,57};
static int [] lock2 = {9,2,58,68,48,64};
static int [] lock3 = {29,55,16,67,8,91};
static int [] lock4 = {40,54,66,22,32,25};
static int [] lock5 = {49,1,17,41,14,30};
static int [] lock6 = {44,63,10,83,46,3};
static int [] index =  new int[6];
static int total = 419;

public static void main(String[] args) {
    if(Tset.getIndex()!=null){

    }

}


    public static int[] getIndex(){
        int total1 =0;
        for(int i1 :lock1){
              for(int i2 :lock2){
                  for(int i3 :lock3){
                      for(int i4 :lock4){
                          for(int i5 :lock5){
                              for(int i6 :lock6){
                                       total1=lock1[i1]+lock2[i2]+lock4[i3]+lock4[i4]+lock5[i5]+lock6[i6];
                                    if (total1==total) {
                                             index[0] = i1;
                                             index[1] = i2;
                                             index[2] = i3;
                                             index[3] = i4;
                                             index[4] = i5;
                                             index[5] = i6;
                                        return index;
                                    }

                              }

                          }

                      }

                  }

              }
        }
        return null;
    }

}

- Ragavan

这是一种做法。我只是好奇，这是唯一的做法吗？ - Prateek

我认为唯一的方法是暴力破解法，这在上面的代码中已经处理了。你可以将代码移动到这里和那里，得出略微不同的代码，但思路是相同的。 - Ragavan

没有理由不将它简单地写入代码中，因为这只涉及到 47000 种情况。然而，对于一般性的问题，例如在小于 1000 的 k 个数字之间进行 k 种锁定，这可能会更具有趣味性。 - clwhisk

1

这个解决方案可以适用于任何一组数组，并且可以找到产生所需总和的所有组合。

public static void main(String[] args) throws Exception {
    int[] lock1 = { 39, 6, 75, 88, 15, 57 };
    int[] lock2 = { 9, 2, 58, 68, 48, 64 };
    int[] lock3 = { 29, 55, 16, 67, 8, 91 };
    int[] lock4 = { 40, 54, 66, 22, 32, 25 };
    int[] lock5 = { 49, 1, 17, 41, 14, 30 };
    int[] lock6 = { 44, 63, 10, 83, 46, 3 };
    int[][] locks = { lock1, lock2, lock3, lock4, lock5, lock6 };
    int[] a = new int[6];
    find(locks, 0, a, 419);
}

static void find(int[][] locks, int i, int[] a, int x) {
    if (i < locks.length) {
        for (int j = 0; j < locks[i].length; j++) {
            a[i] = j;
            int n = 0;
            for (int k = 0; k < a.length; k++) {
                n += locks[k][a[k]];
            }
            if (n == x) {
                System.out.println(Arrays.toString(a));
            }
            find(locks, i + 1, a, x);
        }
    }
}

- Evgeniy Dorofeev

0

在编写这样的循环时，请注意可以通过保存工作总数来进行小优化。当然，时间复杂度相同，但操作次数肯定会减少。

   int sum = lock1[0]+lock2[0]+lock4[0]+lock4[0]+lock5[0]+lock6[0];
   for(int i1 :lock1){
       sum += lock1[i1];
            ...
               ...
                   for(int i6 :lock6){
                       sum += lock6[i6];
                       //test total=sum  
                       sum -= lock6[i6];
                   }
               ...
            ...
       sum -= lock1[i1];
   }

- clwhisk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dcaswell · Accepted Answer

输出结果为：3, 3, 5, 0, 0, 3，对应的数字是88、68、91、40、49、83。

需要理解的关键是我们需要考虑6 ^ 6种组合。因此我们生成从0到6 ^ 6 -1的数字。

public class Locks{
    public static void main(String[] args) {
        int [][] locks = {
            {39,6,75,88,15,57},
            {9,2,58,68,48,64},
            {29,55,16,67,8,91},
            {40,54,66,22,32,25},        
            {49,1,17,41,14,30},
            {44,63,10,83,46,3}};
        int i, j;
        int total = 419;
        int dims = 6;               // number of dimensions in array
        int loops = 1; 
        for(i = 0; i < dims; ++i)   // maximum number of elements to test 
             loops *= dims;
        for(i=0; i < loops; ++i) {  // loop over all possibilities
            int cTotal = 0;         // Total for this selection of 6 columns
            int rTotal = 1;
            for(j = 0; j < dims; ++j) {       // generate six array indexes
                cTotal += locks[j][i / rTotal % dims];
                rTotal *= dims;
            }
            rTotal = 1;
            if(cTotal == total) {
                for(j = 0; j < dims; ++j) {
                    System.out.println(i / rTotal % dims);
                    rTotal *= dims;
                }
                return;
            }
        }
    }
}