Сложность бинарного поиска

@Melvil · Регистрация: 20.05.2015

Студворк — интернет-сервис помощи студентам

Добрый вечер, решал данную задачу:

Кликните здесь для просмотра всего текста

Девочка загадала число от 1 до N. За какое наименьшее количество вопросов вида «Загаданное тобой число больше числа X?», подразумевающих ответы «Да» или «Нет», мальчик гарантированно сможет отгадать число девочки?

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 10^18).

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.

Если какая-либо формула для её решения? И где же ошибка в моём решении?

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
#include <iostream>
using namespace std;
 
int main() 
{
    int N, counter = 0;
    cin >> N;
    N = N / 2;
    counter += 1;
    if (N % 2 == 0)
    {
        N = N / 2;
        counter += 1;
    }
    else
    {
        while (N!=1)
        {
            N -= 1;
            counter += 1;
        }
    }
    cout << counter;
}

@Renji · 18.08.2015, 21:25

Двоичный логарифм от N, с округлением в большую сторону.
Вообще-то, задача из серии "открывали ли вы учебник? Помните вы хотя-бы какого он цвета?".

@Melvil · 18.08.2015, 23:47 **[ТС]**

Сообщение от Renji

Вообще-то, задача из серии "открывали ли вы учебник? Помните вы хотя-бы какого он цвета?".

Увы, нет. Можете что-то посоветовать?

@Renji · 18.08.2015, 23:48

Дональд Кнут, Искусство Программирования.

@Melvil · 18.08.2015, 23:51 **[ТС]**

Сообщение от Renji

Дональд Кнут, Искусство Программирования.

Спасибо, обязательно прочту.

@dvoechnik · 20.05.2016, 09:18

C++
1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    cout<<ceil(log2(n));
}

Работает только до 8 теста.

@msz301005 · 19.04.2018, 18:05

dvoechnik, там ограничения 5*10^18. Тут даже в __int64 не влезет. Вот в double все прекрасно лезет. Поставь double.
P.S. у меня не проходит с double на 14 тесте

C++
1
2
3
4
5
6
7
8
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    double n;
    cin >> n;
    cout << ceil(log2(n));
}

Потому что надо писать самому двоичный логарифм, а то там происходит ошибка округления. Поэтому напиши свой двоичный логарифм и ты сдашь эту задачу.

@Kuzia domovenok · 19.04.2018, 18:07

msz301005, где "там"? Вы сами с собой разговариваете?

@P x sin_A_ · 15.03.2019, 11:15

почему это падает (тест 14)? из-за потери точности? как исправить?

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int main()
{
long long n;
cin >> n;
cout << ceil(log(n)/log(2));
return 0;
}

@Kuzia domovenok · 16.03.2019, 00:02

P x sin_A_, не легче по маске определить двоичный порядок числа?

@StillCF · 21.07.2020, 15:19

C++
1
2
3
4
5
6
7
8
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    double n;
    cin >> n;
    cout << ceil(log2(n/log2(2)));
}

@VyacheslavSqrt · 26.08.2021, 19:10

Просто степень двойки....
Проходит все 60 тестов.

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
 
int main() {
    ll n, t = 1, ans = 0; cin >> n;
    while (t < n) {
        ans++;
        t *= 2;
    }
    cout << ans;
}

@Kuzia domovenok · 27.08.2021, 17:18

VyacheslavSqrt, Каких "тестов"? О чём вы? ТС эту задачу несколько лет назад придумал.

ФедосеевПавел · 27.08.2021, 18:32

Вряд ли придумал...
Существует задача 1130 на acmp, и, наверное, её дубль на информатиксе.

Добавлено через 17 минут
Судя по расположению задачи на сайте, она входит в "домашние задания" на курсе изучения языка C++.

@Kuzia domovenok · 27.08.2021, 20:40

ФедосеевПавел, ааа, понял, но разве эти сайты проводят какую-то контрольную работу в официальных учебных заведениях? Я думал у каждого универа своя такая система.

ФедосеевПавел · 27.08.2021, 21:38

Не знаю. Не у кого спросить.
Был "наплыв" сириусников - те точно работают на таком сайте. Не знаю только, на каком этапе - отбор или обучение в Сочи. Один из сириусят упоминал о дополнительной автоматической проверке на плагиат. Как преподаватели узнают о выполнении заданий - для меня открытый вопрос.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	18.08.2015, 21:25
	Двоичный логарифм от N, с округлением в большую сторону. Вообще-то, задача из серии "открывали ли вы учебник? Помните вы хотя-бы какого он цвета?". 1

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	18.08.2015, 23:48
	Дональд Кнут, Искусство Программирования. 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	19.04.2018, 18:07
	msz301005, где "там"? Вы сами с собой разговариваете? 0

@P x sin_A_ 0 / 0 / 0 Регистрация: 15.03.2019 Сообщений: 1
	15.03.2019, 11:15
	почему это падает (тест 14)? из-за потери точности? как исправить? #include <iostream> #include <algorithm> #include <math.h> using namespace std; int main() { long long n; cin >> n; cout << ceil(log(n)/log(2)); return 0; } 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	16.03.2019, 00:02
	P x sin_A_, не легче по маске определить двоичный порядок числа? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	27.08.2021, 17:18
	VyacheslavSqrt, Каких "тестов"? О чём вы? ТС эту задачу несколько лет назад придумал. 0

ФедосеевПавел Модератор 8659 / 4494 / 1669 Регистрация: 01.02.2015 Сообщений: 13,905 Записей в блоге: 12
	27.08.2021, 18:32
	Вряд ли придумал... Существует задача 1130 на acmp, и, наверное, её дубль на информатиксе. Добавлено через 17 минут Судя по расположению задачи на сайте, она входит в "домашние задания" на курсе изучения языка C++. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	27.08.2021, 20:40
	ФедосеевПавел, ааа, понял, но разве эти сайты проводят какую-то контрольную работу в официальных учебных заведениях? Я думал у каждого универа своя такая система. 0

ФедосеевПавел Модератор 8659 / 4494 / 1669 Регистрация: 01.02.2015 Сообщений: 13,905 Записей в блоге: 12
	27.08.2021, 21:38
	Не знаю. Не у кого спросить. Был "наплыв" сириусников - те точно работают на таком сайте. Не знаю только, на каком этапе - отбор или обучение в Сочи. Один из сириусят упоминал о дополнительной автоматической проверке на плагиат. Как преподаватели узнают о выполнении заданий - для меня открытый вопрос. 0