Введение в язык программирования Си

Михаил Медведев

[к списку лекций]

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

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

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

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

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

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

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

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

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

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

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

2.7. Условный оператор.

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). Четыре раза чемпионами мира и соответственно обладателями кубка становились команды из России (icpc.baylor.edu/past/default.htm): Санкт-Петербургский государственный университет (2000, 2001), Санкт-Петербургский институт механики и оптики (2004), Саратовский государственный университет (2006).

Чемпионат мира под эгидой АСМ является командным соревнованием. Трем участникам необходимо решить от 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. ПРОГРАММА "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 в Паскале.

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

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

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

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

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

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

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

int x,y;

char c;

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

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

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

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

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

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

Пример 2.4.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.4.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.4.1. Напишите программу, которая выведет на экран строку из четырех символов, ASCII коды которых соответственно равны 3, 4, 5 и 6.

Пример 2.4.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 библиотеки <iostream.h>. Но они работают значительно медленнее, чем prinf и scanf. Поэтому для выполнения операций ввода-вывода рекомендуется пользоваться библиотекой <stdio.h>.

Пример 2.4.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.4.2. Напишите программу, которая по заданным двум действительным числам a и b находит и выводит значение выражения a2 + b2.

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 2.5.1. Если к макимальному целочисленному значению прибавить 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, объявленные в библиотеке <limits.h>, соостветственно равны наименьшему и наибольшему значению, которое может принимать переменная типа int.

Пример 2.5.2. Выведем значения переменных 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. ОПЕРАТОР ПРИСВАИВАНИЯ

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

a = b = 1;

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

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

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

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

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

2.7. УСЛОВНЫЙ ОПЕРАТОР

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

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

или

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

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

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

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

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

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

if (x == 2) . . .

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

y(x) =

Пусть аргумент и значение функции являются действительными числами. Программа ввода переменной 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.7.2. Вычислить значение функции:

y(x) =

#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.7.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.7.1. Вычислить значение функции:

y(x) =

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

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

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

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

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

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

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

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

[к списку лекций]