Статья Автор: Лебедев Дмитрий

Разбор Статграда от 2024-12-17. Часть 2( 2, 5, 12, 15)

Задание 2

Логическая функция F задаётся выражением: (x ≡ (y → z)) ∧ (y ≡ ¬(z → w))
Дан частично заполненный фрагмент, содержащий неповторяющиеся
строки таблицы истинности функции F.

???	???	???	???	F
0	0		0	1
	0		0	1
1	0	1		0

Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.

Стандартное (для Статграда) задание. Решаем также стандарнтным образом

Дополняем в таблице значение 1 в позицию (3 строка, 4 столбец), так как
"одинаковых столбцов быть не должно"
Пишем функцию для вычисления формулы и программу для полной таблицы
Выводим строки с тремя 1 и значением функцмм 0:
определяем переменную на второй позиции
Выводим строки с тремя и более 0 и значением функцмм 1:
определяем переменную на третьей позиции
Затем разбираемся с 1 и 4 позициями

def z2(A):
  w,x,y,z = A
  return ( x == int(y<=z)) and (y != (z<=w))
for i in range(16,32):
  A = [int(s) for s in bin(i)[-4:]]
  if (A.count(1) == 3) and z2(A) == False : print(*A)

Реализация пункта 3 дала два варианта: на позиции 2 стоит x или z
Проверяем пункт 4 для 'позиция 2' ='x'

def z2(A):
  w,x,y,z = A
  return ( x == int(y<=z)) and (y != (z<=w))
for i in range(16,32):
  A = [int(s) for s in bin(i)[-4:]]
  if (A.count(0) >= 3) and z2(A) == True : print(*A)

Получаем противоречие, что х должен стоять и на позиции 3.
Ставим на вторую позицию 'z' и запускаем для пункта 4

def z2(A):
  w,z, x,y = A
  return ( x == int(y<=z)) and (y != (z<=w))
for i in range(16,32):
  A = [int(s) for s in bin(i)[-4:]]
  if (A.count(0) >= 3) and z2(A) == True : print(*A)

Получили, что на позиции 3 стоит x и ..... так как выведена только ОДНА строка, что в строке 2 не более двух нулей
Запускаем с этим условием и выбираем те, в которых 0 на позиции 2

def z2(A):
  w,z, x,y = A
  return ( x == int(y<=z)) and (y != (z<=w))
for i in range(16,32):
  A = [int(s) for s in bin(i)[-4:]]
  if (A.count(0) <= 2) and z2(A) == True : print(*A)

Такая строчка ОДНА (1010) и она соответствует указанному порядку.
Следовательно ответ wzxy

Задание 5

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N без ведущих нулей.
2. Подсчитывается количество единиц и количество нулей в полученной двоичной записи.
Эти числа переводятся в двоичную систему и записываются друг за другом без использования ведущих нулей:
сначала количество единиц, затем количество нулей.
3. Результатом работы алгоритма становится десятичная запись полученного числа R.

Определите минимальное число N, для которого результатом работы данного алгоритма будет R = 214.

Задача смотриться как стандартная: небольшое R, несложный алгоритм.
Реализуем функцию, проверим на тесте и некоторых числах, выведем двоичное представление числа 214.

def z5(N):
  s=bin(N)[2:]
  k0=s.count('0')
  k1=s.count('1')
  return bin(k1)[2:]+bin(k0)[2:]
M=214
print(M,bin(M)[2:])
N=int(input())
s=z5(N)
print(N,s,int(s,2))

Результат работы (небольшое значение получаемого результата) и вид 214 дают понять, что решение "в лоб" не лучший результат

214='11010110' = ...	цифр 1	цифр 0	всего цифр
'1' +'1010110'	1	86	87
'110'+'10110'	6	22	28
'11010'+'110'	26	6	32
'110101'+'10'	53	2	55
'1101011'+'0'	107	0	107

в таблице представлено разбиени двоичной записи числа 214 на две части
(учитывалось отсутствие ведущих нулей)
Самым лучшим надо признать '110'+'10110' и тогда число N = 2²⁷+2⁵-1
(в этом числе 22 нуля, и 6 единиц)
Проверим

def z5(N):
  s=bin(N)[2:]
  k0=s.count('0')
  k1=s.count('1')
  return bin(k1)[2:]+bin(k0)[2:]
M=214
print(M,bin(M)[2:])
N=2**27+2**5-1
s=z5(N)
print(N,s,int(s,2))

Получилось, что задание выполнено (почти полностью) аналитически.
Зачем тогда писать программу?

для понимания того, что нет "переборного"решения
для проверки результата

Задание 15

На числовой прямой даны три отрезка: P = [153697; 780411], Q = [275071; 904082], R = [722050; 984086].
Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(¬(x ∈ A)) → (((x ∈ P) ≡ (x ∈ Q)) → ((x ∈ R) ≡ (x ∈ Q)))
истинно (т.е. принимает значение 1) при любом значении переменной x.

Решать задание можно разными способами, но решим "методом прочтения задания"

Надо найти минимальную длину для A, значит входит в формулу без отрицания
Составим новую формулу, заменив условие x ∈ A на False
(True) → (((x ∈ P) ≡ (x ∈ Q)) → ((x ∈ R) ≡ (x ∈ Q))) = (((x ∈ P) ≡ (x ∈ Q)) → ((x ∈ R) ≡ (x ∈ Q)))
Выпишем границы всех отрезков по возрастанию
153697; 275071; 722050; 780411; 904082; 984086
Из каждого отрезка/луча возмем по представителю (любой из интервала)
100000; 150000; 250000; 700000; 750000; 900000; 950000; 1000000
Вычислим для них значение новой функции

Пишем функцию и программу

def f15(x):
  p = (153697 <= x <= 780411)
  q = (275071 <= x <= 904082)
  r = (722050 <= x <= 984086)
  return (p == q) <= (r==q)
data = [100000, 150000, 250000, 700000, 750000, 900000,  950000, 1000000]
for x in data :
  print(x, f15(x))

Ответ False получим для 700000 и 950000, а это значит

A должно покрыть промежуток от 275071 до 984086
длина отрезка A равна 984086 - 275071 = 709015

Для "сомневающихся" приведем формульное решение (заменив принадлежность просто на букву)
(¬A) → ((P ≡ Q) → ( R ≡ Q)) = A or ¬(P≡Q) or ( R ≡ Q) = A or P(¬Q) or (¬P)Q or RQ or (¬R)(¬Q) =
= A or [153697; 275071] or [780411; 904082] or [722050; 904082] or [-inf; 275071] or [ 984086; inf] =
= A or [-inf; 275041] or [722050; 904082] or [984086; inf]
значит A = (275041; 722050) U (904082; 984086) и так как A - единый отрезок, то A = [275041; 984086]

Из решения видно, насколько "метод прочтения задания" проще и удобнее

Сомневающиеся могут ещё проверить точки 275041.0001 и 984085.9999

Задание 12

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (111) ИЛИ нашлось (22)

заменить (111, 2)
заменить (222, 1)
заменить (221, 1)
заменить (122, 1)
заменить (22, 2)

КОНЕЦ ПОКА
КОНЕЦ
Определите, сколько различных строк, содержащих ровно 9 двоек,
может получиться в результате применения этой программы к строкам,
состоящим только из единиц и двоек.

Очень интересное задание. Для решения нужно проанализировать условие

Финальная последовательность не может содержать двух 2 подряд и трех 1 подряд,
то есть сответствует одной из масок (* это одна или две цифры 1) :
1. 2*2*2*2*2*2*2*2*2
2. 2*2*2*2*2*2*2*2*2*
3. *2*2*2*2*2*2*2*2*2
4. *2*2*2*2*2*2*2*2*2*
"Беглый взгляд" на программу убеждает, что ни одна из таких последовательностей не будет изменена,
а значит надо просто подсчитать их количество

Для * есть два варианта, значит масок будет

2⁸ (8 звездочек)
2⁹ (9 звездочек)
2⁹ (9 звездочек)
2¹⁰ (10 звездочек)

всего 256+512+512+1024 = 2304

Надо ли писать программу? Наверное нет ...

Чтобы оставить комментарий нужна авторизация

Печать