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

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

Войти
Регистрация
Восстановить пароль
 
Mdx Can9
0 / 0 / 0
Регистрация: 30.06.2015
Сообщений: 29
#1

Отсортировать массив по убыванию и найти в нем элемент, равный X - C++

07.07.2015, 10:53. Просмотров 392. Ответов 2
Метки нет (Все метки)

Всем привет.Помогите написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск.Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2015, 10:53     Отсортировать массив по убыванию и найти в нем элемент, равный X
Посмотрите здесь:

C++ Упорядочить массив по убыванию элементов, найти минимальный элемент
C++ Отсортировать массив по убыванию и по возрастанию
C++ Найти максимальный элемент. Отсортировать предшествующие ему элементы по убыванию, а следующие за ним элементы по возрастанию.
C++ дан целочисленный массив Х из 30-ти элементов. найти в нем элемент с максимальным значением, обменять значениями найденный элемент массива с элементов
Создать двумерный массив N*M и найти в нем максимальный и минимальный элемент и их индексы C++
C++ Преобразовать одномерный массив и найти в нем элемент
C++ Отсортировать массив со случайными числами по убыванию
C++ Отсортировать массив по убыванию
Отсортировать массив по убыванию или по возрастанию C++
C++ Отсортировать массив по убыванию и найти в нем элемент, равный X
C++ Отсортировать массив по убыванию и найти количество и произведение элементов массива кратных 5
C++ Отсортировать массив на N элементов по убыванию

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kurles
154 / 119 / 29
Регистрация: 30.05.2015
Сообщений: 373
07.07.2015, 10:59     Отсортировать массив по убыванию и найти в нем элемент, равный X #2
В интернете полно реализаций как сортировки, так и бинарного поиска. Учитесь в гугл.
Геомеханик
534 / 341 / 258
Регистрация: 26.06.2015
Сообщений: 770
07.07.2015, 13:15     Отсортировать массив по убыванию и найти в нем элемент, равный X #3
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
#include <iostream>
#include <cstdlib>
void b_heapify(int* arr, size_t N, size_t i, 
               bool (*pcmp)(int, int));
void psort(int* arr, size_t N, bool (*pcmp)(int, int));
bool bfind(const int* f, const int* l, int x, 
           bool (*pcmp)(int, int));
 
bool compare(int a, int b){ return (a > b); }
 
 
 
int main(void){
    const size_t N = 20;
    int A[N];
 
    for(size_t i = 0; i < N; ++i){
        A[i] = std::rand() % 10;
        std::cout << A[i] << ' ';
    }
    std::cout << std::endl;
 
    //сортируем
    psort(A, N, compare);
 
    //вывести отсортированный массив
    for(size_t j = 0; j < N; ++j){
        // для теста
        if(bfind(A, A + N, A[j], compare))
            std::cout << A[j] << ' ';
    }
    std::cout << std::endl;
 
    // найти число X
    int X = 7;
/*  
    std::cout << "Enter X: ";
    std::cin  >> X;
    std::cin.sync();
*/
    if(bfind(A, A + N, X, compare))
        std::cout << "Yes find." << std::endl;
    else
        std::cerr << "not found X!" << std::endl;
    return 0;
}
 
 
/* двоичный поиск ищет значение в упорядоченном 
   массиве, значение x */
bool bfind(const int* f, const int* l, int x, 
           bool (*pcmp)(int, int)){
    size_t i, j, m;
    if((*pcmp)(x, *f) || (*pcmp)(*(l - 1), x))
        return false;
 
    i = 0;
    j = (size_t)(l - f);
    while(i < j){
        m = (i + j) >> 1;
        if((*pcmp)(x, f[m]))
            j = m;
        else {
            if(x == f[m])
                return true;
            i = m + 1;
        }
    }
    return false;
}
 
//---------------------------------------------
 
//восстановление свойства бинарной кучи
void b_heapify(int* arr, size_t N, size_t i, 
               bool (*pcmp)(int, int)) {
    size_t li, ri, big;
 
    while(1){
        li = (i << 1) + 1;
        ri = (i << 1) + 2;
        if((li < N) && (*pcmp)(arr[i], arr[li]))
            big = li;
        else
            big = i;
 
        if((ri < N) && (*pcmp)(arr[big], arr[ri]))
            big = ri;
 
        if(big != i){
            std::swap(arr[big], arr[i]);
            i = big;
        } else
            break;
    }
}
 
// пирамидальная сортировка
void psort(int* arr, size_t N, bool (*pcmp)(int, int)){
    //собрать кучу
    for(size_t i = N >> 1; i > 0; --i) 
        b_heapify(arr, N, i, pcmp);
    b_heapify(arr, N, 0, pcmp);
 
    for(size_t j = 0; j < N; ++j){
        std::swap(arr[0], arr[N - 1 - j]);
        b_heapify(arr, N - 1 - j, 0, pcmp);
    }
}
Результат работы кода
Yandex
Объявления
07.07.2015, 13:15     Отсортировать массив по убыванию и найти в нем элемент, равный X
Ответ Создать тему
Опции темы

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