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

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

Войти
Регистрация
Восстановить пароль
 
 
Тан10шка
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 7
#1

Элемент в массиве через двоичную систему поиска - C++

10.02.2012, 11:35. Просмотров 901. Ответов 15
Метки нет (Все метки)

Нужно найти элемент в массиве через двоичную систему поиска и поставить счетчик, который вычислит количество операций сравнений.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2012, 11:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Элемент в массиве через двоичную систему поиска (C++):

перевод в двоичную систему через классы - C++
Помогите решить задачу используя классы. Дано натуральное число Р. Переведите его в двоичную систему счисления.

Юникод в двоичную систему - C++
Добрый день! Подскажите, как из файла прочитать знак (на русском языке), после чего напечатать на экране представление знака в двоичной...

Задача на двоичную систему - C++
Необходимо вывести в консоль все положительные четырехзначные числа, в записи которых нет 7. Понимаю что скорее всего надо использовать...

Перевод в двоичную систему - C++
Есть такой рабочий код #include <iostream> #include <locale.h> using namespace std; int main(void) { setlocale(LC_ALL,...

Перевод числа в двоичную систему - C++
Скажите , что не так в коде? Перевод в 2ичную систему счисления . Получается бесконечным int main() { ...

Перевод в двоичную систему счисления - C++
Пожалуйста, помогите с задачкой. Даны два числа a, b их нужно сперва перевести в двоичную систему счисления (сами они из десятичной), а...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
-=ЮрА=-
Заблокирован
Автор FAQ
10.02.2012, 17:24 #2
Цитата Сообщение от Тан10шка Посмотреть сообщение
Нужно найти элемент в массиве через двоичную систему поиска и поставить счетчик, который вычислит количество операций сравнений.
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
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
 
int getBinVal(int val)
{
    int binRew = val - 2*(val/2);
    while(0 < (val /= 2))
    {
        binRew *= 10;
        binRew += val - 2*(val/2);
    }
    //Òåïåðü "ïåðåâîðГ*Г·ГЁГўГ*ГҐГ¬" äâîè÷Г*îå çåðêГ*ëî Г·ГЁГ±Г«Г*
    int binVal = binRew % 10;
    while(0 < (binRew /= 10))
    {
        binVal *= 10;
        binVal += binRew % 10;
    }
    return binVal;
}
 
int main()
{
    int * arr = 0;
    int i, n, binMask, count;
    time_t t;
    while(true)
    {
        srand(time(&t));//×òîáû îò ГЁГІГҐГ°Г*öèè ГЄ ГЁГІГҐГ°Г*öèè ñëó÷Г*Г©Г*ûå Г·ГЁГ±Г«Г* Г*ГҐ ïîâòîðÿëèñü
        cout<<"Enter num of elements : ";cin>>n;
        if(!(arr = new int[n]))
            cout<<"Allocation memory error\n";
        else
        {
            count = 0;
            for(i = 0; i < n; i++)
                cout<<(arr[i] = rand()%256)<<" ";
            cout<<"\nEnter binary mask : ";cin>>binMask;
            for(i = 0; i < n; i++)
            {
                if(getBinVal(arr[i]) == binMask)
                {
                    cout<<"arr["<<i + 1<<"] = "<<arr[i]<<endl;
                    count++;
                }
            }
            delete [] arr;
        }
        arr = 0;
    }
    system("pause");
    return 0;
}
Алгоритм нахождения двоичного числа на скрине
0
Миниатюры
Элемент в массиве через двоичную систему поиска   Элемент в массиве через двоичную систему поиска  
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.02.2012, 17:28 #3
Хм, желательно пояснение от ТС. Может быть имелся в виду бинарный поиск в отсортированном массиве (хотя про отсортированность не было ни слова...)?
0
-=ЮрА=-
10.02.2012, 17:36
  #4

Не по теме:

Цитата Сообщение от I.M. Посмотреть сообщение
(хотя про отсортированность не было ни слова...)?
- I.M., а откуда отсортированность вообще взялась???

0
I.M.
10.02.2012, 17:41
  #5

Не по теме:

Не более, чем предположение Ведь если трактовать условие как "реализуйте-ка бинарный поиск", то нужно сортировать массив перед поиском.

0
-=ЮрА=-
10.02.2012, 17:44
  #6

Не по теме:

Цитата Сообщение от I.M. Посмотреть сообщение
то нужно сортировать массив перед поиском.
- есть массив, есть число в двоичном представлении binMask, нужно каждый элемент массива перевести в двоичное и сравнить с binMask, вот и всё...

0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.02.2012, 17:57 #7
Возможно, мы говорим о разных вещах, именуя их одинаково. Я говорю об этом - Бинарный поиск.
При реализации этого алгоритма актуально и другое требование ТС -
поставить счетчик, который вычислит количество операций сравнений
Т.е. счетчик выдаст число шагов, за которое алгоритм нашел искомый элемент.
Но, повторюсь, это не более, чем предположение. Вполне возможно, что вы уже верно решили поставленную задачу.
0
-=ЮрА=-
Заблокирован
Автор FAQ
10.02.2012, 17:58 #8
Тан10шка,
Цитата Сообщение от I.M. Посмотреть сообщение
поставить счетчик, который вычислит количество операций сравнений
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
count++;
- я забыл в cout вывести
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
10.02.2012, 18:07 #9
Цитата Сообщение от Тан10шка Посмотреть сообщение
Элемент в массиве через двоичную систему поиска
Здесь binary search, точно. Т.к. иначе билеберда получается.
0
Тан10шка
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 7
11.02.2012, 11:36  [ТС] #10
Спасибо!!!

Проблема в том,что точного задания я так и не получила.
Но я думаю,что бинарный поиск ето именно то
0
easybudda
Модератор
Эксперт CЭксперт С++
9622 / 5570 / 946
Регистрация: 25.07.2009
Сообщений: 10,695
11.02.2012, 18:07 #11
Цитата Сообщение от Dani Посмотреть сообщение
Здесь binary search, точно. Т.к. иначе билеберда получается.
Если телепатические способности Dani не подвели и больше никаких уточнений не придвидится, то и так сойдёт:
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
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
/* понадобится для сортировки */
int asccmp(const void * a, const void * b){
    return *(int*)a - *(int*)b;
}
 
/* заполнение массива случайными числами */
void rndfill(int * arr, size_t size){
    while ( size-- )
        *arr++ = rand() % 10;
}
 
/* вывод на экран */
void dump(const int * arr, size_t size){
    while ( size-- )
        printf("%d%c", *arr++, ( size ) ? ' ' : '\n');
}
 
/* возвращает указатель на последнее найденное значение или NULL, counter - счётчик */
int * binsearch(const int * arr, size_t size, const int val, int * counter){
    const int * middle = arr + size / 2; /* указатель на середину массива */
    *counter += 1; /* отметились :) */
 
    if ( middle > arr ){ /* если элементов больше одного */
        if ( *(arr + size - 1) == val ) /* последний элемент */
            return (int*)(arr + size - 1);
        if ( *middle == val ) /* средний */
            return (int*)middle;
        if ( *middle > val ) /* искомый элемент между первым и средним */
            return binsearch(arr, middle - arr, val, counter);
        return binsearch(middle, size - (middle - arr), val, counter); /* в другом случае */
    }
    if ( *arr == val ) /* если нашли в начале массива */
        return (int*)arr;
        
    /* не нашли */
    return NULL;
}
 
int main(void){
    int * arr, val, * found;
    size_t size, counter;
    
    srand(time(NULL)); /* это чтобы при каждом запуске программы циферки разные были */
    
    while ( printf("Number of elements: ") && scanf("%u", &size) == 1 && size && printf("Value to search: ") && scanf("%d", &val) == 1 ){
        /* создаём и заполняем массив */
        if ( ! ( arr = (int*)malloc(sizeof(int) * size) ) ){
            perror("malloc");
            exit(1);
        }
        
        rndfill(arr, size);
        qsort(arr, size, sizeof(int), asccmp);
        printf("Array:\n");
        dump(arr, size);
        
        /* ищем элемент */
        counter = 0;
        if ( found = binsearch(arr, size, val, &counter) )
            printf("Last value %d found at pos %u with %u attempt(s)\n", val, found - arr + 1, counter);
        else
            printf("Can't find value %d after %u attempt(s)\n", val, counter);
        
        /* удаляем массив */
        free(arr);
    }
    
    exit(0);
}
0
Тан10шка
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 7
11.02.2012, 19:30  [ТС] #12
Большое спасибо всем!!!!
ОООООчеьнь помогли!!!!!!!!!
0
vladislavchick
35 / 35 / 1
Регистрация: 22.05.2010
Сообщений: 107
12.02.2012, 12:12 #13
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение

Не по теме:

- есть массив, есть число в двоичном представлении binMask, нужно каждый элемент массива перевести в двоичное и сравнить с binMask, вот и всё...

Это самый обыкновенный ПОСЛЕДОВАТЕЛЬНЫЙ поиск
0
-=ЮрА=-
12.02.2012, 12:23
  #14

Не по теме:

vladislavchick, не занимайся офтопом...

0
easybudda
Модератор
Эксперт CЭксперт С++
9622 / 5570 / 946
Регистрация: 25.07.2009
Сообщений: 10,695
12.02.2012, 14:47 #15
-=ЮрА=-, ну по сути-то он прав, это действительно последовательный поиск, да ещё и с непонятным геморроем из перевода чисел в двоичный вид. Для полноты ощущений их бы ещё в лексикографическом порядке сравнивать...

Нашёл у себя в архивах маргинальную функцию
C
1
2
3
4
int * binsearch(int val, int * arr, int cnt){
    int * middle = arr + cnt / 2;
    return ( middle > arr ) ? ( *middle > val ) ? binsearch(val, arr, middle - arr) : binsearch(val, middle, cnt + arr - middle) : ( *middle == val ) ? middle : NULL;
}
всё-таки надо проще быть...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2012, 14:47
Привет! Вот еще темы с ответами:

Перевод из десятичной в двоичную систему - C++
нужно перевести число из десятичной в двоичную систему! На форуме искал но не подходит! Вот мое творение #include &lt;iostream&gt; using...

Перевод с десятичной в двоичную систему - C++
Здравствуйте,нужно написать програму (только чистый Borland C), которая переводит числа из десятичных в двоичные..!

Не получается перевести в двоичную систему - C++
Требуется перевести в двоичную систему счисления, но потом некоторые переменные меняют своё значение. У меня CodeBlocks. #include...

Перевод числа в двоичную систему - C++
Каким циклом можно перевести число из десятичной в двоичную и присвоить переменной это число? Например из чисел 1, 2, 3 получить 01,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
12.02.2012, 14:47
Ответ Создать тему
Опции темы

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