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

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

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

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

08.07.2011, 11:53. Просмотров 760. Ответов 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++
Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений(Это общее задание для всех вариантов) Элемент равный...

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

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

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

Посчитать количество сравнений элементов массива - 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
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
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
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 12:30  [ТС]     Количество сравнений в массиве #5
Не получается пока. убил вообще весь код.
co6ak
Кошковед
407 / 500 / 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
Кошковед
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
42 / 42 / 1
Регистрация: 11.02.2010
Сообщений: 358
08.07.2011, 12:49  [ТС]     Количество сравнений в массиве #9
Вроде, работает. Спасибо большое. Теперь разобраться бы, правильно ли считает)))) . Спасибо большое!
co6ak
Кошковед
407 / 500 / 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++
реализация сортировки вставками где поставить счетчики сравнения и обменов ? вот код: // insertion_sort.cpp: определяет точку входа...

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

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

Найти количество сравнений после сортировки массива - C++
Нужно чтобы писала количество сравнений после сортировки массива, но я вроде все прописал #include &quot;stdafx.h&quot; #include...


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

Или воспользуйтесь поиском по форуму:
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
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     Количество сравнений в массиве
Ответ Создать тему
Опции темы

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