Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11656
Последний выпуск: 19.06.2015

Линейный поиск в двумерном массиве.

98K
03 июня
Катя Якубова
1 / / 03.06.2017
Всем привет, я столкнулась с одной задачей и затрудняюсь с написанием кода.Помогите пожалуйста. Дано: Двумерный массив:

0 1 0 1 1 0
1 0 1 1 0 0
0 0 0 1 0 1
0 0 0 0 0 0
1 0 1 1 0 0
0 1 0 1 1 1
Вход: определим что дыра k это когда в строке ее все нули ,а в столбце все 1 кроме самого k который равен 0. Выход: существует ли такой k и если да вернуть его значение если нет вернуть -1. Код должен пройти со сложностью O(n). Метод: public static int isSink(int [][] mat)

я написала такой код,но мне сказали что он неверный:

Код:
public static int isSink(int[][] mat) {
    int n = mat[0].length;
    boolean[] check = new boolean[n];
    for (int i = 0; i < n; i++)
        check[i] = true;
    for (int i = 0; i < n; i++)
        if (check[i]) {
            for (int j = 0; j < n; j++) {
                if (i != j)
                    check[j] = false;
                else {
                    check[i] = false;
                    break;
                }
                if (i == j)
                    continue;
                if (mat[j][i] == 1)
                    check[j] = false;
                else {
                    check[i] = false;
                    break;
                }
            }
            if (check[i])
                return i;
        }
    return -1;
}
Надо просто пройти по диагонали ,при каждом нахождении нуля проверять строку в которой он находится если там все 0, плюс ко всему надо найти столбик со всеми 1 кроме этого 0 при нахождении такого надо вывести его значение а тоесть k=0 , а если таков не имеется то вывести -1.Таков имеется 4-ый столбик 4-ая строка .Но я затрудняюсь в самом построение цыкла....for...if...
595
12 июня
Charley
170 / / 16.08.2011
Честно говоря мне не приходит в голову алгоритм поиска "дыры" за O(n). Вот код простого алгоритма поиска, который мне кажется подходящим.
Код:
/*
 * если номер столбца равен номеру строчки по определению "дыры"
 */


        public static int isSink()
        {
           
            int n = mat[0].lenght;

            for (int i = 0; i < n; i++)
            {
                boolean flag = true;

                if (mat[i,i] == 0)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (i == j)
                        {
                            j++;
                        }
                        if (mat[i,j] == 1 || mat[j,i] == 0)
                        {
                            flag = false;
                            j = n;
                        }
                    }
                    if (flag)
                        return i;
                }
            }
            return -1;
        }
421
16 июня
cronya
420 / / 03.01.2009
Код написан на С++, думаю под джаву сами адаптируете. Задача нетривиальная, алгоритм написан, как осознан, но в общих чертах должно быть так.
Код:
#include <iostream>
#include <ctime>
using namespace std;

int** setArray(int cellsPtr, int zeroLinePtr, bool flag);
void ouArray(int** arr, int cellPtr);
int searchHole(int** arr, int cellsPtr);

int main(int argc, char** argv[])
{
    srand((unsigned)time(NULL));
    /*случайное кол-во строк и столбцов, квадратная матрица*/
    int cells = rand() % 4 + 4;
    /*случайная строка, где будет принудительная дыра*/
    int zeroLine = rand() % cells;
    /*
    Заполнения массива случайным образом
    true = принудительно создаем дыру в случайном месте
    false = заполнение случайной полседоваетльностью
    */

    int** arr = setArray(cells, zeroLine, false);
    cout << "Array:" << endl;
    /*вывод массива в консоль*/
    ouArray(arr, cells);
    /*поиск дыры в массиве*/
    cout << endl << "Rezult = " << searchHole(arr, cells) << endl;;
    /*освобождение памяти*/
    for (int idx = 0; idx < cells; idx++)
    {
        delete[] arr[idx];
    }
    delete[] arr;
    cout << endl;
    system("pause");
    return 0;
}

int** setArray(int cellsPtr, int zeroLinePtr, bool flagPtr)
{
    /*выделение памяти под массив*/
    int** arr = new int*[cellsPtr];
    for (int idx = 0; idx < cellsPtr; idx++)
    {
        arr[idx] = new int[cellsPtr];
    }  
    if (flagPtr)
    {
        /*если истина, создаем принудительно в случайной строке, по значению из ZeroLine*/
        for (int idx = 0; idx < cellsPtr; idx++)
        {
            for (int jdx = 0; jdx < cellsPtr; jdx++)
            {
                /*заполняем все элементры строки 0*/
                if (zeroLinePtr == idx)
                {
                    arr[idx][jdx] = 0;
                }
                /*если строка не из zeroLine, заполняем случайно 0 или 1*/
                else
                {
                    arr[idx][jdx] = rand() % 2;
                }
            }
        }
        for (int idx = 0; idx < cellsPtr; idx++)
        {
            /*заполняем столбец 1, чтобы создать принудительно дыру по значению zeroLine*/
            if (idx != zeroLinePtr)
            {
                arr[idx][zeroLinePtr] = 1;
            }
        }
    }
    else
    {
        /*случайное заполнение массива 0 или 1*/
        for (int idx = 0; idx < cellsPtr; idx++)
        {
            for (int jdx = 0; jdx < cellsPtr; jdx++)
            {
                arr[idx][jdx] = rand() % 2;
            }
        }
    }
    return arr;
}

void ouArray(int** arr, int cellsPtr)
{
    for (int idx = 0; idx < cellsPtr; idx++)
    {
        for (int jdx = 0; jdx < cellsPtr; jdx++)
        {
            cout << arr[idx][jdx]<< "t";
        }
        cout << endl;
    }
}

int searchHole(int** arr, int cellsPtr)
{
    /*флаг возрата функции 1 - дыра есть, -1 - дыры нет*/
    int flag = 0;
    /*флаг,показывающий что в строке, где дыра все 0*/
    bool flagRow = false;
    /*флаг,показывающий что в столбце, где дыра все 1*/
    bool flagColumn = false;
    /*индекс строки*/
    int idxRow = 0;
    /*индекс столбца*/
    int idxColumn = 0;
    for (int idx = 0; idx < cellsPtr; idx++)
    {
        /*проеряем строку на условия дыры, то есть все 0 встроке*/
        if (arr[idx][idx] == 0)
        {
            flagRow = true;
            for (int jdx = 0; jdx < cellsPtr; jdx++)
            {
                idxRow = idx;
                if (arr[idx][jdx] != 0)
                {
                    flagRow = false;
                    break;
                }
            }
            /*если строка прошла проверку, проверяем столбцы на дыру, чтобы все 1*/
            if (flagRow)
            {
                flagColumn = true;
                for (int jdx = 0; jdx < cellsPtr; jdx++)
                {
                    idxColumn = idx;
                    if (idx != jdx)
                    {
                        if (arr[jdx][idx] != 1)
                        {
                            flagColumn = false;
                            break;
                        }
                    }
                }
            }          
        }
        /*находим первую дыру в матрице, поиск дальше с низкой вероятностью даст 2-у дыру*/
        if (flagColumn)
            break;
    }
    /*Сообщения о наличии дыры в матрице*/
    if (flagColumn)
    {
        flag = 1;
        cout << endl << "There is a hole." << endl;
        cout << endl << "Index Row = " << idxRow << "; Index Column = " << idxColumn << endl;
    }
    else
    {
        flag = -1;
        cout << endl << "There is no a hole." << endl;
    }
    return flag;
}

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог