DjangoBB LoFi version

Полная версия: Алгоритм

Nolan

Сен. 25, 2022 20:44:08

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.
3. Шаг 2 повторяется ещё два раза.
4. Результат переводится в десятичную систему счисления.
При каком наибольшем исходном числе N < 750 в результате работы алгоритма получится чётное число, которое не делится на 4?

py.user.next

Сен. 26, 2022 12:07:31

Это фрагменты для построения программы

Nolan
1. Строится двоичная запись числа N.

  
>>> def f(n):
...     zeros = ones = 0
...     if n == 0:
...         zeros = 1
...     while n > 0:
...         if n % 2 == 0:
...             zeros += 1
...         else:
...             ones += 1
...         n //= 2
...     return zeros, ones
... 
>>> f(0)
(1, 0)
>>> f(1)
(0, 1)
>>> f(2)
(1, 1)
>>> f(3)
(0, 2)
>>> f(4)
(2, 1)
>>> f(10)
(2, 2)
>>> f(1000)
(4, 6)
>>>

Nolan
в конец записи добавляется её последняя цифра.

  
>> def f(n, digit):
...     out = None
...     if digit == 0:
...         out = n * 2
...     else:
...         out = n * 2 + 1
...     return out
... 
>>> f(5, 0)
10
>>> f(5, 1)
11
>>> 
>>> bin(5)
'0b101'
>>> bin(10)
'0b1010'
>>> bin(11)
'0b1011'
>>>

Nolan
получится чётное число, которое не делится на 4

  
>>> n = 2
>>> n % 2 == 0 and n % 4 != 0
True
>>> n = 4
>>> n % 2 == 0 and n % 4 != 0
False
>>> n = 6
>>> n % 2 == 0 and n % 4 != 0
True
>>> n = 8
>>> n % 2 == 0 and n % 4 != 0
False
>>> 
>>> n = 7
>>> n % 2 == 0 and n % 4 != 0
False
>>>

xam1816

Сен. 26, 2022 22:56:14

 def get_bin(num):
	return bin(num).split('b')[1]
 
def get_last_digit(num_bin):
	one = zero = 0
	for i in num_bin:
		if i == '1':
			one += 1
		else:
			zero += 1
	if one == zero:
		return num_bin[-1]
	elif one < zero:
		return '1'
	else:
		return '0'
 
def create_num(num):
	b = get_bin(num)
	for i in range(2):
		b += get_last_digit(b)
	return int(b, 2)
 
for i in range(750, 0, -1):
	new_num = create_num(i)
	if new_num % 2 == 0 and new_num % 4 != 0:
		print(i)
		break

737

Process finished with exit code 0