|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.01.2017, 20:46 | #1 |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
Последовательность N-битных чисел.
Всем доброго времени суток!
Решаю задачу и нет вообще никаких идей для решения, буду очень благодарен за намёки на правильную идею. Ниже сама задача: Задана отсортированная последовательность всех N-битных чисел, в которой были удалены все числа, имеющие в своей двоичной записи более, чем L единиц. Вам необходимо найти I тый элемент этой последовательности. Нумерация элементов начинается с единицы. Ограничения по времени 1 секунда. Формат ввода: N L I (1 ≤ N ≤ 31, 1 ≤ L ≤ N) Формат вывода: I-й элемент последовательности Пример ввода: 3 1 3 Пример вывода: 010 Всем заранее спасибо за помощь! Последний раз редактировалось VladKB1; 20.01.2017 в 22:44. |
20.01.2017, 22:19 | #2 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
Перебором не пробовали решить для начала?
Язык какой?
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
20.01.2017, 22:44 | #3 |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
|
22.01.2017, 00:19 | #4 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
А почему будет долго?
Есть обзорная статья на хабре об алгоритмах подсчёта количества единиц - https://habrahabr.ru/post/276957/ Ещё описания http://myworkonly.blogspot.ru/2012/01/blog-post_05.html Т.е. в цикле от 0 до ((2^N)-1) перебираете числа и находите I. Причём, можно ускорить поиск, начиная не от 0, а от ((2^L)-1). |
22.01.2017, 10:10 | #5 |
Участник клуба
Регистрация: 14.05.2016
Сообщений: 1,793
|
Попробуй решить сначала последовательно:
1) По данным N=4 заполнить массив всех возможных комбинаций: Код:
Код:
Код:
Ну ты понял последнюю мою мысль, да? Код:
Последний раз редактировалось Вадим Мошев; 09.02.2017 в 23:49. |
22.01.2017, 16:17 | #6 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
2^31 эта два миллиарда
А по теме. Есть задача насчитать сколько существует N-битный чисел, в которых нет более K нулей подряд. Заменяем 1 на 0. А потом.. Стоит мы сейчас в i-ой позиции. Значит остается N-i (с точность до 1, не хочу думать) разрядов. Давайте поставим 0(или 1, не хочу думать) и посчитаем сколько попадает ли мы туда? В зависимости от этого ставим 1 или 0 и идем дальше. Если что - вот пример 3 1 3 010 мы на первой позиции. Нужно понять что ставить. Если поставим 0 - останется две позиции. И варианты 00 01 10 - всего 3. 3<=3. Да. Идем. Первая цифра 0 На втором бите стоим. Есть поставить 0. Останется одна позиция 0 или 1. Давайте 0 поставим. Получится одно место. А там 0 или 1. 2 варианта. 3 <= 2? Нет. Значит ставим 1. Дальше снова пляшем. Последний раз редактировалось Dekay; 22.01.2017 в 16:22. |
22.01.2017, 18:58 | #7 | |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
Цитата:
|
|
22.01.2017, 21:04 | #8 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
Какое у вас ограничение на I ?
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
22.01.2017, 23:09 | #9 |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
|
23.01.2017, 01:55 | #10 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Пробовал простой перебор.
Потом лёгкую оптимизацию на случай, если I меньше первого числа с L+1 единицей. Потом сделал начало перебора не от 0, а от 1<<(L+1). Далее сделал пропуск всех чисел, в которых старшие разряды содержат L+1 единицу - прыжок на число вида 1<<t большее, чем текущее значение. Код:
Т.е. в начальный момент имеется диапазон без удалённых чисел Xstart=0 и Xfinish=(1<<(L+1))-1 - или для исключения переполнения Xfinish=(((1<<L)-1)<<1)+1 В этом диапазоне Xfinish-Xstart подходящих чисел. Их можно не перебирать, если их количество меньше I. Далее, найдём следующий диапазон. Он будет Xstart:=Xfinish+1 и Xfinish:=следующее сочетание из N по L Опять, количество подходящих чисел можно вычислить Xfinish-Xstart. И теперь всего Count:=Count+(Xfinish-Xstart) подходящих чисел в диапазоне от 0 до Xfinish. Продолжая так, в какой-то момент получим Count>=I. Тогда и завершить перебором от Xstart до Xfinish. Хотя и это не нужно - ведь этот диапазон - непрерывный. Получение очередного Xfinish не очень сложно. Видимо понадобится массив для заполнения разрядов. Или можно воспользоваться битовыми полями прямо в Xfinish (в FreePascal - они быстро работают). |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм формирования 32-битных чисел с плав. точкой из полученных 16-ти битных integer | MaratMT | Помощь студентам | 5 | 22.01.2016 14:09 |
Сложение 48-битных чисел. Ассемблер | zwenya | Помощь студентам | 1 | 29.03.2015 19:15 |
программа сложения 64-битных чисел | olikik | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 09.12.2010 23:23 |
Сложение 64 битных чисел вручную. Как? | coolibin | Общие вопросы C/C++ | 2 | 19.10.2010 14:06 |
Принцип хранения 32-битных integer-чисел | AndruXa | Свободное общение | 0 | 26.04.2008 13:43 |