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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
18.10.2012, 23:07     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #1
Даны два неубывающих массива X=(xi),i=1..n, n<=10, и Y=(yi),i=1..m, m<=10 и число q. Найти сумму вида (x(i)+y(j)), наиболее близкую к числу q. (Число действий порядка m+n, дополнительная память - фиксированное число целых переменных, сами массивы менять не разрешается.)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2012, 23:07     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q
Посмотрите здесь:

C++ Найти элемент массива наиболее близкий к заданному числу.
C++ Найти элемент массива, значение которого наиболее близко к какому-нибудь целому числу
Найти два элемента массива, сумма которых наиболее близка к заданому числу. C++
Найти два элемента массива, сумма которых наименее близка к данному числу C++
Найти два различных элемента массива, сумма которых наиболее близка к числу R C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
19.10.2012, 11:04     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #2
Решение практически "в лоб"
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");
}
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
19.10.2012, 16:12  [ТС]     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #3
John Prick, До такого я тоже додумался, но тут слишком большое количество действий. Для n=10 и m=8 в худшем случае будет 80 действий, а нужно уложиться в 18.
В этом и загвоздка, что решение "в лоб" не прокатывает.
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
19.10.2012, 16:19     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #4
А, этот пункт упустил. Тогда подумать надо
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
19.10.2012, 16:23  [ТС]     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #5
John Prick, Ну, я поэтому сюда и скинул задачу) У меня только осталась идея как-нибудь использовать бинарный поиск.
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 22:48  [ТС]     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #6
Неужели никто не хочет/не может помочь? Помогите, пожалуйста!
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
25.10.2012, 22:50     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #7
Ну у тебя самого какие мысли есть?
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 22:57  [ТС]     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #8
John Prick, В том и дело, что я уже много вариантов перепробовал, и ничего не вышло. Я тупо не могу придумать алгоритм решения. А так как сижу на этой задаче долго, уже не могу посмотреть свежим взглядом на задачу.
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
25.10.2012, 23:09     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #9
Ну у меня сходу тож мало что придумывается. Ситуаций много: число больше максимальных элементов обоих массивов, число больше максимального элемента одного массива, но меньше максимального элемента другого, число меньше максимальных элементов обоих массивов, то же самое с "меньше минимального".

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

Добавлено через 2 минуты
Возможно, делить надо не на 2, а в долях, пропорциональных среднему квадратичному каждого из массивов.
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 23:21  [ТС]     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #10
John Prick, А код приблизительно набросать можешь? Я просто сейчас вообще ничего не соображаю, даже элементарных вещей не понимаю.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2012, 23:44     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q
Еще ссылки по теме:

Найти точку из множества A, наиболее близкую к точке B C++
C++ Найти элемент массива, который наиболее близок к данному числу
Найти номера элементов массива, равных заданному числу и номер числа расположенного наиболее близко к середине C++

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

Или воспользуйтесь поиском по форуму:
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
25.10.2012, 23:44     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q #11
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 и сравнивать вместе с дробной частью. И т.д...
Yandex
Объявления
25.10.2012, 23:44     Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q
Ответ Создать тему
Опции темы

Текущее время: 00:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru