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

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

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

перевод в двоичную систему через классы C++
Перевод числа в двоичную систему C++
Перевод в двоичную систему C++
C++ Не получается перевести в двоичную систему
C++ Перевод в двоичную систему счисления
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор 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;
}
Алгоритм нахождения двоичного числа на скрине
Миниатюры
Элемент в массиве через двоичную систему поиска   Элемент в массиве через двоичную систему поиска  
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.02.2012, 17:28     Элемент в массиве через двоичную систему поиска #3
Хм, желательно пояснение от ТС. Может быть имелся в виду бинарный поиск в отсортированном массиве (хотя про отсортированность не было ни слова...)?
-=ЮрА=-
10.02.2012, 17:36
  #4

Не по теме:

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

I.M.
10.02.2012, 17:41
  #5

Не по теме:

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

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

Не по теме:

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

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

Проблема в том,что точного задания я так и не получила.
Но я думаю,что бинарный поиск ето именно то
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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);
}
Тан10шка
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 7
11.02.2012, 19:30  [ТС]     Элемент в массиве через двоичную систему поиска #12
Большое спасибо всем!!!!
ОООООчеьнь помогли!!!!!!!!!
vladislavchick
35 / 35 / 1
Регистрация: 22.05.2010
Сообщений: 107
12.02.2012, 12:12     Элемент в массиве через двоичную систему поиска #13
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение

Не по теме:

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

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

Не по теме:

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

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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;
}
всё-таки надо проще быть...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2012, 15:09     Элемент в массиве через двоичную систему поиска
Еще ссылки по теме:

Юникод в двоичную систему C++
Перевод из десятичной в двоичную систему C++
C++ Задача на двоичную систему

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

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
12.02.2012, 15:09     Элемент в массиве через двоичную систему поиска
  #16

Не по теме:

Ну значит я неверно воспринял задание, ТС удовлетворилась, а больше ничего и не надо

Yandex
Объявления
12.02.2012, 15:09     Элемент в массиве через двоичную систему поиска
Ответ Создать тему
Опции темы

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