Форум программистов, компьютерный форум CyberForum.ru

Последовательный и бинарный поиск - C++

Восстановить пароль Регистрация
 
Nikkun
0 / 0 / 0
Регистрация: 14.12.2012
Сообщений: 25
23.12.2013, 23:38     Последовательный и бинарный поиск #1
Мне надо было произвести поиск элемента (последовательности элементов) по столбцам матрицы последовательным и бинарным поиском. Подскажите пожалуйста как осуществить последовательный поиск если массив из одной строки ?
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include "StdAfx.h"
#include <iostream>
#include <fstream>
#include <time.h>
using namespace std;
int main()
{
    setlocale(LC_ALL, "Russian");
    srand(time(0));
    int n, m,i,j,pepl;
    cout << "Введите целое число кол-во строк в матрице от 1 до 10!"<< endl;
    cin >> n;
    if (!cin||n < 1||n > 10){
        cout << "Input error"<< endl;
        return 1;
    }
    pepl=n;
    cout << "Введите целое число кол-во столбцов в матрице от 1 до 10!"<< endl;
    cin >> m;
    if (!cin||m < 1||m > 10){
        cout << "Input error"<< endl;
        return 1;
    }
    int **a = new int*[n];
    for (i = 0; i < n; i++)
    {
        a[i] = new int[m];
        for (int j = 0; j < m; j++)
        {
            int chisl = rand() % 10;
                a[i][j] = chisl;
                cout << a[i][j] << ' ';
        }
        cout<<"\n";
    }
    int counter = 0;
    int *key = new int[n];
    cout << "Последовательный поиск " << endl;
    cout << "Введите искомый элемент или их последовательность:" << endl;
    int l=0;
    
    for (i=0; i<n; i++){
        cin >> key[l];
        l++;
        if (cin.peek()=='\n') break;
    }
 
    for (j = 0; j < m; j++)
    {       
 
        int keyc= 0;
        for (i =0; i < n; ++i)
        {           
            if (keyc!=0 && key[keyc] != a[i][j])
                keyc =0;
            if (a[i][j] == key[keyc]) 
            {
                keyc++;
                if (keyc==l){
                    counter++;
                    }
            }
        }
    }
    delete []key;
    cout << "Элемент(ы) встречается " << counter <<" раз" << endl<< endl;
    if (l > 1)
    {
        cout << "Всё!";
        cout<<"\n";
        return 0;
    }
    cout << "Матрица после сортировки:" << endl;
 
    int k, tmp=n;
    for (int j = 0; j < m; j++)
    {
        for (int k = n - 1; k > 0; k--)
        {       
            for (int i = 0; i < tmp-1; i++)
            {
                if (a[i][j] >  a[i+1][j])
                {
                    int c = a[i][j];
                    a[i][j] = a[i+1][j];
                    a[i+1][j] = c;
                }
            }
            tmp--;
        }
        tmp=n;
    }
 
    for (i = 0; i < n; i++)
    {       
        for (j = 0; j < m; j++)
        {
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }   
    cout << "Бинарный поиск" << endl;
    cout << "Введите искомый элемент:" << endl;
    int key1;
    cin >> key1;
    counter = 0;
    int mid, current, counter1, counter2;
    if (n==1&&m==1){
        if (key1==a[0][0])cout <<"Элемент встречается 1 раз" << endl;
        else cout <<"Элемент не найден"<<endl;  }
    else{
    for (j=0; j<m; j++){
        mid=n/2-1;      
        counter1=0;
        counter2=0;
        for (int k=0; k<n; k++) {
            if (a[k][j]==key1) counter2++;
        }
        do
        
            if (a[mid][j]==key1){
                current=mid;
                while (current!=0){
                    if (a[mid][j]==key1){
                        mid--;
                    }
                    else break;
                    current--;
                }
                while (mid<n){
                    if (a[mid][j]==key1){
                        counter++;
                    }
                    mid++;
                }
                counter1++;
            }
            else {
            if (a[mid][j]>key1) mid=mid/2;
            else mid=mid+(n-mid)/2;
            }
        
        while (counter1==0 && counter2!=0);
    }
    cout << "Элемент встречается " << counter <<" раз" << endl;
    }
    for (i = 0; i < n; i++)
    {
        delete []a[i];
    }
    delete []a;
    return 0;
}
Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2013, 23:38     Последовательный и бинарный поиск
Посмотрите здесь:

C++ Индексно-последовательный поиск
C++ Поиск. Последовательный поиск
C++ Бинарный поиск
Последовательный и быстрый последовательный поиски C++
C++ Бинарно-последовательный поиск
C++ Бинарный поиск
Массивы и последовательный поиск C++
Поиск числа в двумерном массиве (бинарный поиск) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 11:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru