Сайт підготовки до олімпіади з інформатики

програмування в С++

01.10.2014 Базові структури алгоритмів (С++) PDF Печать E-mail
Добавил(а) Administrator   
06.10.14 11:39

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, nk. nn, n!, logk 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. Типи величин, вираз, операції, функції

Типи величин

Тип даних:

Размір в байтах:

Діапазон

char

1

один символ від 0 до 255

wchar_

2

от -32768 to +32767

short

2

от -2^8 до 2^8 от -32768 to +32767

int

4

от -2^16 до 2^16 2147483648 до 2147483647

float

4

от -2^16 до 2^16   ± 3,4x10±38, примерно с 7-значной точностью

long

4

от -2^16 до 2^16 2147483648 до 2147483647

long long (int_64)

8

от -2^32 до 2^32

unsigned long long

8

от 0 до 18446744073709551616

double

8

от -2^32 до 2^32 ± 1,7x10*308, примерно с 15-значной точностью

long double

8

от -2^32 до 2^32

unsigned short

2

от 0 до 2^16 від 0 до 65535

unsigned int

4

от 0 до 2^32 от 0 до 4294967295

unsigned float

4

от 0 до 2^32

unsigned double

8

от 0 до 2^64

long double

8

± 1,7x10*308, примерно с 15-значной точностью

string

 

рядок

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;

}

Операції

Ім'я

Опис

+

с=a+b; k=k+1; k++; s+=k;

-

c=a-b; k=k-1; k--; s-=k;

*

c=a*b;

/

a=5.0/2;//2.5   a=5/2;//2

%

a=5%2;//1

Функції

Ім'я

Опис

abs(i)

модуль числа

ceil(f)

округлення до найближчого більшого цілого числа

fabs(f)

абсолютне значення

floor(f)

округлення до найближчого меншого цілого цілого

fmod(a,b)

повертає залишок від ділення двох чисел

modf(x,p)

повертає цілу та дробову частину аргументу х зі знаком

pow(x,y)

вираховує значення xy

sqrt(f)

квадратний корінь

#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. Два  резистори  R1  і  R2  з'єднані паралельно. Визначити сумарний  опір за формулою .

2.     Обчислити  відстань  між двома точками з координатами X1,Y1 і X2,Y2  за формулою 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. Масиви

Операція

Лінійний масив

Прямоктна таблиця

Опис

Int a[100];

int i, n;//індекс, кількість елементів

Int a[100][100];

int i,j, n,m;//індекс, кількість елементів

Введення

cin>>n;

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

cin>>n>>m;

for(i=1;i<=n;i++)

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

Виведення

for(i=1;i<=n;i++)cout<<a[i<<>" ";

for(i=1;i<=n;i++)

for(j=1;j<=m;j++) cout<<a[i][j]<<" ";

Сумування

s=0;

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

s=0;

for(i=1;i<=n;i++)

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

Пошук

cin>>k;

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

cin>>k;

for(i=1;i<=n;i++)

for(j=1;j<=m;j++) if (a[i][j]==k) cout<<i<<" "<<j;

Пошук максимального

max=a[1];nmax=1;

for(i=2;i<=n;i++)if  (a[i]>max) {max=a[i];nmax=i;}

max=a[1];imax=1;jmax=1;

for(i=1;i<=n;i++)

for(j=1;j<=m;j++) if  (a[i][j]>max) {max=a[i][j];

imax=i;jmax=j;}

Сортування

for(i=1;i<n;i++)

for(j=1;j<n;j++)

if  (a[j]>a[j+1]) {temp=a[j];  a[j]=a[j+1]; a[j+1]=temp;}

 

Стирання

n=n-1;

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

 

Вставка

n=n+1;

for(i=n;i>=1;i--) a[i]=a[i-1]; 

 

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();

}

Последнее обновление 06.10.14 11:47
 

Статистика

Пользователей : 152
Статей : 222
Просмотрено статей : 89861

Вход/Регистрация

Нет