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

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 12:47     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #1
Задание:
В первой строке входных данных содержатся числа N и K (0NK100001). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109.

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
Пример:

Входные данные:
5 4
1 4 5 8 10
5 6 1 9

Выходные данные:
5
5
1
8

http://informatics.mccme.ru/mod/stat...w.php?id=192#1 - Это задача


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
#include <iostream>
using namespace std;
const int n = 5 ; //двоичный поиск
int BinarySearch(int a[], int key)
{
    int left = 0, right = n, mid;
    while (left <= right)
    {
        mid = left + (right - left)/2;
        if (key < a[mid]) right = mid-1;
        else if (key > a[mid]) left = mid+1;
        else return mid;
    }
    return -1;
}
//главная функция
void main()
{
    setlocale(LC_ALL,"Rus");
    int i, key, k, n;
    int a[100001], b[100001];
    cin >> n >> k;
    cout<<"Первый массив: ";
    for (i = 0; i < n; i++) //заполнение и вывод массива
    { cin >> a[ i ]; }
    cout<<"Второй массив: ";
    for (int j = 0; j < k; j++){
        cin >> b[ j ];} 
        for ( int j = 0; j < k; j++)   {
            key = b[ j ] ; 
              for ( int i = 0; i < n; i++){ 
    if (BinarySearch(a, key)==-1) cout<<"\nЭлемент не найден";
    else cout<<"\nНомер элемента: "<<BinarySearch(a, key)+1;}}
    system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.07.2014, 12:47     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному
Посмотрите здесь:

Дано вещественное число R и массив вещественных чисел. Найти 2 элементы массива, которые наименее близки к данному числу R C++
C++ Сравнение (значение из ряда, наиболее близкое к полученному)
C++ Выведите на экран значения корней и квадратов каждого из элементов массива
Как создать отдельную функцию для каждого объекта класса C++
C++ Массив. Выведите на экран значения корней и квадратов каждого из элементов массива
C++ Найти элемент массива, который наиболее близок к данному числу
Найти произведение двух последовательностей наиболее близкое к числу R C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 12:48     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #2

Не по теме:

shatov05, бинарный наверно поиск?


C++
1
int a[100001], b[100001];
это вы эмулировали двоичные числа?
И где вводится key? У вас там мусорное значение будет, если не забьете туда число
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 13:03  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #3
ах да.

Добавлено через 11 минут
Это я дал размер массиву.
key я обозначил b [ j ], так как он должен каждое b [ j ] брать и проверять на схожесть с массивом a [ i ].
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 13:07     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #4
shatov05, по идее поиск будет так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binarySearch(int *a, int left, int right, int key)
{
    if (right-left == 1)
    {
        if (a[right] == key) return right;
        if (a[left] == key) return left;
        return -1;
    }
    int mid = left + (right-left)/2;
    return (a[mid] == key ? mid : a[mid] > key ? binarySearch(a, left, mid, key) : binarySearch(a, mid, right, key));
}
 
int main()
{
    int x[7] = {1, 2, 3, 4, 5, 8, 10};
    cout << binarySearch(&x[0], 0, 6, 10) << endl;
    return 0;
}
на будущее, ну вы так щедро то память не раскидывайте
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 13:10  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #5
можете объяснить свой код, пожалуйста.
по условию задачи память дается 100001.
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 13:18     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #6
shatov05, функции передается указатель на массив, левый крайний и правый крайний индексы и число-ключ. Проверяется, есть ли вообще хоть какие то числа между этими границами. Если нет, то проверяем, может быть искомое число как раз на одной из границ, если границы не подходят, то чисел для поиска больше нет, выходим. Если числа между границами есть, то находим центральный элемент, проверяем его на совпадение (если совпал, возвращаем значение mid), иначе вызываем функцию с новыми границами (то есть отсекли один из участков и передали его в другую функцию поиска)
Kuzia domovenok
 Аватар для Kuzia domovenok
1886 / 1741 / 117
Регистрация: 25.03.2012
Сообщений: 5,910
Записей в блоге: 1
17.07.2014, 14:11     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #7
shatov05, сразу вопрос: массив отсортирован по возрастанию? Это важно!
Вместо того, чтобы бросать свои наработки и бездумно заменять на код от Хедин лучше всё-таки разобраться в причинах ошибки.
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:13  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #8
первый массив отсортирован. да. второй можно любой написать.. в чем ошибка может быть?
Kuzia domovenok
 Аватар для Kuzia domovenok
1886 / 1741 / 117
Регистрация: 25.03.2012
Сообщений: 5,910
Записей в блоге: 1
17.07.2014, 14:14     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #9
Цитата Сообщение от shatov05 Посмотреть сообщение
C++
1
2
3
4
5
6
7
for (int j = 0; j < k; j++){ cin >> b[ j ];}
 for ( int j = 0; j < k; j++) {
   key = b[ j ] ; 
  for ( int i = 0; i < n; i++){ 
    if (BinarySearch(a, key)==-1) cout<<"\nЭлемент не найден"; 
    else cout<<"\nНомер элемента: "<<BinarySearch(a, key)+1;
}}
вот это какой-то бред! что за циклы такие? Зачем нужен второй цикл по i, если i нигде не используется?
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:18  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #10
исправил... удалил
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:21     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #11
Согласен с Kuzia domovenok, лучше вначале все таки попытаться сравнить функции и найти ошибку
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:24  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #12
я уже 3 день не могу решить эту задачу. даже не знаю в чем ошибка уже..
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:29     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #13
shatov05, а в чем конкретно проблема? Судя по всему, у вас там не проверяются некоторые элементы
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:33  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #14
ну я вроде массивы ввел... проверил второй с первым.... он выдает ответ.. только не правильный..
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:36     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #15
shatov05, скопируйте, что вводите и что выводит
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:45  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #16
н = 5, k = 4.

первый массив : 1 4 5 8 10
второй массив : 5 6 1 9

ответ выводит:

Номер элемента : 3

Элемент не найден

Номер элемента : 1

Элемент не найден

Добавлено через 1 минуту
вот. отправил
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:52     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #17
shatov05, а что неправильно то? 5 находится на 3 позиции, 6 нет, 1 находится на первой позиции, 9 тоже нет. Что не так?
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:56  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #18
а.. то есть я на правильном пути.. но он должен выдавать такой ответ как на этом сайте http://informatics.mccme.ru/mod/stat...w.php?id=192#1
DarkerSigner
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 4
17.07.2014, 16:16     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #19
Если есть желание могу скинуть рабочее решение, но со временем работы у него мелкие проблемы, позже перепишу(наверно), а так при данных с сайта 0.729 на всю обработку.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2014, 17:10     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному
Еще ссылки по теме:

Объясните программу по переводу каждого слова предложения на отдельную строку C++
После каждого отрицательного числа вставьте в вектор отрицательное число -20 и выведите содержимое вектора C++
Найти значение температуры наиболее близкое к нулю C++
Получить делимое, наиболее близкое к заданному числу C++
C++ Для каждого прочитанного числа напечатать строку, содержащую соответствующее число звездочек

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

Или воспользуйтесь поиском по форуму:
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 17:10  [ТС]     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному #20
скинь плиз
Yandex
Объявления
17.07.2014, 17:10     Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному
Ответ Создать тему
Опции темы

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