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

Количество сравнений в массиве - C++

Восстановить пароль Регистрация
 
viktorrrr
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 11:53     Количество сравнений в массиве #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
154
155
156
157
158
159
#include <iostream>
#include <cstdlib>
using namespace std;
 
void Sort(int *arr, int n)
{
 
    for (int i=0; i<n; i++)
    {
    int indexmin=i;
    for (int j=indexmin; j<n; j++)
    if (arr[indexmin]>arr[j])
    indexmin=j;
    if (i!=indexmin)
    {
    int tmp=arr[indexmin];
    arr[indexmin]=arr[i];
    arr[i]=tmp;
    }
    }
 
}
 
int *Create(int n)
{
 
    if(n<=10000)
    {
    int *arr = new int [n];
    int i=0;
    while(i<n)
    {
 
        int flag=0;
        arr[i]=rand()%(n+n); //Случайные числа до суммы введенного размера массива
        for(int j=0; j<i; j++)
        if (arr[j]==arr[i])
        {
        flag=1;
        break;
        }
        if (flag==1)
        continue;
        else
        i++;
        
    }
    Sort(arr, n);
    return arr;
    }
    
    else
    return NULL;
    
}
 
void Show(int *arr, int n)
{
 
    for (int i=0; i<n; i++)
    cout << arr[i] << " ";
    cout << endl;
 
}
 
int BinarySearch(int *arr, int n, int x)
{
 
    int index=-1;
    int L=0, R=n, m;
    while(L<R)
    {
    m=(L+R)/2;
    if (arr[m]==x)
    {
    index=m;
    break;
    }
    if (x<arr[m])
    R=m;
    else
    L=m+1;
    cout<<m%2;
    }
    return index;
 
}
 
int main()
{
 
    int *arr=NULL;
    int n;
    char action;
    setlocale(LC_ALL,"Russian");
    do
    {
 
        cout << "1. Создать массив чисел" << endl
        << "2. Показать исходный массив" << endl
        << "3. Двоичный поиск" << endl
        << "0. Выход:" << endl;
        cin >> action;
        switch(action)
        {
        case '1':
 
            if (arr!=NULL)
            {
            delete[] arr;
            }
            cout <<"Введите размер массива = ";
            cin >> n;
            arr=Create(n);
            if (arr!=NULL)
            cout << "Массив чисел создан" << endl;
            else
            cout << "Невозможно создать массив" << endl;
            break;
 
        case '2':
 
            if (arr!=NULL)
            {
            cout << "Исходный массив:" << endl;
            Show(arr,n);
            }
            else
            cout << "Создайте массив" << endl;
            break;
 
        case '3':
 
            if (arr!=NULL)
            {
            cout << "Искомый элемент = ";
            int x;
            cin >> x;
            if (BinarySearch(arr,n,x)!=-1)
            cout << "Элемент найден. Его индекс = " << BinarySearch(arr,n,x) << endl;
            else
            cout << "Элемент не найден" << endl;
            }
            else
            cout << "Создайте массив" << endl;
            break;
 
        case '0':
 
            if (arr!=NULL)
            delete[] arr;
            break;
 
        }
 
    }while(action!='0');
    cin.get();
 
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 11:57     Количество сравнений в массиве #2
видимо добавить в функцию еще 1 параметр-счетчик, который будет передаваться через &.
типо void Sort(int *arr, int n, int &counter), и где то в тушке функции, непосредственно там где интересует количество сравнений - делать counter++.

Добавлено через 1 минуту
кстати, хорошим тоном считается делать прототипы функций сверху мейна, а сами функции - снизу. код становится более читабельным
viktorrrr
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 12:00  [ТС]     Количество сравнений в массиве #3
Прототипы счаз воткну. ) уже контрольную одну сегодня сдал. Вот этот код просто нашел, как часть программы. Все хорошо, а именно со счетчиком не соображу. Тут как бы мне требуется прямая подсказка)
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 12:24     Количество сравнений в массиве #4
не знаю как подробнее сказать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Sort ( int *, int, int & );
int main()
{ ....
   int counter = 0;
   ....
   Sort( arr, n, &counter);
   ...
   cout << "Number of compairs: " << counter; 
   ....
}
 
void Sort( int *arr, int n, int &counter ) 
{
... 
counter++;
}
viktorrrr
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 12:30  [ТС]     Количество сравнений в массиве #5
Не получается пока. убил вообще весь код.
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 12:34     Количество сравнений в массиве #6
напиши какие именно сравнения тебя интересуют
viktorrrr
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 12:38  [ТС]     Количество сравнений в массиве #7
Сначала же у меня идет сортировка, которая расставляет элементы массива. Здесь счетчик перестановок не нужен. Когда я выбираю поиск выбранного элемента, то должен выяснить, сколько раз пришлось сравнить, чтобы найти искомый. Вот. Как-то так.
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 12:39     Количество сравнений в массиве #8
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
154
155
156
157
158
159
160
161
162
163
164
#include <iostream>
#include <cstdlib>
using namespace std;
 
void Sort(int *arr, int n)
{
 
    for (int i=0; i<n; i++)
    {
    int indexmin=i;
    for (int j=indexmin; j<n; j++)
    if (arr[indexmin]>arr[j])
    indexmin=j;
    if (i!=indexmin)
    {
    int tmp=arr[indexmin];
    arr[indexmin]=arr[i];
    arr[i]=tmp;
    }
    }
 
}
 
int *Create(int n)
{
 
    if(n<=10000)
    {
    int *arr = new int [n];
    int i=0;
    while(i<n)
    {
 
        int flag=0;
        arr[i]=rand()%(n+n); //Случайные числа до суммы введенного размера массива
        for(int j=0; j<i; j++)
        if (arr[j]==arr[i])
        {
        flag=1;
        break;
        }
        if (flag==1)
        continue;
        else
        i++;
                
    }
    Sort(arr, n);
    return arr;
    }
        
    else
    return NULL;
        
}
 
void Show(int *arr, int n)
{
 
    for (int i=0; i<n; i++)
    cout << arr[i] << " ";
    cout << endl;
 
}
 
int BinarySearch(int *arr, int n, int x, int &counter)
{
 
    int index=-1;
    int L=0, R=n, m;
    while(L<R)
    {
    m=(L+R)/2;
    if (arr[m]==x)
    { 
    counter++;
    index=m;
    break;
    }
    if (x<arr[m]) 
    {
        R=m;
        counter++;
    }
    else
    L=m+1;
        cout<<m%2;
    }
    return index;
 
}
 
int main()
{
 
    int *arr=NULL;
    int n;
    char action;
    int counter=0;
    setlocale(LC_ALL,"Russian");
    do
    {
 
        cout << "1. Создать массив чисел" << endl
        << "2. Показать исходный массив" << endl
        << "3. Двоичный поиск" << endl
        << "0. Выход:" << endl;
        cin >> action;
        switch(action)
        {
        case '1':
 
            if (arr!=NULL)
            {
            delete[] arr;
            }
            cout <<"Введите размер массива = ";
            cin >> n;
            arr=Create(n);
            if (arr!=NULL)
            cout << "Массив чисел создан" << endl;
            else
            cout << "Невозможно создать массив" << endl;
            break;
 
        case '2':
 
            if (arr!=NULL)
            {
            cout << "Исходный массив:" << endl;
            Show(arr,n);
            }
            else
            cout << "Создайте массив" << endl;
            break;
 
        case '3':
 
            if (arr!=NULL)
            {
            cout << "Искомый элемент = ";
            int x;
            cin >> x;
            if (BinarySearch(arr,n,x, counter)!=-1)
            cout << "Элемент найден. Его индекс = " << BinarySearch(arr,n,x, counter) << endl << "Number of compaers = " << counter << endl;
            else
            cout << "Элемент не найден" << endl;
            }
            else
            cout << "Создайте массив" << endl;
            break;
 
        case '0':
 
            if (arr!=NULL)
            delete[] arr;
            break;
 
        }
 
    }while(action!='0');
    cin.get();
 
}
Добавлено через 20 секунд
ну вот как-то так значит

Добавлено через 18 секунд
я просто честно не смотрел код и что в нем происходит
viktorrrr
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 12:49  [ТС]     Количество сравнений в массиве #9
Вроде, работает. Спасибо большое. Теперь разобраться бы, правильно ли считает)))) . Спасибо большое!
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 12:51     Количество сравнений в массиве #10
ну так через отладчик посмотри когда срабатывает условие
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.07.2011, 18:29     Количество сравнений в массиве
Еще ссылки по теме:

Количество произведенных сравнений в Быстрой Сортировке C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++

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

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
08.07.2011, 18:29     Количество сравнений в массиве #11
Цитата Сообщение от co6ak Посмотреть сообщение
void Sort(int *arr, int n, int &counter)
Не проще
C
1
int sort(int * arr, size_t size)
и возвращать количество сравнений?..
Yandex
Объявления
08.07.2011, 18:29     Количество сравнений в массиве
Ответ Создать тему
Опции темы

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