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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
#1

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

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

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

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

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

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

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

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

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

Бинарный поиск - C++
Добрый день , возникла проблема с бинарным поиском . Я его просто нашел в интернете и вставил в программу не много отредактировав . Вобщем...

Бинарный поиск - C++
Найти индекс расположения числа 15 в массиве на 20 элементов и сумму элементов предшествующих ему. Методом бинарного поиска. Вот код в...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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++
1286 / 1220 / 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++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:39     Деление пополам(бинарный поиск) #6
Да. Это, как-бы, он.
Суть бинарного поиска в разделении области поиска на две части на каждом шаге поиска. За известное время область поиска будет сужена до единицы.
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
02.04.2011, 15:39     Деление пополам(бинарный поиск) #7
lips!!, вас на википедии забанили?
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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++
Вот вроде бы всё работает только как-то не очень правильно не находит 2 позицию в массиве и пред последнею может ещё что-то не находит , я...

Бинарный поиск - C++
Вообщем, написал бинарный поиск, а он не работает для ключа со значением 9, может кто объяснить, как решить эту проблему? А ещё я не совсем...

Бинарный поиск - C++
Написал программу бинарного поиска элемента v. Не могу понять в чем ошибка, не считает количество элементов массива удовлетворяющий...

Бинарный поиск - 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     Деление пополам(бинарный поиск)
Ответ Создать тему
Опции темы

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