|
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), наиболее близкую к числу q18.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
|
|
| 18.10.2012, 23:07 | |
|
Ответы с готовыми решениями:
10
Массив: Найти сумму вида X[i]+Y[i] , наиболее близкую к числу q
Дано число и массив, найти два элемента массива сумма которых наиболее близка к числу |
|
2395 / 1924 / 763
Регистрация: 27.07.2012
Сообщений: 5,569
|
||||||
| 19.10.2012, 11:04 | ||||||
|
Решение практически "в лоб"
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 | |||||||
Добавлено через 1 минуту Добавлено через 10 минут Пока из видимы улучшений: сравнивать не просто "больше предыдущего, меньше текущего", а вычислять разницу с предыдущим и с текущим и брать ту i, где эта разница наименьшая. Делить не на 2, а как уже говорил, на какое-нибудь более "информативное" число. Наверное, для minDistance взять тип double и сравнивать вместе с дробной частью. И т.д...
1
|
|||||||
| 25.10.2012, 23:44 | |
|
Помогаю со студенческими работами здесь
11
Даны два массива: x[1] ≤… ≤ x[k], y[1] ≤ … ≤ y[l] и число q. Найти сумму вида...
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Установка 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.
Задача: при создании документов установить период списания автоматически. . .
|