0 / 0 / 0
Регистрация: 17.11.2019
Сообщений: 41

Исправить программу

27.05.2020, 12:13. Показов 1027. Ответов 0

Студворк — интернет-сервис помощи студентам
Помогите исправить программу, запутался с шаблонами
задание такое:Написать алгоритм который ищет в массиве элементы следующим образом: если его длинна меньше n ,то используется линейный поиск, иначе - сортировка Хоара, а затем бинарный поиск. Экспериментальным путем определить оптимальное значение n для поиска 1000 элементов типов double, int и строк длинны 8.
Нужно определить, при какой длине массива алгоритм A2 становится эффективнее, чем A1


C++ (Qt)
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
165
166
167
168
169
170
171
172
173
174
175
176
#include<iostream>
#include <ctime>
 
using namespace std;
 
struct str8 
{
    char str[8];
};
str8 Str8[1000];
 
 
int cmp(int arg1, int arg2) {
    if (arg1 > arg2)
        return 1;
    else if (arg1 < arg2)
        return -1;
    else
        return 0;
}
 
int cmp(str8 arg1, str8 arg2) 
{
    for (int i = 0; i < 8; i++) {
        if (arg1.str[i] > arg2.str[i])
            return 1;
        if (arg1.str[i] < arg2.str[i])
            return -1;
    }
    return 0;
}
 
 
template < typename T > //сортировка Хоара
void qs(T* a, int left, int right, T c)
{
    int i, j;
    T x, y;
    i = left;
    j = right;
    x = a[(left + right) / 2];
    do {
        while (a[i] < x && i < right)
            i++;
        while (a[j] > x&& j > left)
            j--;
        if (i <= j) {
            y = a[i];
            a[i] = a[j];
            a[j] = y;
            i++;
            j--;
        }
    } while (i <= j);
 
    if (left < j)
        qs(a, left, j, c);
    
    if (right > i)
        qs(a, i, right,c);
 
    bfind(a, size, c);
}
 
template < typename T > //линейный поиск
T* lfind(T* a, int size, T c)
{
    while (size) {
        if (*a == c)
            return a;
        a++;
        size--;
    }
    return NULL;
}
 
template < typename T > //бинарный поиск
T* bfind(T* a, int size, T c)
{
    while (size) {
        int middle = size / 2;
        if (c == a[middle])
            return a + middle;
        if (c < a[middle])
            size = middle;
        else {
            a += middle + 1;
            size -= middle + 1;
        }
    }
    return NULL;
}
 
void randArr(int* mass, int size) //рандомное заполнение массива типа int
{
    for (int i = 0; i < size; i++) {
        mass[i] = rand();
    }
}
void randArr(str8* mass, int size) //рандомное заполнение массива типа char длинны 8
{
    for (int i = 0; i < size; i++)
        for (int j = 0; j < 8; j++)
            mass[i].str[j] = rand() % 255;
}
 
void randArr(double* mass, int size) //рандомное заполнение массива типа double
{
    for (int i = 0; i < size; i++) {
        mass[i] = rand();
    }
}
 
 
 
template < typename T > //подсчет оптимального времени работы алгоритмов
int optimal( T c ) {
    int result = 0;
    int iter = 400;
    for (int i = 0; i < iter; i++) {
        float LPTime = 0, SHBPTime = 0;
        int n = 2;
        for (; SHBPTime >= LPTime; n++) {
            T* mass = new T[n];
            randArr(mass, n);
            clock_t t0 = clock();
            lfind(mass, n, c);
            clock_t t1 = clock();
            LPTime = (float)t1 - t0;
            clock_t t2 = clock();
            qs(mass, 0,n - 1, c );
            clock_t t3 = clock();
            SHBPTime = (float)t3 - t2;
        }
        result += n;
    }
    return result / iter;
}
 
 
 
template < typename T > //определение наиболее эффективного способа поиска
void myPoisk(T* mass, int count, T c)
{
    int o = optimal<T>(c);
    if (count < o) {
        lfind<T>(mass, count, c);
        cout << "lfind poisk    :" << endl;
    }
    else {
        qs<T>(mass, 0, count - 1, c);
        cout << "Quick sort and bin.poisk   :" << endl;
    }
}
 
 
 
int main() {
    
    cout << "For int    :" << optimal<int>(1000) << endl;
    cout << "For double :" << optimal<double>(1000) << endl;
    cout << "For str8   :" << optimal<str8>(Str8[1000]) << endl;
    int count = 10;
    int* mass = new int[count];
    randArr(mass, count);
    cout << "Test sequence  :" << endl;
    for (int i = 0; i < count; i++)
        cout << mass[i] << " ";
    cout << endl;
    
    myPoisk<int>(mass, count, 1000);
    for (int i = 0; i < count; i++)
        cout << mass[i] << " ";
    cout << endl;
    return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
27.05.2020, 12:13
Ответы с готовыми решениями:

Исправить программу
Дано выражение. По законам математики вне зависимости от значений переменных a и b выражение всегда имеет значение 1. Нужно исправить...

Исправить программу
#include &quot;&lt;iostream.h&gt;&quot; #include &quot;diophantine.h&quot; void main() { CDiophantine dp(1,2,3,4,30); int ans; ans =...

Исправить программу
Здравствуйте! У меня рабочая программа, которая удваивает каждый символ в строке, все работает) Препод сказал, что нужно сделать эту...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
27.05.2020, 12:13
Помогаю со студенческими работами здесь

исправить программу
Помогите исправить программу #include &lt;iostream&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include &lt;ctype.h&gt; #include...

Исправить программу С++
Помогите пожалуйста исправить программу. Нужно , чтобы массив задавался с клавиатуры , а не выдавал уже имеющиеся числа. Массив должен...

Исправить программу
Задание: Задан целочисленный одномерный массив а состоящий из n элементов. Написать программу вычисления суммы, разности и произведения...

Исправить программу
Здравствуйте, не могли бы подсказать, как переделать программу, чтобы она выдавала только одно слово да П.5.18.Правил Запрещено...

Исправить программу
Как сделать ,чтобы последовательность символов выводился после 1 символа в слове. Результат работы программы. Введите предложение : ...


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

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

Новые блоги и статьи
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя
Maks 08.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru