Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Классы, моделирование товарного чека Всем привет ребят. Взялся за вот такое задание: Товарный чек содержит список товаров, купленных покупателем в магазине. Один элемент списка представляет собой пару: товар-сумма. Товар — это класс... https://www.cyberforum.ru/ cpp-beginners/ thread2719194.html Что выведет программа при вызове F(6)? C++
Что выведет программа при вызове F(6)? Пробелы не учитываются void F(int n) { if (n>=5) { F(n-1); printf("%d", n); F(n-3); } }
C++ c++ Дан номер дня – целое число от 1 до 31 и месяца — целое число в диапазоне 1–12 (1 — январь, 2 — февраль и т. д.). Вы https://www.cyberforum.ru/ cpp-beginners/ thread2719171.html
Дан номер дня – целое число от 1 до 31 и месяца — целое число в диапазоне 1–12 (1 — январь, 2 — февраль и т. д.). Вывести дату в виде текста (например, «пятое января»). C++
C++ Удаление нечётных элементов из бинарного дерева(что в моём коде не так?) Нужно удалить нечётные элементы из бинарного дерева. Одни у меня в программе удаляются, но заменяются на чётные. Как это исправить? #include<iostream> #include<cstdlib> using namespace std; ... https://www.cyberforum.ru/ cpp-beginners/ thread2719160.html
Определить,принадлежит ли точка с координатами Х,У заштрихованной части плоскости C++
Даны целые числа Х,У. Определить, принадлежит ли точка с координатами (Х,У) заштрихованной части плоскости. Составить математическую модель, алгоритм и программу . Заранее спасибо)
C++ Одна запись в списке запланированных дел представляет собой структуру Dai lyl tern, которая содержит время начала и Одна запись в списке запланированных дел представляет собой структуру Dai lyl tern, которая содержит время начала и окончания работы, описание и признак выполнения. Реализовать класс DailySchedule,... https://www.cyberforum.ru/ cpp-beginners/ thread2719150.html
C++ Найти число сочетаний https://www.cyberforum.ru/ cpp-beginners/ thread2719145.html
Даны натуральные числа m и n.Требуется найти число сочетаний из по известной рекуррентной формуле. Не используя рекурсию. Использовать стек Пользуйтесь редактором формул: C_{n}^{0}=1,\,...
C++ C++
Помогите кто может, написать программу: Нагрузка преподавателя за учебный год представляет собой список дисциплин, преподаваемых им в течение года. Одна дисциплина представляется информационной...
C++ Округление вверх Как округлить число n вверх в С++? https://www.cyberforum.ru/ cpp-beginners/ thread2719134.html C++ Описать функцию, меняющую местами первую и последнюю цифру трёхзначного числа Описать функцию void f(int *n), меняющую местами первую и последнюю цифру трёхзначного числа. Пример: 382 - 283. https://www.cyberforum.ru/ cpp-beginners/ thread2719128.html
C++ Задача с пост и предусловием
Решить задачу вычисления значения функции, содержащей сумму или (и) произведение. При вычислении суммы используется цикл с предусловием. При вычислении произведения используется цикл с...
C++ Сумма цифр в строке Почему при расчёте суммы выходит 5 ? Хотя должно быть 11. int main() { int i = 0; int sum = 0; string t = "10"; string a; char ch; for (i = 0; i < 11; i ++) https://www.cyberforum.ru/ cpp-beginners/ thread2719124.html
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689
0

Бинарный поиск в частично упорядоченном массиве - C++ - Ответ 14951852

28.10.2020, 13:10. Показов 1856. Ответов 1
Метки (Все метки)

Подскажите, пожалуйста, как получить из исходного массива, например, M[9, 10, 13, 2, 2, 5, 7, 8] массив Х[2, 2, 5, 7, 8, 9, 10, 13] с временной сложностью O(2log2n) и чтобы была та самая перестановка двух его частей, потому что у меня просто задается рандомный упорядоченный массив.

Дан частично упорядоченный массив, который был получен из упорядоченного по не убыванию элементов массива путем перестановки двух его частей. Например, массив M[9, 10, 13, 2, 2, 5, 7, 8] был получен из массива Х[2, 2, 5, 7, 8, 9, 10, 13]. Реализовать алгоритм поиска элемента А в массиве M, имеющий оценку временной сложности О(2log2n).
Входные данные
Частично упорядоченный массив M
Число А
Выходные данные
True, если число А содержится в массиве М, False – в противном случае.


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
#include <iostream>
#include <windows.h>
#include <cmath>
#include <iomanip>
#include <limits.h>
 
const int CP = 1251;
 
using namespace std;
 
void main() {
    SetConsoleOutputCP(CP);
    SetConsoleCP(CP);
    const int N = 8;
    int a[N];
    const int A = 0, B = 30;
    int i, imin, min, j, t;
    cout << "Сортировка массива по возрастанию\n";
    for (i = 0; i < N; i++)
        a[i] = A + rand() % (B - A + 1);//создание массива
 
    cout << "\n";
 
    for (i = 0; i < N; i++) {//Внешний цикл
        imin = i;
        min = a[i];
        for (j = i; j < N; j++) {
            if (a[j] < min) {
                min = a[j];
                imin = j;
            }//if
        }//for j
 
        //Меняем местами i-й и imin элемент a[i]----a[imin]
        t = a[i];
        a[i] = a[imin];
        a[imin] = t;
    }//for
 
    cout <<"Отсортированый массив по возрастанию\n";
    for (i = 0; i < N; i++) {
        cout << setw(3) << a[i];
        if ((i + 1) % 8 == 0)cout << "\n";
    }
    cout << "\n";
 
    int key, middle, right, left;
    bool find;
 
    cout << "Введите число: ";
    cin >> key;
 
    right = N - 1;
    left = 0;
    find = false;
    for (;;) {
 
        middle = (left + right) / 2;
        if (a[middle] == key) {
            find = true;
            break;
        }//if
        if (a[middle] < key) {
            left = middle;
        }//if
 
        if (a[middle] > key) {
            right = middle;
        }//if
        if (abs(left - right) <= 1) {
            break;
        }//if
    }
    if (find)
        cout << "True " << "\n";
    else {
        cout << "False " << "\n";
    }
}//for


Вернуться к обсуждению:
Бинарный поиск в частично упорядоченном массиве C++
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.10.2020, 13:10
Готовые ответы и решения:

Бинарный поиск в упорядоченном массиве
Задали реализовать бинарный поиск в упорядоченном массиве.Уже пол дня творю,3 листа исписал и...

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

Бинарный поиск числа в упорядоченном массиве
В упорядоченном массиве надо найти число. Программа должна выполняться с рекурсией

Бинарный (двоичный) поиск по алфавиту в упорядоченном массиве структур
Приветствую товарищей-программистов! Есть массив структур StructWords massiv. struct...

1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.10.2020, 13:10
Помогаю со студенческими работами здесь

Написать функцию, которая осуществляет бинарный поиск на упорядоченном полуинтервале
Написать функцию, которая осуществляет бинарный поиск на упорядоченном полуинтервале. В качестве...

Двоичный поиск в упорядоченном массиве
Дан упорядоченный по неубыванию целочисленный массив и набор чисел ki. Требуется для каждого числа...

Поиск элемента, меньшего заданного, в упорядоченном массиве
Добрый день. Мне необходимо найти в массиве первый элемент, который меньше заданного, и, очень...

Поиск заданного элемента в упорядоченном по возрастанию массиве целых чисел
Осуществить поиск заданного элемента в упорядоченном по возрастанию (по убыванию) массиве целых...

Бинарный поиск в упорядоченном по возрастанию массиве
9 лаб.работа Бинарный поиск в упорядоченном по возрастанию массиве

Бинарный поиск числа в упорядоченном массиве
Написать бинарный поиск искомого числа(введенного пользователем) в отсортированном массиве....

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