Задача Биты

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н, профессор Пирогов В.Ю,, к.п.н, доцент Слинкин Д.А,

Модераторы: xdsl, Vladislav_133

Задача Биты

Сообщение Vladislav_133 15 мар 2017, 10:42

Разбор задачи "Поиск битов" здесь
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Биты

Сообщение ddzet 15 мар 2017, 11:15

А если ноль баллов значит вообще не один тест не прошел, даже с положительными числами? :D
ddzet
 
Сообщения: 12
Зарегистрирован: 11 мар 2017, 13:36
Полное имя: Глеб

Re: Задача Биты

Сообщение ddzet 15 мар 2017, 13:22

В тестах странность, по условию в файле input.txt в первой строке должны быть биты, а во второй числа, а здесь все в одной строке

Поэтому, ни один тест не проходит. Если же перенести число на след. строку в input, тогда работает
Вложения
input.JPG
Как по условию
input.JPG (15.4 Кб) Просмотров: 3868
beats.JPG
И как в input
beats.JPG (29.18 Кб) Просмотров: 3846
ddzet
 
Сообщения: 12
Зарегистрирован: 11 мар 2017, 13:36
Полное имя: Глеб

Re: Задача Биты

Сообщение xdsl 15 мар 2017, 13:43

Владислав Юрьевич, у нас опять проблемы с пользователями нестандартных операционных систем! Они хотят, чтобы строки обязательно заканчивались парой символов с кодами 13 и 10. Стандартный юниксовый и маковский \n их не устраивает. Мне кажется, их работы надо перепроверить.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задача Биты

Сообщение Vladislav_133 15 мар 2017, 13:52

Я думаю, что результаты можно пересмотреть в пользу студентов.
Хотя все таки укажу, что в этом отношении у участников есть недоработка.
Программа должна работать и при наличии перевода строки в конце и без наличия.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Биты

Сообщение ddzet 15 мар 2017, 13:59

Понял, значит в следующий раз буду внимательнее относиться к таким важным вещам

А за перепроверку спасибо!
ddzet
 
Сообщения: 12
Зарегистрирован: 11 мар 2017, 13:36
Полное имя: Глеб

Re: Задача Биты

Сообщение Vladislav_133 15 мар 2017, 14:27

Проверил у спорного человека, фамилию не называю.
Он писал на PascalABC. Проблема в Паскале, а не в участнике.
После перекомпиляции в FP все стало работать. Соответственно за Поиск Битов получает 2 очка.
А PascalABC выбросите. :)
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Биты

Сообщение ddzet 15 мар 2017, 14:43

Большое спасибо!

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

И от abc конечно надо избавиться
ddzet
 
Сообщения: 12
Зарегистрирован: 11 мар 2017, 13:36
Полное имя: Глеб

Re: Задача Биты

Сообщение xdsl 15 мар 2017, 14:56

Я бы сказал, что проблема даже не в ABC, а в .NET. Вернее, в несоответствии версий .NET, под которую собиралась программа в среде PascalABC и версии, установленной на компьютере судьи.
И действительно, FreePascal - лучший среди компиляторов языка Паскаль. Вот уж действительно "раз собери, запускай везде".
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задача Биты

Сообщение Vladislav_133 18 мар 2017, 15:34

Ликбез по битовой арифметике

Часть 1. Введение.

Решение данной задачи лежит в плоскости битовой арифметики и не требует никакой алгоритмической изощренности.
В действительности в задаче имеется две "изюминки", которые для некоторых оказались камнем преткновения.
Хотя все довольно просто, если имеешь представление о битовой арифметике.
1. Первая "изюминка".
В задаче сказано, что речь идет о 16-битовых числах. Вот это некоторые упустили. Вообще в разных языках понятие целого числа может несколько отличаться друг от друга.
Например, в языке C++ int - это 32-битовые числа, в Паскале принято, что integer это 16-битовые числа.
Кроме того надо различать знаковые и беззнаковые типы. Скажем, в языке C++ short int - это знаковые 16-битовые числа, а unsigned short int - беззнаковые целые числа.
В Паскале integer и word - соответственно. Для других языков, чтобы корректно решать подобные задачи, нужно предварительно изучить документацию.

2. Вторая "изюминка".
Для того, чтобы корректно решать подобные задачи, надо иметь некоторые, хотя бы элементарные представления о том, как представляются числа в памяти компьютера.
Тут важно иметь в виду, что числа располагаются в ячейках и представляются последовательностью нулей и единиц, т.е. записываются в двоичной системе.
Другими словами кроме нулей и единиц там нет ничего. А ведь, как мы уже упомянули, у нас могут быть знаковые и беззнаковые числа.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Биты

Сообщение Vladislav_133 18 мар 2017, 19:13

Часть 2. Беззнаковые целые числа

Беззнаковое целое 16-битовое число должно представляться 16 единицами и нолями.
Соответственно легко сообразить, что минимальным будет число, состоящее из 16-ти нолей:
00000000 00000000
максимальным же число будет
11111111 11111111
Как получить десятичное выражение двоично числа?
Получим, например, максимальное число, которое может хранится в 16-ти битах.
11111111 11111111 = 1*2^0+1*2^1+1*2^2+...+1*2^15 = 65535.
Как видим, перевод из двоичного вида к десятичному алгоритмически прост.
Обратный перевод чуть сложнее, но этот стандартный алгоритм обычно проходят, когда занимаются программированием
на первом курсе. Впрочем ниже я этот алгоритм представлю.
И так мы получаем, что 16-битовое беззнаковое число оказывается в промежутке [0,65535].
В принципе это довольно просто. Касательно беззнаковых чисел остается еще определится с тем,
что произойдет если к максимальному числу добавить 1 или от минимального числа отнять 1.
В принципе это уже неординарная ситуация, исключение, другими словами, есть еще термин переполнение.
Если произвести побитовое сложение
11111111 11111111
+
00000000 00000001
--------------------------
00000000 00000000

Т.е. получили 0.
Соответственно
00000000 0000000
-
00000000 0000001
-------------------------
11111111 1111111
Т.е. получаем 65535.
Другими словами переполнение приводит к тому, что значение как бы располагаются по кругу.
При решении стандартных задач программист не должен допускать переполнения, т.е.
всегда понимать со скольки-битовым числом он имеет дело.
В некоторых языках переполнение обрабатывается как ошибка.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Биты

Сообщение Vladislav_133 20 мар 2017, 18:03

Часть 3. Знаковые числа

Теперь перейдем к знаковым числам. Понятно, что мы можем исходить опять
только из битового представления. Причем речь опять будем вести о
16-битовых числах.

Рассуждение можно провести следующим образом. Имеем очевидное равенство 1+-1=0.
1 = 00000000 00000001. Нужно подобрать такой набор битов, чтобы в сумме с 1
получить 0. Легко увидеть, что это будет 11111111 11111111. Да, скажете вы,
это же 65535. Конечно, но это в беззнаковом представлении, а в знаковом это -1.
Аналогично можно найти, что -2 = 11111111 11111110. И т.д. Интересное здесь то,
что у отрицательных чисел старший бит всегда равен 1. Знаковые числа оказываются
в промежутке [-32768,+32767]. Также как и знаковые они расположены как бы по кругу:
-32768 - 1 = 32767 и 32767 + 1 = -32767. Это естественно, как и в случае с беззнаковыми
числами это есть факт переполнения, о котором надо помнить.

Но это еще не все. Самое потрясающее то, что этот бит при сложении и вычитании складывается и
вычитается как обычные биты. При этом само сложение и вычитание будет проходить
по одному и тому же алгоритму, что для знаковых, что для беззнаковых чисел.
Машинные команды сложения и вычитания одинаковы для обеих типов чисел.

Отсюда мы получаем важный алгоритм для получения битового представления отрицательных чисел.
Нужно осуществить преобразование типов от знакового к беззнаковому представлению,
а затем использовать стандартный алгоритм преобразования от десятичного представления
к двоичному. Но об этом в следующей части.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Биты

Сообщение Vladislav_133 21 мар 2017, 11:43

Часть 4. Переход от десятичного к двоичному представлению числа

И так, отрицательные числа нам не страшны. Надо просто перейти от знаковых к беззнаковым переменным и все у нас получится.
На языке C++ это выглядело бы так:
Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
short  m = -2;
unsigned short n;
n = (unsigned short)m;
 

Теперь можно работать с беззнаковой переменной n, в частности получить ее двоичное представление, которое вместе с тем будет двоичным представлением числа -2.

Идея получения двоичного представления очень проста. Она основывается на том, что остаток от деления числа на 2 дает всегда младший бит двоичного представления, деление же на сдвигает биты вправо, т.е. удаляет младший бит. И так, на языке C++ это можно записать, например, так
Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
i=0; j=n;
while(1){
  j=(j/2);
  n=n%2;
  if(!n)s[i]='0';else s[i]='1';
  i++;
  if(!j)break;
  n=j;
}
s[i]='\0';
 


Здесь массив s (символьный) получает биты числа, i - нумерует количество битов.
Ну все, наслаждайтесь программированием.
Да, чуть не забыл. Порядок в массиве s надо будет потом изменить на противоположный, но это уже совсем просто, я уж не говорю о поиске подстроки в строке.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Биты

Сообщение [DD] 14 апр 2017, 09:07

Способ конечно же читерный, но ни каких ограничений для существования данного решения в условиях не нашел.
Подсветка синтаксиса: (main.rs) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка php
  1. use std::fs::File;
  2. use std::io::{Write, Read};
  3.  
  4. fn main() {
  5.     let mut input = File::open("input.txt").unwrap();
  6.     let mut output = File::create("output.txt").unwrap();
  7.     let mut data = String::new();
  8.     input.read_to_string(&mut data).unwrap();
  9.     let mut data:Vec<&str> = data.split("\n").filter_map(|x|{let x = x.trim(); if x.len() == 0{None} else {Some(x)}}).collect();
  10.     let bits = data.remove(0);
  11.     let search = format!("{:b}", data.remove(0).parse::<i16>().unwrap());
  12.     let search = search.trim_left_matches("0");
  13.     match bits.find(&search) {
  14.         Some(pos) => {
  15.             let mut res = String::new();
  16.             res.push_str(&" ".repeat(pos));
  17.             res.push('|');
  18.             if search.len() > 3{
  19.                 res.push_str(&"-".repeat(search.len() - 2));
  20.             }
  21.             if search.len() > 1{
  22.                 res.push('|');
  23.             }
  24.             let f = format!("{}\n{}", bits, res);
  25.             output.write(&f.into_bytes()).unwrap();
  26.         },
  27.         None => {
  28.             output.write(b"None").unwrap();
  29.         }
  30.     };
  31. }
  32.  
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron