Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Ошибка в алгоритме.

Автор: dajver 26.2.2007, 16:52

Итак, дан двумерный массив 8 на 8, заполненный случайным образом. Его нужно преобразовать в одномерный массив по следующей схеме: . Моя программа: Код import java.util.*; public class ZigZag{     public static void main(String args[]){         int n=8, m, i, j, k;         Random rnd = new Random();         int mas1[] = new int[n*n], mas2[][] = new int[n][n];         for(i=0; i<n; i++){             for(j=0; j<n; j++){                 mas2[i][j] = rnd.nextInt(200);                 System.out.println(mas2[i][j]+"\t");             }             System.out.println();         }         System.out.println("\n");                  for(i=0; i<n; i++){             for(j=0; j<n; j++){                 if((i==j)&&((j==0)||(j==n)))                     mas1[i] = mas2[i][j];                 else{                     k=i+j+1;   /* здесь я узнаю, сколько всего элементов будет на данной "хорде" квадрата*/                     m=k*(k-1)/2;   /*здесь я вычисляю кол-во элементов до начала текущей "хорды"*/                     if(k%2==0)                         mas1[m+i] = mas2[i][j];                     else                         mas1[m+j] = mas2[i][j];                 }             }         }                           for(i=0; i<n*n; i++){             System.out.println(mas2[i]+"\t");         }     } } Если я правильнопонял компилятор: Код Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 70         at ZigZag.main(ZigZag.java:24) , то у меня происходит выход за границы массива. Подскажите, пожалуйста, в чем моя ошибка. p.s. Под хордой квадрата я понимаю любую прямую линию из элементов массива, параллельную побочной диагонали.

Автор: Norb 26.2.2007, 22:29

Ну я постараюсь ответить наиболее полно и в меру своих пониманий дела. Но скажу откровенно, что сам алгоритм я не понял в принципе, но и свою версию пока что придумал в общих чертах, но реализовать пока не пытался, так что может он и не верный. Мои домыслы: Вот выдержка из программы: Цитата Код                 if((i==j)&&((j==0)||(j==n)))                     mas1[i] = mas2[i][j];                 else{                     k=i+j+1;                        m=k*(k-1)/2;                     if(k%2==0)                         mas1[m+i] = mas2[i][j];                     else                         mas1[m+j] = mas2[i][j];                 } Во-первых: у тебя массивы  Код         for(i=0; i<n; i++){             for(j=0; j<n; j++){ то есть i и j строго меньше n, и значит, что никогда не выполнится условие (j==n) Далее что касается выхода за пределы массива. у тебя i и j пробегают в пределах от 0 до n, точнее до n-1. В таком случае максимальное значение k=n-1+n-1+1=2*n-1, а m=(2*n-1)(2*n-2)/2=(n-1)(2*n-1)=2*n*n - 3*n +1. Значит в выражении  Код mas1[m+i] = mas2[i][j];  ты обращаешься к элементу массива с номером 2*n*n - 3*n +1+n-1 = 2*n*n - 2*n, что больше, чем n*n при всех n>2 (n<0 нас не интересует)

Автор: dajver 26.2.2007, 23:09

Да, спасибо, и с первым (просто запутался с итерацией) и со вторым (как раз, ошибка алгоритма). Буду думать дальше.

Автор: nornad 27.2.2007, 04:07

Вот примерный вариант решения. Я его не проверял, но идея вроде бы верная. Нарекаю алгоритмом маятника.    Код int n = 8; // размерность исходного массива int z = 2 * n - 1; // количество "колебаний" по матрице int[][] ary; // исходный массив int[] res; // массив, который надо получить boolean direction = true; // так сказать, направление движения маятника int resIndex = 0; for( int k = 0; k < z; ++k ) {   int sumIndexes = k <= n ? k : z - k;   int i = direction ? sumIndexes : 0;   int j = direction ? 0 : sumIndexes;   for( int w = 0; w < k + 1; ++w ) {     res[resIndex++] = ary[i][j];   }   direction = !direction; }

Автор: sergejzr 27.2.2007, 04:20

Что-то когда-то здесь писал на эту тему... Код public class MatrixReader {     static final int UPRIGHT = 11; // go diagonal up-right     static final int DOWNLEFT = 15; // go diagonal down-left     public static void ReadZigZack(Matrix m, ReaderListener l) {         int x = 0, y = 0, direction = UPRIGHT;         int maxX = m.colsCount(); // matrix width         int maxY = m.rowsCount(); // matrix height         while (x < maxX || y < maxY) { // Do, until we are not in the right                                         // lower corner.         // correct border, if we are out of bounds with one coordinate             if (!(y < maxY))                 y--;             if (!(x < maxX))                 x--;             // read character.             l.character(m.getAt(x, y));             switch (direction) {             case UPRIGHT: {                 if (x == maxX - 1) { // we are at the right border. Go one                                         // step down and change direction                     y++;                     direction = DOWNLEFT;                 } else {                     if (y > 0)// we can follow the diagonal since we have not                                 // reached the top row                         y--;                     else if (x % 2 == 0) // we are at the top row. every                                             // second cell changes the direction                         direction = DOWNLEFT;                 }                 x++;             }                 break;             // The same in a mirror             case DOWNLEFT: {                 if (y == maxY - 1) {                     x++;                     direction = UPRIGHT;                 } else {                     if (x > 0)                         x--;                     else if (y % 2 != 0)                         direction = UPRIGHT;                 }                 y++;             }                 break;             }         }     } } Цикл можно заменить на: Код        while (x < maxX || y < maxY) {              if (!(y < maxY)) y--;             if (!(x < maxX)) x--;             l.character(m.getAt(x, y));             if (direction) {                 if (x == maxX - 1) {y++; direction = false;}                 else {                     if (y > 0) y--;                     else if (x % 2 == 0) direction = false;                 }x++;             }else {                 if (y == maxY - 1) {x++; direction = true;}                 else {                     if (x > 0) x--;                     else if (y % 2 != 0) direction = true;                 }y++;             } Скорее всего у nornad будет поэлегантнее. Добавлено @ 04:21  А вообще оптимальное решение - это где-то в JPEG алгоритме

Автор: nornad 28.2.2007, 08:33

В алгоритме (моём) была ошибка. Вот исправленный вариант: Код for( int k = 1; k <= z; ++k ) {     int steps = k <= n ? k : ( z - k + 1 );     int min = k <= n ? 0 : n - steps;     int max = k <= n ? steps - 1 : n - 1;     int i = direction ? max : min;     int j = direction ? min : max;     for( int w = 0; w < steps; ++w ) {         res[resIndex++] = ary[i][j];         i += direction ? -1 : 1;         j += direction ? 1 : -1;     }     direction=!direction; } Всё-таки код проверять стоит.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)