Разборы задач №2. Системы счисления

Содержание

Слайд 2

Содержание

3 – Золотая система счисления – codeforces 457A
8 – Universal convertor –

Содержание 3 – Золотая система счисления – codeforces 457A 8 – Universal
informatics 749
12 – Two's complement – 1 – informatics 750
16 – Two's complement – 2 – informatics 751

Слайд 3

Золотая система счисления – codeforces 457A

 

Золотая система счисления – codeforces 457A

Слайд 4

Золотая система счисления – codeforces 457A

Входные данные: две строки, в каждой из

Золотая система счисления – codeforces 457A Входные данные: две строки, в каждой
которых записана непустая строка из нулей и единиц. Длина каждой строки не превосходит 100000.
Выходные данные: «>», если первое число больше второго; «<», если первое число меньше второго; «=», если числа равны.


Слайд 5

Золотая система счисления – codeforces 457A

Примеры

Золотая система счисления – codeforces 457A Примеры

Слайд 6

Золотая система счисления – codeforces 457A

Вспомнив правила сложения двоичных чисел, будем учитывать,

Золотая система счисления – codeforces 457A Вспомнив правила сложения двоичных чисел, будем
что возможна замена единицы в старшем разряде на ноль с добавлением единиц в двух предшествующих разрядах без потери числа.
Тогда мы можем привести числа к одной длине и провести вычитание одного из другого. В результате мы получим число, обладающее следующими свойствами при замене единицы в старшем разряде:
Если во время замены получено 2, то уменьшаемое меньше вычитаемого.
Если во время замены получено -2, то вычитаемое меньше уменьшаемого.
Если 2 или -2 не получены, а два последних разряда равны 0, то исходные числа равны.
Если 2 или -2 не получены, а последний разряд больше 0 или последний разряд равен 0, а предпоследний больше 0, то вычитаемое меньше уменьшаемого
В иных случаях уменьшаемое меньше вычитаемого.

Слайд 7

Золотая система счисления – codeforces 457A

#include
using namespace std;
int main() {
string

Золотая система счисления – codeforces 457A #include using namespace std; int main()
a,b;
cin>>a>>b;
int n=max(a.size(),b.size());
if(a.size() else if(b.size() int c[100002];
for( int i=0;i c[i]=a[i]-b[i];
}
for( int i=0;i if(c[i]>2) {
cout<<">";
return 0;
}
if(c[i]<-2) {
cout<<"<";
return 0;
}
c[i+1]+=c[i];
c[i+2]+=c[i];
c[i]=0;
}
if(c[n-2]==0 && c[n-1]==0){
cout<<"=";
return 0;
}
if(c[n-2]>0 || (c[n-2]==0 && c[n-1]>0)) {
cout<<">";
return 0;
}
cout<<"<";
return 0;
}

Слайд 8

Universal convertor – informatics 749

 

Universal convertor – informatics 749

Слайд 9

Universal convertor – informatics 749

Примеры

Для решения данной задачи достаточно сперва перевести исходное

Universal convertor – informatics 749 Примеры Для решения данной задачи достаточно сперва
число в десятичную СЧ, а потом в целевую.

Слайд 10

Universal convertor – informatics 749

string dex="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int to_dex(string num, int radix){
int res=0;
for

Universal convertor – informatics 749 string dex="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; int to_dex(string num, int radix){
(unsigned int i=1;i<=num.length();i++)
res+=dex.rfind(num[i-1])*pow(radix, num.length()-i);
return res;
}

Слайд 11

Universal convertor – informatics 749

string to_radix(int num, int radix){
string res="";
while (num>=radix){

Universal convertor – informatics 749 string to_radix(int num, int radix){ string res="";
int x=num%radix;
res+=dex[x];
num/=radix; }
res+=dex[num];
reverse(res.begin(),res.end());
return res;}

Слайд 12

Two's complement – 1 – informatics 750

 

Two's complement – 1 – informatics 750

Слайд 13

Two's complement – 1 – informatics 750

Примеры

Two's complement – 1 – informatics 750 Примеры

Слайд 14

Two's complement – 1 – informatics 750

Поскольку числа изначально хранятся, как правило,

Two's complement – 1 – informatics 750 Поскольку числа изначально хранятся, как
в дополнительном коде, нам достаточно вывести n последних бит числа.
Получить i-тый бит можно так:
int bit = (x >> i) & 1;

Слайд 15

Two's complement – 1 – informatics 750

#include
using namespace std;
int main(){
int

Two's complement – 1 – informatics 750 #include using namespace std; int
x; cin>>x;
int n; cin>>n;
int *bits=new int[n];
for (int i=0;i int bit = (x >> i) & 1;
bits[n-1-i]=bit; }
for (int i=0;i cout< return 0;}

Слайд 16

Прыгающая лягушка – codeforces 1077A

Дана запись некоторого числа в двоичном дополнительном коде.

Прыгающая лягушка – codeforces 1077A Дана запись некоторого числа в двоичном дополнительном
Выведите десятичную запись этого числа.
Входные данные
Программа получает на вход строку из нулей и единиц. Длина строки не меньше 2 и не больше 16.
Выходные данные
Программа должна вывести десятичную запись числа, записанного в этой строке в двоичном дополнительном коде.

Слайд 17

Two's complement – 1 – informatics 750

Примеры

Two's complement – 1 – informatics 750 Примеры

Слайд 18

Two's complement – 1 – informatics 750

Если число положительное, то достаточно просто

Two's complement – 1 – informatics 750 Если число положительное, то достаточно
получить число из входной строки.
Если же число отрицательное, то сперва нужно привести число из дополнительного кода в прямой. Для этого:
Инвертируем все биты числа (включая знаковый).
К полученному числу добавляем единицу.
Умножаем результат на -1.

Слайд 19

Two's complement – 1 – informatics 750

Пример: перевод -5 из дополнительного кода

Two's complement – 1 – informatics 750 Пример: перевод -5 из дополнительного
в прямой и получение результата:
-5=1011
1) Инверсия битов: 1011->0010 (4)
2) Добавление единицы: 0100+1=0101 (5)
3) Умножение на -1: 5*(-1)=-5;