0 / 0 / 0
Регистрация: 30.06.2015
Сообщений: 29
1

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

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

Всем привет.Помогите написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск.Заранее спасибо.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.07.2015, 10:53
Ответы с готовыми решениями:

Отсортировать массив по убыванию и найти в нем элемент, равный X
Помогите пожалуйста написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент,...

Отсортировать массив по убыванию и найти в нем все значения, равные введенному числу
Напишите программу, которая сортирует массив по убыванию и ищет в нем все значения, равные...

Сортировать массив ПО УБЫВАНИЮ и найти в нем элемент
Просьба перевести из Паскаля на С++ Const n=20; var a:array of integer; ...

Отсортировать массив по убыванию, затем добавить недостающий элемент и отсортировать массив по возрастанию
2) В массиве a ...a встречаются по одному разу все целые числа от 0 до n, кроме одного. За n...

2
161 / 126 / 30
Регистрация: 30.05.2015
Сообщений: 380
07.07.2015, 10:59 2
В интернете полно реализаций как сортировки, так и бинарного поиска. Учитесь в гугл.
0
837 / 640 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
07.07.2015, 13:15 3
Лучший ответ Сообщение было отмечено Mdx Can9 как решение

Решение

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);
    }
}
Результат работы кода
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.07.2015, 13:15
Помогаю со студенческими работами здесь

Массив: Найти в каждом столбце наибольший элемент и отсортировать все нижестоящие элементы по убыванию
Найти в каждом столбце матрицы наибольший элемент и отсортировать все нижестоящие элементыпо...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru