ЛЕКЦИЯ 21 Целые типы 1. 2 http://www.checkio.org/ http://projecteuler.net/ http://acm.timus.ru/ Задачи. - презентация

1 ЛЕКЦИЯ 21 Целые типы 1

2 Задачи

3 Биты и байты 3 «бит» – это количество памяти, необходимое для хранения одноразрядного двоичного числа. Развитая Шенноном теория информации позволила решить главные проблемы, связанные с передачей сообщений, а именно: устранить избыточность передаваемых данных, произвести кодирование и передачу сообщений по каналам связи с шумами. Клод Шеннон Количество информации в сообщении (по Шеннону):

4 Байты и килобайты 4 НазваниеСимволКоличество байтB10 0 килобайтKB10 3 – килограмм мегабайтMB10 6 – метр гигабайтGB10 9 – гектар терабайтTB10 12 – тонна - объем современного жесткого диска петабайтPB10 15 эксабайтEB10 18 – первые 12 EB за 300 тыс. лет, вторые – за 2 года зеттабайтZB10 21 – объем информации, созданной человечеством за 2010 год йоттабайтYB10 24

5 Числа со знаком и без знака 5 РазмерЗнаковыйБеззнаковый 1sbytebyte 2shortushort 4intuint 8longulong sbyte byte int.MinValue int.MaxValue

6 Операция сдвига sbyte byte 5 > 2 = 1 Для типов int и uint важны 5 младших двоичных разрядов второго операнда, для типов long и ulong – 6 разрядов. int u = -10; u = u >> 7; Console.WriteLine(u);

7 Манипуляция битами 7 & | ~ >> > n) & 1; }

8 Манипуляция битами 8 Установить n-й разряд числа x в 1. Прочие разряды не менять. static int SetBit(int x, int n) { int u = 1

9 Цифровая поразрядная сортировка 9 Алгоритм 1. Сортируем массив по младшей цифре. 2. Сортируем массив по следующей цифре.... x. Сортируем массив по старшей цифре. Пример Оценка сложности ? def bin(lst, z): l = [] r = [] u = 1

10 Анатомия отрицательных чисел 10 Прямой код – – – – – – – – – – – – – – – – -7 Дополнительный – – – – – – – – – – – – – – – – -1 код + число = 2 3

11 Вычитание равно сложению 11 Дополнительный – – – – – – – – – – – – – – – – -1 Пример: 6 – 2 = 6 + (-2) = (6) (2) (4)

12 Самостоятельно 12 1.Дано целое число х. Установить n-й разряд этого числа в m (m = 0, 1). Остальные биты числа оставьте без изменений. 2.Дано целое число. Сосчитать количество единиц в его двоичной записи. 3.Дано целое число. Определить, есть ли в его двоичной записи три единицы подряд. 4.Запрограммировать цифровую поразрядную сортировку на С#. 5.В целом массиве находится двоичная запись отрицательного числа в прямом коде (знак записан в самом старшем элементе массива). Постройте в этом же массиве дополнительный код этого числа.

13 ЛЕКЦИЯ 22 Вещественные типы 13

14 Вещественные числа Плохая новость Только некоторые вещественные числа представимы в компьютере. Хорошая новость Любое вещественное число может быть записано в памяти компьютера приближенно. Вещественное число изображается при помощи двух целых чисел. 123/ * порядок мантисса 14

15 Представление в памяти мантисса порядок 64.0 = 16 * 2 2 = 8 * 2 3 = 4 * 2 4 = 2 * 2 5 = 1 * 2 6 = 0.5 * 2 7 = 0.25 * 2 8 = … Для однозначности представления мантисса должна быть нормализована: 2 > m >= 1 15

16 Стандарт IEEE 754 IEEE 754 стандарт формата представления числа с плавающей запятой, используемый как в программных реализациях арифметических действий, так и во многих аппаратных реализациях. Многие компиляторы языков программирования используют этот стандарт для хранения и выполнения математических операций. Стандарт определяет: форматы хранения мантиссы, показателя и знака, форматы положительного и отрицательного нуля, плюс и минус бесконечностей, а также определение "не числа", методы округления числа в процессе математических операций, порядок обработки исключительных ситуаций, таких как деление на ноль, переполнение и т.д. 16

17 Типы float и double float.MaxValue.MinValue.Epsilon.PositiveInfinity.NegativeInfinity.NaN.IsNaN.Parse() float: 4 байта (3 + 1) double: 8 байтов (6 + 2) double G = 6.67E-11d; double G = d; 17

18 Сложение вещественных чисел Алгоритм сложения: 1)выровнять порядок; 2)сложить мантиссы; 3)нормализовать результат. Пример сложения в десятичном виде. 0.5e e2исходные данные 0.005e e2 порядок выровнен 1.0e2 сложение произведено 0.1e3результат нормализован 18

19 Умножение вещественных чисел Алгоритм умножения: 1)перемножить мантиссы; 2)сложить порядки; 3)нормализовать результат. Пример умножения в десятичном виде. 0.11e3 * 0.123e2 исходные данные * e(3 + 2)мантиссы перемножены * e5порядки сложены 0.1e3результат нормализован 19

20 Сравнение вещественных чисел Не стоит сравнивать вещественные значения на равенство или не равенство. if ( != 0.1) Console.WriteLine("Кошмар бухгалтера."); Замечание. Именно поэтому, вещественные числа не применяются в бухгалтерских расчетах. Для бухгалтеров в С# существует особый тип целых чисел – decimal. 20

21 Сюрприз double a = 1e20, b = 1234; Console.WriteLine(a + b - a); // Эта строка напечатает 0 Console.WriteLine(a - a + b); // Эта строка напечатает

22 Самостоятельно 1.Найти местоположение заданного вещественного числа в вещественном же массиве. Два числа считать одинаковыми, если они отличаются меньше, чем на 1e Напишите программу, которая напечатает все положительные числа, представимые в разрядной сетке с двумя битами на мантиссу и двумя битами на порядок. 3.Напишите функцию, которая напечатает вещественное число в двоичной форме. В первом параметре функции задайте вещественное число, а во втором параметре – число разрядов в дробной части. 4.Разработайте алгоритм вывода на печать правильной дроби m/n в форме десятичной дроби вида 0.x 1 x 2...x k – всего k разрядов. 5.Дана правильная дробь m/n. Напечатать ее в десятичной форме с периодом в круглых скобках. Например, 2/30 = 0.0(6). 22

23 ЛЕКЦИЯ 23 Символы и строки 23

24 Символ – феномен культуры 24 Символ можно описать словесно, например, «Восьмерка, лежащая на боку, – математическое обозначение бесконечности». Символ может быть многозначным.

25 Основные термины 25 Символ – феномен культуры. Код символа – натуральное число. Разные символы должны иметь разные коды. Глиф – графическое изображение символа, обычно черно-белое. Шрифт – набор изображений символов (глифов), имеющий единый стиль.

26 Кодировка ASCII 26 Кодировка ASCII - 7-битная кодировка для представления латинского алфавита, десятичных цифр, некоторых знаков препинания, арифметических операций и управляющих символов (всего 128 символов). Роберт Бемер Символы с 0 по 1F предназначались для управления устройствами ввода-вывода.

27 Unicode (Юникод) 27 В 1991 г. общественная организация Unicode Consortium (в нее вошли ведущие производители компьютеров и ПО) предложила стандарт кодирования Unicode. В Юникоде первые 128 символов совпадают с соответствующими символами ASCII. Юникод поддерживает несколько способов преобразования потока символов в поток байтов UTF- 8, UTF-16 и UTF-32.

28 UTF x x F: 0xxxxxxx 0x x000007FF: 110xxxxx 10xxxxxx 0x x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx 0x x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx В тексте, сохраненном в формате UTF-8, любой байт со значением меньше 128 изображает символ ASCII с тем же кодом. Остальные символы Юникода изображаются последовательностями длиной от 2 до 4 байтов, в которых первый байт всегда имеет вид 11xxxxxx, а остальные 10xxxxxx. Количество байтов в коде, записанное в единичной с.с.

29 Тип char 29 В языке C# символы представлены типом char (от слова character – символ). Символьные константы заключаются в одинарные кавычки: 'а', 'B'. Для обозначения невидимых символов в C# применяют такие же константы, как в языке Си: '\n', '\r', '\t', '\a', '\\', Для обозначения всех без исключения символов применяют 16-ичные константы, например, '\U0041' – латинская прописная буква "А". Все символы в программе на C# кодируются в формате UTF-16 – два байта на символ.

30 Ввод с клавиатуры 30 Ввод одного символа char c = (char)System.Console.Read(); Немедленный вод символов: for (;;) { char c = Console.ReadKey(true).KeyChar; Console.WriteLine("Введен символ " + c); }

31 Тип string 31 char = Char, string = String Тип string основан на типе char. Кратко описать значение типа string, можно так: "Неизменяемый массив символов". string s = "abc"; s[0] = 'd'; // ОШИБКА! Примеры строковых констант: "Hello!\n" "C:\\Program строковая константа"

32 Операции над строками 32 string s = "abc" + "def"; string s1 = s; // копируется ссылка string s2 = new string(s); // копируется строка s[s.Length – 1] // s[-1] s.Substring(p, n) // s[p : p + n] s.Substring(0, s.Length – 1) // s[:-1] s.IndexOf(c) // s.find(c) s.LastIndexOf(c) // s.rfind(c)

33 Ввод и вывод строк 33 string s = Console.ReadLine(); // Преобразование к целому. short x = Convert.ToInt16(s); int i = Convert.ToInt32(s); long l = Convert.ToInt64(s); // Преобразование к вещественному. float f = Convert.ToSingle(s); double d = Convert.ToDouble(s); int x = 10, y = 20; Console.Write("Ширина = {0} Высота = {1}", x, y);

34 Форматирование вывода 34 Шаблон для форматирования чисел может включать в себя дополнительную информацию. В целом его структура такова: {index[,alignment][:formatString]} index – номер, нумерация шаблонов ведется с нуля. alignment – целое со знаком – ширина поля и выравнивание. Если ширина положительная – выравнивание вправо, если отрицательная – влево. :formatString – формат представления. Например, {0, -10:F2} означает выравнивание влево, ширина не менее 10 позиций, формат с фиксированной точкой, 2 знака после запятой.

35 Самостоятельно 35 1.Ввести с клавиатуры несколько символов и вывести на экран наименьший символ из введенных. Ввод символов закончить нажатием клавиши Enter. 2.Ввести с клавиатуры несколько символов и вывести их на экран в обратном порядке. 3.Ввести пароль в виде строки символов. Вычислить его хэш в виде суммы кодов всех символов по модулю 19. (Хэш в данном случае это однозначное преобразование пароля, которое меняет его до неузнаваемости). 4.Ввести несколько строк с клавиатуры. Вывести самую длинную строку. Признаком конца ввода пусть будет пустая строка. 5.Ввести с клавиатуры два слова, например, «комар» и «кошмар». Если введенные слова рифмуются, вывести «В рифму», если не рифмуются, вывести «Не в рифму».