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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
#1

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

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

Задание:
В первой строке входных данных содержатся числа 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/statements/view.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");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.07.2014, 12:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному (C++):

Объясните программу по переводу каждого слова предложения на отдельную строку - C++
Добрый день. Помогите, пожалуйста, разобрать эту задачу. Распишите, чтобы было понятно новичку (не понимаю, что написано в условиях...

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

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

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

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

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

28
Хедин
74 / 69 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 12:48 #2

Не по теме:

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


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

Добавлено через 11 минут
Это я дал размер массиву.
key я обозначил b [ j ], так как он должен каждое b [ j ] брать и проверять на схожесть с массивом a [ i ].
0
Хедин
74 / 69 / 36
Регистрация: 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
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 13:10  [ТС] #5
можете объяснить свой код, пожалуйста.
по условию задачи память дается 100001.
0
Хедин
74 / 69 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 13:18 #6
shatov05, функции передается указатель на массив, левый крайний и правый крайний индексы и число-ключ. Проверяется, есть ли вообще хоть какие то числа между этими границами. Если нет, то проверяем, может быть искомое число как раз на одной из границ, если границы не подходят, то чисел для поиска больше нет, выходим. Если числа между границами есть, то находим центральный элемент, проверяем его на совпадение (если совпал, возвращаем значение mid), иначе вызываем функцию с новыми границами (то есть отсекли один из участков и передали его в другую функцию поиска)
1
Kuzia domovenok
2059 / 1904 / 174
Регистрация: 25.03.2012
Сообщений: 6,557
Записей в блоге: 1
17.07.2014, 14:11 #7
shatov05, сразу вопрос: массив отсортирован по возрастанию? Это важно!
Вместо того, чтобы бросать свои наработки и бездумно заменять на код от Хедин лучше всё-таки разобраться в причинах ошибки.
0
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:13  [ТС] #8
первый массив отсортирован. да. второй можно любой написать.. в чем ошибка может быть?
0
Kuzia domovenok
2059 / 1904 / 174
Регистрация: 25.03.2012
Сообщений: 6,557
Записей в блоге: 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
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:18  [ТС] #10
исправил... удалил
0
Хедин
74 / 69 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:21 #11
Согласен с Kuzia domovenok, лучше вначале все таки попытаться сравнить функции и найти ошибку
0
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:24  [ТС] #12
я уже 3 день не могу решить эту задачу. даже не знаю в чем ошибка уже..
0
Хедин
74 / 69 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:29 #13
shatov05, а в чем конкретно проблема? Судя по всему, у вас там не проверяются некоторые элементы
0
shatov05
0 / 0 / 0
Регистрация: 09.03.2014
Сообщений: 14
17.07.2014, 14:33  [ТС] #14
ну я вроде массивы ввел... проверил второй с первым.... он выдает ответ.. только не правильный..
0
Хедин
74 / 69 / 36
Регистрация: 17.05.2014
Сообщений: 301
17.07.2014, 14:36 #15
shatov05, скопируйте, что вводите и что выводит
0
17.07.2014, 14:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2014, 14:36
Привет! Вот еще темы с ответами:

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

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

Найти произведение двух соседних элементов массива, наиболее близкое по модулю к К - Turbo Pascal
Найти произведение двух соседних элементов массива, наиболее близкое по модулю к К.

Номер первого по порядку столбца массива, содержащей наиболее число пробелов - C#
Решить в консольном режиме : Найти : а)Номер первого по порядку столбца массива, содержащей наиболее число пробелов ; б)Номер...


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

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

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