Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201

Деление на два

19.02.2022, 10:57. Показов 3111. Ответов 36
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Гоша очень любит делить числа на два. Иногда он развлекается следующим образом: берет какое-то число x, и делит его на два, потом результат снова делит на два, и так далее, пока не получит нечетное число. Например, если он выбрал число x=24, то сначала у него получится 12, затем 6, затем 3. Гоше нравится, когда этот процесс продолжается долго, поэтому он просит вас найти число из диапазона от a≤x≤b, выбрав которое можно делить на два как можно больше раз.



Входные данные:
Первая строка содержит число a, вторая строка содержит число b (1≤a≤b≤1012).




Выходные данные:
Выведите число x, которое нужно выбрать. Если ответов несколько, выведите любой.




Примеры:
входные данные
20
30
выходные данные
24


входные данные
316
412
выходные данные
384


входные данные
1
1000000000000
выходные данные
549755813888


входные данные
15
15
выходные данные
15
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.02.2022, 10:57
Ответы с готовыми решениями:

Задать два числа как два массива и потом выполнить сложение, умножение и деление
Здравствуйте! Суть задачи в следующем: Нужно задать два числа как два массива и потом выполнить сложение, умножение и деление с помощью...

Деление Wav-файла на два канала
Реализовать функцию разделяющую входной wav файл на каналы (на два выходных файла) с возможностью уменьшения амплитуд любого из каналов. ...

Деление на два
Гоша очень любит делить числа на два. Иногда он развлекается следующим образом: берет какое-то число x, и делит его на два, потом результат...

36
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
19.02.2022, 19:17
Студворк — интернет-сервис помощи студентам
Вот еще идея. Ищем такаю M = 2kчто b/M - a/M == 1 (границы надо уточнить.
Дальше - просто
Радует, что практически без перебора.

Добавлено через 1 минуту
HaisTous, это похоже на ваш подход.
1
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
19.02.2022, 20:31
Хм! А если в битах? Достаточно будет создать двоичное число, которое входит в границы с наибольшим числом нулей сзаду!

Добавлено через 6 минут
Т.е. однозначно берём первые единицы максимума, а дальше пока не придумал

Добавлено через 18 минут
Цитата Сообщение от Folian Посмотреть сообщение
Т.е. однозначно берём первые единицы максимума, а дальше пока не придумал
И двигать последнюю из первых вправо?

Добавлено через 2 минуты
Цитата Сообщение от Folian Посмотреть сообщение
И двигать последнюю из первых вправо?
Не эт фигня для например
1111
1001

Добавлено через 2 минуты
Цитата Сообщение от Folian Посмотреть сообщение
Т.е. однозначно берём первые единицы максимума
Эт тоже фигня отсюда
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
19.02.2022, 20:36
Цитата Сообщение от shinzin Посмотреть сообщение
10 в 12 степени
Так а почему в вопросе написано 1012, если нужно было "10 в 12 степени"?
0
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
19.02.2022, 20:51
Чую что плясать нужно от первого расхождения в битах минимума и максимума

Добавлено через 6 минут
Цитата Сообщение от Folian Посмотреть сообщение
плясать нужно от первого расхождения в битах минимума и максимума
Во! т.к. понятно что нижняя граница меньше - у неё ноль в первом расхождении бит от большего к меньшему. Берём всё что равно + бит(1), а остальное нули

Добавлено через 5 минут
Цитата Сообщение от Folian Посмотреть сообщение
Во! т.к. понятно что нижняя граница меньше - у неё ноль в первом расхождении бит от большего к меньшему. Берём всё что равно + бит(1), а остальное нули
не, опять не совсем
Code
1
2
3
1100001111
0100000100
1100000000
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
19.02.2022, 21:16
Очевидно, что задача заключается в том, чтобы найти число, чья двоичная запись содержит максимальное количество замыкающих нулей.

Если в наш диапазон [a, b] попадают степени двойки, то максимальная из них - ответ задачи. Все. Так что задача является "интересной" только для диапазонов, не содержащих степеней двойки.

"Поисковое" решение за логарифм очевидно:

1. Берем максимальную степень двойки, не превосходящую b. Если она в диапазоне - это ответ.

2. Дописываем в нее еще одну 1 в позицию сразу после старшей 1. Если мы попали в диапазон [a, b], то это ответ. Если мы все еще ниже a - сохраняем эту новую 1 в числе. Если мы оказались выше b - заменяем ее на 0.

3. Циклически повторяем шаг 2 для следующей двоичной позиции справа. В какой-то момент мы должны попасть в диапазон [a, b].

Добавлено через 7 минут
Толком не проверял, но приведенные тесты проходят

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C++20
#include <numeric>
#include <iostream>
 
int main()
{
  unsigned long a, b;
  std::cin >> a >> b;
  
  unsigned long n = std::bit_floor(b); // C++20
  
  for (unsigned long bit = n >> 1; n < a; bit >>= 1)
    if (n | bit <= b)
      n |= bit;
      
  std::cout << n << std::endl;
}

Но, разумеется, сохраняется надежда на остроумное "тривиальное" решение .
1
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
19.02.2022, 21:45  [ТС]
Надо перевести два числа в двоичную систему, потом добавить нули

Переведем число в двоичную систему счисления. В таком представлении число можно делить тем дольше, чем больше нулей в конце числа.

Для решения нужно:
- перевести оба числа в двоичный вид (меньшее число дополнить незначащими нулями)
- сравнивать биты числа начиная со старших разрядов

Пока значения разрядов одинаковые, то переходим к следующему разряду.
Если нашли разные разряды (0 в числа a, 1 в числе b), то считаем этот разряд равным единице, а остальные - до младших разрядов - нулями.

Код
10100 (20)
11110 (30)
---
11000 (24) - здесь второй слева разряд отличается



Код
100111100 (316)
110011100 (412)
---
110000000 (384) - здесь тоже второй слева разряд отличается
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
19.02.2022, 22:05
Цитата Сообщение от shinzin Посмотреть сообщение
Если нашли разные разряды (0 в числа a, 1 в числе b), то считаем этот разряд равным единице, а остальные - до младших разрядов - нулями.
Решение фактически эквивалентно приведенному мною выше. Разница лишь в интерпретации.

---

Другими словами, вся задача фактически эквивалентна

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

Разница только в характере приписываемого хвоста. Там приписывался хвост 011...1, Здесь приписывается хвост 00...0.
0
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
19.02.2022, 22:10
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Толком не проверял
Иногда выше верха берёт.

Я тут заколхозил чо в виду имел:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
uint64_t foo(uint64_t max, uint64_t min)
{
    if(min >= 1) --min; //это костыль, я ХЗ уже, устал сегодня;
                        //по нижней границе глючил
    if(max == min) return max;
 
    uint64_t ping { ~((~0ULL) >> 1 ) }; //верхний бит
    size_t shift { sizeof(uint64_t) * 8 };
    while((ping & max) == (ping & min))
    {
        ping >>= 1;
        --shift;
    }
    --shift;
    max >>= shift;
    max <<= shift;
 
    return max;
}
Вроде работает, но в проверке нуждается.
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
19.02.2022, 22:13
Цитата Сообщение от Folian Посмотреть сообщение
Иногда выше верха берёт.
Например?

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Кстати, по приведенной там же альтернативной схеме получаем альтернативное решение: Начинаем с числа b. В цикле сбрасываем у числа b самый младший единичный бит в 0 пока мы находимся не ниже a. Вот и все.

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_b;
  std::cin >> a >> b;
  
  while ((next_b = b & (b - 1)) >= a)
    b = next_b;
  
  std::cout << b << std::endl;
}
1
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
19.02.2022, 22:19
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
while ((next_b = b & (b - 1)) >= a)
    b = next_b;
Круто! Ёмко!

Добавлено через 24 секунды
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Например?
200, 201 --> 224
Ну и в таком духе проскакивало
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
19.02.2022, 22:26
Цитата Сообщение от Folian Посмотреть сообщение
200, 201 --> 224
Ну и в таком духе проскакивало
А, блин! Я - полено. Это банальная ошибка приоритетов операторов в коде

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C++20
#include <numeric>
#include <iostream>
 
int main()
{
  unsigned long long a, b;
  std::cin >> a >> b;
  
  unsigned long long n = std::bit_floor(b); // C++20
  
  for (unsigned long long bit = n >> 1; n < a; bit >>= 1)
    if ((n | bit) <= b)
      n |= bit;
      
  std::cout << n << std::endl;
}
Спасибо.
0
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
19.02.2022, 22:27  [ТС]
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math
a = 0
def bebra(x, y):
    assert x <= y
    k = 0
    while True:
        n = 2 ** k
        d = math.ceil(x / n)
        c = math.floor(y / n)
        if c == d:
            return (y // n) * n
        k += 1
x = input()
y = input()
x = int(x)
y = int(y)
print(bebra(x, y))

Вот готовый код на питоне, работающий, тут легко в с++ переделать можно
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
19.02.2022, 22:52
Цитата Сообщение от shinzin Посмотреть сообщение
Вот готовый код на питоне
Не самая оптимальная реализация, но и это - тоже вариант. При соответствующей интерпретации все это - разные записи одного и того же алгоритма.

Цитата Сообщение от shinzin Посмотреть сообщение
тут легко в с++ переделать можно
Готовый код на С++ вам уже предоставили.
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
20.02.2022, 19:23
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
#include <iostream>
 
int f(long long a) {
    int count = 0;
 
    while (a) {
        count++;
        a /= 2;
        if (a % 2 == 1)break;
    }
    return count;
}
 
int main(){
    long long n1= 1,n3=3,a=1,b=1e12;
 
    while (n1 <= b)n1 *= 2; 
    while (n3 < b)n3 *= 2; 
    if (a == b) {
        std::cout << a;
        return 0;
    }
    if (n1 / 2 < a)n1 = n3;
    f(n1/2)<=f(n3/2) ? std::cout << n3/2  : std::cout <<n1/2;
    return 0;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
20.02.2022, 19:25
Цитата Сообщение от повар1 Посмотреть сообщение
n3=3
???

a=9,b=12. В ответ получаем 6.
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
20.02.2022, 22:12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
a=9,b=12. В ответ получаем 6.
TheCalligrapher, вместо
C++
1
while (n3 < b)
вставляем
C++
1
while (n3 <= b)
Добавлено через 5 минут
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
???
остаток единица дает самое большое количество двоек, за ним идет остаток три. вот мы и ищем числа с такими остатками.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,400
20.02.2022, 22:45
Цитата Сообщение от повар1 Посмотреть сообщение
вставляем
C++
1
while (n3 <= b)
a=10,b=11. В ответ получаем 12.
a=13,b=17. В ответ получаем 12.

Цитата Сообщение от повар1 Посмотреть сообщение
остаток единица дает самое большое количество двоек, за ним идет остаток три. вот мы и ищем числа с такими остатками.
А как насчет остатков 5, 7, 11...? С ними не может быть "большого количества двоек"?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.02.2022, 22:45

Деление файла на два
Не могу понять в чем ошибка.Выдает такой результат file D:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 // исходный файл ...

Программа про деление на два
Дано три целых числа, вывести на екран те из них которые являются чётыми

Деление звукового сигнала на два канала
Всем привет ! Петцольд в статье описал как реализовать выдачу сигнала на оба канала... А есть возможность пихать разные сигналы в...

Деление с выводом остатка два двоичных числа Emu8086
Помогите разобраться.Нужна программа позволяющая делить с выводом остатка два произвольныхх двоичных положительных целых числа.Ввод...

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


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

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Новые блоги и статьи
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru