01-basics1 (1238871)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ОСНОВЫ ЯЗЫКА CТипы данных. Функции. Циклы. Простые программыК. Владимиров, Intel, 2019mail-to: konstantin.vladimirov@gmail.comКак зовут преподавателя?•Владимиров Константин Игоревич• Телефон: +7-903-842-27-55•Email: konstantin.vladimirov@gmail.com•Слайды: http://cs.mipt.ru/wp/?page_id=7775•Контесты: http://olymp1.vdi.mipt.ru•Основная коммуникация через emailHello, world!•Простейшая программа на языке C выводит приветствие миру на экран &#include <stdio.h>int main() {printf("%s\n", "Hello, world!");return 0;}•Наберите её в консоли, используя vim, скомпилируйте gcc и запустите•Справка по командам консоли: linux command line cheat sheet•Справка по работе с vim: vim cheat sheet•Справка по опциям gcc: gcc cheat sheetWarmup: частное и остаток•Для всех и ≠ 0, найдутся такие и , что = ∗ + #include <stdio.h>int main() {int a, b, p, q;printf("input a and b: ");scanf("%d%d", &a, &b);p = a / b; q = a % b;printf("p = %d, q = %d\n", p, q);}•Кто нибудь видит проблемы в этом коде?Компиляция и запуск> gcc divmod.c -o divmod> ./divmodinput a and b: 10 3p = 3, q = 1Реальная жизнь•В реальной жизни в программах бывают проблемы#include <stdio.h>int main() {int a, b, p, q;printf("input a and b: ");scanf("%d%d", &a, &b); // что если введены не два числа?p = a / b; q = a % b; // что если b == 0?printf("p = %d, q = %d\n", p, q);}•Варианты решения?Assert, assert, assert•Первый вариант: проверка утверждений (assertions)#include <assert.h>#include <stdio.h>int main() {int a, b, p, q, nitems;printf("input a and b: ");nitems = scanf("%d%d", &a, &b);assert((nitems == 2) && (b != 0));p = a / b; q = a % b;printf("p = %d, q = %d\n", p, q);}•Теперь будет ошибка.

Ещё вариант: после проверки ввода спросить ещё разПроверить и спросить ещё раз•Второй вариант: тщательная проверка вводаint main () {int a, b, p, q, nitems;for (;;) {printf("input a and b: ");nitems = scanf("%d%d", &a, &b);if ((nitems == 2) && (b != 0))break;printf("Wrong input!\n");fpurge(stdin); // or scanf("%*s");}p = a / b; q = a % b;printf("p = %d, q = %d\n", p, q);}Хочется вынестипроверку ввода вотдельную функциюМинимум о функциях•Объявление функции задаёт сигнатуру (типы аргументов и тип значения)int foo(int x, double y);void bar(); // эта функция ничего не вернёт•Функция может быть вызвана даже если ещё не определенаint t = 42; int s; s = foo(t, 1.0);•Где-то в программе (но только один раз) должно найтись тело функцииint foo(int x, double y) { int t = x + (int) y; return t; }•Возвращаемое значение можно проигнорировать даже если оно не voidint t = 42; foo(t, 1.0); // okВыносим проверку в функцию#include <stdio.h>void read_input(int*, int*);int main () {int a, b, p, q;read_input(&a, &b);p = a / b;q = a % b;printf("p: %d, q: %d\n", p, q);}void read_input(int *pa, int *pb) {for (;;) {int nitems;printf("input a and b: ");nitems = scanf("%d%d", pa, pb);if ((nitems == 2) && (*pb != 0))break;printf("Wrong input!\n");fpurge(stdin);}}• Функция должна быть объявлена до использования и определена где-то в коде• Часто объявления функций выносят в специальный заголовочный файл• Например объявления для printf и scanf находятся в stdio.hНаибольший общий делитель•Говорят, что целое число делит если их частноеявляется целым числом ∖  ∃ | = •Наибольшее среди чисел, которые делят оба числа и называется ихнаибольшим общим делителем (greatest common divisor, gcd) = gcd ,  = max | ∖ ∧ ∖ •Например наибольшим общим делителем чисел 14 и 8 является число 2•Как найти наибольший общий делитель чисел 698917 и 102089?Первый алгоритм: НОД• ∖  ∃ | = • = gcd ,  = max | ∖ ∧ ∖ •Задача: найти gcd(, )int gcd(int x, int y) {???} = ∗ + Пусть − общий делитель и Тогда = − ∗ тоже делится на Значит gcd(, ) = gcd(, )•Как перевести математический инсайт в программу?•Очень часто это основной вопрос в программированииПервый алгоритм: НОД• ∖  ∃ | = • = gcd ,  = max | ∖ ∧ ∖ int gcd(int x, int y) {assert(x > y);assert(y > 0);int q = x % y;if (q == 0)return y;return gcd(y, q);} = ∗ + Пусть − общий делитель и Тогда = − ∗ тоже делится на Значит gcd(, ) = gcd(, )•Посчитайте gcd(698917, 102089)•Покритикуйте приведённую функцию.

Не слишком ли строгий в ней первый assert?Алгоритм E•Вычисляет gcd(, ), при этом числа могут идти в любом порядкеint gcd(int x, int y) {int q;if (y > x)return gcd(y, x);assert(y > 0);q = x % y;if (q == 0)return y;return gcd(y, q);}•Как бы вы протестировали эту функцию? Нет ли в ней ошибок?Типы данных•Пока что на слайдах выше использовался только тип int•Но что такое int?Типы данных•Пока что на слайдах выше использовался только тип int•Но что такое int?•int это множество всех его допустимых значений (value type)Пример: число 1073741824 помещается в int, а 4294967296 или 1.1 нет•int это множество всех его допустимых операций (object type)Пример: операция x / y имеет разный смысл для int и doubleоперация x % y вообще невозможна для doubleassert (5.0 / 2.0 == 2.5);assert (5 / 2 == 2);Обсуждение•Когда начинается наше время?Наше время•0 секунд было 1 января 1970 года (Unix time)•Диапазон от − 231 − 1 до 231 − 1 сек•То есть от 13 декабря 1901 года до 19 января 2038 года•Но почему это так?Наше время•0 секунд было 1 января 1970 года (Unix time)•Диапазон от − 231 − 1 до 231 − 1 сек•То есть от 13 декабря 1901 года до 19 января 2038 года•Но почему это так?•Дело в том, что в 1970м году, в машине PDP-11 для хранения времени былвыбран тип, размером 4 байта•С тех пор человечество целиком так и не перешло на 8-байтное время.

Но мыв процессе•Вопрос к математически настроенной аудитории: надолго ли хватит 8 байт?Типы данных•char, short, int, long, long long•1 = sizeof(char) <= .... <= sizeof(long long)•CHAR_BIT >= 8 bit•Диапазон от − 2−1 − 1 до 2−1 − 1, где = () ∗ _•Все эти типы имеют беззнаковых двойников:unsigned char, unsigned short, unsigned int,unsigned long, unsigned long long•Обычно sizeof(T) == sizeof(unsigned T)•Диапазон от 0 до 2 − 1, где = ∗ _•unsigned int принято записывать просто как unsignedУпражнения с двоичными числами•В языке C используются префиксы 0 и 0x для 8-битных и 16-битных чисел.Также в этих лекциях будет использован нестандартный суффикс 0b длядвоичных чисел.•Верно ли следующее (подсчитайте без использования компьютера)1.assert (0xA0 == 0b10100000); // ?2.assert (075 == 0b111101);// ?3.assert (075 == 0x3E);// ?4.assert (0xA0 == 0240);// ?•Назовите минимальные типы данных для перечисленных чисел?Ввод и вывод разных типов•Для работы с разными типами, функции printf и scanf используютформатные спецификаторыint x = 2; unsigned long y = 0x30ff;printf("x = %d, y = %lu\n", x, y);•Сводная табличкаint%dlong%ldunsigned%ulong long%lldfloat%funsigned long%luchar%c, %hhdunsigned long long%llushort%hddouble%lfМинимум о циклах•В языке C есть три основных типа циклов: for, while и do-while•Циклы while: выполняются пока какое-то условие истинноwhile (i < 100) { /* тело цикла */ }•Циклы do-while: точно выполняются единождыdo { /* тело цикла */ } while (i < 100);•Циклы for: содержат инициализацию и изменение индуктивной переменнойfor (i = 0; i < 100; ++i) { /* тело цикла */ }i = 0; while(i < 100) { /* тело цикла */ ; ++i; }Перевод в системы счисления••Можно использовать деление с остатком, чтобы напечатать число в системе пооснованию N для небольшого N1262310= 110001010011112= 1220221123= 30110334= 4004435int print_converted(unsigned n, unsigned base) {assert (base > 1);while (n > 0) {printf("%d", n % base);n = n / base;}}•Процедура print_converted не вполне хороша: число выводится перевёрнутым•Скоро мы увидим как её улучшить, используя массивыProblem RL – рекурсия в цикл•Алгоритм E можно переписать, используя широкие беззнаковые типыunsigned long long gcd(unsigned long long x,unsigned long long y) {unsigned long long q;if (y > x)return gcd(y, x);assert(y > 0);q = x % y;if (q == 0)return y;return gcd(y, q);}•Задача: написать то же самое без рекурсии, с явным цикломProblem EE – расширенный алгоритм E•Даны два числа и •Необходимо вычислить их общий делитель и два числа и , такие, что + = •Обратите внимание, числа и целые положительные, числа и целые,но могут быть отрицательными, например для = 1769 и = 551 имеем:5 ∗ 1769 − 16 ∗ 551 = 29•То есть = 5 и = −16•Можно ли внести в алгоритм Е простую модификацию, чтобы получить обаэтих числа одновременно с общим делителем? Математический инсайтможно найти в , 1.2.1Warmup: числа Фибоначчи• Паре молодых кроликов нужен месяцчтобы вырасти• Каждая пара взрослых кроликовприносит пару молодых кроликовкаждый месяц• Сколько кроликов будет через год?001112233455Наивное решение•Очевидная рекуррентность = −1 + −2•Ведёт к очевидной функции на Cunsigned long long fib (unsigned n) {if (n == 0) return 0ull;if (n <= 2) return 1ull;return fib(n - 1) + fib(n - 2);}•Хороша ли эта функция?•Посчитайте на своей машине fib(5), fib(10), fib(20), fib(50)•Визуализация: http://www.cs.usfca.edu/~galles/visualization/DPFib.htmlАлгоритм F•Заменяем рекурсию на цикл (каждая итерация обновляет два числа)unsigned long long fib (unsigned n) {unsigned long long first = 0ull, second = 1ull; int idx;if (n == 0) return 0ull;for (idx = 2; idx <= n; ++idx) {unsigned long long tmp = second;second = second + first;first = tmp;}return second;}•Посчитайте на своей машине fib(5), fib(10), fib(20), fib(50)Переполнения•Подсчитайте fib(90) ...

fib(100) с помощью алгоритма F•Что на экране?Переполнения•Подсчитайте fib(90) ... fib(100) с помощью алгоритма F•Что на экране?fib(90) = 2880067194370816120fib(91) = 4660046610375530309fib(92) = 7540113804746346429fib(93) = 12200160415121876738fib(94) = 1293530146158671551 // oopsДо 93-го числа всё шло хорошо, но 94-е очевидно неверно, должно быть19740274219868223167. Давайте подсчитаем их в шестнадцатеричном виде.Переполнения•Подсчитайте fib(90) ...

fib(100) с помощью алгоритма F в hex-виде•Что на экране?fib(90) = 27f80ddaa1ba7878fib(91) = 40abcfb3c0325745fib(92) = 68a3dd8e61eccfbdfib(93) = a94fad42221f2702fib(94) = 11f38ad0840bf6bf // oopsОшибка там же, но теперь очевидно, что сложение 64-битных чисел идёт помодулю 264 . Настоящий результат 111F38AD0840BF6BF был сокращён поэтому модулю.Математика по модулю•Два числа называются равными по модулю m если m делит их разность•10 ≡ 6 (2) так как 2 \ (10 - 6)•Вообще все чётные числа равны по модулю 2: 10 ≡ 0 (2)•В некотором смысле по модулю 2 существует всего два числа: 0 и 1•Законы арифметики по модулю:(a + b) mod m == ((a mod m) + (b mod m)) mod m(a * b) mod m == ((a mod m) * (b mod m)) mod m•Пример: 29 ∗ 17 3 = 2 ∗ 2 3 = 1 (3)Пример: в степень по модулю•Возведение чисел в большие cтепени по небольшому модулю широкоиспользуется в криптографии.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций