eolymp

Лекция 1. Введение в язык Си

ЗАНЯТИЕ 1

1. Чемпионат мира по программированию под эгидой ACM.

1.1. Соревнования в интернете. Правила участия.

1.2. Задача, решение, тест. Правила оформления.

1.3. Командный и индивидуальный принципы соревнования на олимпиадах.

2. Введение в язык Си.

2.1. Создание консольного приложения в MICROSOFT VISUAL C++ 6.0.

2.2. Создание консольного приложения в MICROSOFT VISUAL STUDIO 2005.

2.3. Программа HELLO WORLD!

2.4. Переменные и их объявления

2.5. Вычисление суммы двух чисел. Формат ввода-вывода.

2.6. Биты. Байты. Слова.

2.7. Оператор присваивания.

2.8. Условный оператор и операции сравнения.

3. Задачи.

http://acm.timus.ru: 1000 (A + B Problem).

http://acm.sgu.ru: 100 (A + B).

1. ЧЕМПИОНАТ МИРА ПО ПРОГРАММИРОВАНИЮ ПОД ЭГИДОЙ ACM

   Ежегодно в мире проходит огромное количество олимпиад по информатике и программированию разного уровня. Самым серьезным и престижным соревнованием является Первенство Чемпионата Мира по программированию среди студентов высших учебных заведений, которое ежегодно проводит ассоциация компьютерных машин (www.acm.org). Официальная страница соревнований находится на acm.baylor.edu. Студенческие соревнования стимулируют научную деятельность Вуза, помогают одаренной молодежи реализовать свои возможности, имеют огромное значение при определении развития компьютерных наук в Вузе.

   Первенство мира проходит в несколько этапов: национальные олимпиады, региональные олимпиады, которые проходят за географическим принципом в более чем 30 регионах (icpc.baylor.edu/past) и финал первенства мира, в котором берут участие более 70 команд – победителей и призеров региональных олимпиад.

   Популярность этих соревнований, определяющих уровень страны в области информационных технологий, очень велика. Например, в 2002/2003 учебном году только в региональных олимпиадах взяло участие 3850 команд из 1329 университетов из 65 стран, а общее число команд-участников национальных первенств приблизительно оценивалась в 24-25 тысяч. В полуфиналах 2004/2005 года взяло участие около 4100 студенческих команд, а общее число команд в четвертьфинальных соревнованиях 2005/2006 года оценивается в 60 тысяч команд, или около 200 тысяч участников.

   Европейские страны начали брать участие в соревнованиях с 1991 года, а Восточно-Европейские с 1995. Чемпионами Восточной Европы становились Чехия (1998), Польша (2003, 2007). Шесть раз чемпионами мира и соответственно обладателями кубка становились команды из России (icpc.baylor.edu/past/default.htm): Санкт-Петербургский государственный университет (2000, 2001), Санкт-Петербургский институт механики и оптики (2004, 2008, 2009), Саратовский государственный университет (2006). В 2002, 2005 и 2010 годах чемпионом мира становился Шанхайский университет (Китай).

   Чемпионат мира под эгидой АСМ является командным соревнованием. Трем участникам необходимо решить от 8 до 10 задач за 5 часов, используя только один компьютер. Среди основных разделов компьютерных дисциплин, знаниями которых должен обладать студент для удачного выступления на международной арене, являются чисто математические дисциплины (математический анализ, алгебра), дискретная математика, методы оптимизации, вычислительная геометрия, теория чисел, и конечно же построение и анализ алгоритмов.  Кроме теоретических занятий при подготовке к соревнованиям следует тренироваться решать сложные задачи и писать оптимальный код программ. В мире существует множество WEB страниц, которые помогают молодежи в этом процессе:

  1. http://acm.timus.ru  –  Уральский университет, Россия
  2. http://acm.sgu.ru – Саратовский университет, Россия
  3. http://acm.uva.es/problemset  – университет Вальядолид, Испания
  4. http://ace.delos.com/usacogate – USA Computing Olympiad, США
  5. http://acm.zju.edu.cn  – университет Жейанг, Китай
  6. http://cs.tju.edu.cn/acm/ – университет Тяншань, Китай
  7. http://acm.fjnu.edu.cn/ – университет Фужан, Китай
  8. http://acm.pku.edu.cn/JudgeOnline – Пекинский университет, Китай
  9. https://spoj.sphere.pl  – Варшавский университет, Польша
  10. http://www.topcoder.com – соревнования по программированию, США

   На них собрано большое количество задач, которые предлагались на предыдущих соревнованиях. На них работает система Online judge. На этих страницах часто проходят дистанционные соревнования в реальном времени, участие в которых дает возможность молодежи оценить свои знания и возможности. Например, страничка www.topcoder.com предлагает не только денежные призы за победу в конкурсах, но и обеспечивает их работой.

    Следующие страницы также посвящены олимпиадному программированию:

  1. http://dl.gsu.unibel.by – Система дистанционного образования, Беларусь
  2. http://www.uoi.kiev.ua – Всеукраинские олимпиады
  3. http://www.ttb.by – Беларусь
  4. http://plg.uwaterloo.ca/~acm00/ – университет Ватерлоо, Канада
  5. http://neerc.ifmo.ru/school/ – соревнования для школьников, Санкт-Петербург

 2. ВВЕДЕНИЕ В ЯЗЫК СИ

2.1. СОЗДАНИЕ КОНСОЛЬНОГО ПРИЛОЖЕНИЯ В MICROSOFT VISUAL C++ 6.0

   1. Создаем новый пустой проект.

   File → New → Win32 Console Application, в окне Project Name вводим имя проекта, в окне Location выбираем место расположения проекта.

   В следующем окне выбираем тип консольного приложения: An empty project.. Далее нажимаем Finish, ok.

   2. В пустой проект добавляем файл .сpp, в котором пишем код программы.

   File → New → (закладка Files) → C++ Source File, вводим имя файла в окне File Name. В открывшийся файл вводим текст программы.

2.2. СОЗДАНИЕ КОНСОЛЬНОГО ПРИЛОЖЕНИЯ В MICROSOFT VISUAL STUDIO 2005

   1. Создаем новый пустой проект.

   File → New → Project → Win32 (в окне project types), Win32 Console Application (в окне templates) в строке Name вводим имя проекта, в строке Location выбираем место расположения проекта.

   В следующем окне наживаем на кнопку "Next".

   Откроется окно "Application Settings". Выбираем следующие опции: Application Type: Console application, Additional options: Empty project. Далее нажимаем Finish, ok.

   2. В пустой проект добавляем файл .сpp, в котором пишем код программы.

   В окне Solution Eplorer правой кнопкой мыши выбираем папку Source Files, далее Add → New Item. В категории "Visual C++" выбираем "Code", в списке "Templates" выбираем C++ File (.cpp), вводим имя файла в строке Name. Нажимаем кнопку "Add". В открывшийся файл вводим текст программы.

2.3. ПРОГРАММА HELLO WORLD!

   Программа печати сообщения “Hello World!” имеет вид:

#include< stdio.h >

void main(void)

{

 printf("Hello World!\n");

}

   Для использования функций ввода-вывода следует подключить библиотеку стандартного ввода-вывода (STanDart Input-Output). Библиотека подключается ключевым словом include, перед которым ставится символ #.

   Строки в языке Си выделяются двойными кавычками (в Паскале – одинарными). Символ перевода курсора на новую строку имеет вид ‘\n’. При помощи функции printf в программе выводится строка "Hello World!", после чего производится перевод курсора на новую строку.

   После компиляции программы на языке Си операционная система вызывает функцию main. Слово main являет ключевым – оно является именем функции, которая вызывается операционной системой при старте программы. Функция main обязана присутствовать в любой программе Си, так как она является точкой входа в программу.

   Открывающаяся и закрывающаяся скобки { … } в Си являются аналогом begin .. end в Паскале.

   Внимание! Для запуска проекта в среде разработки MICROSOFT VISUAL STUDIO 2005 следует воспользоваться сочетанием клавиш CTRL + F5 (Start Without Debugging).

algo_lec01_ris01

2.4. ПЕРЕМЕННЫЕ И ИХ ОБЪЯВЛЕНИЯ

    Переменные представляют собой область памяти для хранения данных. Имя переменных называют идентификатором.

   Имя переменной может содержать от одного до 32 символов. Разрешается использовать строчные и прописные буквы, цифры и символ подчёркивания, который в Си считается буквой. Первым символом обязательно должна быть буква. Имя переменной не может совпадать с зарезервированными словами.

  Объявление переменных происходит в операторе описания, состоящем из спецификации типа и списка имён переменных, разделённых запятой. В конце оператора должна стоять точка с запятой. Простейший формат объявления переменной имеет вид:

спецификатор_типа идентификатор [, идентификатор] ... ;

   Спецификатором типа является ключевое слово, определяющее тип объявляемой переменной, а идентификатором - имя переменной.

   Например, объявить две целочисленные переменные x, y и одну символьную c можно следующим образом:

int x,y;

char c;

2.5. ФОРМАТ ВВОДА-ВЫВОДА. ВЫЧИСЛЕНИЕ СУММЫ ДВУХ ЧИСЕЛ

   Для форматированного ввода-вывода данных пользуются функциями scanf и printf. Первый аргумент функций содержит формат ввода-вывода. Далее следуют вводимые (выводимые) переменные. Следующая таблица представляет формат ввода-вывода элементарных типов данных в Си:

описание типа

тип

формат

целочисленный, 4 байта

int

%d

целочисленный, 8 байт

__int64

%I64d

целочисленный, 8 байт

long long

%lld

действительный, 4 байта

float

%f

действительный, 8 байт

double

%lf

символьный, 1 байт

char

%c

строка, массив символов

char[], строка

%s

   Оператор присваивания в языке Си имеет вид знака равенства ‘=’.

   Операторы в языке Си разделяются знаком ‘;’.

   Комментарии в языке Си выделяются символами /* … */.

   Комментарии до конца строки следуют после символов //.

   Пример 2.5.1. Инициализируем переменные i (целое), j (вещественное), c (символьное) соответственно значениями 4, 5,4, ‘A’ и выведем их на экран. В дальнейшем операции ввода-вывода будем комментировать, указывая вводимые и выводимые значения.

#include< stdio.h >

int i = 4;

double j = 5.4;

char c = 'A';

void main(void)

{

  printf("%d %lf %c\n", i, j, c);  // 4 5.400000 A

}

   Символьным переменным можно присваивать не только символы, но и значения от 0 до 255. В таком случае переменная будет принимать значение того символа, ASCII код которого ей присвоен. Значения символьных переменных можно выводить как символы (используя формат вывода %c) или как числа – ASCII коды символов (используя формат вывода %d).

   Напоминание! Сокращение ASCII расшифровывается как American Standart Code for Information Interchange.

   Пример 2.5.2. Присвоим символьной переменной с значение 65 и выведем ее, используя форматы %c и %d. Напомним, что ASCII код символа 'A' равен 65.

#include< stdio.h >

char c = 65;

void main(void)

{

  printf("%c %d\n", c, c);  // A 65

}

   Упражнение 2.5.1. Напишите программу, которая выведет на экран строку из четырех символов, ASCII коды которых соответственно равны 3, 4, 5 и 6.

    Пример 2.5.3. Рассмотрим программу, которая вводит два целочисленных числа a и b, вычисляет их сумму в переменной res и выводит на печать пример в формате

«слагаемое + слагаемое = сумма»

   В качестве второго аргумента функции scanf следует передавать адреса переменных. Адрес переменной x обозначается &x.

#include< stdio.h >

int a, b, res;

void main(void)

{

  scanf("%d %d",&a,&b);                    // a = 3, b = 5

  res = a + b;

  printf("%d + %d = %d\n", a, b, res);     // 3 + 5 = 8

}

   Операции ввода-вывода можно также выполнять при помощи потоковых бесформатных функций cin и cout библиотеки . Но они работают значительно медленнее, чем prinf и scanf. Поэтому для выполнения операций ввода-вывода рекомендуется пользоваться библиотекой .

   Пример 2.5.4. Перепишем программу из примера 2.3.3. вычисления суммы двух чисел с использованием функций cin и cout:

#include< iostream.h >

int a, b, res;

void main(void)

{

  cin >> a >> b;         // a = 3, b = 5

  res = a + b;

  cout << res << endl;   // 8

}

   Упражнение 2.5.2. Напишите программу, которая по заданным двум действительным числам a и b находит и выводит значение выражения a2 + b2.

2.6. БИТЫ. БАЙТЫ. СЛОВА

  Битом называется единица информации. В одну ячейку памяти размером 1 бит можно занести два значения: 0 или 1.

   Байтом называется ячейка памяти, состоящая из 8 битов.

   Словом называется ячейка памяти, состоящая из двух байт или 16 битов.

   Двойным словом называется ячейка памяти, состоящая из четырех байт или 32 битов.

   В языках программирования различают, как правило, знаковые и беззнаковые типы данных. Беззнаковые типы данных хранят только неотрицательные значения, знаковые могут содержать как положительные, так и отрицательные числа.

    Беззнаковые типы данных. Пусть имеется два бита. В них можно занести одно из четырех значений:

содержимое 2 битов

значение

00

0

01

1

10

2

11

3

   Соответственно в трех битах можно хранить значения от 0 до 7:

содержимое 3 битов

значение

000

0

001

1

010

2

011

3

100

4

101

5

110

6

111

7

   В n битах можно хранить числа от 0 до 2n – 1. Например, в беззнаковом байте (8 бит) можно записать любое число от 0 до 255, а в беззнаковом двойном слове – число от 0 до 232 – 1 = 4294967295.

   При выводе десятичных значений переменных беззнаковых типов вместо %d (decimal) пользуются %u (unsigned). Значения можно выводить также в беззнаковом восьмеричном типе %o (octal) и шестнадцатиричном %x (hexadecimal).

    Знаковые типы данных. Старший бит знакового типа данных отвечает за знак числа. Число является положительным, если бит равен 0 и отрицательным, если бит равен 1. Например, в трех битах можно хранить знаковые значения от -4 до 3:

содержимое 3 битов

значение

011

3

010

2

001

1

000

0

111

-1

110

-2

101

-3

100

-4

   В n битах можно хранить знаковые числа от -2n-1 до 2n-1 – 1. Например, в байте можно записать любое число от -128 до 127, в двойном слове – число от -231 = -2147483648 до 231 – 1 = 2147483647.

   Целочисленный тип int в языке Си четырехбайтовый, поэтому переменные типа int могут хранить значения в промежутке [-231; 231 – 1] = [-2147483648; 2147483647].

   Целочисленный тип long long в языке Си восьмибайтовый, поэтому переменные типа long long могут хранить значения в промежутке [-263; 263 – 1] = [-9223372036854775808; 9223372036854775807].

   Упражнение 2.6.1. Указать интервал чисел, которые можно хранить в 2 байтах в случае знакового и беззнакового типа.

   Пусть algo_lec01_ris02 – двоичная запись числа n. Тогда для получения десятичной записи числа -n необходимо инвертировать все биты в десятичной записи числа n и прибавить 1. То есть двоичная запись числа -n будет иметь вид algo_lec01_ris03, где через algo_lec01_ris04 обозначено инвертирование бита .

   Пример 2.6.1. Пусть под знаковый целочисленный тип отведено 4 бита. Какое десятичное число будет обозначать двоичная запись 1101?

   Поскольку на первом месте стоит 1, то число отрицательное. Инвертируем биты: 0010 и прибавляем 1, получим 00112 = 310. Таким образом, число 1101 обозначает -3.

    Пример 2.6.2. Если к макимальному целочисленному значению прибавить 1, то получится наименьшее целочисленное значение. Аналогично если из наименьшего значения типа int вычесть 1, то получится  наибольшее значение типа int.

#include< stdio.h >

int i = 2147483647;

void main(void)

{

  printf("%d %d\n", i, i + 1);  // 2147483647 -2147483648

  i++;

  printf("%d %d\n", i, i - 1);  // -2147483648 2147483647

}

   Константы INT_MIN и INT_MAX, объявленные в библиотеке , соостветственно равны наименьшему и наибольшему значению, которое может принимать переменная типа int.

   Пример 2.6.3. Выведем значения переменных INT_MIN и INT_MAX.

#include< stdio.h >

#include< limits.h >

int i = INT_MIN, j = INT_MAX;

void main(void)

{

  printf("Min Value:%d \nMax Value: %d\n", i, j);

  // Min Value: -2147483648

  // Max Value: 2147483647

}

   Пример 2.6.4. Выведем наибольшее и наименьшее значение восьмибайтового целочисленного знакового типа  long long. Для того чтобы число имело тип long long, а не int, после него следует писать суффикс LL. Например, значение (1LL << 63) – 1 будет иметь тип long long и равняться 9223372036854775807 (19 десятичных знаков), а (1 << 63) – 1 будет типа int и равняться -1 (значение 1 << 63 при вычислении на 32 битах равно нулю).

#include< stdio.h >

long long i;

void main(void)

{

  i = (1LL << 63) - 1;

  printf("%lld %lld\n",i,i+1);

  // i     =  9223372036854775807 = 2 ^ 63 - 1

  // i + 1 = -9223372036854775808 = -2 ^ 63

}

   Пример 2.6.5. Выведем наибольшее значение беззнаковых 32 и 64 – битовых целочисленных типов.

#include< stdio.h >

unsigned int i = -1;

unsigned long long j = -1;

void main(void)

{

  printf("%u %llu\n",i,j);

  // 4294967295 = 2 ^ 32 - 1, 18446744073709551615 = 2 ^ 64 - 1

}

   Пример 2.6.5. Выведем десятичное, двоичное и шестнадцатиричное представление числа 255. Шестнадцатиричное представление чисел можно выводить как прописными (%x), так и заглавными (%X) буквами.

#include< stdio.h >

int i = 255;

void main(void)

{

  printf("%o %d %x %X\n",i,i,i,i);

  // 377 255 ff FF

}

2.7. ОПЕРАТОР ПРИСВАИВАНИЯ

   Как мы уже увидели в разделе 2.5, оператор присваивания в Си имеет вид знака равенства “=”. Язык Си позволяет производить транзитивные присваивания. Например, оператор

a = b = 1;

сначала присвоит переменной b значение 1, а потом переменной a присвоит значение переменной b.

   Пример 2.7.1. Целочисленные переменные a и b содержат некоторые значения. Поменять местами значения переменных a и b.

   Решение. Задачу легко можно решить, используя третью целочисленную переменную t. Последовательность операций, ведущих к решению задачи, имеет вид:

t = a; a = b; b = t;

   Упражнение 2.7.1. Решите задачу из примера 2.7.1, не вводя дополнительных переменных.

2.8. УСЛОВНЫЙ ОПЕРАТОР И ОПЕРАЦИИ СРАВНЕНИЯ

Синтаксис условного оператора:

   if (<условное выражение >) <выражение 1>;

или

   if (<условное выражение >) <выражение 1>; else <выражение 2>;

 

Основные отличия синтаксиса условного оператора от языка программирования Паскаль:

1. Условное выражение всегда берется в круглые скобки, даже если оно имеет простой вид;

2. Отсутствует ключевое слово then;

3. Перед ключевым словом else всегда ставится символ “;”

Операция сравнения в языке Си имеет вид “==” (два знака равенства). Например, проверка равенства значения целочисленной переменной x двойке имеет вид:

if (x == 2) . . .

Операция «меньше или равно» в языке Си имеет вид “<=”.

Операциятор «больше или равно» в языке Си имеет вид “>=”.

Операциятор «не равно» в языке Си имеет вид “!=”.

Словесное выражение

Запись выражения в языке Си

если , то . . .

if (x > 4)  . . .

если , то . . .

if (x >= 4) . . .

если , то . . .

if (x < 6)  . . .

если , то . . .

if (x <= 6) . . .

если , то . . .

if (x == 7) . . .

если , то . . .

if (x != 9) . . .

   Пример 2.8.1. Вычислить значение функции:

algo_lec01_ris05

 

   Пусть аргумент и значение функции являются действительными числами. Программа ввода переменной x, вычисления значения функции y и вывода результата имеет вид:

#include< stdio.h >

double x,y;

void main(void)

{

  scanf("%lf", &x);

  if (x >= 0) y = x + 1; else y = x * x;

  printf("%lf\n", y);

}

   Пример 2.8.2. Вычислить значение функции:

algo_lec01_ris06 

#include< stdio.h >

double x,y;

void main(void)

{

  scanf("%lf", &x);

  if (x < 0) y = x + 1; else

  if (x < 10) y = x * x; else y = x - 4;

  printf("%lf\n", y);

}

   Пример 2.8.3. На вход программы подается одно из целочисленных значений: 0 или 1. Если введен 0, то программа должна вывести 1. Если введена 1, то следует вывести 0. Реализовать такую программу.

   Для реализации программы можно воспользоваться условным оператором:

#include< stdio.h >

int x,y;

void main(void)

{

  scanf("%d",&x);

  if (x == 1) y = 0; else y = 1;

  printf("%d\n",y);

}

   При решении задачи можно обойтись и без условного оператора. Для этого следует заметить, что y = 1 – x. Программа примет вид:

#include< stdio.h >

int x,y;

void main(void)

{

  scanf("%d",&x);

  y = 1 - x;

  printf("%d\n",y);

}

   Упражнение 2.8.1. Вычислить значение функции:

algo_lec01_ris07

 

   Пример 2.8.4. На вход программы подаются три целых числа. Вывести на экран наибольшее число.

#include< stdio.h >

int a, b, c, max;

void main(void)

{

  scanf("%d %d %d",&a,&b,&c);

  if (a > b)

   if (c > a) max = c; else max = a;

  else

    if (c > b) max = c; else max = b;

  printf("%d\n",max);

}

  Упражнение 2.8.2. Найти наименьшее среди трех заданных целых чисел.

УКАЗАНИЯ К РЕШЕНИЮ УПРАЖНЕНИЙ

  Упражнение 2.4.1. Символы, ASCII коды которых равны соответственно 3, 4, 5, 6, невозможно набрать на клавиатуре непосредственно. Это символы мастей карт: "чирва", "бубна", "крест", "пика". Поэтому следует завести переменную c типа char, присвоить ей значение 3, после чего вывести значения c, c + 1, c + 2, c + 3 , используя формат “%c”.

   Упражнение 2.4.2. В задаче достаточно ввести значения двух переменных a и b, найти значение выражения a2 + b2 и вывести его на консоль.

   Упражнение 2.6.1. Знаковые 2 байта: [-215; 215 – 1] = [-32768; 32767], беззнаковые 2 байта: [0; 216 – 1] = [0; 65535]. 

   Упражнение 2.7.1. Для решения задачи следует выполнить следующую последовательность операций:

a = a + b;  b = a – b;  a = a - b;

   Проиллюстрируем выполнение приведенных выше операций в таблице:

a

b

операция

a + b

b

a = a + b

a + b

a

b = ab

b

a

a = ab

   Упражнение 2.8.1. Воспользуйтесь примером 2.8.2.

   Упражнение 2.8.2. Воспользуйтесь примером 2.8.4.