0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
1

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

17.07.2014, 12:47. Показов 10380. Ответов 28
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задание:
В первой строке входных данных содержатся числа 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/mo... p?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");
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.07.2014, 12:47
Ответы с готовыми решениями:

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному
Здравствуйте,помогите пожалуйста написать код,спасибо.Реализуйте алгоритм приближенного бинарного...

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному
Формат входных данных В первой строке входных данных содержатся числа N и K (0&lt;N,K&lt;100001 ). Во...

Найти число наиболее близкое к заданному для массива 8-разрядных чисел со знаком
Помогите, найти ошибку) format PE console ; 32-разрядная консольная...

Для каждого из K чисел вывести в отдельную строку "YES", если число встречается в первом массиве
Здравствуйте,помогите пожалуйста написать код,спасибо.Реализуйте алгоритм бинарного поиска.Входные...

28
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 12:48 2

Не по теме:

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


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

Добавлено через 11 минут
Это я дал размер массиву.
key я обозначил b [ j ], так как он должен каждое b [ j ] брать и проверять на схожесть с массивом a [ i ].
0
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 13:07 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;
}
на будущее, ну вы так щедро то память не раскидывайте
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 13:10  [ТС] 5
можете объяснить свой код, пожалуйста.
по условию задачи память дается 100001.
0
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 13:18 6
shatov05, функции передается указатель на массив, левый крайний и правый крайний индексы и число-ключ. Проверяется, есть ли вообще хоть какие то числа между этими границами. Если нет, то проверяем, может быть искомое число как раз на одной из границ, если границы не подходят, то чисел для поиска больше нет, выходим. Если числа между границами есть, то находим центральный элемент, проверяем его на совпадение (если совпал, возвращаем значение mid), иначе вызываем функцию с новыми границами (то есть отсекли один из участков и передали его в другую функцию поиска)
1
4063 / 3317 / 924
Регистрация: 25.03.2012
Сообщений: 12,483
Записей в блоге: 1
17.07.2014, 14:11 7
shatov05, сразу вопрос: массив отсортирован по возрастанию? Это важно!
Вместо того, чтобы бросать свои наработки и бездумно заменять на код от Хедин лучше всё-таки разобраться в причинах ошибки.
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:13  [ТС] 8
первый массив отсортирован. да. второй можно любой написать.. в чем ошибка может быть?
0
4063 / 3317 / 924
Регистрация: 25.03.2012
Сообщений: 12,483
Записей в блоге: 1
17.07.2014, 14:14 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 нигде не используется?
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:18  [ТС] 10
исправил... удалил
0
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:21 11
Согласен с Kuzia domovenok, лучше вначале все таки попытаться сравнить функции и найти ошибку
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:24  [ТС] 12
я уже 3 день не могу решить эту задачу. даже не знаю в чем ошибка уже..
0
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:29 13
shatov05, а в чем конкретно проблема? Судя по всему, у вас там не проверяются некоторые элементы
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:33  [ТС] 14
ну я вроде массивы ввел... проверил второй с первым.... он выдает ответ.. только не правильный..
0
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:36 15
shatov05, скопируйте, что вводите и что выводит
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:45  [ТС] 16
н = 5, k = 4.

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

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

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

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

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

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

Добавлено через 1 минуту
вот. отправил
0
76 / 71 / 55
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:52 17
shatov05, а что неправильно то? 5 находится на 3 позиции, 6 нет, 1 находится на первой позиции, 9 тоже нет. Что не так?
1
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:56  [ТС] 18
а.. то есть я на правильном пути.. но он должен выдавать такой ответ как на этом сайте http://informatics.mccme.ru/mo... p?id=192#1
0
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 4
17.07.2014, 16:16 19
Если есть желание могу скинуть рабочее решение, но со временем работы у него мелкие проблемы, позже перепишу(наверно), а так при данных с сайта 0.729 на всю обработку.
0
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 17:10  [ТС] 20
скинь плиз
0
17.07.2014, 17:10
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.07.2014, 17:10
Помогаю со студенческими работами здесь

В последовательности из n чисел найдите число, наиболее близкое к "x"
В последовательности из n чисел найдите число, наиболее близкое к x. Если к x одинаково близки два...

Найти наиболее близкое число
Вот такое задание: Есть файлик с числами, пользователь вводит b и x, высчитывается функция, потом...

Найти беззнаковое число наиболее близкое к заданному
Напишите пожалуйста программу на Ассемблере. Вот задание: Найти беззнаковое число наиболее близкое...

Как найти наиболее близкое число в массиве?
Здравствуйте! Есть массив var a = и есть число var b = -620 Как выбрать...

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

Найти число, наиболее близкое какому-нибудь целому числу
используя цикол написать программу обеспечивающую ввод N вещественных чисел и выводящую на экран то...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru