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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 06.10.2008, 03:48
гость

 
Сообщений: n/a

Следующее число
решаю задачу что то никак
http://acmp.ru/index.asp?main=task&id_task=318
вот сама задача
Задано натуральное число N.

Требуется написать программу, которая найдет следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N.
Входные данные

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

Выходной файл OUTPUT.TXT должен содержать ответ на задачу.
INPUT.TXT
1
2
3
OUTPUT.TXT
2
4
5
я думал для чётных умножаем на 2, а для не чётных, так считать степени двойки в числе потом эту степень делить пополам и складывать с самим числом делённым на 2, но не на всех тетстах проходит пробовал подругому что странно может я чего не понимаю..
  #2  
Старый 06.10.2008, 06:39
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Задача эквивалентна перечислению комбинаций (сочетаний) в лексикографическом порядке(точнее операции NextCombination)
  #3  
Старый 06.10.2008, 12:08
Новичок

Отправить личное сообщение для L.E.O. Посмотреть профиль Найти все сообщения от L.E.O.
 
Регистрация: 06.10.2008
Сообщений: 1

Можно решить задачу по другому, а именно исходить от 2-ой СС (по моему это будет быстрее).
!!Нумерация битов, в моем размышлении, идет с конца, т.к. в машине старшему биту соответствует старшая ячейка!!
Если число нечетное (т.е. первый бит равен 1), то достаточно сдвинуть последний бит влево.
Например:
00000011 -> 00000101; 00000001 -> 00000010; 00110011 -> 00110101;
Если число четное (т.е. первый бит равен 0), то делаем тоже самое, только с модификацией, а именно, мы все биты до последнего бита перемещаем в начало и первые нули мы игнорируем.
Например:
00000010 -> 00000100; 00000110 -> 00001001; 00110000 -> 01000001;

Вот код, написанный на С++:
Код:
#include <stdio.h>

int main()
{
	int a;
	scanf("%d", &a);
	int i = 1;
	if (a & 1)
	{
		while ((a >> i) & 1)
			i++;
		a &= ~(1 << (i - 1));
		a |= (1 << i);
	}
	else
	{
		while (((a >> i) & 1) == 0)
			i++;
		int count = 0;
		while ((a >> i) & 1)
		{
			a &= ~(1 << i);
			i++;
			count++;
		}
		a &= ~(1 << (i - 1));
		a |= (1 << i);
		count--;
		for (i = 0; i < count; i++)
			a |= (1 << i);
	}
	printf("%d\n", a);
	return 0;
}

Последний раз редактировалось L.E.O., 06.10.2008 в 12:14.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как присвоить переменной число более 2^64 Bra1n Реализация, исходники, языки 10 28.02.2008 12:37
как составить максимально приближенное число. Vovik Математические алгоритмы 4 16.05.2007 10:41
число = экспонента + мантисса Mr.Oduvanchik Математические алгоритмы 2 30.01.2007 14:22
число пи незарегистрированный Математические алгоритмы 2 21.12.2006 22:24