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

Отгадать загаданное число за наименьшее количество вопросов

16.02.2015, 16:29. Показов 13520. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
Как реализовать на С++ ?
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
16.02.2015, 16:29
Ответы с готовыми решениями:

Отгадать число загаданное программой
Доброго времени суток. Необходимо отгадать случайное число загаданное программой, при этом если пользователь ошибся, программа должна...

Играющему нужно угадать загаданное число за минимальное количество вопросов
Пожалуйста помогите c алгоритмом к следующей задаче: Дано множество чисел от 1 до N. Играющему нужно угадать загаданное число за...

Отгадать число,загаданное компьютером максимум за 3 попытки
domains int = integer predicates ask(int) check(int,int) popitka(int,int) clauses ask(K) if...

10
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
16.02.2015, 16:31
kruglov1, насколько я помню, бинарный поиск. Выбираете диапазон от 1 до N, находите середину (N/2) спрашиваете "число больше загаданного?", в зависимости от ответа отсекаете часть диапазона, повторяете вопрос
0
Эксперт PHP
4925 / 3920 / 1620
Регистрация: 24.04.2014
Сообщений: 11,441
16.02.2015, 16:32
Цитата Сообщение от kruglov1 Посмотреть сообщение
За какое наименьшее количество вопросов
За 1:
Петя: - Ты загадал число 3?
Вася: - Да.
Цитата Сообщение от kruglov1 Посмотреть сообщение
Как реализовать на С++ ?
C++
1
2
3
4
#include <iostream>
int main() {
    std::cout << 1;
}
0
1 / 1 / 1
Регистрация: 04.10.2014
Сообщений: 38
16.02.2015, 16:33  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
насколько я помню, бинарный поиск. Выбираете диапазон от 1 до N, находите середину (N/2) спрашиваете "число больше загаданного?", в зависимости от ответа отсекаете часть диапазона, повторяете вопрос
У меня вот есть код
C++
1
2
3
4
5
6
int x;
    int result;
    cin >> x;
    result = log(x) / log(2);
    cout <<  result+1;
        return 0;
но тестирующая система не принимает, там по тестам лишь 14 из 19 проходит
0
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
16.02.2015, 16:36
kruglov1, а что, так программа правильно находит ваше число? :о
0
1 / 1 / 1
Регистрация: 04.10.2014
Сообщений: 38
16.02.2015, 16:38  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
а что, так программа правильно находит ваше число? :о
ну 14 раз нашла

Добавлено через 52 секунды
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
Выбираете диапазон от 1 до N, находите середину (N/2) спрашиваете "число больше загаданного?"
Вы имели ввиду что-то вроде этого ?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;
    cin >> n;
    int A[n];
    for (int r = 0; r < n; r++)
    {
        cin >> A[r];
    }
    int i = 0,j = n-1, k;
    while( i <= j )
    {
        k = ( i + j ) /2;
        if(n == A[k])
            return k;
        else
            if(n < A[k])
                j = k - 1;
        else
            if( n > A[k] )
            i = k + 1;
    }
0
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
16.02.2015, 16:40
kruglov1, ну да, что-то типа того. Только массив не нужен, с k сравнивайте, вы же рассматриваете числа от 1 до N
1
 Аватар для irthgr
24 / 21 / 2
Регистрация: 15.05.2021
Сообщений: 57
29.07.2021, 13:08
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
 
int main()
 
{
int n, k, m;
    cin >> n;
    k = 0;
    m = 1;
    while (m < n){
        m = m *2;
        k += 1;
    }
    cout << k;
    return 0;
 
}
не надо благодарности
код рабочий, прошел сириус!

Можно попросить код задачи Upper Bound?
0
2 / 2 / 0
Регистрация: 03.05.2020
Сообщений: 202
29.07.2021, 14:01
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
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    unsigned int n;
    cin >> n;
    int* A = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    sort(A, A + n, greater<int>());
    int m;
    cin >> m;
    int x = m;
    int* B = new int[m];
    for (int i = 0; i < m; i++)
    {
        cin >> B[i];
    }
    int f = 250000;
    int* V = new int[f];
    for (int i = 0; i < x; i++)
    {
        int L = -1;
        int R = n;
        while (R - L > 1)
        {
            m = (R + L) / 2;
            if (A[m] > B[i])
            {
                L = m;
            }
            else
            {
                R = m;
            }
        }
        V[i] = n-R;
    }
    for (int i = 0; i < x; i++)
    {
        cout << V[i] << " ";
    }
}
Добавлено через 15 секунд
upper bound
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
29.07.2021, 17:39
Цитата Сообщение от kruglov1 Посмотреть сообщение
За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
На этот вопрос ответ такой: Петя может угадать Васино число за ceil(log2(N)) вопросов в худшем случае, используя метод бинарного поиска числа Х на интервале от 1 до N.
Вопросы будут вида "загаданное число меньше Х?".

Пример:
N = 4, искомое число X = 4;
Загаданное число меньше 3? - Нет
Загаданное число меньше 4? - Нет
Ответ: Загаданное число - 4.
0
3 / 3 / 0
Регистрация: 07.04.2023
Сообщений: 30
23.04.2023, 16:38
Цитата Сообщение от irthgr Посмотреть сообщение
Можно попросить код задачи Upper Bound?
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
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{   int n;
    std::cin >> n;
    std::vector<int> data(n);
    for(auto& e : data) std::cin >> e;
 
    std::sort(data.begin(), data.end());
 
    std::cin >> n;
 
    for (int i = 0, nn = n-1; i < n; ++i)
    {   int value;
        std::cin >> value;
 
        auto first(data.begin());
        {   auto it   (data.begin());
            auto last (data.end  ());
 
            typename std::iterator_traits<std::vector<int>::iterator>::
                                                    difference_type count, step;
            count = std::distance(first, last);
 
            while (count > 0)
            {   it = first;
                step = count / 2;
                std::advance(it, step);
                if (!(value < *it))
                {   first = ++it;
                    count -= step + 1;
                }
                else
                    count = step;
            }
        }
 
        std::cout << first - data.begin();
        if(i != nn) std::cout << ' ';
    }
}


Держи, прошел)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
23.04.2023, 16:38
Помогаю со студенческими работами здесь

Какое минимальное количество вопросов, требующих ответа "да" или "нет", необходимо, чтобы отгадать число
36. Человек загадывает число в диапазоне от 0 до 15. Известно, что загадывающий точно через раз дает то верный, то неверный ответ. Какое...

Определить, за какое наименьшее количество вопросов можно угадать задуманное число
Помогите пожалуйста. Некто загадал число от 1 до N. За какое наименьшее количество вопросов (на которые он отвечает &quot;да&quot; или...

За какое наименьшее количество ходов Петрик сможет отгадать заданное слово?
Петрик и Маричка увлеклись игрой поле-чудес: Маричка записывает слово, состоящее из Больших английских букв, а Петрик старается распознать...

Какое наименьшее число вопросов нужно задать чтобы гарантировано угадать число?
не мог найти куда написать свой пост ,решил сюда , задача из контрольной по информатике по ЕГЭ. Загадано число от 1 до 100. загадавший на...

За какое наименьшее число вопросов удастся целиком определить порядок?
Илюша решил поехать путешествовать. Он в каком-то порядке посетил 8 городов Золотого кольца России: Сергиев Посад, Переславль-Залесский,...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru