Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.91/43: Рейтинг темы: голосов - 43, средняя оценка - 4.91
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86

Деление пополам(бинарный поиск)

02.04.2011, 15:08. Показов 9174. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем доброго времени суток!
уже часа 2 ломаю голову над проблемой:
комьютер должен отгадать число за 10 или менее вопросов в диапозоне от 1 до 1000
применить идею методом деления пополам(бинарного поиска) хотя что это такое бинарный поиск я понятия неимею...

намекните примерно как это реализовать
чуть ли не забыл... реализовать надо на борланде 3.1
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
02.04.2011, 15:08
Ответы с готовыми решениями:

Бинарный поиск деления пополам
Здравствуйте, не могу понять почему так: ввожу число 3 и ничего не выводится(со всеми остальными числами всё получалось) #include...

Рекурсивное деление пополам с функцией для каждого отрезка
Нужно произвести вычисление на отрезке до определенной точности. При невыполнении условия отрезок делится пополам и действия повторяются....

Поиск числа в двумерном массиве (бинарный поиск)
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и бинарным(двоичным). Первый работает на ура. Второй...

11
 Аватар для apple29
91 / 24 / 2
Регистрация: 18.02.2011
Сообщений: 59
02.04.2011, 15:11
может найдеш здесь что-то полезное
0
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:24  [ТС]
Цитата Сообщение от apple29 Посмотреть сообщение
может найдеш здесь что-то полезное
эм.. ну мне надо к понедельнику.. а ту кучу книг.. до понедельника я врядле прочитаю
ненадо кидать сылки на хелп ><
я же не прошу готовый листинг, а просто принцип, как это реализовать засчёт чего??
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:29
Загадал число 167.

Меньше 512? Да
Меньше 256? Да
Меньше 128? Нет
Меньше 192? Да
Меньше 160? Нет
Меньше 176? Да
Меньше 168? Да
Меньше 164? Нет
Меньше 166? Нет
Меньше 167? Нет
Это 167? Угу.

Воооть.
0
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:34  [ТС]
Цитата Сообщение от Deviaphan Посмотреть сообщение
Загадал число 167.

Меньше 512? Да
Меньше 256? Да
Меньше 128? Нет
Меньше 192? Да
Меньше 160? Нет
Меньше 176? Да
Меньше 168? Да
Меньше 164? Нет
Меньше 166? Нет
Меньше 167? Нет
Это 167? Угу.

Воооть.
это и есть бинарный поиск?
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:39
Да. Это, как-бы, он.
Суть бинарного поиска в разделении области поиска на две части на каждом шаге поиска. За известное время область поиска будет сужена до единицы.
1
Каратель
Эксперт С++
6610 / 4029 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
02.04.2011, 15:39
lips!!, вас на википедии забанили?
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
02.04.2011, 15:48
Примерный код:
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
#include <stdio.h>
 
int main()
{
    char answer = 0;
    int x = 0, low = 1, hi = 1000, current = 500;
 
    printf ("input `x`: ");
    scanf ("%d", &x);
 
    while (x != current) {
        printf ("is it less than %d? ", current);
        
        getchar();
        answer = getchar();
        if (answer == 'y') {
            hi = current;
            current -= (current - low) / 2;
        }
        else {
            low = current;
            current += (hi - current) / 2;
        }
    }
 
    printf ("it is %d\n", current);
}
2
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:48  [ТС]
Цитата Сообщение от Maxwe11 Посмотреть сообщение
lips!!, вас на википедии забанили?
там нихрена не понятно, да и учитель наш говарит что там много ерунды попанописано


Deviaphan спасибо!!
0
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:50  [ТС]
спасибо за код
0
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
02.04.2011, 17:20
Предлагается на занятиях начального уровня (проверено - с 13 лет массово (70%) понимают).

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
#include <iostream>
#define U0 1001
#define L0 0
using namespace std;
 
int main() 
{   setlocale(LC_ALL,"");    
    int lower,upper,num, guess, found, step;
 
    while(1)
    {   system("cls");
        lower = L0,upper = U0,found = 0, step = 0;
        cout<<"Демонстрация возможностей бинарного поиска\n";
        cout<<"Введите число в диапазоне от "<<L0+1<<" до "<<U0-1<<"\n";
 
        cout<<"N = ";
        cin>>num;
 
        while((upper-lower)!=1)
        {   guess = (upper+lower)/2;
            cout<<"Шаг "<<++step<<" Это "<<guess<<" ?\n";
            if(guess == num) 
            {   found=1;
                break;
            }
            else if(num < guess)
            {   cout<<"\tНет, оно меньше...\n";
                upper = guess;
            }
            else 
            {   cout<<"\tНет, оно больше...\n";
                lower = guess;
            }
        }
 
        if(found) cout<<"\n\nДа, "<<guess<<" найдено! "<<(char)1<<"\n";
        else cout<<"Ваше число не входит в диапазон поиска\n";
 
        cin.sync(); cin.get();
    }
        return 0;
}
0
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 19:44  [ТС]
вот загадал я к примеру число 743
>500? y
>750? n
и тут он у меня спрашивает:
>375?
хотя 500 должен был записать как min

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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int maxx(int, int, int);
int minn(int, int, int);
void main()
{
 int a=0,c=500,max=1000,min=1;
 clrscr();
 randomize();
 printf("3arogauTe 4ucJlo, oTBe4auTe y/n\n");
 getch();
 for(int i=0;i<10;i++)
 {
  printf("\n>%i",c);
  a=getch();
   if(a==121)
   c=minn(min,max,c);
  else
   c=maxx(min,max,c);
 }
}
 
 
 
int minn (int min,int max,int c)   //y
{
 min=c;
 if((min/2)+min<max)
 {
  c=min/2+min;
 }
 else
 {
  c=min+50;              //тут непридумал ещё чё писать
 }
 return(min,c);
}
int maxx (int min,int max,int c)      //n
{
 max=c;
 if((max-min)/2+min>min)
 {
  c=(max-min)/2+min;
 }
 else
 {
  c=max+50;                    //тут непридумал ещё чё писать
 }
 return(max,c);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
02.04.2011, 19:44
Помогаю со студенческими работами здесь

Поиск методом деления пополам.
Имеется железнодорожное расписание, содержащее номер рейса поезда, времена отправления и прибытия и станцию прибытия. Организовать поиск...

Поиск экстремума методом деления отрезка пополам
Выдаёт ошибку в 15 строчке. Не могу понять в чём дело, помогите) #include&lt;iostream&gt; #include&lt;math.h&gt; #include&lt;cmath&gt; ...

Поиск максимального елемента ,методом деления пополам
Программа ищет максимальный элемент в массиве a1, ..., an, используя метод деления пополам max (a1, ..., an) = max (max (a1, ..., an/2),...

Поиск максимального елемента массива , используя метод деления пополам
Найти максимальный элемент в массиве a1, ..., an, используя метод деления пополам max (a1, ..., an) = max (max (a1, ..., an/2), max...

Бинарный поиск
Никак не могу понять почему у меня не проходит тесты данный код. Задача выглядит так: Входные данные В первой строке входных...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Жизнь в неопределённости
kumehtar 23.03.2026
Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения.
anaschu 23.03.2026
geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
1С: Контроль уникальности заводского номера
Maks 23.03.2026
Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения
anaschu 22.03.2026
e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
1С: Программный отбор элементов справочника по группе
Maks 22.03.2026
Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .
Как я обхитрил таблицу Word
Alexander-7 21.03.2026
Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
Krabik - рыболовный бот для WoW 3.3.5a
AmbA 21.03.2026
без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .
1С: Программный отбор элементов справочника по значению перечисления
Maks 21.03.2026
Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru