0 / 0 / 0
Регистрация: 30.10.2020
Сообщений: 4
1

Найти в заданном интервале число двоичная запись которого содержит наибольшее количество единиц

15.10.2021, 17:08. Показов 3820. Ответов 2

Author24 — интернет-сервис помощи студентам
Алиса учится работать с двоичными числами. Она уже поняла, что число в двоичной записи получается в несколько раз длиннее, чем в десятичной. А еще она поняла, что нули писать дольше чем единицы. И теперь ее любимые числа — это те, двоичная запись которых содержит как можно больше единиц. Алисе дали задание — выбрать одно произвольное число из заданного закрытого интервала [a;b] и перевести его в двоичную запись. И теперь Алиса просит, чтобы вы написали программу, которая найдет в этом интервале число, двоичная запись которого содержит наибольшее количество единиц. Если таких чисел будет несколько, то Алиса будет рада любому из них.

Формат входных данных
На вход через пробел подаются два натуральных числа a и b. При этом 1≤a≤b≤10^18. Обратите внимание, что для хранения таких чисел в программе на С++ вам потребуется тип long long. В программе на PascalABC такой тип называется Int64.

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

Методика проверки и пояснение к тесту
Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. При этом в первых пяти тестах
1≤a≤b≤1000. Тесты из условия задачи при проверке не используется.

Пример ввода 1:
150 200

Пример вывода 1:
191

Пример ввода 2:
1 255

Пример выводаt 2:
255

Пример ввода 3:
127 200

Пример вывода 3:
127


Time Limit: 1 секунда
Memory Limit: 256 MB
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.10.2021, 17:08
Ответы с готовыми решениями:

Определить количество нечетных чисел, двоичная запись которых содержит 17 единиц
3. Определить кол-во нечетных чисел, меньших {2}^{21}, двоичная запись которых содержит 17 единиц....

В заданном интервале найти число имеющее наибольшее количество делителей
Мне извесно число n.Как мне найти число от 1 до n что имеет как можно больше делителей ?

Даны числа: 1, 3, 11 и 33. Указать среди них число, двоичная запись которого содержит ровно 3 единицы
Даны числа: 1, 3, 11 и 33. Указать среди них число, двоичная запись которого содержит ровно 3...

Даны числа: 1, 3, 11 и 33. Указать среди них число, двоичная запись которого содержит ровно 3 единицы
Даны числа: 1, 3, 11 и 33. Указать среди них число, двоичная запись которого содержит ровно 3...

2
Модератор
Эксперт С++
13532 / 10777 / 6423
Регистрация: 18.12.2011
Сообщений: 28,777
15.10.2021, 18:16 2
Полный перебор для такой задачи не прокатит.
Нужно найти число x, такое, что 2x<=b<2x+1
Тогда число y= x-1 будет содержать наибольшее к-во единиц.
Остается проверить, что это число больше a.
Если это не так, то придется перебрать все числа между a и b (их будет мало).
0
Вездепух
Эксперт CЭксперт С++
11719 / 6397 / 1725
Регистрация: 18.10.2014
Сообщений: 16,127
15.10.2021, 22:13 3
Цитата Сообщение от zss Посмотреть сообщение
Нужно найти число x, такое, что 2x<=b<2x+1
Тогда число y= x-1 будет содержать наибольшее к-во единиц.
y = 2x-1 ?

Цитата Сообщение от zss Посмотреть сообщение
Если это не так, то придется перебрать все числа между a и b (их будет мало).
Мало? Длина этого интервала может достигать расстояния между соседними степенями двойки. Это совсем не мало.

Цитата Сообщение от bad boy Посмотреть сообщение
написали программу, которая найдет в этом интервале число, двоичная запись которого содержит наибольшее количество единиц.
Запишем числа a и b в двоичном формате одно под другим с одинаковой длиной (дополним a нулями слева, если необходимо).

Если у чисел a и b есть общий префикс из 1, то этот префикс обязан войти в искомое результирующее число, ибо иначе оно не попадет в диапазон [a, b].

Как только мы при просмотре слева-направо найдем первый отличающийся бит между a и b (он, разумеется, будет равен 1 в b и 0 в a), нам нужно будет просто приписать к результирующему числу "хвост" вида 011...1 до конца числа.

Это и есть искомый результат.

Например: a = 8045 и b = 8091, т.е. 11111011011012 и 11111100110112

Код
a = 11111 0 1101101
b = 11111 1 0011011
    |---| ^ |-----|
      |   |    |
      |   |    хвост длины 7
      |   |
      |   первое отличие при просмотре слева-направо
      |
      общий префикс
Тогда ответом является 11111 0 1111111: 11111011111112 = 8063.

Очевидно, что такое число содержит максимальное количество единиц: в нем установлены все единицы, кроме того единственного нуля, который нужен для попадания в диапазон. То есть фактически задача сводится к поиску самого старшего различающегося бита между числами a и b.

Добавлено через 9 минут
---

Аааа... В решении есть неточность. Получаемое в результате число будет заведомо меньше b, т.е. будет принадлежать диапазону [a, b). А что если ответ задачи - именно b, что будет иметь место когда b целиком состоит из единиц? Подозреваю, что достаточно изначально взять диапазон [a, b + 1) и просто применить то же самое решение.

Добавлено через 2 часа 48 минут
---

Кстати, пораженческий поиск в инете находит еще один алгоритм, который, впрочем достаточно хорошо виден и при рассмотрении результатов того, что я привел выше:

Просто берем число a в качестве отправной точки и начинаем осторожно наращивать количество единиц в нем. "Осторожно" означает, что мы берем самый младший 0, заменяем его на 1 и проверяем, не превысили ли мы при этом b.

Тут нам на помощь приходят известные бит-хаки:

C++
1
2
n &= n - 1; // сбросить в 0 самую младшую 1 в числе
n |= n + 1; // установить в 1 самый младший 0 в числе
то есть получаем

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
int main()
{
  unsigned long long a = 0, b = 0, next_a;
  std::cin >> a >> b;
  
  while ((next_a = a | (a + 1)) <= b)
    a = next_a;
  
  std::cout << a << std::endl;
}
4
15.10.2021, 22:13
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.10.2021, 22:13
Помогаю со студенческими работами здесь

Определить какое число содержит наибольшее количество единиц
Написать программу, которая по трем введенными числами определяет то, которое содержит наибольшее...

Вывести десятичное простое число, в двоичной записи которого наибольшее число единиц
Привет всем! Помогите, пожалуйста. Суть задачи: На вход с клавиатуры программа получает N На...

Циклы: в интервале [A, B] найти число, имеющее наибольшее количество делителей
В интервале найти число, имеющее наибольшее количество делителей. (10 ≤ A, B ≤ 10000)....

Массив. Найти число, которое содержит наибольшее количество нулей
Помогите решить пожалуйста... 2) Создать массив случайных четырехзначных целых чисел (N &lt;= 30)....

В интервале [A,B] найти число, что имеет наибольшее количество делителей (10<=A,B<=10000)
Пожалуйста напишите программу. Задача ниже: В интервале найти число, что имеет наибольшее...

Найти число от M до N, квадрат которого содержит максимальное количество троек
Задача: Найти число от M до N, квадрат которого содержит максимальное количество троек.Если...


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

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

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