Блог

работает: означает отсутствие ошибки точности :: Просто массив выходит за пределы

 long a[] =new long[1000000];
int no=2,n;
long i;
a[no]=i a[n];
if(a[no]>longChain)
{
    longChain = a[no];
    startNo = no;
}
  

и когда я делаю

 long a[] =new long[1000000];
long no=2,n;
long i,longChain=1,startNo;
a[no]=i a[n];
if(a[no]>longChain)
{
    longChain = a[no];
    startNo = no;
}
  

затем потеря точности

найдено: long

требуется: int

в чем проблема?

Мой код для вышеупомянутой проблемы, его проблема с ProjectEuler № 14

 class P14
{
    public static void main(String args[])
    {
        long a[] =new long[1000000];
        long no=2,n;
        long i,longChain=1,startNo;
        a[1]=1;
        while(no<1000000)
        {
            n=no;
            i=0;
            while(n>no-1)
            {
                if(n%2==0)
                    n=n/2;
                else
                    n=3*n 1;
                i  ;
                //System.out.println(n);
            }
            a[no]=i a[n];
            if (a[no] > longChain)
            {
                longChain=a[no];
                startNo=no;
            }
            no  ;
            //System.out.println(no);
        }
    }
}
  

Это мой код для того, где возникает вышеуказанная проблема

Ответ:: Замените [no] на [(int)n]

a[n],a[(int)n]

ваши переменные no и n должны быть int, а не long . Массивы не могут быть проиндексированы long . Изменение кода на:

 int no=2,n;
  

заставляет код компилироваться.

Исключение ArrayIndexOutOfBoundsException вызвано тем, что вы написали алгоритм, предполагая, что он был длинным.

Этот код в конечном итоге приведет n к тому, что он станет отрицательным:

 n=3*n 1;
  

Трудно понять, почему, когда вы выполняете целочисленную арифметику. Небольшое изменение, чтобы заставить код использовать длинную арифметику и распечатать промежуточный результат, показывает, когда именно он становится отрицательным и как:

 while(n>no-1)
{
    long newN = n;

    if (n % 2 == 0) newN = newN / 2L;
    else newN = 3L * newN   1L;

    if (newN > Integer.MAX_VALUE) System.out.println("about to fail");

    //this is where the magic happens
    n = (int)newN;
    System.out.println("converted "   newN   " to "   n);

    i  ;
}
  

Вероятно, это связано с тем, что индексация массива принимает an int в качестве индекса. Но все ваши переменные имеют тип long .

 a[no]
  

no является long .

Таким образом, использование long в качестве индекса массива является неявным понижением, что может привести к потере точности.

Итак, либо вы вручную отбрасываете его, либо меняете no на int .

РЕДАКТИРОВАТЬ: (после дополнительной информации в вопросе)

Я не уверен на 100%, является ли это причиной:

 n=3*n 1;
  

Вы используете n as в индексе. Но n для начала может стать довольно большим. Таким образом, a *3 может сделать его больше, чем размер массива.

Вероятно, вам следует перепроверить, каким бы ни был ваш алгоритм. (что я не могу понять из самого кода)

Проблема, с которой вы сталкиваетесь, заключается в том, что вы не можете сохранить все возможные значения, которые вы вычисляете в массиве. Числа могут вырасти за пределы 2 ^ 31-1, и вы получите переполнение.

Что вы можете сделать, это сделать

 long n;
  

и

 while (n > no - 1 || n >= a.length) {

}
// is safe as n < a.length;
a[no] = i   a[(int) n];
  

Это гарантирует, что вы будете искать только кэшированные значения, которые находятся внутри вашего массива.

n должно быть длинным, потому что оно может стать слишком большим для int. (Если вы используете int, он переполнится отрицательными числами и вызовет исключение ArrayIndexOutOfBoundsException .)

Вы должны объявить n as long и преобразовать его в int при использовании его в качестве индекса ( no может быть int)

 a[no]=i a[(int)n];