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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:08     Деление пополам(бинарный поиск) #1
Всем доброго времени суток!
уже часа 2 ломаю голову над проблемой:
комьютер должен отгадать число за 10 или менее вопросов в диапозоне от 1 до 1000
применить идею методом деления пополам(бинарного поиска) хотя что это такое бинарный поиск я понятия неимею...

намекните примерно как это реализовать
чуть ли не забыл... реализовать надо на борланде 3.1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.04.2011, 15:08     Деление пополам(бинарный поиск)
Посмотрите здесь:

C++ Бинарный поиск
C++ Поиск методом деления пополам.
C++ Бинарный поиск
C++ Бинарный поиск деления пополам
C++ Поиск максимального елемента массива , используя метод деления пополам
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
apple29
 Аватар для apple29
90 / 23 / 1
Регистрация: 18.02.2011
Сообщений: 59
02.04.2011, 15:11     Деление пополам(бинарный поиск) #2
может найдеш здесь что-то полезное
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:24  [ТС]     Деление пополам(бинарный поиск) #3
Цитата Сообщение от apple29 Посмотреть сообщение
может найдеш здесь что-то полезное
эм.. ну мне надо к понедельнику.. а ту кучу книг.. до понедельника я врядле прочитаю
ненадо кидать сылки на хелп ><
я же не прошу готовый листинг, а просто принцип, как это реализовать засчёт чего??
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:29     Деление пополам(бинарный поиск) #4
Загадал число 167.

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

Воооть.
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:34  [ТС]     Деление пополам(бинарный поиск) #5
Цитата Сообщение от Deviaphan Посмотреть сообщение
Загадал число 167.

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

Воооть.
это и есть бинарный поиск?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:39     Деление пополам(бинарный поиск) #6
Да. Это, как-бы, он.
Суть бинарного поиска в разделении области поиска на две части на каждом шаге поиска. За известное время область поиска будет сужена до единицы.
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
02.04.2011, 15:39     Деление пополам(бинарный поиск) #7
lips!!, вас на википедии забанили?
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
02.04.2011, 15:48     Деление пополам(бинарный поиск) #8
Примерный код:
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);
}
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:48  [ТС]     Деление пополам(бинарный поиск) #9
Цитата Сообщение от Maxwe11 Посмотреть сообщение
lips!!, вас на википедии забанили?
там нихрена не понятно, да и учитель наш говарит что там много ерунды попанописано


Deviaphan спасибо!!
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:50  [ТС]     Деление пополам(бинарный поиск) #10
спасибо за код
IrineK
Заблокирован
02.04.2011, 17:20     Деление пополам(бинарный поиск) #11
Предлагается на занятиях начального уровня (проверено - с 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.04.2011, 19:44     Деление пополам(бинарный поиск)
Еще ссылки по теме:

Поиск максимального елемента ,методом деления пополам C++
C++ Бинарный поиск
Поиск числа в двумерном массиве (бинарный поиск) C++

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

Или воспользуйтесь поиском по форуму:
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 19:44  [ТС]     Деление пополам(бинарный поиск) #12
вот загадал я к примеру число 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);
}
Yandex
Объявления
02.04.2011, 19:44     Деление пополам(бинарный поиск)
Ответ Создать тему
Опции темы

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