Форум » Выполнение и анализ алгоритмов для исполнителей » Задание 5 № 3455 » Ответить
Задание 5 № 3455
oksa: Автомат обрабатывает десятичное натуральное число N по следующему алгоритму: 1) Строится двоичная запись числа N. 2) К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае. 3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное. 4) Результат переводится в десятичную систему. Пример. Дано число N = 11. Алгоритм работает следующим образом. 1) Двоичная запись числа N: 11 = 10112 2) Единиц больше, чем нулей, новая запись 101102. 3) Длина начётная, удаляем три средних разряда, новая запись 102. 4) Десятичное значение полученного числа 2. Сколько различных значений на отрезке [50; 100] может получиться в результате работы автомата? В ответе - 13 У меня получается больше. Уже и в Excel построила табличку.( Объясните, пожалуйста, ход решения!!!
Ответов - 8
Поляков: Один из вариантов - через программу: [pre2] def alg( x ): s = bin(x)[2:] if s.count('1') > s.count('0'): s += '0' else: s += '1' m = len(s) // 2 if len(s) % 2 == 0: s = s[:m-1] + s[m+1:] else: s = s[:m-1] + s[m+2:] return s MAX = 100000 d = {} for N in range(10, MAX): R = int( alg(N), 2 ) d[R] = 1 count = 0 for R in range(50, 100): if R in d: print(R) count += 1 print( count )[/pre2]
oksaklk: Спасибо, но, вот список Ваших значений: 50 51 52 53 54 55 56 57 58 59 60 61 62 Берем число из отрезка [50; 100] - например, 68: 1) Строится двоичная запись числа N: 68=1000100 2) К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае: кол-во единиц в числе меньше - дописываем 1: 10001001 3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное: кол-во разрядов 8 - четное - убираем из середины два разряда: 100001 4) Результат переводится в десятичную систему: 100001=33 Такого числа в Вашем списке нет. Что я сделала не так? У меня другой выходной список чисел.
Поляков: oksaklk пишет:Берем число из отрезка [50; 100] - например, 68: Проблема в том, что отрезок [50; 100] относится не входным, а к ВЫХОДНЫМ значениям алгоритма.
oksakol: Спасибо! Из условия задания это было не очень понятно!
aei_73: Скажите пожалуйста, а есть ли какой-то другой способ решить эту задачу без использования языков программирования, т.е. вручную?
Поляков: aei_73 пишет: есть ли какой-то другой способ решить эту задачу без использования языков программирования, т.е. вручную? Конечно. По построению полученное число имеет четное количество разрядов, для диапазона [50;100] - это 6. Можно было бы думать, что подходят все числа от 50 до 63 включительно, но это не так. На шаге 2 мы дописываем в конец 1 только тогда, когда в числе нулей не меньше, чем единиц. Получается, что при результате 63 исходное число в двоичном коде имеет вид 111**11 или 111***11. Последний бит, приписанный на шаге 1, отброшен, середина, которая выкидывается, обозначена звездочками. Понятно, что в любом варианте количество нулей будет меньше, чем количество единиц. Поэтому число 63 получить не удастся, а остальные [50; 62] - можно. Всего 13.
VectorASD: Вот моя версия алгоритма, где юзаются множества ;'-} если N будет больше 255, то уже никак не выйдут числа от 50 до 100... Но для достоверности всё же я до 10к считаю :S [pre2] def Bin(Ch): return bin(Ch)[2:].rjust(8, "0") #Здесь не нужна, но так, оставил... :S def Bin2(Ch): return bin(Ch)[2:] def Z3453(): print("Z3453, Z3454 и Z3455 служат императору!") Res, Res2 = set(), set() Res3 = None for N in range(4, 10000): B = Bin2(N) if B.count("1") > B.count("0"): B += "0" else: B += "1" L = len(B) if L % 2 == 0: B2 = B[: L // 2 - 1] + B[L // 2 + 1 :] else: B2 = B[: L // 2 - 1] + B[L // 2 + 2 :] R = int(B2, 2) #print(N, B, B2, R) if R in range(50, 101): if R not in Res: print(N, R) #Вываливает изначальное число и ответ, если ответ на промежутке [50;100] будет встречаться впервые :S if R == 58: Res2.add(N) if R == 55: Res3 = N Res.add(R) print("Z3453:") print("Ответ:", Res3) print("Валидол:", "есть" if Res3 == 195 else "просрочен :/") print("Z3454:") print("Промежуточные результаты:", Res2) print("Ответ:", len(Res2)) print("Валидол:", "есть" if len(Res2) == 11 else "просрочен :/") print("Z3455:") print("Промежуточные результаты:", Res) print("Ответ:", len(Res)) print("Валидол:", "есть" if len(Res) == 13 else "просрочен :/") def Z3454(): Z3453() def Z3455(): Z3453() Z3455() #Z3520() #Z3524() #Z3526() [/pre2] UPD: срастил 3455 и 3454 в одну упаковку!!! UPD2: здесь УЖЕ есть ответ на 3453 :S
Starlen: Огромное спасибо за разъяснения
полная версия страницы