Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include <pch.h>
- #include <iostream>
- #include <windows.h>
- #include <stdio.h>
- #include <conio.h>
- #include <math.h>
- #include <cmath>
- #include <malloc.h>
- #include <iomanip>
- #include <clocale>
- using namespace std;
- HANDLE hout;
- int BinarnuiPoisk(int** arr, int stroki, int stolb, int iskomui, int* inum)
- {
- int j = 0;
- int first, last, mid, temp;
- for (int i = 0; i < stroki; i++) {
- first = 0;
- last = stolb;
- while (first < last) {
- mid = first + (last - first) / 2;
- if (iskomui <= arr[i][mid])
- last = mid;
- else
- first = mid + 1;
- }
- if (arr[i][last] == iskomui) {
- *inum = ++j;
- temp = last;
- while (arr[i][--last] == iskomui && last > 0)
- *inum = ++j;
- while (arr[i][++temp] == iskomui && temp < stolb)
- *inum = ++j;
- goto stop;
- }
- else {
- goto stop;
- }
- stop:;
- }
- if (j != 0) return 0;
- else return -1;
- }
- void insertSort(int* arr, int arr_size)
- {
- int tmp;
- for (int i = 1, j; i < arr_size; ++i)
- {
- tmp = arr[i];
- for (j = i - 1; j >= 0; j -= 1)
- {
- if (arr[j] > tmp)
- {
- arr[j + 1] = arr[j];
- }
- else break;
- }
- if ((j + 1) != i)
- arr[j + 1] = tmp; // вставить проверяемый элемент в найденную позицию
- }
- }
- int main()
- {
- setlocale(LC_ALL, "Russian");
- HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
- CONSOLE_SCREEN_BUFFER_INFO s_a;
- GetConsoleScreenBufferInfo(hOut, &s_a);
- hout = GetStdHandle(STD_OUTPUT_HANDLE);
- int M = 0;
- int N = 0;
- cout << "Задана матрица размером M х N" << endl;
- cout << "Введите кол-во столбцов M: ";
- cin >> M;
- cout << "Введите кол-во строк N: ";
- cin >> N;
- cout << endl;
- if (((M < 1) || (double(M) - int(M) != 0)) || ((N < 1) || (double(N) - int(N) != 0)))
- {
- cout << "Пожалуйста, введите значения правильные!!!";
- system("pause");
- return 0;
- }
- else
- {
- //ЗАДАЕМ МАССИВ
- int** matr;
- matr = new int* [N];
- for (int i = 0; i < N; i++)
- matr[i] = new int[M];
- cout << "МАССИВ: ";
- int i, j;
- srand(time(0));
- for (i = 0; i < N; i++)
- {
- cout << endl;
- for (j = 0; j < M; j++)
- {
- matr[i][j] = 1+ rand() % 10;
- printf("%6i", matr[i][j]);
- }
- }
- cout << endl;
- cout << endl;
- cout << "Задание: Произвести поиск элемента(последовательности элементов) по четным строкам и нечетным столбцам матрицы." << endl;
- cout << endl;
- int dlinaa;
- cout << "Последовательность какой длины Вы хотите найти? ";
- cin >> dlinaa;
- if ((dlinaa < 1) || (double(dlinaa) - int(dlinaa) != 0))
- {
- cout << "Вы ввели недопустимое значение!";
- system("pause");
- return 0;
- }
- cout << "Введите элементы последовательного поиска: ";
- int* posl = new int[dlinaa];
- for (int i = 0; i < dlinaa; i++) {
- cin >> posl[i];
- }
- int** prov; //проверочный массив
- prov = new int* [N];
- for (int i = 0; i < N; i++)
- prov[i] = new int[M];
- for (i = 0; i < N; i++)
- {
- for (j = 0; j < M; j++)
- {
- prov[i][j] = 0;
- }
- }
- int sov = 0;
- int check1, check2;
- for (int i = 0; i < N; i++) { //ПОИСК ПО ЧЕТНЫМ СТРОКАМ
- if (i % 2 != 0) {
- for (int j = 0; j < M; j++) {
- if (matr[i][j] == posl[0] && (M - j) >= dlinaa) {
- check1 = 0; check2 = 0;
- for (int s = 0; s < dlinaa; s++) {
- if (matr[i][j + s] != posl[s])
- {
- check1++;
- if (prov[i][j + s] != 0)
- check2++;
- }
- }
- if (check1 == 0 && check2 < dlinaa) {
- sov++;
- for (int s = 0; s < dlinaa; s++) {
- prov[i][j + s] = 1;
- }
- }
- }
- }
- }
- }
- for (int j = 0; j < M; j++) { //ПОИСК ПО НЕЧЕТНЫМ СТОЛБЦАМ
- if (j % 2 != 1) {
- for (int i = 0; i < N; i++) {
- if (matr[i][j] == posl[0] && (N - i) >= dlinaa) {
- check1 = 0; check2 = 0;
- for (int s = 0; s < dlinaa; s++) {
- if (matr[i + s][j] != posl[s])
- {
- check1++;
- if (prov[i + s][j] != 0)
- check2++;
- }
- }
- if (check1 == 0 && check2 < dlinaa) {
- sov++;
- for (int s = 0; s < dlinaa; s++) {
- prov[i + s][j] = 1;
- }
- }
- }
- }
- }
- }
- int sum = 0; //Сумма пров массива
- for (i = 0; i < N; i++)
- {
- for (j = 0; j < M; j++)
- {
- sum = sum + prov[i][j];
- }
- }
- cout << endl;
- cout << "Количество совпадений: ";
- if (dlinaa == 1)
- cout << sum;
- else cout << sov;
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < M; j++) {
- prov[i][j] = 0;
- }
- }
- cout << endl << endl;
- cout << "Бинарный поиск:" << endl << endl;
- for (i = 0; i < N; i++)
- {
- for (j = 0; j < M; j++)
- {
- }
- }
- int c;
- cout << "Введите элемент бинарного поиска: ";
- cin >> c;
- cout << endl;
- for (i = 0; i < N; i = i + 2)
- {
- for (j = 1; j < M; j = j + 2)
- {
- matr[i][j] = -1;
- }
- }
- for (int i = 0; i < N; ++i)
- {
- insertSort(matr[i], M);
- }
- int number = 0;
- int* inum = &number;
- if (BinarnuiPoisk(matr, N, M, c, &number) != -1)
- {
- cout << "Искомый элемент есть в матрице" << endl;
- cout << "Количество совпадений: " << number << endl;
- }
- else cout << "Искомый элемент не найден" << endl;
- delete(matr);
- delete(prov);
- return 0;
- system("pause");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement