Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
viktorrrr
45 / 47 / 4
Регистрация: 11.02.2010
Сообщений: 376
1

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

08.07.2011, 11:53. Просмотров 854. Ответов 10
Метки нет (Все метки)

И снова здравствуйте!) Есть рабочий код - поиск в двоичном массиве. Как модифицировать код, чтоб вычислить число сравнений при поиске??
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();
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2011, 11:53
Ответы с готовыми решениями:

Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений
Выполнить поиск указанных в массиве элементов и подсчитать количество...

Количество сравнений в сортировках
Подскажите как вывести количество сравнений в сортировке вставками, никак не...

Быстрая сортировка,количество сравнений
Если я правильно понимаю, то количество сравнений находится в Вайлах, но мне...

Определить количество перестановок и сравнений
как вывести для функций перестановки и сравнения?очень нужно)))вот примером для...

Количество сравнений в сложных условиях
Нужно посчитать количество сравнений в функции сортировки массива целых чисел....

10
co6ak
Кошковед
515 / 503 / 63
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 11:57 2
видимо добавить в функцию еще 1 параметр-счетчик, который будет передаваться через &.
типо void Sort(int *arr, int n, int &counter), и где то в тушке функции, непосредственно там где интересует количество сравнений - делать counter++.

Добавлено через 1 минуту
кстати, хорошим тоном считается делать прототипы функций сверху мейна, а сами функции - снизу. код становится более читабельным
1
viktorrrr
45 / 47 / 4
Регистрация: 11.02.2010
Сообщений: 376
08.07.2011, 12:00  [ТС] 3
Прототипы счаз воткну. ) уже контрольную одну сегодня сдал. Вот этот код просто нашел, как часть программы. Все хорошо, а именно со счетчиком не соображу. Тут как бы мне требуется прямая подсказка)
0
co6ak
Кошковед
515 / 503 / 63
Регистрация: 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++;
}
1
viktorrrr
45 / 47 / 4
Регистрация: 11.02.2010
Сообщений: 376
08.07.2011, 12:30  [ТС] 5
Не получается пока. убил вообще весь код.
0
co6ak
Кошковед
515 / 503 / 63
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 12:34 6
напиши какие именно сравнения тебя интересуют
0
viktorrrr
45 / 47 / 4
Регистрация: 11.02.2010
Сообщений: 376
08.07.2011, 12:38  [ТС] 7
Сначала же у меня идет сортировка, которая расставляет элементы массива. Здесь счетчик перестановок не нужен. Когда я выбираю поиск выбранного элемента, то должен выяснить, сколько раз пришлось сравнить, чтобы найти искомый. Вот. Как-то так.
0
co6ak
Кошковед
515 / 503 / 63
Регистрация: 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 секунд
я просто честно не смотрел код и что в нем происходит
1
viktorrrr
45 / 47 / 4
Регистрация: 11.02.2010
Сообщений: 376
08.07.2011, 12:49  [ТС] 9
Вроде, работает. Спасибо большое. Теперь разобраться бы, правильно ли считает)))) . Спасибо большое!
0
co6ak
Кошковед
515 / 503 / 63
Регистрация: 12.04.2010
Сообщений: 1,392
08.07.2011, 12:51 10
ну так через отладчик посмотри когда срабатывает условие
1
easybudda
Модератор
Эксперт CЭксперт С++
10120 / 6027 / 1511
Регистрация: 25.07.2009
Сообщений: 11,422
08.07.2011, 18:29 11
Цитата Сообщение от co6ak Посмотреть сообщение
void Sort(int *arr, int n, int &counter)
Не проще
C
1
int sort(int * arr, size_t size)
и возвращать количество сравнений?..
0
08.07.2011, 18:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.07.2011, 18:29

Количество обменов и сравнений в HeapSort
Всем доброго времени суток! :) Помогите, пожалуйста, разобраться с задачей. Мне...

Количество сравнений и перестановок в алгоритме слиянием
Привет всем, пробуй найти количество сравнений и перестановок в алгоритме...

Количество произведенных сравнений в Быстрой Сортировке
Помогите подсчитать выполненное количество сравнений при алгоритме быстрой...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru