-2

Задан целочисленный массив N*M (N - количество строк, M - столбцов). Каждая строка массива упорядочена по возрастанию. Требуется написать программу, которая находит число, встречающееся во всех строках.

Я подготовил решение, но не понимаю, как довести его до конца.

#include <iostream>
using namespace std;
int func (int h,int length,int &arr[h][length],int height,int check)
{
  int otvet=0;
  for (int i=0;i<length;i++)
  {
    if (arr[height][i]==check)
    {
      otvet=1;
      break;
    }
  }
  if (otvet==1 && height==(h-1)) return 1;
  if (otvet==1) return func(arr,height+1,check,length,h); else return 0;
}
int main()
{
  int y,x;
  cin >> y >> x;
  int arr[y][x];
  for (int i=0;i<y;i++)
  {
    for (int j=0;j<x;j++)
    {
      cin >> arr[i][j];
    }
  }
  for (int i=0;i<x;i++)
  {
    int b,ok;
    b=arr[0][i];
    ok=func(y,x,arr,i,b);
    if (ok==0) continue;
    else {
      cout << b;
      break;
    }
    if (ok==0) cout << "NO";
  }
  return 0;
}
13
  • Как я понял, нужна рекурсивная проверка каждой следующей строки, пока элемент текущей равен элементу предыдущей.
    – Max
    4 янв 2019 в 13:19
  • 1
    Так не понятно: хотите использовать алгоритм std::set_intersection или нет? 4 янв 2019 в 13:19
  • 1
    Так у вас уже есть псевдокод алгоритма и нужно написать код, или нужен алгоритм?
    – Harry
    4 янв 2019 в 13:20
  • 1
    @Max В C++ нет массивов переменной длины. 4 янв 2019 в 13:21
  • 2
    Сдаюсь. "Нужно, чтоб он заработал" - алгоритм? код? Понятно, что нужно гулять по первым элементам строк, переходя к следующему элементу строки там, где он минимален... Но если у вас есть готовый псевдокод - то что я пытаюсь рассказывать? У вас же уже есть работающий алгоритм (что такое иначе псевдокод, как не описание работающего алгоритма?)
    – Harry
    4 янв 2019 в 13:24

3 ответа 3

3

Если дано, что каждая строка уже заранее упорядочена по возрастанию, то (без использования рекурсии)

#include <algorithm>
#include <iostream>
#include <iomanip>

int main(int argc, char* argv[])
{
  const unsigned N = 20, M = 20;
  int arr[N][M];

  // Подготовка входных данных

  for (auto &row: arr)
  {
    for (auto &e : row)
      e = std::rand() % 10;
    std::sort(std::begin(row), std::end(row));
    for (auto e : row)
      std::cout << std::setw(2) << e << " ";
    std::cout << std::endl;
  }

  // Собственно поиск

  unsigned i_pos[N] = {}, i_row;
  int value;

  for (; i_pos[0] < M; ++i_pos[0])
  {
    value = arr[0][i_pos[0]];
    // Будем искать это значение в остальных строках матрицы

    for (i_row = 1; i_row < N; ++i_row)
    {
      int test_value;

      for (; i_pos[i_row] < M; ++i_pos[i_row])
        if ((test_value = arr[i_row][i_pos[i_row]]) >= value)
          break;

      if (i_pos[i_row] == M || test_value != value)
        // В первом случае: значение не найдено - полный провал
        // Во втором случае: значение не найдено, но следует попробовать следующее
        break;

      // Значение найдено - переходим к поиску в следующей строке
    }

    if (i_row == N || i_pos[i_row] == M)
      // В первом случае: значение найдено - успех
      // Во втором случае: значение не найдено - полный провал
      break;

    // Значение не найдено, но следует попробовать следующее
  }

  if (i_pos[0] < M && i_row == N)
    std::cout << "Common value: " << value << std::endl;
  else
    std::cout << "No common value" << std::endl;
}
2
  • Ваше решение за O(n*m) работает? 21 янв 2019 в 7:15
  • @hedgehogues: Да, за O(nm) в худшем случае и за O(n) в лучшем. 21 янв 2019 в 15:05
3
#include <vector>
#include <algorithm>
#include <functional> 
#include <iostream>

using namespace std;

void intersect(vector<int> v, vector<vector<int>> a, size_t& n, vector<int>& r)
{
    if (++n >= a.size()) return;

    sort(v.begin(), v.end(), greater<int>());
    sort(a[n].begin(), a[n].end(), greater<int>());

    vector<int> t(min(v.size(), a[n].size()));

    vector<int>::iterator i = set_intersection(v.begin(), v.end(), a[n].begin(), a[n].end(), t.begin(), greater <int>());
    r.resize(0);
    for (vector<int>::iterator j = t.begin(); j != i; j++)
        r.push_back(*j);

    intersect(r, a, n, r);
}

int main()
{
    vector<vector<int>> a = { { 1,2,3,18},{ 4,3,5,18 },{ 7,8,3 } };
    vector<int> r(a[0]);
    size_t n = 0;
    intersect(a[0], a, n, r);

    for (vector<int>::iterator j = r.begin(); j != r.end(); j++)
        cout << *j << ";";

    return 0;
}
3
  • Ваше решение за O(n*m) работает? 21 янв 2019 в 7:15
  • Оценочно. На практике чуть быстрее из за сортировки. STL при этом оптимизирует поиск. Так что это самый быстрый способ. Заниматься самому тем, что делает STL, оптимизируя поиск отсортированного, слишком накладно. 21 янв 2019 в 7:55
  • Это решение работает намного медленнее, чем O(mn) из-за странных ненужных копирований данных и сортировок. Если избавиться от ненужных действий, то работать будет за О(mn), но накладные расходы в худшем случае все равно будут велики. 21 янв 2019 в 15:03
2
+50

Пример программы на базе кода автора, с тем же алгоритмом (т.е. линейный поиск и рекурсивный спуск по строкам)

#include <iostream>
using namespace std;
/*
 * Функция проверяет есть ли заданный элемент в заданной и последующих строках
 * На входе:
 *   arr - массив сортированных строк из целых чисел
 *   height - количество строк
 *   length - длина строк
 *   s - индекс заданной строки
 *   elem - искомый элемент
 * На выходе:
 *   true - если элемент присутствует во всех строках начиная с заданной
 *   false - заданного элемента в следующих строках нет
 */
bool func(int** arr, int height, int length, int s, int elem)
{
  // ищем элемент в строке:
  for (int i=0; i<length; ++i) {
    if (elem < arr[s][i])
      return false; // дальше все элементы больше, конец рекурсии
    else if (elem == arr[s][i]) { // нашли элемент
      if ((s+1) == height) // строка последняя, конец рекурсии 
        return true;
      else // а вот тут собственно и рекурсия:
        return func(arr, height, length, s+1, elem); // проверяем последующие строки тем же самым образом
    }
  }
  return false; // ничего не нашли, конец рекурсии
}

int main()
{
  int N,M;
  cout << "Lines:";
  cin >> N;
  if (N<2) return -1; // минимальная проверка размерности не помешает
  cout << "Columns:";
  cin >> M;
  if (M<1) return -1; // минимальная проверка размерности не помешает
  int** arr = new int*[N]; // массив строк
  for (int i=0; i<N; i++) {
    cout << "Line " << i+1 << ':';
    arr[i] = new int[M]; // инициализируем строки
    for (int j=0; j<M; j++) cin >> arr[i][j]; // заполняем столбцы
    // тут бы следовало проверить строку: отсортирована ли она, или принудительно сортировать
  }
  int i=0;
  // ищем элементы первой строки во второй и последующих
  while((i<M) && (!func(arr,N,M,1,arr[0][i]))) ++i;
  if (i==M) cout << "NO" << endl;
  else cout << arr[0][i] << endl;
  // подчищаем за собой
  for (int i=0; i<N; i++) delete[] arr[i];
  delete[] arr;
  system("pause");
  return 0;
}

Доработанный алгоритм, на базе бинарного поиска. Рекурсия уже по окну поиска в строке и по спуску на последующие строки. Плюс запоминание левых индексов окон поиска

#include <iostream>
#include <time.h>
using namespace std;

/*
 * Функция проверяет есть ли заданный элемент в заданной и последующих строках
 * На входе:
 *   arr      - массив сортированных строк из целых чисел
 *   height   - количество строк
 *   length   - длина строк
 *   s        - индекс заданной строки
 *   elem     - искомый элемент
 *   lIndexes - массив индексов левых границ поиска в строках начиная со второй
 *              (индекс первого проверяемого элемента)
 *   right    - правая граница поиска
 *              (индекс элемента следующего за последним проверяемым)
 * На выходе:
 *   true     - если элемент присутствует в заданных границах поиска такущей строки
 *              и на всех строках начиная с заданной
 *   false    - заданного элемента нет
 */
bool func(int** arr, int height, int length, int s, int elem, int* lIndexes, int right)
{
  int left = lIndexes[s-1]; // для уменьшения времени доступа
  if (elem == arr[s][left]) { // искомое число найдено
    lIndexes[s-1] = left+1; // последующие числа следует искать со следующего индекса в этой строке
    if ((s+1) == height) // строка последняя, конец рекурсии
      return true;
    else { // проверяем следующие строки
      if (lIndexes[s] >= length) // следующая строка уже гарантированно имеет меньшие числа
        return false;
      else
        return func(arr, height, length, s+1, elem, lIndexes, length);
    }
  }
  if (elem < arr[s][left]) // число меньше всех в имеющихся в строке, выходим
    return false;
  if (elem > arr[s][right-1]) { // число больше всех в имеющихся в строке, выходим
    lIndexes[s-1] = right; // все последующие искомые числа также будут больше этого элемента
    return false;
  }
  if ((right-left) < 2) // в окне один элемент и мы его уже проверили, выходим
    return false;

  // уменьшаем окно поиска:
  int middle = left + (right - left) / 2; // новая граница окна поиска
  if (elem < arr[s][middle]) // новая граница справа
    return func(arr, height, length, s, elem, lIndexes, middle);
  else { // новая граница слева, сохраняем её и ищем дальше
    lIndexes[s-1] = middle;
    return func(arr, height, length, s, elem, lIndexes, right);
  }
  return false; // ничего не нашли
}

int main()
{
  srand ((unsigned)time(nullptr));
  int N,M;
  cout << "Lines:";
  cin >> N;
  if (N<2) return -1; // минимальная проверка размерности не помешает
  cout << "Columns:";
  cin >> M;
  if (M<1) return -1; // минимальная проверка размерности не помешает
  int** arr = new int*[N]; // массив строк
  int* lIndexes = new int[N-1]; // индексы левых границ окна поиска
  for (int i=0; i<N; i++) {
    if (i>0) lIndexes[i-1] = 0; // поиск начинаем с первых элементов
    cout << "Line " << i+1 << ':';
    arr[i] = new int[M]; // инициализируем строки
    int randValue = 0;
    for (int j=0; j<M; j++) { // заполняем столбцы
      //cin >> arr[i][j]; // слишком мучительно вручную это всё вводить...
      // вместо строки выше, формируем искусственный сортированный массив
      randValue += 1+std::rand() % 2;
      arr[i][j] = randValue;
      cout << randValue << ' ';
    }
    cout << endl;
  }
  int i=0, elem = arr[0][0]-1;
  // ищем элементы первой строки в последующих
  while(i<M) {
    if (elem != arr[0][i]) { // проверка на случай повтора предыдущего элемента
      elem = arr[0][i];
      if (func(arr, N, M, 1, elem, lIndexes, M)) break; // нашли число, выходим
    }
    ++i;
  }
  if (i==M) cout << "NO" << endl;
  else cout << arr[0][i] << endl;
  // подчищаем за собой
  delete[] lIndexes;
  for (int i=0; i<N; i++) delete[] arr[i];
  delete[] arr;
  system("pause");
  return 0;
}
4
  • медленно. Тут скользящее окно надо. Каждая строка массива упорядочена по возрастанию существенно упрощает.
    – pavel
    17 янв 2019 в 7:53
  • человек хотел довести код с рекурсией до работающего. Понятно что метод поиска в строке можно было бы оптимизировать, но я посчитал, что это усложнит восприятие кода рекурсивной функции
    – Vadim
    17 янв 2019 в 8:26
  • Ваше решение за O(n*m) работает? 21 янв 2019 в 7:15
  • Т.к. использован линейный поиск, да, сложность O(nm). Без кардинальной переделки кода автора можно перейти внутри функции к бинарному поиску, тогда получим O(mlog(n))
    – Vadim
    21 янв 2019 в 12:26

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.