Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
1

Даны два неубывающих массива 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. Просмотров 1683. Ответов 10
Метки нет (Все метки)

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

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

Найти два элемента массива, сумма которых наиболее близка к заданому числу.
Помогите пожалуйста, срочно нужно написать такую программу: задано...

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

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

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

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

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

Добавлено через 2 минуты
Возможно, делить надо не на 2, а в долях, пропорциональных среднему квадратичному каждого из массивов.
0
Liveral486
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 28
25.10.2012, 23:21  [ТС] 10
John Prick, А код приблизительно набросать можешь? Я просто сейчас вообще ничего не соображаю, даже элементарных вещей не понимаю.
0
John Prick
837 / 768 / 258
Регистрация: 27.07.2012
Сообщений: 2,180
Завершенные тесты: 3
25.10.2012, 23:44 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 и сравнивать вместе с дробной частью. И т.д...
1
25.10.2012, 23:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2012, 23:44

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru