Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62

Алгоритм линейного и бинарного поиска

23.04.2019, 16:15. Показов 3135. Ответов 13

Студворк — интернет-сервис помощи студентам
Задана матрица K, содержащая n строк и m столбцов. Седловой точкой
этой матрицы назовем элемент, который одновременно является минимумом в
своей строке и максимумом в своем столбце. Найдите количество седловых
точек заданной матрицы.
Формат входного файла
Первая строка входного файла содержит целые числа n и m (1 <= n, m <=
750). Далее следуют n строк по m чисел в каждой.j -ое число i -ой строки равно
kij. Все kij по модулю не превосходят 1000.
Формат выходного файла
В выходной файл выведите ответ на задачу.
Пример входного файла
2 2
0 0
0 0
Пример выходного файла
4
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
23.04.2019, 16:15
Ответы с готовыми решениями:

Поиск минимального элемента массива с помощью бинарного и линейного поиска
Помогите пожалуйста. Нужно реализовать способ поиска минимального элемента в одномерном массиве с помощью двух алгоритмов: 1.Бинарный...

Алгоритм бинарного поиска (поиска делением пополам)
Необходимо реализовать алгоритм бинарного поиска (поиска делением пополам). Алгоритм в качестве входных данных получает массив...

Алгоритм бинарного поиска
Добрый вечер, есть алгоритм бинарного поиска void bs(prov mas1, int sh, int s, int e) { int left = s, right = e -...

13
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,532
Записей в блоге: 1
23.04.2019, 16:27
Ferruw, при чём тут?
Алгоритм линейного и бинарного поиска
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62
23.04.2019, 19:25  [ТС]
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ferruw, при чём тут?
Данную задачу нужно решить с помощью данных алгоритмов, не могу решить
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,532
Записей в блоге: 1
23.04.2019, 19:41
Цитата Сообщение от Ferruw Посмотреть сообщение
Данную задачу нужно решить с помощью данных алгоритмов, не могу решить
то есть услышав на уроке "Данную задачу нужно решить с помощью данных алгоритмов", ты послушно записал задание и как ни в чём не бывало пошёл домой, не попытавшись даже спорить с учительницей?

Спрошу конкретнее. В каких массивах применяетсяя бинарный поиск?
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62
23.04.2019, 20:02  [ТС]
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
то есть услышав на уроке "Данную задачу нужно решить с помощью данных алгоритмов", ты послушно записал задание и как ни в чём не бывало пошёл домой, не попытавшись даже спорить с учительницей?
Спрошу конкретнее. В каких массивах применяетсяя бинарный поиск?
К сожалению, не было возможности спрашивать, даже и лекции не было на эту тему. Просто подкинули нам)) Бинарный поиск применяется в отсортированных массивах....
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16125 / 11249 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
23.04.2019, 21:51
Цитата Сообщение от Ferruw Посмотреть сообщение
Просто подкинули нам)) Бинарный поиск применяется в отсортированных массивах....
Если б Вы хоть чуток знали, что изучаете....

Чисто по логике.

Бинарный поиск действительно применяется в отсортированном одномерном массиве или списке. У Вас матрица. Как здесь применить бинарный поиск? Он по самому смыслу не применим к матрице.

Даже если есть отсортированная матрица, то это значит что все элементы расположены строго по возрастанию или убыванию (монотонно), а седловая точка это один из типов немонотонности. А как теперь искать в монотонной матрице немонотонность?

Из всего можно сделать такой вывод. Либо Вам дали, в принципе, невыполнимое задние, либо Вы что-то "проспали" и сами напутали с заданием.

На мой взгляд, более вероятно - второе.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62
23.04.2019, 23:19  [ТС]
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Даже если есть отсортированная матрица, то это значит что все элементы расположены строго по возрастанию или убыванию (монотонно), а седловая точка это один из типов немонотонности. А как теперь искать в монотонной матрице немонотонность?
задание -"При выполнении работы для каждого задания требуется написать программу на языке С#, которая получает на данные из входного файла, выполняет их обработку в соответствии с требованиями задания и выводит результат в выходной файл. Для обработки данных необходимо реализовать функции алгоритмов последовательного и бинарного поиска в
линейных структурах". Спасибо за пояснение про матрицы, я пока не знакома с ними достаточно, поэтому и вопрос. Но ведь последовательный поиск здесь применим?
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16125 / 11249 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
24.04.2019, 00:22
Цитата Сообщение от Ferruw Посмотреть сообщение
Но ведь последовательный поиск здесь применим?
Да, последовательный применим.

Добавлено через 51 минуту
Ferruw, вот метод для подсчёта.
Не проверял. Если не работает - напишите. Будет время - отлажу.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
        static int CountSaddlePoint(int[,] matrix)
        {
            if (matrix == null || matrix.Length == 0)
                return 0;
 
            List<int> mins = new List<int>(); // Список минимумов
            // Получение колонок минимальных элементов
            for (int row = 0; row < matrix.GetLength(0); row++)
            {
                int min = int.MaxValue;
                int minCol = -1;
                for (int col = 0; col < matrix.GetLength(1); col++)
                {
                    if (matrix[row, col] <= min)
                    {
                        min = matrix[row, col];
                        minCol = col;
                    }
                }
                mins.Add(minCol);
            }
            // Проверка элементов на максимум
            int count = 0;
            for (int rowMin = 0; rowMin < matrix.GetLength(0); rowMin++)
            {
                int maxCol = mins[rowMin];
                int max = matrix[rowMin, maxCol];
 
                bool flag = true;
                for (int row = 0; row < matrix.GetLength(0); row++)
                {
                    if (matrix[row, maxCol] > max)
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    count++;
            }
            return count;
        }
Добавлено через 9 минут
Ferruw, имейте ввиду, надо правильно подобрать данные, что для условий задачи весьма не просто.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62
25.04.2019, 10:28  [ТС]
Цитата Сообщение от Элд Хасп Посмотреть сообщение
static int CountSaddlePoint(int[,] matrix)
{
* * * * * * * *
* * * * * * * *
}
Модификатор static недопустим для этого элемента
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16125 / 11249 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
25.04.2019, 10:33
Цитата Сообщение от Ferruw Посмотреть сообщение
Модификатор static недопустим для этого элемента
Вы вставили этот код, наверное, внутрь метода.
Его надо вставлять на уровень класса.
В другом методе сформировать матрицу и обратиться к этому передав матрицу.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62
25.04.2019, 10:55  [ТС]
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Вы вставили этот код, наверное, внутрь метода.
Его надо вставлять на уровень класса.
В другом методе сформировать матрицу и обратиться к этому передав матрицу.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Program
    {
        static void CountSaddlePoint(int[,] matr)
        {
            if (matr == null || matr.Length == 0)
                return 0; 
            
                List<int> mins = new List<int>(); // Список минимумов
                // Получение колонок минимальных элементов
                for (int row = 0; row < matr.GetLength(0); row++)
                {
                    int min = int.MaxValue;
                    int minCol = -1;
                    for (int col = 0; col < matr.GetLength(1); col++)
                    {
                        if (matr[row, col] <= min)
                        {
                            min = matr[row, col];
                            minCol = col;
                        }
                    }
                    mins.Add(minCol);
                }
                // Проверка элементов на максимум
                int count = 0;
                for (int rowMin = 0; rowMin < matr.GetLength(0); rowMin++)
                {
                    int maxCol = mins[rowMin];
                    int max = matr[rowMin, maxCol];
 
                    bool flag = true;
                    for (int row = 0; row < matr.GetLength(0); row++)
                    {
                        if (matr[row, maxCol] > max)
                        {
                            flag = false;
                            break;
                        }
                    }
                    if (flag)
                        count++;
                }
                return count;
            }
                
 
                    
            static void Main(string[] args)
            {
               
                string[] Testfile = File.ReadAllLines(@"E:\Алгоритмы и структуры данных\Dv.txt ", System.Text.Encoding.Default);//опр-ние файла, 
            //из кот-го происходит считывние данных
                int[] row = Testfile[0].Split().Select(int.Parse).ToArray();//преобразование данных из файла в массив
                int[] col = Testfile[1].Split().Select(int.Parse).ToArray()
 
                int[,] matr = new int [row,col];
            String fileName = @"E:\Алгоритмы и структуры данных\Vyhod.txt ";//создание файла для записи
            StreamWriter sw = new StreamWriter(File.Open(fileName, FileMode.Append));//открытие файла для внесения изменений
            sw.WriteLine("Ответ:", count);//запись элементов в открытый файл
            sw.Close();//закрыть файл после записи туда
 
            static void CountSaddlePoint(ref int[,] matr)
 
 
        } } }
что-то не получается...подскажите, что не так?
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16125 / 11249 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
25.04.2019, 11:00
Цитата Сообщение от Ferruw Посмотреть сообщение
что-то не получается...подскажите, что не так?
По-моему скобок не хватает.
Проверьте вложенность.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 62
25.04.2019, 11:16  [ТС]
Цитата Сообщение от Элд Хасп Посмотреть сообщение
По-моему скобок не хватает.
Проверьте вложенность.
Большое количество ошибок(
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16125 / 11249 / 2888
Регистрация: 21.04.2018
Сообщений: 33,082
Записей в блоге: 2
25.04.2019, 11:40
Лучший ответ Сообщение было отмечено Ferruw как решение

Решение

Ferruw, убрал ошибки какие нашёл.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using System;
using System.Collections.Generic;
using System.IO;
 
class Program
{
    static int CountSaddlePoint(int[,] matr)
    {
        if (matr == null || matr.Length == 0)
            return 0;
 
        List<int> mins = new List<int>(); // Список минимумов
                                          // Получение колонок минимальных элементов
        for (int row = 0; row < matr.GetLength(0); row++)
        {
            int min = int.MaxValue;
            int minCol = -1;
            for (int col = 0; col < matr.GetLength(1); col++)
            {
                if (matr[row, col] <= min)
                {
                    min = matr[row, col];
                    minCol = col;
                }
            }
            mins.Add(minCol);
        }
        // Проверка элементов на максимум
        int count = 0;
        for (int rowMin = 0; rowMin < matr.GetLength(0); rowMin++)
        {
            int maxCol = mins[rowMin];
            int max = matr[rowMin, maxCol];
 
            bool flag = true;
            for (int row = 0; row < matr.GetLength(0); row++)
            {
                if (matr[row, maxCol] > max)
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
                count++;
        }
        return count;
    }
 
 
 
    static void Main(string[] args)
    {
        string fileNameSource = @"E:\Алгоритмы и структуры данных\Dv.txt "; // Имя файла из кот-го происходит считывние данных
        string fileNameResult = @"E:\Алгоритмы и структуры данных\Vyhod.txt ";//Имя файла для результата
 
        // Чтение всего текстового файла в массив строк
        string[] lines = File.ReadAllLines(fileNameSource, System.Text.Encoding.Default);
 
        char[] separators = " :;\\/\"'-".ToCharArray(); // Строка с допустимыми символами-разделителями
 
        string[] size = lines[0].Split(separators, StringSplitOptions.RemoveEmptyEntries); // Строковые значения размеров
        int rowCount = int.Parse(size[0]); // Количество строк
        int colCount = int.Parse(size[1]); // Количество колонок
 
 
        int[,] matr = new int[rowCount, colCount]; // Создание матрицы для данных
 
        // Заполнение матрицы данными
        for (int row = 0; row < rowCount; row++) // Цикл по строкам
        {
            string[] rowValues = lines[row + 1].Split(separators, StringSplitOptions.RemoveEmptyEntries); // Строковые значения элементов строки
            for (int col = 0; col < colCount; col++) // Цикл по колонкам
                matr[row, col] = int.Parse(rowValues[col]); // Запись элементов строки  
        }
 
 
        using (StreamWriter sw = new StreamWriter(File.Open(fileNameResult, FileMode.Append)))//открытие файла для внесения изменений
        {
            sw.WriteLine("Ответ:", CountSaddlePoint(matr));//запись результата в открытый файл
            sw.Close();//закрыть файл после записи туда
        }
    }
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.04.2019, 11:40
Помогаю со студенческими работами здесь

Не работает алгоритм бинарного поиска в массиве
В чем,собственно, ошибка. Линейный поиск с тем же массивом работает нормально. static int Pr = 0, Sr = 0, result = -1; public ...

Как модифицировать алгоритм бинарного поиска
Здравствуйте. Подскажите пожалуйста как можно модифицировать алгоритм бинарного поиска. Мне нужно чтобы он находил не номер индекса...

Написать алгоритм поиска данных методом линейного поиска
написать алгоритм поиска данных методом линейного поиска

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

Алгоритм линейного поиска
Здорова, в чем проблема данной функции? почему алгоритм не срабатывает? Когда пишу отдельно все прекрасно работает #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru