Форум » Выполнение и анализ алгоритмов для исполнителей » задание 5(1751) » Ответить
задание 5(1751)
MblUlb: Добрый день, наткнулся на интересное задание на сайте: (№ 1751) Автомат обрабатывает натуральное число N < 256 по следующему алгоритму: 1) Строится восьмибитная двоичная запись числа N-1. 2) Инвертируются все разряды исходного числа, кроме последней единицы и стоящих за ней нулей (0 заменяется на 1, 1 на 0). 3) Полученное число переводится в десятичную систему счисления. Для какого значения N результат работы алгоритма равен 143? Ответ с сайта: 113 При его решении столкнулся с проблемой: при выполнении 2-го условия, а конкретней, части "кроме...", задача не имеет решения. Если откинуть его, то все работает, ответ тоже сходится с представленным на сайте. Кстати, еще непонятно последней с какой стороны является единица. Если я неправильно понял условие, прошу исправить меня. Вот примеры кода, которым решал задачу: 1(2-я часть второго условия отсутствует): [more] [pre2] for i in range(1, 256 + 1): n = i # print('n:', n) # 1 r = bin(n - 1)[2:] if len(r) < 8: r = '0' * (8 - len(r)) + r # print('#1:', r) # 2 # count1 = r.count('1') # print('count1:', count1) r = list(r) for k in range(len(r)): if r[k] == '0': r[k] = '1' elif r[k] == '1': # and count1 > 1: r[k] = '0' # count1 -= 1 # if count1 == 1: # break r = ''.join(r) # print('#2:', r) # 3 r = int(r, base=2) # print('#3:', n, r) if r == 143: print('-----------------', n) [/pre2] ответ: ----------------- 113 [/more] 2(полная программа): [more] [pre2] for i in range(1, 256 + 1): n = i # print('n:', n) # 1 r = bin(n - 1)[2:] if len(r) < 8: r = '0' * (8 - len(r)) + r # print('#1:', r) # 2 count1 = r.count('1') # print('count1:', count1) r = list(r) for k in range(len(r)): if r[k] == '0': r[k] = '1' elif r[k] == '1' and count1 > 1: r[k] = '0' count1 -= 1 if count1 == 1: break r = ''.join(r) # print('#2:', r) # 3 r = int(r, base=2) # print('#3:', n, r) if r == 143: print('-----------------', n) [/pre2] ответ отсутствует [/more] если единица с другого конца: [more] [pre2] for i in range(1, 256 + 1): n = i # print('n:', n) # 1 r = bin(n - 1)[2:] if len(r) < 8: r = '0' * (8 - len(r)) + r # print('#1:', r) # 2 count1 = r.count('1') # print('count1:', count1) r = list(r[::-1]) for k in range(len(r)): if r[k] == '0': r[k] = '1' elif r[k] == '1' and count1 > 1: r[k] = '0' count1 -= 1 if count1 == 1: break r = ''.join(r) # print('#2:', r) # 3 r = int(r[::-1], base=2) # print('#3:', n, r) if r == 143: print('-----------------', n) [/pre2] ответ: ----------------- 145 ----------------- 177 ----------------- 241 [/more]
Ответов - 3
Поляков: MblUlb пишет: Если я неправильно понял условие, прошу исправить меня. Вот правильный код: [pre2] N = 113 s = "{:08b}".format(N) p = s.rfind('1') sR = s[p:] for i in range(p-1,-1,-1): sR = ('1' if s[ i] == '0' else '0') + sR print( int(sR,2) )[/pre2]
MblUlb: Идею понял, спасибо, красиво написано). Какова вероятность встретить такое(по сложности) на ЕГЭ? И каково ученикам, изучавших всякие паскали до 3-й четверти 11 класса на уровне: это-ЯП и ОНО умеет складывать числа? 95% одноклассников не умеют им пользоваться вообще, а половина из них даже не понимает, что происходит.
Поляков: MblUlb пишет: 95% одноклассников не умеют им пользоваться вообще, а половина из них даже не понимает, что происходит. Цель ЕГЭ - отобрать тех, кто понимает, что происходит, и сможет успешно учиться дальше. Жизнь после школы - суровая штука.
полная версия страницы