Первое по С++: линейные алгоритмы.

Немного теории.

Перед тем, как приступить к самой интересной части – созданию наших первых программ, нам нужно усвоить несколько базовый понятий. Убедись, что все термины тебе понятны.

Алгоритм – конечная последовательность действий, которая приводит к решению поставленной задачи.

Как это ни удивительно, из определения алгоритма следует важная идея: алгоритм всегда должен иметь конец. Принцип работы котобутербродного генератора алгоритмом не является.

Алгоритм можно задать несколькими способами, например:

  • Словами
  • Блок-схемой
  • Программой на языке программирования

Блок-схема – графическое представление алгоритма.

В блок схеме мы можем использовать блоки ввода и вывода для общения с внешним миром и универсальный блок для совершения каких либо действий. Если же нам надо задать в программе закрытый вопрос, нам понадобится уловный оператор.

Блок схема составляется из нескольких типов блоков.

Начало — каждая блок схема должна начинаться с такого блока
Блок ввода — попросить у пользователя ввести что либо с клавиатуры. В данном случае ввести a и b с клавиатуры.
Блок вывода — вывести что либо на экран. В данном случае вывести hello world.
Универсальный блок — любая работа с данными, вызов функций и тд. В данном случае прибавить к a 10.
Условный оператор. В данном случае мы узнаем, что больше a или b. В отличие от всех остальных блоков имеет два выхода(не больше т.к. условие — общий вопрос, а на можно ответить только да или нет — каждому ответу свой выход.)
Конец

 

Допустим у нас есть клетчатое поле 8*8, в центре стоит ладья, который понимает команды вперед, назад, вправо, влево. Каждая команда приводит к перемещению в соответствующую сторону. Допустим нам надо попасть в следующую точку:

Задача: Решение:

 

Допустим у нас есть следующая задача: с клавиатуры вводиться число, если оно меньше 12 вывести «Goodnight world», иначе «Hello world».

Как тебе, скорее всего, когда-то говорили в школе на уроках информатики, данные внутри компьютера существуют только в виде нулей и единиц — машинных кодов. А значит и команды компьютеру надо давать тоже в двоичном формате.

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

Хотя существуют и более подробные определения:

Программирование — процесс и искусство создания компьютерных программ и/или программного обеспечения с помощью языков программирования. Программирование сочетает в себе элементы искусства, фундаментальных наук (прежде всего информатика и математика), инженерии, спорта и ремесла.

Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия, которые выполнит исполнитель (компьютер) под ее управлением.

Выделяют два вида языков программирования: интерпретируемые и компилируемые. Давай разберемся, в чем их различия. Допустим у нас есть программа: Вася сходи в магазин и купи хлеба. Вся проблема в том, что наш любимый компьютер понимает только единицы  и нули, а значит слова для него — пустой звук) Значит нам необходимо как то преобразовать в эти самые единицы и нули. Вот тут и возникаем различие.

  1. Интерпретируемый язык. На компьютере у пользователя установлена программа — интерпретатор. Ты даешь ей файл с командами для нашего любимого Васи, после чего интерпретатор читает, что его попросили и самостоятельно выполняет нужные команды. Ну грубо говоря ты попросил некоторого дядю Степу и он хорошенько пнул доходчиво объяснил Васе, что ему делать. В данном случае ключевой момент состоит в том, что на компьютере и конечного пользователя должен стоять этот самый интерпретатор, и без него ничего работать не будет. По такой технологии работают например макросы в Microsoft Office или например интернет сайты(VB, PHP, ASP.NET…)
  2. Компилируемый язык. Тут дело обстоит несколько иначе. Мы набираем программу на понятном нам языке и отправляем ее в компилятор. Компилятор превратит наш код во что то типа 11001000100100101100… и на выходе выдаст нам, я надеюсь знакомый всем, .exe файлик. Такую программу(окончательно превращенную в машинный код) уже можно использовать на любом компьютере. По такой технологии сделаны наверное все встречающиеся нам программы(С, C++, C#, Delphi…).

Компилятор – программа, преобразующая код с языка программирования, на язык понятный компьютеру — машинный код.

Компьютер — это устройство для обработки данных. За расчеты в нем отвечает процессор (CPU), а обрабатываемая в данный момент информация хранится в оперативной памяти (RAM). С точки программиста оперативная память разделяется на именованные ячейки предназначенные для хранения информации различного типа и размера — чисел, символов и тд.

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

Вполне возможно, ты уже успел встретиться с переменными на уроках математики. Скорей всего это были x, y, v, обозначавшие некоторую неизвестную величину. В программировании все немного по-другому. Во-первых, наши переменные – прежде всего ячейки в памяти, а не изменяющиеся значения. Во-вторых, в математике переменные могли принимать только различные числовые значения, а мы будем работать с разными типами данных.

Возникает вопрос: что такое тип данных? Дело в том, что С++ – язык со строгой типизацией. Это значит, что данный язык позволяет выделять переменные для чисел, символов, ссылок и т.д. В числовую переменную нельзя положить символ, а в символьную — число.

Как наглядно представить переменную? Представь себе большой склад с большим количеством полок. На каждой полке стоят коробки. У каждой коробки есть свое имя, что рабочие на складе могли быстро найти ее содержимое. Так вот это коробка, в которой мы можем что-то хранить – переменная, а склад – оперативная память компьютера. Причем на полках также могут стоять банки, пакеты и другие сосуды. Если нам нужно будет хранить некоторое количество варенья, мы не сможем налить его в коробку, мы нальем его в банку. Также и числа можно класть только в числовые переменные, а символы – в символьные. Чуть позже мы поговорим об этом подробней.

Как решать задачи?

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

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

Как решать задачку по программированию?

  1. Придумать алгоритм.
  2. Составить блок схему.
  3. Реализовать на языке программирования.
  4. Проверить на своих тестах и тестах из условия.

Ну а сейчас мы наконец-то приступим к практике!

Привет, мир!

Итак, твоя первая задача: вывести на экран фразу «Hello, world!».

В нашей блок схеме будет всего один блок вывода. Должно получиться вот так:

А теперь самое интересное – наша первая программа.

Сначала нам нужно скачать среду разработки с компилятором. Мы будем использовать Microsoft Visual Studio Community.

 

С установкой, я думаю, ты справишься самостоятельно – все настройки оставляем нетронутыми.

Для создания нового проекта выбери «File»->»New Project»->Visual C++ (Слева) -> Консольное приложение Win32.

Теперь нажми на кнопку [Ctrl+F5] , и посмотри, что получится!

Mission completed! =)

Ты только что скомпилировал и запустил свою первую программу! А теперь давай разбираться, что же там написано.

Первое время все наши программы будут начинаться и заканчиваться одинаково – так, как показано на рисунке. Мы уже рассматривали этот вопрос в методичке.

Команда cout<<”Hello world!” выводит текст «Hello world!» на экран.

Кстати, можно писать сразу много стрелочек, и это будет работать.

сout << ”Hello” << ” ” << ”world” << ”!” <<endl; — выведет абсолютно то же самое. Выводы ты можешь сделать сам =).

А вот то, что идет дальше, уже ново для тебя.

endl — перенос строки, он пишется без кавычек.

endl и “n” –  одно и то же, но первое иногда писать быстрее.

 

Быть или не быть?

Ну а теперь решим задачку посложнее:

С клавиатуры вводится два числа, вывести наибольшее.

Ввод Вывод
3 5 5
-100500 9001 9001

 

Поехали! Итак, нам нужно сначала ввести два числа с клавиатуры. Когда мы используем какие-то данные, нам надо их где то хранить. Где мы будем хранить введенные числа? Конечно же, в переменных. Например, мы введем переменные a и b. На самом деле, ты можешь придумать любое английское название (главное чтобы оно начиналась с буквы или символа подчеркивания «_», и не содержало служебных символов), например, cat1 и dog_34, но в данном примере это нас только запутает.

Второй вопрос: как ввести числа? Для этого нам нужен блок ввода! В него мы пишем названия переменных, которые мы хотим попросить пользователя ввести.

Третий вопрос: что надо сделать с числами, чтобы узнать, какое из них больше. В условном операторе мы можем задать только закрытый вопрос (ответ на него «да» или «нет»), а значит, нам надо задать вопрос немного по-другому: a больше b?  Если записать математически: a>b?

Осталось только взять листочек в клеточку, и аккуратно все это нарисовать. Должно получиться вот так:

 

Теперь как же это реализовать? Ты уже знаешь, как использовать блок ввода и блок вывода из методички, а вот блок условия мы еще не проходили.

Он записывается вот так:

 

if (условие)
{
   //код для положительного ответа (+)
}
else
{
   //код для отрицательного ответа (-)
}

 

Причем, если бы наша блок схема выглядела вот так:

Блок else можно бы было не писать:

if (условие)
{
  //код для положительного ответа (+)
}

Так тоже будет работать =).

Вдобавок, если надо совершить только одно действие, то можно обойтись и без фигурных скобок:

if (условие)
  //код для положительного ответа (+)

Теперь наша задача — применить полученные знания. Сначала давай запишем стандартную структуру программы:

#include <iostream>

using namespace std;

int main () {
    //тут будет наш код
    return 0;
}

Теперь нам надо ввести два числа в переменные a и b. А вот тут возникает отличие: если в блок схеме мы просто написали «ввести a и b», то компьютеру надо сначала сказать, что нам такие переменные понадобятся, то есть определить их. Это все равно, что забронировать место на складе, прежде чем использовать его.

Для этого мы напишем вот так:

#include <iostream>

using namespace std;

int main () {
   int a; 
   int b;
   //int a, b; - тоже будет работать.
   //тут будет наш код
   return 0;
}

Здесь int – название типа данных, который может хранить целые числа от -2147483648 до 2147483647, а a и b – имена переменных.

Имена переменных в с++ могут состоять из латинских букв, цифр и символа _, но всегда должны начинаться с буквы!

Более подробно мы поговорим о типах данных чуть позже.

И так теперь у нас есть место на «складе», то есть в оперативной памяти компьютера (если быть совсем точным, когда программа запустится, процессор сразу выделит нам место в оперативной памяти). Теперь надо ввести значения с клавиатуры. Как ты уже знаешь из вступительной методички, для этого нам понадобится команда cin:

#include "stdafx.h"
#include <iostream>

using namespace std;

int main () {
   int a; 
   int b;
   cin >> a;
   cin >> b;

   //cin >> a >> b; - тоже будет работать, как и в случае с cout.
   //тут будет наш код

   return 0;
}

Осталось вставить условный оператор:

#include "stdafx.h"
#include <iostream>

using namespace std;

int main () {
   int a, b;
   cin >> a >> b;
   if (a > b)
   {
       //здесь находится код для + ветки
       cout << a;
   }
   else 
   {
       //здесь находится код для - ветки
       cout << b;
   }
   return 0;
}

Все готово, нажимай [F9]! Когда ты введешь два числа (через пробел, или нажимая enter после каждого), компьютер выведет наибольшее.

Теперь твои знания позволяют тебе самостоятельно решать некоторые задачи.

Условия в условном операторе.

Что можно писать в блоке условия, кроме знака больше для сравнения переменных? Все операции сравнения!

a > b  //a больше b
a >= b //больше либо равно
a < b  //меньше
a <= b //меньше или равно
a == b // равно! не путай с = - оператором присваивания
a != b // не равно

Иногда нужно, чтобы выполнялось сразу два условия. Например, в математике мы можем написать a > b > c, а в с++ так, к сожалению, нельзя 🙁 . Ничего страшного, специально для этого в С++ можно использовать логические операторы: И, ИЛИ и НЕ.

a > b && a > c //a > b и a > c
a > b || a > c //a > b или a > c
!(a < b) // НЕ (a < b), это то же самое, что a >= b =)

Работа с переменными.

С целочисленными переменными (int) можно делать все тоже самое, что и с обычными числами, а в частности:

  • складывать
  • вычитать
  • целочислено делить
  • умножать
  • делить с остатком
int a = 10;
int b = 20;
a = a + 5;  //a = 15
a = a + b;  //a = 35
a = a - 20; //a = 15
a = a * 2;  //a = 30
a = b / 2;  // a = 10
b = a % 3;  // b = 1, этот оператор возвращает остаток от деления, очень удобная штука

Сокращенная запись операций с переменными (*).

Если мы что-то делаем с переменной, и в нее же кладем результат, то это можно записать короче:

a += 5; // a = a + 5;
a -= 2; // a = a - 2;
a *= 3; // a = a * 3;
a /= 8; // a = a / 8;
a %= 4; // a = a % 4 - остаток от деления a на 4 =)

i++; // i = i + 1;
++i; // тоже самое, о разнице чуть позже =)
i--; // i = i - 1; 
--i; // и опять тоже самое =)

Калькулятор в консоли.

Поставим следующую задачу: нам необходимо сделать калькулятор. С клавиатуры вводится три числа: первое – номер действия (1 – сложение, 2  — вычитание, 3 – умножение, 4- деление) следующие два – сами числа. Чтобы понять логику данной программы, для начала нарисуем блок-схему. Она должна выглядеть примерно следующим образом:

Как мы видим в блок-схеме у нас четыре условных оператора (это логично, т.к. у нас четыре варианта действий), причем слева ни в одном случае у нас не стоит ни одного оператора,а значит else нам вообще не понадобиться. Ну что ж, за дело =)

#include "stdafx.h"
#include <iostream>

using namespace std;

int main () {
   int a, b, c;
   cin >> a >> b >> c;
   if (a == 1) { 
     cout << (b + c);
   }
   if (a == 2) {
     cout << (b - c);
   }
   if (a == 3) { 
     cout << (b * c);
   }
   if (a == 4) {
     cout << (b / c);
   }
   return 0;
}

Кстати, как ты думаешь, что выведет программа, если мы попросим: раздели 5 на 2? Попробуй 🙂
Ответ скорей всего получился не совсем такой, как ты хотел. О том, почему так получилось, мы поговорим на следущих занятиях! =)

Множественный выбор (switch)

Чтобы избежать вот такой мешанины условных операторов (спагетти) из сравнений одной переменной с несколькими значениями используют команду switch. Она позволяет более красиво организовать код, в котором одна переменная сравнивается со многими значениями:

switch( переменная ) {
  case значение_1:
    // код 1
  break;
  case значение_2:
    // код 2...
  break;
   // .....
  case значение_N:
    // код N...
  break;
  default: // Если ни одно значение не подошло :(
    // код...
  break;
}

Её использование необязательно, однако ее очень удобно применять для таких случаев.
Давайте перепишем программу с ее использованием:

#include "stdafx.h"
#include <iostream>

using namespace std;

int main () {
   int a, b, c;
   cin >> a >> b >> c;
   switch (a) {
     case 1: cout << (b + c); break;
     case 2: cout << (b - c); break;
     case 3: cout << (b * c); break;
     case 4: cout << (b / c); break;
   }
   return 0;
}

Действительно, switch явно выделяет цифры, с которыми производится сравнение. Такой код действительно проще, легче для понимания человеком, а это — ключевой момент для написания реальных больших проектов.

Немного этикета.

Теперь поговорим о правилах оформления кода.

  1. Одна инструкция – одна строка.
  2. Каждая фигурная скобочка – на отдельной строке.
  3. Чем больше вложенность (чем больше фигурных скобочек) – тем больше отступ в каждом блоке, чтобы было сразу видно, что к чему относиться.

Зачем это надо? Ведь даже если написать код в одну строку, MinGW все равно его скомпилирует! Но если я дам тебе пример в таком формате, тебе вряд ли будет понятно:

#include "stdafx.h"
#include <iostream>
using namespace std;int main(){int a,b;cin>>a;cin>>b;if(a>b)cout<<a;else{;cout<<b;}return 0;}

Не волнуйся, codeblocks при наборе автоматически будет ставить красивые отступы, главное ему не мешать 🙂 .

Задачи для самостоятельного решения.

Для каждой задачи нужно сначала нарисовать блок-схему, а только затем написать код на компьютере. Блок-схему можно делать на бумаге, либо с помощью компьютера (например, в программе Dia).

Готовые задачи и блок схемы надо выслать на dist@dnttm.ru. Не забудь указать имя и фамилию! 🙂

Любые вопросы ты можешь задавать нам по почте, либо в скайпе или контакте. Наши контакты указаны в разделе «Дистанционные курс по C++» на program-school.ru.

Также у нас есть группа ВК для учеников первого года С++ — vk.com/clubpsc1

Результаты и рейтинг публикуются на странице «Успеваемость».

Удачи! =)

0.1.      Написать программу, которая выводит на экран ваше имя и фамилию (2 балла).

Ввод Вывод
Вася Пупкин

 

0.2. Написать программу, которая выводит на экран стихотворение (3 балла).

Ввод Вывод
Белеет парус одинокой
В тумане моря голубом!
Что ищет он в стране далекой?
Что кинул он в краю родном?Играют волны — ветер свищет,
И мачта гнется и скрипит…
Увы! он счастия не ищет,
И не от счастия бежит!Под ним струя светлей лазури,
Над ним луч солнца золотой…
А он, мятежный, просит бури,
Как будто в бурях есть покой!

 

0.3. Написать программу вычисления площади прямоугольника (5 баллов).

Ввод Вывод
Вычисление площади прямоугольника
Введите исходные данные:
Длина (см) -> 30
Ширина (см) -> 2
Площадь прямоугольника: 60  кв.см.
Вычисление площади прямоугольника
Введите исходные данные:
Длина (см) -> 5
Ширина (см) -> 23
Площадь прямоугольника: 115  кв.см.
Вычисление площади прямоугольника
Введите исходные данные:
Длина (см) -> -100
Ширина (см) -> 500
Недопустимые данные

 

0.4. Написать программу вычисления стоимости некоторого количества (по весу) яблок (5 баллов).

Ввод Вывод
Вычисление стоимости яблок.
Введите исходные данные:
Цена одного килограмма яблок (руб.) -> 25
Вес яблок (кг) -> 4
Стоимость покупки: 100 руб.
Вычисление стоимости яблок.
Введите исходные данные:
Цена одного килограмма яблок (руб.) -> -25
Вес яблок (кг) -> 4
Недопустимые данные

 

1.1.6. Три числа вводятся с клавиатуры, вывести на экран максимальное и минимальное из этих чисел (5 баллов).

1.1.7. Три числа вводятся с клавиатуры вывести на экран наибольшее из положительных чисел и наименьшее из отрицательных (5 баллов).

1.1.8. С клавиатуры вводится 4 числа. Вывести на экран сумму двух наименьших (5 баллов).

1.1.2. Поменять местами значения двух переменных с использованием третьей переменной (5 баллов).

Ввод Вывод
100 4 4 100
-23 1 1 -23
1.1.9. (*)Поменять местами значения двух переменных без использования третьей переменной (10 баллов).
Ввод Вывод
100 4 4 100
-23 1 1 -23

Сложная задача.

Такие задачи решать не обязательно, но за их решение мы будем начислять дополнительные баллы. Блок-схему для них рисовать не обязательно.

1.2.0 (**). Космический путешественник.

Рассмотрим прямоугольную декартову систему координат OXY (будем считать ее моделью Вселенной). Предположим, что в точке (x1, y1) находится космический корабль. За одну секунду из точки (x, y) он может телепортироваться в точки (x + C, y + C), (x + C, y – C), (x – C, y + C), (x – C, y – C), где C — произвольное натуральное число. Какое минимальное время понадобится кораблю для того, чтобы достичь точки (x2, y2)?

Формат входных данных

Во входном файле находятся координаты пункта отправления и пункта назначения x1, y1, x2, y2 — целые числа, по модулю не превосходящие 109.

Формат выходных данных

Если возможно достичь точку (x2, y2) из точки (x1, y1), то выведите минимальное время в секундах, необходимое для этого. В противном случае выведите число 0.

Примеры

Входные данные Выходные данные
0 0
0 2
2

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *