Форум программистов, компьютерный форум, киберфорум
C/С++ под Linux
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/1: Рейтинг темы: голосов - 1, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 17.11.2019
Сообщений: 41

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

27.05.2020, 12:13. Показов 1025. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизита табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru