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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
viktorrrr
43 / 43 / 1
Регистрация: 11.02.2010
Сообщений: 363
#1

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

08.07.2011, 11:53. Просмотров 767. Ответов 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();
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2011, 11:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Количество сравнений в массиве (C++):

Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений - C++
Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений(Это общее задание для всех вариантов) Элемент равный...

Быстрая сортировка,количество сравнений - C++
Если я правильно понимаю, то количество сравнений находится в Вайлах, но мне всегда выдает количество сравнений = 1, что бы я ни делал....

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

Сортировка вставками: количество сравнений и обменов - C++
реализация сортировки вставками где поставить счетчики сравнения и обменов ? вот код: // insertion_sort.cpp: определяет точку входа...

Посчитать количество сравнений элементов массива - C++
Имеется код, сортировка вставками, нужно в этот код всунуть счетчик &quot;количество сравнений элементов массива&quot;. Как это сделать? Простым...

Количество произведенных сравнений в Быстрой Сортировке - C++
Помогите подсчитать выполненное количество сравнений при алгоритме быстрой сортировки. Не могу определиться, куда нужно вставить счетчик. ...

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

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

Как определить количество перестановок и сравнений - C++
У меня есть алгоритм Quicksort как определить количество перестановок и сравнений?? #include &lt;iostream&gt; #include &lt;conio.h&gt; #include...

Быстрая сортировка: посчитать количество сравнений и обменов - C++
помогите, пожалуйста ) нужно посчитать количество сравнений и обменов в алгоритме &quot;быстрой&quot; сортировки. для этого нужно установить два...

Посчитать количество сравнений и перестановок в сортировке выбором - C++
Доброго времени суток, столкнулся с проблемой, не знаю куда поставить счетчики на сравнения и перестановки в сортировке выбором, уже всяко...

Количество сравнений/перестановок в сортировке естественным слиянием - C++
Добрый день ! Никак не могу понять как создать счётчик и куда его вставить , лазил по форумах и не нашел всё равно , помогите , если кто-то...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.07.2011, 18:29
Ответ Создать тему
Опции темы

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