Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
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 - C++

18.10.2012, 23:07. Просмотров 1383. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Даны два неубывающих массива X=(xi),i=1.n, n<=10, и Y=(yi),i=1.m, m<=10 и число q. Найти сумму вида (x(i)+y(j), наиболее близкую к числу q (C++):

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

Найти два различных элемента массива, сумма которых наиболее близка к числу R - C++
Найти два различных элемента массива, сумма которых наиболее близка к числу R. С соседними все понятно, но как перебрать все различные...

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

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

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

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

10
John Prick
805 / 738 / 146
Регистрация: 27.07.2012
Сообщений: 2,110
Завершенные тесты: 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
805 / 738 / 146
Регистрация: 27.07.2012
Сообщений: 2,110
Завершенные тесты: 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
805 / 738 / 146
Регистрация: 27.07.2012
Сообщений: 2,110
Завершенные тесты: 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
805 / 738 / 146
Регистрация: 27.07.2012
Сообщений: 2,110
Завершенные тесты: 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
805 / 738 / 146
Регистрация: 27.07.2012
Сообщений: 2,110
Завершенные тесты: 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[1] ≤… ≤ x[k], y[1] ≤ … ≤ y[l] и число q. Найти сумму вида... - C#
Даны два массива: x ≤… ≤ x, y ≤ … ≤ y и число q.Найти сумму вида x + y, наиболее близкую к числу q (число действий порядка k + l,...

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

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

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


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

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

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