13.03.2013 Специална сбирка на школата - среща със студенти от 1 курс, кандидати за състезатели по програмиране

Стандарти на С++, компилатори

Dev-C++ за Windows, gcc за Linux, BSD и др. UNIX-ови ОС
Конзолни приложения, вход и изход

Стандартен вход и изход за езика C++

cin >> <име на променлива>;

Пример: 

int k;
cin >> k;

cout << <име на променлива>;

Пример: 

int ik = -10;
unsigned int uk = 10;
long lk = -1000000;
unsigned long ulk = 1000000; // 16 битов цял тип данни
double dk = 2.52;
cout << ik << " " <<uk << " " << lk << " "
     << ulk<< " " << dk << "\n";

Пренасочване на входа и изхода

Пренасочване на стандартни вход и изход.

Файл с програма на C или C++ със стандартни вход и изход:
prog.exe
Текстов файл с входните данни за програмата:
test1.inp
Изпълнение на програмата:
prog <test1.inp >test1.out
Текстов файл, произведен от програмата при това изпълнение:
test1.out

Пример 1: Сума на две числа

Дадени са две цели числа в интервала [-100, 100].  Напишете програма, която пресмята сумата на числaтa.

#include <iostream>
using namespace std;
int main()
{
        int i, j;
        cin >> i >> j;
        cout << (i+j);    
        return 0;
}

Име на файл с текст на програмата: add.cpp
Име на изпълним файл (Windows): add.exe

Изпълнение на програмата:

C:\my_dir\>add < inp.txt > out.txt

Файл за вход: inp.txt

12
5

Създаден от ОС файл: out.txt

17

Вход и изход за много примери

while (cin >> x) { ...}
while (cin >> x && x > 0) { ... }

int n;
cin >> n;
for (int i = 0; i < n; i++) { cin >> ... }

string st;
getline(cin, st);
Пример 2: Сума на две числа
Дадени са две цели числа в интервала [-100, 100].  Напишете програма, която пресмята сумата на числaтa.

Вход
От стандартния вход се въвеждат много примери. Първото число е броят на примерите, на всеки следващ ред са дадени по две числа за събиране.

Изход
За всеки пример от входа на стандартния изход се извежда едно число - сумата на числата от съответния пример от входа

Пример:
Вход
3
-10 2
20 3
30 4

Изход
-8
23
34

Решение:
// Николай Киров F123456
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int k = 0; k < n; k++)
    {
        int i, j;
        cin >> i >> j;
        cout << (i+j) << endl;
    }    
    return 0;
}
Решението като файл: f123456_0a.cpp
Пример 3: Сума на две числа
Дадени са две числа в интервала [-100, 100].  Напишете програма, която пресмята сумата на числaтa.

Вход
От стандартния вход се въвеждат много примери, на всеки ред са дадени по две числа за събиране.

Изход
За всеки пример от входа на стандартния изход се извежда едно число - сумата на числата от съответния пример от входа

Пример:
Вход
-10 2
20 3
30 4

Изход
-8
23
34

Решение:
// Николай Киров F123456
#include <iostream>
using namespace std;

int main()
{
    int i, j;
    while(cin >> i >> j) cout << (i+j) << endl;
    return 0;
}
Пример 4: Сума на две числа
Дадени са две цели числа в интервала [-10100, 10100].  Напишете програма, която пресмята сумата на числaтa.

Вход
От стандартния вход се въвеждат много примери, на всеки ред са дадени по две числа за събиране.

Изход
За всеки пример от входа на стандартния изход се извежда едно число - сумата на числата от съответния пример от входа

Пример:
Вход
-100000000000000000000000000 1
200000000000000000000000000000000000000 -200000000000000000000000000000000000000

Изход
-999999999999999999999999999
0

Решение:
// Николай Киров F123456
#include <iostream>
#include <string>
using namespace std;

string sum(string s1, string s2)
{
    ......
}

int main()
{
    string i, j;
    while(cin >> i >> j) cout << sum(i, j) << endl;
    return 0;
}
Нека разгледаме следния програмен фрагмент:

cin >> n;
sum = 0;
for (i=0; i<n; i++)
 for (j=0; j<n; j++) sum++;
 

Колко бързо ще работи горната програма, т.е. какви са критериите по които се определя бързината й? Това, което можем да направим експериментално е да проверим за колко време ще се изпълни и ще завърши работата си. За да изследваме по-общо нейното поведение е възможно да я изпълним за други стойности на n.

Резултатите от последното са обобщени в следната таблица:
Размер на входа
n 		Време за изпълнение
сек.
10 10-6
100 10-4
1000 0.01
104 1.071
106 106.5
108 10663.6
От таблицата се вижда, че когато увеличаваме n (размерността на входа)10 пъти, времето за изпълнение се увеличава 100 пъти.
Времето за изпълнение е пророрционално на  f (n) = c1n2 + c2n+ c3, където c1, c2, c3 са константи, които могат да се определят от дадената част от програмата.
 
Сравняване на двете функции f (n)= 2n2 и g(n)= 200n, които показват времето за изпълнение на два дадени алгоритъма А1 и A2, в зависимост от n. 
 
 

Асимптотично алгоритъмът A2 е по-бърз и неговата сложност е линейна, докато тази на A1 е квадратична.
n f (n) g(n)
1 2 200
10 200 2000
100 2.104 2.104
1000 2.106 2.105
104 2.108 2.106
106 2.1012 2.108

 Размер на входните данни

    Нека е дадена задача, в която размерът на входните данни е определен от дадено цяло число n. Почти всички задачи, които ще разглеждаме, притежават това свойство. Ще поясним последното като разгледаме няколко примера:

Пример 1.
Да се сортира масив с n елемента.
Размерът на входните данни се определя от броя n на елементите на масива .

Пример 2.
Да се намери най-големият общ делител на a и b.
В този пример размерът на входните данни се определя от броя на двоичните цифри (битовете) на по-голямото от числата a и b.

Пример 3.
Да се намери покриващо дърво на граф.
В този случай характеризираме размера на входа с две числа: брой на върховете и брой на ребрата.

Асимптотична нотация

    Когато се интересуваме от сложността на алгоритъм най-често се интересуваме как ще работи при достатъчно голям размер n на входните данни. При формалното оценяване на сложността на алгоритмите изследваме поведението им при "достатъчно голямо" n, т.е. клонящо към безкрайност.

1. O(F) определя множеството от всички функции  f, които нарастват не по-бързо от F, т.е. съществува константа c > 0 такава, че f (n) <= cF(n), за всички достатъчно големи стойности на n.

Нарастване на най-често използваните функции:

Функция / n
1
2
10
100
1000
5
5
5
5
5
5
log n
0
1
3.32
6.64
9.96
n
1
2
10
100
1000
n log n
0
2
33.2
664
9996
n2
1
4
100
104
106
n3
1
8
1000
106
109
2n
2
4
1024
1030
10300
n!
1
2
3628800
10157
102567
nn
1
4
1010
10200
103000

Определяне на сложност на алгоритъм:
- елементарна операция - не зависи от размера на обработваните данни - O(1) ;
- последователност от оператори - определя се от асимтотично най-бавния -  f + g ~ max(O( f ), O(g));
- композиция на оператори - произведение от сложностите - f  g ~ O( f g);
- условни оператори - определя се от асимтотично най-бавния между условието и различните случаи;
- цикли, вложени цикли - O(n), O(np) .

Оценка на сложността на следните цикли (колко пъти ще се изпълни цикъла в най-лошия случай):

// 1
for (i = 0; i < n; i++)
 for (j = 0; j < n; j++, sum++);
// 2
for (i = 0; i < n; i++)
 for (j = 0; j < n; j++) if (a[i] == b[j]) return;
// 3
for (i = 0; i < n; i++)
 for (j = 0; j < n; j++) if (a[i] != b[j]) return;
// 4
for (i = 0; i < n; i++)
 for (j = 0; j < n; j++) if (a[i] == a[j]) return;
// 5
for (i = 0; i < n; i++)
 for (j = 0; j < i; j++) sum++;
// 6
for (i = 0; i < n; i++)
 for (j = 0; j < n*n; j++) sum++;
// 7
for (i = 0; i < n; i++)
 for (j = 0; j < i*i; j++) sum++;
// 8
for (i = 0; i < n; i++)
 for (j = 0; j < i*i; j++)
   for (k = 0; k < j*j; k++) sum++;

  • транзитивност: ако f ~ О(g), g ~ О(h), то  f ~ О(h);
  • константите могат да бъдат игнорирани: за всяко k > 0, kF ~ О(F);
  • n, повдигнато в по-висока степен, нараства по-бързо: nr~ О(ns), за 0 < r < s.
  • нарастването на сума от функции се определя от най-бързо нарастващата от тях: f + g ~ max(O( f ), O(g));
  • ако f(n) е полином от степен d, то f ~ О(nd);
  • ако f нараства по-бързо от g, а g нараства по-бързо от h, то следва, че f нараства по-бързо от h.
    • Задача за домашно:

    Кредитни карти

    Петър и Павел написали програма за генериране на номера на кредитни карти, но не били сигурни дали работи вярно. Напишете програма, която проверява дали резултатът от програмата на Петър и Павел е валиден номер на кредитна карта VISA или MasterCard.

    Номерата на кредитните карти са 16-цифрени, разделени на групи от по 4 цифри, като всяка група е разделена от съседните й с тире. Проверката за валидност на картата се извършва по следния алгоритъм:

    1. Цифрите на номера се вземат в обратен ред и се премахват тиретата;

    2. Цифрите, стоящи на четни места се удвояват. Ако след удвояване на цифра се получи 2-цифрено число, то цифрата се замества с двете цифри на числото;

    3. Намира се сбора на всички получени цифри;

    4. Ако полученият сбор се дели на 10 без остатък, то номерът на картата е валиден. Ако номерът започва с 4, то типът й е VISA, а ако има префикс от 51 до 55 е MasterCard.

    Вход

    От стандартния вход се прочита цяло число k – броя номера на кредитни карти, които трябва да бъдат проверени. От всеки от следващите редове се прочита по един номер на карта.

    Изход

    За всеки един от номерата програмата трябва да изведе на отделен ред на стандартния изход  VISA, ако това е валиден номер на VISA карта, MasterCard –  ако е валиден номер на  Master Card, YES – ако е валиден номер, който не е нито VISA, нито Master Card и NO –  ако не е валиден номер на карта.

    Пример

    Вход

    Изход

    3

    4204-5876-9012-5234

    5173-1249-4804-2492

    8699-3855-7635-7380

    VISA

    MasterCard

    NO


    Изпратете текст на програмата (.cpp файл) на: nkirov<at>nbu.bg