Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/21: Рейтинг темы: голосов - 21, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28

Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q

18.10.2012, 23:07. Показов 4412. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Даны два неубывающих массива X=(xi),i=1..n, n<=10, и Y=(yi),i=1..m, m<=10 и число q. Найти сумму вида (x(i)+y(j)), наиболее близкую к числу q. (Число действий порядка m+n, дополнительная память - фиксированное число целых переменных, сами массивы менять не разрешается.)
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
18.10.2012, 23:07
Ответы с готовыми решениями:

Массив: Найти сумму вида X[i]+Y[i] , наиболее близкую к числу q
.Даны два массива x &lt;=...&lt;=X, и Y &lt;=...&lt;=Y и число q . Найти сумму вида X+Y , наиболее близкую к числу q

Найти сумму элементов из двух массивов, наиболее близкую к заданному числу
Даны два массива x содержащий k элементов и y содержащий n элементов и число q. Найти сумму вида x+y, наиболее близкую к числу q

Дано число и массив, найти два элемента массива сумма которых наиболее близка к числу
дано число и массив, найти два элемента массива сумма которых наиболее близка к числу r. Я нашел только один элемент,как найти два? ...

10
2395 / 1924 / 763
Регистрация: 27.07.2012
Сообщений: 5,569
19.10.2012, 11:04
Решение практически "в лоб"
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
/*
Даны два неубывающих массива X=(xi),i=1..n, n<=10, и Y=(yi),i=1..m, m<=10 и число q.
Найти сумму вида (x(i)+y(j)), наиболее близкую к числу q. (Число действий порядка m+n,
дополнительная память - фиксированное число целых переменных, сами массивы менять не разрешается.)
*/
 
#include <iostream>
#include <algorithm>
 
const int N = 10;
const int M = 8;
 
int getRand(void) { return rand() % 10; }
 
int main(void)
{
    setlocale(0, "rus");
    int X[N];
    int Y[M];
    // генерируем массивы
    std::generate(X, X + N, getRand);
    std::generate(Y, Y + M, getRand);
    // делаем их неубывающими
    std::sort(X, X + N);
    std::sort(Y, Y + M);
 
    std::cout << "Массив X: ";
    std::copy(X, X + N, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    std::cout << "Массив Y: ";
    std::copy(Y, Y + M, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::cout << '\n';
    int q = 0;
    std::cout << "Введите: q = ";
    std::cin >> q;
 
    int minDistance = q;
    int minI = 0, minJ = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (abs( (X[i] + Y[j]) - q ) < minDistance)
            {
                minDistance = abs( (X[i] + Y[j]) - q );
                minI = i;
                minJ = j;
            }
        }
    }
    std::cout << "Решение: " << "X[" << minI << "] + Y[" << minJ << "] = " << X[minI] + Y[minJ] << std::endl;
    system("pause");
}
1
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
19.10.2012, 16:12  [ТС]
John Prick, До такого я тоже додумался, но тут слишком большое количество действий. Для n=10 и m=8 в худшем случае будет 80 действий, а нужно уложиться в 18.
В этом и загвоздка, что решение "в лоб" не прокатывает.
0
2395 / 1924 / 763
Регистрация: 27.07.2012
Сообщений: 5,569
19.10.2012, 16:19
А, этот пункт упустил. Тогда подумать надо
0
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
19.10.2012, 16:23  [ТС]
John Prick, Ну, я поэтому сюда и скинул задачу) У меня только осталась идея как-нибудь использовать бинарный поиск.
0
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 22:48  [ТС]
Неужели никто не хочет/не может помочь? Помогите, пожалуйста!
0
2395 / 1924 / 763
Регистрация: 27.07.2012
Сообщений: 5,569
25.10.2012, 22:50
Ну у тебя самого какие мысли есть?
0
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 22:57  [ТС]
John Prick, В том и дело, что я уже много вариантов перепробовал, и ничего не вышло. Я тупо не могу придумать алгоритм решения. А так как сижу на этой задаче долго, уже не могу посмотреть свежим взглядом на задачу.
0
2395 / 1924 / 763
Регистрация: 27.07.2012
Сообщений: 5,569
25.10.2012, 23:09
Ну у меня сходу тож мало что придумывается. Ситуаций много: число больше максимальных элементов обоих массивов, число больше максимального элемента одного массива, но меньше максимального элемента другого, число меньше максимальных элементов обоих массивов, то же самое с "меньше минимального".

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

Добавлено через 2 минуты
Возможно, делить надо не на 2, а в долях, пропорциональных среднему квадратичному каждого из массивов.
0
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 23:21  [ТС]
John Prick, А код приблизительно набросать можешь? Я просто сейчас вообще ничего не соображаю, даже элементарных вещей не понимаю.
0
2395 / 1924 / 763
Регистрация: 27.07.2012
Сообщений: 5,569
25.10.2012, 23:44
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
/*
Даны два неубывающих массива X=(xi),i=1..n, n<=10, и Y=(yi),i=1..m, m<=10 и число q.
Найти сумму вида (x(i)+y(j)), наиболее близкую к числу q. (Число действий порядка m+n,
дополнительная память - фиксированное число целых переменных, сами массивы менять не разрешается.)
*/
 
#include <iostream>
#include <algorithm>
 
const int N = 10;
const int M = 8;
 
int getRand(void) { return rand() % 10; }
 
int main(void)
{
    setlocale(0, "rus");
    int X[N];
    int Y[M];
    // генерируем массивы
    std::generate(X, X + N, getRand);
    std::generate(Y, Y + M, getRand);
    // делаем их неубывающими
    std::sort(X, X + N);
    std::sort(Y, Y + M);
 
    std::cout << "Массив X: ";
    std::copy(X, X + N, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    std::cout << "Массив Y: ";
    std::copy(Y, Y + M, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::cout << '\n';
    int q = 0;
    std::cout << "Введите: q = ";
    std::cin >> q;
 
    int minDistance = q / 2;
    int minI = N, minJ = M;
    for (int i = 1; i < N; ++i)
    {
        if ((X[i - 1] <= minDistance) && (X[i] >= minDistance))
        {
            minI = i;
            break;
        }
    }
    for (int j = 1; j < M; ++j)
    {
        if ((Y[j - 1] <= minDistance) && (Y[j] >= minDistance))
        {
            minJ= j;
            break;
        }
    }
 
    std::cout << "Решение: " << "X[" << minI << "] + Y[" << minJ << "] = " << X[minI] + Y[minJ] << std::endl;
    system("pause");
}
Ну как-то так, но всё равно это несовершенный алгоритм. При нечётных числах не находит точного совпадения. Нужно дорабатывать.

Добавлено через 1 минуту
Цитата Сообщение от Liveral486 Посмотреть сообщение
Я просто сейчас вообще ничего не соображаю, даже элементарных вещей не понимаю.
Тогда ложись спать. На свежую голову решения эффективнее приходят.

Добавлено через 10 минут
Пока из видимы улучшений: сравнивать не просто "больше предыдущего, меньше текущего", а вычислять разницу с предыдущим и с текущим и брать ту i, где эта разница наименьшая. Делить не на 2, а как уже говорил, на какое-нибудь более "информативное" число. Наверное, для minDistance взять тип double и сравнивать вместе с дробной частью. И т.д...
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.10.2012, 23:44
Помогаю со студенческими работами здесь

Даны два неубывающих массива x и y. Найти их соединение, то есть неубывающий массив z
Даны два неубывающих массива x и y. Найти их соединение, то есть неубывающий массив z, содержащий все их элементы, причем каждый элемент...

Даны два массива: x[1] ≤… ≤ x[k], y[1] ≤ … ≤ y[l] и число q. Найти сумму вида...
Даны два массива: x ≤… ≤ x, y ≤ … ≤ y и число q.Найти сумму вида x + y, наиболее близкую к числу q (число действий порядка k + l,...

Дано число R и массив размера N. Найти два соседних элемента массива, сумма которых наиболее близка к числу R,и вывести эти элементы
Дано число R и массив размера N. Найти два соседних элемента мас- сива, сумма которых наиболее близка к числу R, и вывести эти элементы в...

Найти сумму трех соседних элементов массива наиболее "близкую" по модулю к значению K.
Найти сумму трех соседних элементов массива наиболее &quot;близкую&quot; по модулю к значению K. Добавлено через 55 минут 37 секунд дупустим...

Даны два неубывающих списка x и y: найти их соединение
Даны два неубывающих списка x и y. Найти их соединение, то есть неубывающий список z, содержащий все их элементы, причем каждый элемент...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
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. Задача: при создании документов установить период списания автоматически. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru