24.09.2014

1. Етапи розв’язування задач

Задача 1. Перелити рідини з одного стакана в інший (Переставити змінні місцями).

2. Алгоритм: властивості, способи подання, примітиви, псевдокод.

3. Теорія розв’язку задач (Дж. Поліа, 1945)

Задача 2. Людина А хоче визначити вік трьох дітей людини В. Відомо що добуток віку рівний 36 та сума віку. А сказав, що даних недостатньо. В повідомив, що старша дитина грає на піаніно. Тоді А назвав вік дітей.

Задача 3.

 A,B,C, D зробили прогнози:

- A – сказав, що переможе В

- B – сказав, що D буде останнім;

- C - сказав, що учасник А буде третім;

- D - сказав, що збудеться передбачення А.

Один прогноз вірний і це прогноз перемржця.

Задача 4.

1. Знайдіть алгоритм розв’язку задачі і дайте відповідь на запитання.

а) Для заданого додатного числа n знайдіть таку комбінацію цілих додатніх чисел, добуток яких максимальний серед всіх можливих комбінацій цілих додатних чисел, сума яких рівна n. Наприклад, якщо n рівне 4, то шуканий список є (2,2), так як 2*2 більше, ніж 1*1*1*1, 2*1*1 і 3*1. Для n, рівного 5, шукана комбінація буде (2, 3).

б) Яка шукана комбінація для n=2001?

в) Поясніть, як вам вдалось розв’язати задачу.

4. Алгоритмічні структури.

- слідування - послідовний ;

- розгалуження – умовний;

- цикл – повторення;

- підпрограми – під задачі;

- послідовного пошук;

поки (шукане значення ≠ значення яке перевіряється і є ще не перевірені елементи)  вибрати наступний елемент, який перевіряється;

якщо шукане значення = перевіреному значенню то Шуканий елемент знайдено  інакше Шуканий елемент  не знайдено;

- рекурсивний пошук;

Вибрати сер. елемент  m=(L+R)/2;

                    якщо  шуканий елемент < за середній елемент  то  продовжити пошук(L,m-1) в лівій частині інакше  продовжити пошук(m+1, R) в правій частині

5. Ефективність і правильність алгоритму k, n^k. nⁿ, n!, log_k n.

6. Мови програмування

7. Лексеми

- алфавіт

- службові слова

- ідентифікатор

- тип даних

- синтаксис

- семантика

- присвоєння

- керуючі оператори

- процедури та функції

8. Середовище реалізації

- трансляція

- компіляція

- інтерпретація

9. Порядок роботи

1. Встановити Visual С++ Express www.microsoft.com/express/vc/.
2. Запустити середовище Головне меню\Програми\Visual C++ 9.0 Express Edition\Microsoft Visual C++ 2008 Express Edition.
3. Створити новий пустий проект «Консольний додаток Win32», який зберігати в власну папку(*.sln).
4. Створити файл вихідного коду (*.cpp)
5. Перевірити програми з додатку.

Зауваження

Для компіляції та виконання натискуйте клавішу Ctrl F5

// Під'єднання модулів

#include <iostream>//організація введення-виведення в мові програмування C++

#include <math.h>//виконання простих математичних операцій

using namespace std;// звернення до об'єктів напряму

int main()

{

int a,b; //опис цілих

float c; //опис дійсних

cin>>a>>b;//ведення даних

c=a/b;

cout<<c<<”\n”;//виведнння даних

}

11. Типи величин, вираз, операції, функції

Типи величин

int a;

float b=float(a)/3;

#include "iostream"

using namespace std;

int a,b;

int main()

{

//ifstream cin("input.txt");

//ofstream cout("output.txt");

float a;

cin>>a;

cout.precision(2);

cout<<fixed<<a<<endl; //"\n"

return 0;

}

Операції

Функції

#include "iostream"

#include "math.h"

using namespace std;

int main()

{

double f;

f=-5.5; cout<<abs(f)<<endl;//5.5

f=-5.5; cout<<fabs(f)<<endl;//5.5

f=5.8; cout<<floor(f)<<endl;//5

f=5.8; cout<<ceil(f)<<endl;//6

f=9.0; cout<<sqrt(f)<<endl;//3

f=5; cout<<pow(f,2)<<endl;//25

f=5.5; cout<<fmod(f,2)<<endl;//1.5

f=17.25;double p,y;y=modf(f,&p); f=5.2; cout<<y<<" "<<p<<endl;//0.25  17

return 0;}

Структура програми

#include "iostream"

#include <math.h>

using namespace std;

int main()

{

cout <<"Okey";

return 0;

}

12. Слідування

1. Два  резистори  R₁  і  R₂  з'єднані паралельно. Визначити сумарний  опір за формулою .

2.     Обчислити  відстань  між двома точками з координатами X₁,Y₁ і X₂,Y₂  за формулою L=

#include "iostream"

#include <math.h>

using namespace std;

int main()

{

float x1,y1,x2,y2;

cin>>x1>>y1>>x2>>y2;

float l=sqrt(pow((x1-x2),2)+pow(y1-y2,2));

cout<<("L="<<l<<endl;

}

3.   В  рядку  S  символів,  на  сторінці  R рядків. Скільки символів в книжці, у якої N сторінок?

За скільки хвилин учень прочитає книгу, якщо він одну сторінку читає за T хвилин?

#include "iostream"

using namespace std;

int main()

{int s,r,n,t;

cin>>s>>r>>n>> t;

int a=s*r*n;

cout<<"A=”<<a<<”\n;

int b=a/t;

cout<<"B=”<<b<<”\n;

int g,h;

g=b/60; h=b%60;

cout<<g<<”:”<<h;

}

4. Скільки  лампочок потрібно, щоб освітити вулицю довжиною D км, як­­­ що стовпи з ліхтарями стоять на відстані V м?

5. Одна  серія фільму по телевізору триває F хв. Скільки часу в годи­­нах необхідно, щоб переглянути N серій?

13. Розгалуження

Операції порівняння

<, >. <=,>=, !=, ==

Логічні операції

&&, ||, !!

Умовний оператор

if (умова)  команда 1; else команда 2;

6. Знайти максимальне значення серед двох чисел введених з клавіатури.

#include "iostream"

using namespace std;

int main()

{

int a,b,max;

cin>>a>>b;

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

court<<max<<endl;

}

7. Знайти максимальне значення серед трьох чисел введених з клавіатури.

#include "iostream"

using namespace std;

int main()

{

int a,b,c,max;

cin>>a>>b>>c;

if (a>=b && a>=c) max=a;

if (b>=a && b>=c) max=b;

if (c>=a && c>=b) max=c;

cout<<max<<endl;

}

8. Введене число перевірити: додатне, від'ємне чи дорівнює нулю.

9. Напишіть програму перевірки знання додавання трьох введених чисел.

10.Введене число перевірити: менше, більше чи дорівнює воно 100.

11. Перевірити, чи існує трикутник із сторонами A, B, C.

14. Цикл

З параметром

for (i=1;i<=n;i++) {блок операторів};

З перед умовою

while (умова){блок операторів};

Після умовою

do {блок операторів}

while (умова);

12.Скласти програму виведення на екран квадратiв всiх натуральних чисел менших за 20.

#include "iostream"

using namespace std;

int main()

{for (int i=1;i<20;i++) cout<<i<<”*”<<i<<”=”<<,i*i;

}

13. Скласти програму знаходження суми всiх чисел кратних  трьом  з  вiдрiзка [n,50].

#include "iostream"

using namespace std;

int main()

{int n; cin>>n;

int i=48; int s=0;

while (i>=n)

{s+=i;

i-=3;}

cout<<s<<endl;

}

14. Протабулювати функцію f(x)=cos(2x) на проміжку [a,b] розбитого на n проміжків.

#include "iostream"

using namespace std;

int main()

{

const a=0, b=10, n=10;

float h=(b-a)/n;

float x=a;

float y;

while (x<=b)

{ y=cos(2*x);

cin<<x<< “   “<<y;

x=x+h;}

}

15. Написати таблицю переведення температури з градусів  по  шкалі Цельсія (С) в градуси шкали Фаренгейта (F) за формулою F=1.8*C+32  для значень від 10 до 20 градусів з кроком 2 градуси.

16. Написати таблицю переведення радіуса в площу круга для  значень  радіуса від 1 до 18 В кроком 2.

15. Масиви

17. Дано лінійну таблицю  із  n  цілих  чисел.  Знайти  суму  S  всіх елементів.

#include "iostream"

using namespace std;

int main()

{

int a[100];

int i,n,s;

cin>>n;

for (i=1;i<=n;i++){cin>> a[i];}

s=0;

for (i=1;i<=n;i++) s=s+a[i];

cout<<s;

}

18. З масиву стерти K-тий елемент.

#include "iostream"

using namespace std;

int main()

{

int a[100];

int i,n,k,s;

cin>>n;

for (i=1;i<=n;i++) cin>>a[i];

cin>>k;

for (i=k;i<=n;i++) a[i]=a[i+1];

n--;

for (i=1;i<=n;i++) cout<<a[i]<<” “;

}

19. В масив вставити елемент на К-те місце

20. В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати  програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.

21. Скласти програму підрахунку суми елементів з непарними номерами  масиву A[1..25].

22. Задано таблиця A[1..N]. Побудувати таблицю  B[1..N],  в  якій  першими розміщені всі від`ємні елементи таблиці A, а потім всі додатні.

23. Дано натуральна таблиця A[1..10]. В таблицю М записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2.

24. Заданий одномірний числовий масив. Визначити суму добутків  всіх  пар  сусідніх чисел.

25. Дано масив A[1..M]. Скласти програму перестановки місцями елементів з  парними та непарними номерами.

26. Скласти програму запису в таблицю квадратів чисел від 1 до 100.

27. Скласти  програму  підрахунку  кількості  мінімальних  елементів  в масиві A[1..N].

28.В одномірному числовому масиві всі від`ємні елементи замініть  нуля ми.

29. Перевірити, чи є одномірний числовий масив упорядкованим по зростанню.

16. Робота з файлами

#include "iostream"

using namespace std;

int main()

{

ifstream inp;inp.open("input.dat");

int a,b,c;

inp>>a>>b;

inp.close();

c=a+b;

ofstream out;out.open("output.sol");

out<<c;

out.close();

}

www.e-olimp.com.ua

1. Розклад трицифрового числа

   Розкласти дане трицифрове число на цифри.

Технічні умови

   Вхідні дані

   У єдиному рядку задано трицифрове ціле число.

   Вихідні дані

   Вивести кожну цифру з нового рядка. Порядок виведення наведено у прикладі.

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 2
Складність: 18% 189/231

Приклад

198

1

9

8

2. Задача Іосифа Флавія

   Існує легенда, що Іосиф Флавій - відомий історик першого століття - вижив і став відомим завдяки математичній обдарованості. У ході іудейської війны він у складі загону з 41 іудейського воїна був загнаний римлянами у печеру. Віддаючи перевагу самовбивство полону, воїни вирішили вишукуватись у коло і послідовно вбивати кожного третього з живих до тих пір, доки не залишиться жодної людини. Проте Іосиф розом з одним зі своїх еднодумців вважав подібний кінець безглуздим - він швидко вирахував спасительні місця у порочному колі, на які поставив себе і свого товариша. І лише тому ми знаємо його історію.

   У нашому варіанті ми почнемо з того, що вшукуємо у коло N чоловік, пронумерованих числами від 1 до N, і будемо виключати кожного k-ого до тих пір, доки не вціліє лише одна людина. (Наприклад, якщо N=10, k=3, то спочатку помре 3-й, потім 6-й, потім 9-й, потім 2-й, потім 7-й, потім 1-й, потім 8-й, за ним - 5-й, і потім 10-й. Таким чином, вціліє 4-й.)

Технічні умови

   Вхідні дані

   У вхідному файлі задано натуральні числа N і k. 1 ≤ N ≤ 500, 1 ≤ k ≤ 100.

   Вихідні дані

   Вихідний файл повинен містити єдине число - номер людини, що залижилась в живих.

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 9.09091
Складність: 6% 60/64
Класифікація: Сортування та послідовності

Приклад

10 3

4

3. Сортування часу

   Відсортуйте час згідно заданому критерію.

Технічні умови

   Вхідні дані

   У вхідному файлі записано спочатку число N (1 ≤ N ≤ 100), а потім N моментів часу. Кожен момент часу задається 3 цілими числами - години (від 0 до 23), хвилини (від 0 до 60) і секунди (від 0 до 60).

   Вихідні дані

   У вихідний файл виведіть моменти часу, упорядковані в порядку неспадання (момент часу також виводиться у вигляді трьох чисел, ведучі нулі виводити не потрібно).

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 1.96078
Складність: 13% 53/61
Класифікація: Сортування та послідовності

Приклад

4

10 20 30

7 30 00

23 59 59

13 30 30

7 30 0

10 20 30

13 30 30

23 59 59

4. Велике сортування

   Відсортуйте N заданих чисел у неспадаючому порядку.

Технічні умови

   Вхідні дані

   Задано число N (1 ≤ N ≤ 100000), а потім в одному чи декількох рядках N натуральних чисел з діапазону від 1 до 100.

   Вихідні дані

   Виведіть у одному рядку N чисел у неспадаючому порядку.

Інформація про задачу

Ліміт часу: 0.1 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 7.14286
Складність: 27% 43/59
Класифікація: Сортування та послідовності

Приклад

5

3 1 2 4 2

1 2 2 3 4

5. Градуйований лексикографічний порядок

   Розглянемо цілі числа від 1 до n. Назвемо вагою числа його суму цифр, і позначимо вагу числа x як w(x).

   Потім упорядкуємо числа у так званому градуйованому лексикографічному порядку. Нехай задано два числа a та b. Якщо w(a) < w(b), то число a йде у градуйованому лексикографічному порядку до числа b. Якщо ж w(a) = w(b), тоді число a йде у градуйованому лексикографічному порядку до числа b якщо і лише якщо десяткове подання числа a лексикографічно менше десятикового подання числа b.

   Наприклад, у цьому порядку:

·                     число 120 йде до числа 4;

·                     число 555 йде до числа 78;

·                     число 20 йде до числа 200.

   За заданими n і k, знайдіть номер числа k і число, яке знаходиться на k-му місці, у градуйованому лексикографічному упорядкуванні натуральних чисел від 1 до n.

Технічні умови

   Вхідні дані

   У вхідному файлі записані числа n і k (1 ≤ k ≤ n ≤ 10¹⁸).

   Вихідні дані

   У першому рядку вихідного файлу виведіть номер числа k.

   У другому рядку виведіть число, яке знаходиться на k-му місці.

Інформація про задачу

Ліміт часу: 3 секунди
Ліміт пам`яті: 32 MB
Бали за пройдений тест: 4.7619
Складність: 50% 1/2
Класифікація: Сортування та послідовності

Приклад

20

10

2

14