Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Воооть.
0
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? Угу.

Воооть.
это и есть бинарный поиск?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:39 #6
Да. Это, как-бы, он.
Суть бинарного поиска в разделении области поиска на две части на каждом шаге поиска. За известное время область поиска будет сужена до единицы.
1
Jupiter
Каратель
Эксперт С++
6565 / 3986 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
02.04.2011, 15:39 #7
lips!!, вас на википедии забанили?
0
fasked
Эксперт С++
4957 / 2537 / 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);
}
2
lips!!
2 / 2 / 1
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:48  [ТС] #9
Цитата Сообщение от Maxwe11 Посмотреть сообщение
lips!!, вас на википедии забанили?
там нихрена не понятно, да и учитель наш говарит что там много ерунды попанописано


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

Бинарный поиск - C++
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента, текст читается из файла. Лабу сдавать в понедельник а я не знаю...

бинарный поиск - C++
Задали реализовать бинарный поиск в упорядоченном массиве.Уже пол дня творю,3 листа исписал и ничего не получается. Вот пример поиска...

Бинарный поиск - C++
Реализуйте алгоритм бинарного поиска. Входные данные В первой строке входных данных содержатся натуральные числа N и K . Во второй...

Бинарный поиск - C++
за какое время работает бинарный поиск?


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

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

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