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

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

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

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

намекните примерно как это реализовать
чуть ли не забыл... реализовать надо на борланде 3.1
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.04.2011, 15:08
Ответы с готовыми решениями:

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

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

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

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

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

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

Воооть.
это и есть бинарный поиск?
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
02.04.2011, 15:39 6
Да. Это, как-бы, он.
Суть бинарного поиска в разделении области поиска на две части на каждом шаге поиска. За известное время область поиска будет сужена до единицы.
1
Каратель
Эксперт С++
6609 / 4028 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
02.04.2011, 15:39 7
lips!!, вас на википедии забанили?
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 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
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:48  [ТС] 9
Цитата Сообщение от Maxwe11 Посмотреть сообщение
lips!!, вас на википедии забанили?
там нихрена не понятно, да и учитель наш говарит что там много ерунды попанописано


Deviaphan спасибо!!
0
2 / 2 / 2
Регистрация: 02.04.2011
Сообщений: 86
02.04.2011, 15:50  [ТС] 10
спасибо за код
0
Заблокирован
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
2 / 2 / 2
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.04.2011, 19:44
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru