Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.74/34: Рейтинг темы: голосов - 34, средняя оценка - 4.74
0 / 0 / 0
Регистрация: 10.11.2014
Сообщений: 25

Бинарный поиск таких пар чисел массива, чтобы их сумма попадала в заданный диапазон

27.01.2015, 18:44. Показов 7022. Ответов 26
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
доброго времени суток. не смог разобраться с бинарным поиском, математически примерно имею представление, а написать программу не получается... есть массив из N чисел ( N=10e6). Необходимо осуществить бинарный поиск таких пар чисел в этом массиве, чтобы их сумма лежала в диапазоне от -10000 до +10000, т.е. равнялась бы одному из 20001 чисел. помогите, пожалуйста
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
27.01.2015, 18:44
Ответы с готовыми решениями:

Циклы. Среди натуральных чисел от 1 до 100 найти все пары чисел, для которых их сумма равна их произведению и кол-во таких пар.
Среди натуральных чисел от 1 до 100 найти все пары чисел, для которых их сумма равна их произведению и кол-во таких пар. Если таких чисел...

Найти все пары чисел, для которых их сумма равна их произведению и количество таких пар
может есть какие-нибудь другие варианты? procedure TForm1.Button1Click(Sender: TObject); var i,j: integer; begin ListBox1.Clear; ...

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

26
 Аватар для 1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
28.01.2015, 16:58
Студворк — интернет-сервис помощи студентам
... в ответе должно быть 6 пар, а программа выдает 0.
видимо q++ не работает, возможно я неправильно написал бин.поиск или еще что-то
Важно: укажите в файле 10e6.txt хотя бы одно число в диапазоне от -100 до +100 ?!?!?!
0
 Аватар для 1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
28.01.2015, 17:23
Скачайте архив (исходник ниже в след. посте):
Вложения
Тип файла: zip Test-Exe_w10e6+out.zip (599.9 Кб, 5 просмотров)
0
 Аватар для 1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
28.01.2015, 17:29
Лучший ответ Сообщение было отмечено shadow_Azat как решение

Решение

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
#include <stdio.h>
#include <conio.h>
#include <memory.h>
 
#define N 201
#define LEN 100000
 
int bsearch(int begin, int end, int* pn, int value)
{
    int mid = begin + (end - begin) / 2;
    if (pn[mid] == value) return mid;
    else if (pn[mid] > value && mid != begin && mid != end)
        return bsearch(begin, mid, pn, value);
    else if (pn[mid] < value && mid != begin && mid != end)
        return bsearch(mid, end, pn, value);
 
    return -1;
}
 
int main(int argc, char* argv[])
{
    FILE* fp = NULL;
    char* filename = "10e6.txt";
    if ((fp = fopen(filename, "r+")) == NULL)
    {
        printf("Unable to open file %s for reading\n", filename);
        return -1;
    }
 
    int* A = new int[LEN - 1];
    memset((void*)A, 0x00, sizeof(int)*(LEN - 1));
 
    for (int i = 0; !feof(fp); i++)
        fscanf(fp, "%d", &A[i]);
 
    int pn[N] = { 0 };
    memset((void*)pn, 0x00, sizeof(int)* N);
 
    int n = 0, x = -100;
    while (x <= 100)
    {
        *(pn + n) = x++;
        n++;
    }
 
    int count = 0;
    for (int i = 0; i < LEN; i++)
    {
        for (int j = i + 1; j < LEN; j++)
        {
            int pos = -1;
            int u = A[i] + A[j];
            if (u >= -100 && u <= 100)
            {
                if ((pos = bsearch(0, n, pn, u)) != -1)
                {
                    printf("A[%d] = %d A[%d] = %d sum = %d pn[%d] = %d\n", i, A[i], j, A[j], u, pos, pn[pos]);
                    count++;
                }
            }
        }
    }
 
    printf("\ncount = %d\n", count);
    
    return 0;
}
Файл проект (тоже скачайте):
Вложения
Тип файла: zip Test.zip (9.7 Кб, 6 просмотров)
1
0 / 0 / 0
Регистрация: 10.11.2014
Сообщений: 25
28.01.2015, 17:31  [ТС]
спасибо! сейчас скомпилирую
0
 Аватар для 1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
28.01.2015, 17:33
там есть уже скомпилированный Test-Exe_w10e6+out.zip скачайте выше
0
0 / 0 / 0
Регистрация: 10.11.2014
Сообщений: 25
28.01.2015, 17:55  [ТС]
1XPLoade1, спасибо большое! все работает!
0
 Аватар для 1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
28.01.2015, 17:58
да. не за что. все.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
28.01.2015, 17:58

Вектор пар и бинарный поиск
Всем доброго времени суток. Решаю следующую задачу. Есть vector &lt;pair&lt;int,int&gt;&gt; v я его сортирую и потом...

Найти количество таких пар элементов, сумма которых равна заданному числу М
1. Составить программу, которая в целочисленной таблице С, состоящей из N чисел находит количество таких пар элементов, сумма которых равна...

Поиск количества трехзначных чисел, таких, что сумма цифр единиц и десятков этого числа равна самому числу
Написать программу поиска количества трехзначных чисел, таких, что сумма цифр единиц и десятков этого числа равна самому числу. Сделать с...

Бинарный поиск произведения и суммы чисел массива
Создать массив на 16 ячеек. Найти произведение элементов этого массива до первого числа 8 и сумму элементов, расположенных после него. Все...

Даны n пар чисел в каждой строке, выбрать одно число из каждой пары так, чтобы сумма их минимальна
Даны n пар чисел в каждой строке, выбратт одно число из каждой пары так, чтобы сумма их минимальна и не кратна 7. Помогите пожалуйста,...


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

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Новые блоги и статьи
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle | Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru