VPF::Ошибка в алгоритме. - Форум программистов

dajver

Дата 26.2.2007, 16:52 (ссылка)

(нет голосов)

Загрузка ...

заблудившийся

Профиль
Группа: Участник
Сообщений: 26
Регистрация: 1.1.2007
Где: Диптаун

Репутация: нет
Всего: нет

Итак, дан двумерный массив 8 на 8, заполненный случайным образом.
Его нужно преобразовать в одномерный массив по следующей схеме:
user posted image

.

Моя программа:

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 26.1.2007

Репутация: нет
Всего: нет

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

Цитата

Код


                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 (ссылка)

(нет голосов)

Загрузка ...

заблудившийся

Профиль
Группа: Участник
Сообщений: 26
Регистрация: 1.1.2007
Где: Диптаун

Репутация: нет
Всего: нет

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

nornad

Дата 27.2.2007, 04:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31

Вот примерный вариант решения. Я его не проверял, но идея вроде бы верная. Нарекаю алгоритмом маятника. smile

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 6
Всего: 360

Что-то когда-то здесь писал на эту тему...

Код


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 алгоритме

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

nornad

Дата 28.2.2007, 08:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31

В алгоритме (моём) была ошибка. Вот исправленный вариант:

Код


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

Всё-таки код проверять стоит. smile

--------------------

Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »