Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.88
qwerty112358
1 / 1 / 0
Регистрация: 03.08.2011
Сообщений: 3
#1

Двоичный поиск (Керниган-Ритчи, упр. 3.1) - C (СИ)

03.08.2011, 17:42. Просмотров 2133. Ответов 12
Метки нет (Все метки)

Добрый день. Что-то я подвисла немного...

Задание:

В нашем двоичном поиске каждый цикл содержит две проверки, тогда как достаточно было бы одной (зато взамен их потребовалось бы больше снаружи цикла). Напишите версию функции с одной проверкой внутри цикла.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
 
    low=0;
    high=n-1;
        
    while (low<=high)
    {
        mid=(low+high)/2;
        if (x<v[mid])
            high=mid-1;
        else if (x>v[mid])
            low=mid+1;
        else return mid;
        
    }
    return -1;
}
Поиском по форуму уже нашла, что такую задачу решали, но в предложенном решении проверка выносится за тело цикла только формально.
Есть ли какие-то другие варианты решения этой задачи?
Я попробовала покрутить, повертеть, но что-то ничего на ум не идет.
1
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2011, 17:42
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Двоичный поиск (Керниган-Ритчи, упр. 3.1) (C (СИ)):

Ритчи и Керниган
В этом учебники в некоторых примерах прототип функции объявляется внутри другой...

Указатели, Керниган и Ритчи 5.4
Здравствуйте, нужна помощь начинающему. Читаю Керниган и Ритчи и не могу понять...

Керниган/Ритчи упражнение 1.22
&quot;Упражнение 1.22. Напишите программу, печатающую символы входного потока так,...

Компилятор С(Керниган ,Ритчи)
Здравствуйте! Открыл книгу Брайана Кернигана и Денниса Ритчи. Первое задание ...

Керниган Ритчи Упражнение 2.2
Добрый день. Помогите начинающему разобраться пожалуйста. Само...

Керниган/Ритчи упражнение 1.20
&quot;Упражнение 1.20. Напишите программу detab, заменяющую символы табуляции во...

12
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,231
03.08.2011, 20:01 #2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
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;
}
 
#define SIZE 10
 
int main(void){
    int arr[SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, * p, srch;
    
    while ( printf("Value 2 search: ") && scanf("%d", &srch) == 1 ){
        if ( p = binsearch(srch, arr, SIZE) )
            printf("Element with index %d\n", p - arr);
        else
            printf("Not found!\n");
    }
    
    return 0;
}
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
03.08.2011, 20:37 #3
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BinarySearch(const int *a, const int n, const int x)
{
    int l, r, mid; 
    l = 0;
    r = n - 1;
    do {
         mid = (l + r) >> 1; 
         if (a[mid] < x)
            l = mid + 1;
         else  r = mid - 1;
    }
    while (l < r && a[mid] != x);
    return (a[l] == x || a[mid] == x);
}
Добавлено через 19 минут
Данная функция логическая, возвращает истину либо ложь

Порешай задачки отсюда http://www.twirpx.com/file/540580/
0
Сыроежка
Заблокирован
03.08.2011, 21:35 #4
Цитата Сообщение от qwerty112358 Посмотреть сообщение
Добрый день. Что-то я подвисла немного...

Задание:

В нашем двоичном поиске каждый цикл содержит две проверки, тогда как достаточно было бы одной (зато взамен их потребовалось бы больше снаружи цикла). Напишите версию функции с одной проверкой внутри цикла.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
 
    low=0;
    high=n-1;
        
    while (low<=high)
    {
        mid=(low+high)/2;
        if (x<v[mid])
            high=mid-1;
        else if (x>v[mid])
            low=mid+1;
        else return mid;
        
    }
    return -1;
}
Поиском по форуму уже нашла, что такую задачу решали, но в предложенном решении проверка выносится за тело цикла только формально.
Есть ли какие-то другие варианты решения этой задачи?
Я попробовала покрутить, повертеть, но что-то ничего на ум не идет.
Вы просто можете взять разницу двух целых чисел x - v[mid], и ее результат будет либо положительным, либо отрицательным, либо равным нулю. Если равен нулю, то внутри цикла можно вообще ничего не делать. Нужно только условие цикла несколько иначе записать. Поэтому внутри цикла будет лишь проверка

C++
1
2
3
4
5
6
7
8
if ( x - v[mid] < 0 )
{
...
}
else
{
...
}
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
03.08.2011, 22:06 #5
Цитата Сообщение от Сыроежка Посмотреть сообщение
Вы просто можете взять разницу двух целых чисел x - v[mid], и ее результат будет либо положительным, либо отрицательным, либо равным нулю. Если равен нулю, то внутри цикла можно вообще ничего не делать. Нужно только условие цикла несколько иначе записать. Поэтому внутри цикла будет лишь проверка

C++
1
2
3
4
5
6
7
8
if ( x - v[mid] < 0 )
{
...
}
else
{
...
}
Так напишите алгоритм.

Примечание. условия if (a<b) и if (a-b<0) эквивалентны, так что из этого разве что-то выйдет
0
qwerty112358
1 / 1 / 0
Регистрация: 03.08.2011
Сообщений: 3
03.08.2011, 23:50  [ТС] #6
Olga_, смысл функции не должен меняться.
То, что предложили Вы, возвращает истину или ложь, исходная функция возвращает позицию искомого элемента в массиве либо -1, если искомый элемент не найден.
Я спрашивала вариант решения именно этой задачи.

easybudda, в том варианте, что у Вас, формально условие вынесено за тело цикла, а фактически нет.
Подобные решения понятны, меня интересует, можно ли вообще извернуться таким образом, чтобы фактически в теле цикла была одна проверка, не больше. Мне что-то ничего на ум не идет.
Может, конечно, авторы нечто подобное и имели в виду.
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,231
04.08.2011, 00:37 #7
Цитата Сообщение от qwerty112358 Посмотреть сообщение
можно ли вообще извернуться таким образом, чтобы фактически в теле цикла была одна проверка, не больше.
При сравнении двух чисел возможны три варианта: первое число больше, первое число меньше и числа равны. Попробуйте сами себе ответить...
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
04.08.2011, 00:44 #8
Да можно, можно
Раз:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
 
    low = 0;
    high = n - 1;
 
    while (low < high)
    {
        mid = (low + high + 1)/2;
        if (x < v[mid])
            high = mid - 1;
        else
            low = mid;
    }
    if (x == v[low])
        return low;
    return -1;
}
Два:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
 
    low = 0;
    high = n - 1;
 
    while (low < high)
    {
        mid = (low + high)/2;
        if (x <= v[mid])
            high = mid;
        else
            low = mid + 1;
    }
    if (x == v[low])
        return low;
    return -1;
}
2
qwerty112358
1 / 1 / 0
Регистрация: 03.08.2011
Сообщений: 3
04.08.2011, 00:58  [ТС] #9
Цитата Сообщение от easybudda Посмотреть сообщение
При сравнении двух чисел возможны три варианта: первое число больше, первое число меньше и числа равны.
Я бы не спрашивала, если бы в это не уперлась.

grizlik78, спасибо, я представляла нечто подобное, но видимо, где-то неплохо косячила в реализации.

Всем спасибо.
0
accept
4833 / 3254 / 454
Регистрация: 10.12.2008
Сообщений: 10,569
04.08.2011, 06:06 #10
Цитата Сообщение от easybudda
C
1
while ( printf("Value 2 search: ") && scanf("%d", &srch) == 1 ){
printf() может возвращать отрицательное число
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
04.08.2011, 07:15 #11
Цитата Сообщение от qwerty112358 Посмотреть сообщение
Olga_, смысл функции не должен меняться.
То, что предложили Вы, возвращает истину или ложь, исходная функция возвращает позицию искомого элемента в массиве либо -1, если искомый элемент не найден.
Я спрашивала вариант решения именно этой задачи.
Так из логической легко переделать, чтобы индекс возвращала, разве это принципиально вот код

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int BinarySearch(const int *a, const int n, const int x)
{
    int l, r, mid;         
    l = 0;
    r = n - 1;
    do {
         mid = (l + r) >> 1; 
         if (a[mid] < x)
            l = mid + 1;
         else  r = mid - 1;
    }
    while (l < r && a[mid] != x);
 
    if (a[l] == x)
       return l;
    else if (a[mid] == x)
       return mid;
    else
       return -1;
}
Добавлено через 18 минут
Разве что два условия остались... Да, grizlik78 молодец, хорошие алгоритмы
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
04.08.2011, 23:04 #12
qwerty112358, по поводу данной задачи. Как Вы думаете, эффективность поиска в алгоритмах grizlik78 в посте 10 выше или ниже чем в алгоритме из поста 13? То есть вопрос по теме сложности алгоритма.

Добавлено через 3 часа 12 минут
Пусть массив a имеет размерность n (четное число) и искомый элемент находится на n/2-1 месте. Тогда в алгоритмах из поста 10 будет произведено log_2_n итераций, а из поста 13 – только одна итерация.

Но это так, к слову, еще раз повторю, что у grizlik78 получилось решить задачу

Добавлено через 9 часов 32 минуты
Правилами форума запрещено выкладывать книги, поэтому сообщу для всех изучающих язык Си по книжке Кернигана и Ритчи "Язык программирования Си", что существует книжка Тондо "Язык Си. Книга ответов". В ней вы можете найти варианты реализаций алгоритмов задач из книги Кернигана и Ритчи.
1
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
04.08.2011, 23:27 #13
Да, для наихудшего случая количество просматриваемых элементов одинаково, но в среднем исходный вариант меньше элементов проверяет. Я когда отлаживал видел это, но внимания почему-то не обратил.
0
04.08.2011, 23:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2011, 23:27
Привет! Вот еще темы с решениями:

Керниган/ритчи задачи 1.18
Упражнение 1.18. Напишите программу, которая будет в каждой вводимой строке...

Керниган, Ритчи, указатели и упражнение 5.3
Добрый день! &quot;Напишите свою версию функции strcat, ... с применением...

Керниган и Ритчи подсчет строк
после запуска вместо результата просто переходит на следущую строчку ...

Керниган и Ритчи подсчет строк
после запуска вместо результата просто переходит на следущую строчку ...


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

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

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