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

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

Школа олімпійського резерву з інформатики
Типи даних 30_09_2011 PDF Печать E-mail
Добавил(а) Administrator   
14.10.11 11:55

Тип данных:

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

Численный разброс:

Char

1

один символ

Short

2

от -2^8 до 2^8

Int

4

от -2^16 до 2^16

Float

4

от -2^16 до 2^16

Long

4

от -2^16 до 2^16

Double

8

от -2^32 до 2^32

Long Double

8

от -2^32 до 2^32

Unsigned Short

2

от 0 до 2^16

Unsigned Int

4

от 0 до 2^32

Unsigned Float

4

от 0 до 2^32

Unsigned Double

8

от 0 до 2^64

 

unsigned char 1 от 0 до 255
wchar_t 2 от 0 до 65535
short 2 от -32768 to +32767
unsigned short 2 от 0 до 65535
int 4 от -2147483648 до 2147483647
unsigned int 4 от 0 до 4294967295
long 4 от -2147483648 до 2147483647
unsigned long 4 от 0 до 4294967295
float 4 ± 3,4x10±38, примерно с 7-значной точностью
double 8 ± 1,7x10*308, примерно с 15-значной точностью
long double 8 ± 1,7x10*308, примерно с 15-значной точностью

 

#include "stdafx.h"

#include <iostream>

using namespace std;

 

void main( void )

{

cout << " (unsigned)int = " << sizeof(int) << endl;

cout << " (unsigned)short = " << sizeof(short) << endl;

cout << " (unsigned)char = " << sizeof(char) << endl;

cout << " (unsigned)float = " << sizeof(float) << endl;

cout << " (unsigned)double = " << sizeof(double) << endl;

cout << " (unsigned)long = " << sizeof(long) << endl;

cout << " (unsigned)long double = " << sizeof(long double) << endl;

cout << " (unsigned)long long int = " << sizeof(long long int) << endl;

cout << " (unsigned)unsigned long long int = " << sizeof(unsigned long long int) << endl;

cout << " (unsigned)__int64 = " << sizeof(__int64) << endl;

}

 
23_09_2011 Задачі на базові структури PDF Печать E-mail
Добавил(а) Administrator   
14.10.11 11:52

Серйозні розважалки

Структура слідування

1. Якщо на одну шальку терезів посадити Даринку, яка важить n кг, і Наталку, яка важить на 5 кг менше, а на іншу насипати т кг цукерок, то скільки кілограмів цукерок доведеться з'їсти дівчаткам, щоб шальки терезів зрівноважилися?

2. Учень-невдаха Сашко сів виконувати домашнє завдання і про­сидів за столом 2 години. З них χ хв він чухав потилицю і дивився у вікно, у хв шукав у письмовому столі гумку, щоб стерти у підручнику з англійської мови карикатуру на свого товариша, на малювання якої він витратив перед цим z хв Решту часу Сашко перекладав англійські слова. Скільки слів він встиг перекласти, якщо переклад одного слова у нього займав 5 хв?

3. Петрусь задумав число і нікому його не назвав. Друзі упіймали його і примусили подвоїти задумане число, а потім додати до нього 5. І тільки після того, як вони пообіцяли Петрусеві благодійну допо­могу на контрольній з математики, він зізнався, що вийшло число n. Визначити, яке число задумав і приховав від своїх друзів Петрусь?

4. Курочка Ряба знесла яйце, а мишка розбила його. Після цього Ряба знесла на К яєць більше, але мишка знову їх розбила. Ряба знесла знову на К яєць більше, ніж попереднього разу, але мишка розтро­щила й ці. Так продовжувалося п'ять разів. Зі скількох яєць Дід і Баба змогли б врешті-решт зробити собі яєшню?

5. Із тераріуму втекло χ гадюк, у кобр та z гюрз. Довжина кожної гадюки - 1 м, кобри - 1 м 30 см, а гюрзи - 1 м 15 см. Скільки повних метрів отруйних змій утекло з тераріуму? Яку довжину вони складають у сантиметрах?

6. У царівни Несміяни кругле обличчя, радіус якого R. Визначте, яку сторону повинно мати квадратне дзеркало, щоб, коли Несміяна милується собою, її відображення поміщалося у дзеркалі.

7. Чепуруха Катруся, взявши ножиці в руки, змоделювала собі з круглого маминого капелюшка радіусу R капелюшок нового фасо­ну - з квадратними полями. Якою має бути сторона квадратної ко­робки для нового капелюшка?

8. Надіслати вітальну телеграму собі на день народження від президента країни.

9. Створити програму, яка б виводила на екран монітора лист найзапеклішому ворогові, задаючи його ім'я з клавіатури.

 

Структура розгалуження

1. Чебурашка вирішив купити килими, щоб застелити кімнату, в якій він мешкав разом з Геною. Їхня прямокутна кімната вияви­лися розмірами а х b, де а і b - цілі числа. Коли Чебурашка запитав у магазині, які килими є у продажу, то продавець повідомив, що є квадратні килими зі стороною с, де с - ціле число. Яку кількість килимів необхідно придбати Чебурашці, щоб накрити максималь­ну площу кімнати. Килими не можна накладати та підгинати. Визначити, яка площа кімнати буде ненакритою килимами. Передбачити ситуацію, коли розміри килиму перевищують розмі­ри кімнати.

2. На одному маленькому квадратному безлюдному острові зі стороною а м перебували k Робінзонів. Чи не порушені їхні права на житло, якщо на кожного Робінзона повинно припадати S м2 площі острова? Скільком новим Робінзонам ще вистачить місця на острові, якщо поблизу трапиться ще одна аварія?

3. Іван Петрович в нових штанах сів на щойно пофарбовану табуретку. На його штанах з'явилася квадратна пляма з довжиною сторони а см. Виявилося, що у хімчистку беруть одяг, плями на якому не більші Sew2. Визначити, чи вдалося Іванові Петровичу врятувати свої штани?

4. Від річкового вокзалу відійшли одночасно у протилежних нап­рямках теплохід та турист. Теплохід рухався зі швидкістю V1км/год, а турист по стежці вздовж річки зі швидкістю V2 км/год. Якщо через N год турист передумає і вирішить попливти річкою назад за тепло­ходом зі швидкістю V3 км/год, то чи встигне він підсісти на тепло­хід, який має за графіком зупинку через Υ год після початку руху і стоїть на цій зупинці Ζ год? Зважати на те, що всі події відбувалися протягом однієї доби.

5. Жили собі дід і баба і був у них город прямокутної форми. Довжина городу була А м, а ширина складала В м. Якось дід посва­рився з бабою і вирішив поділити город порівну. Тепер у діда квад­ратний город зі стороною С м, відрізаний скраю, а решта дісталася бабі. Визначити, чи не залишилась баба ошуканою та якої форми дістався їй город - прямокутної чи квадратної?

6. Трьом Товстунам подали на десерт кремові тістечка. Маса одного тістечка складала χ кг, а маса Товстунів відповідно x1кг, x2 кг та x3 кг. Перший Товстун з'їв n тістечок. Кожний наступний Товстун з'їдав у два рази більше від попереднього, але при цьому він не міг з'їсти більше половини своєї власної ваги. Скільки тістечок було з'їдено Товстунами за обідом?

7. Якою буде остача після ділення націло числа т на число п?

8. Щоб бути завжди чистим, людині необхідно x (24 < x < 50) шматків мила на рік. Якщо мити лише п'яти, то мила знадобиться у 12 разів менше, а мити лише вуха - ще на один шматок менше. Скласти програму, яка б за вибором користувача давала відповідь, яку кількість шматків мила необхідно закупити на п років уперед, щоб:

1) митися повністю;

2) мити лише п'яти;

3) мити лише вуха;

4) мити п'яти і вуха.

9. Три програмісти гналися по прямій стежці за юним хакером. Перший програміст біг зі швидкістю χ км/год, другий - на h, км/год швидше, а третій - ще на h^ км/год швидше за другого. Хакер тікав зі швидкістю у км/год. Пробігши η год, хакер заліз на дерево та причаївся. А програмісти, пробігши по т год кожний, зупинились і всі троє підняли голови вгору. Той, в полі зору якого (до 5 м) виявився хакер, дуже зрадів. Визначити, хто з програмістів зрадів, а хто залишився сумним? Скільки годин просидів на дереві хакер? Яка відстань була між програмістами в момент зустрічі з хакером?

10. Велосипедист Микола, стартувавши з точки (Хо,Уо) та рухаючись по прямій А(х-Xo)+В(у-Yo)+С=0, мріє про те, як він покатає на своєму велосипеді сусідку Катрусю. Чи здійсняться мрії Миколи, якщо неподалік, у точці (ρ,q), росте дерево?

Структура циклу

1. Вивести на екран монітора своє прізвище дану кількість разів.

2. Ненажера Стецько пробрався перед обідом у шкільну їдаль­ню, де вже були накриті столи, і почав швиденько з'їдати ще теп­ленькі булочки, що стояли на столах. З першого столу він з'їв х1 булочок, з другого - х2 булочок, і, відповідно, з останнього - хn булочок. Але за ним стежив черговий по їдальні Андрійко та ретельно все фіксував на своєму калькуляторі: до булочок, з'їдених з першого столу, додав кількість булочок, що зникла з другого столу, і т.д. Допоможіть крок за кроком відтворити інформацію, яку діставав Андрійко на своєму калькуляторі.

3. Нещасний Петрик їсть несмачну макаронину завдовжки n км. Першого дня він з'їв половину всієї довжини, другого дня - третину від того, що залишилося, третього дня - четверту частину від того, що залишилося другого дня, і т.д. Скільки макаронини ще залишить­ся йому «домучувати» на т-й день?

4. На дверях ліфта висіло загрозливе попередження про те, що двері зачиняються самі в той самий момент, коли зайвий за вагою пасажир переступить поріг ліфта. Котрий пасажир постраждає, якщо ліфт витримує вагу не більше s кг, а вага пасажирів, що стоять у черзі до ліфта, дорівнює відповідно й,, а1, а2, a3 ... αn?

5. Коли Василині Премудрій виповнилося 18 років, Чахлик Невмирущий вирішив взяти її заміж. Василина запитала Чахлика, скільки у нього скринь із золотом. Чахлик сказав, що в нього зараз n скринь і щороку додається ще по т скринь. Василина пообіцяла, що вийде заміж тоді, коли у Чахлика буде k повних скринь із золотом. Скільки років буде тоді нареченій?

6. Капосний папуга навчився висмикувати у дідуся Василя волосся, яке ще залишилось у того на голові. Почавши з однієї волосини, він щодня збільшував порцію вдвічі. Через скільки днів дідусеві не знадобиться гребінець, якщо спочатку в нього на голові було аж N волосин.

7. У понеділок Толя позичив у Миколки 2 цукерки і з'їв. У вівторок він позичив у 2 рази більше цукерок, після чого віддав половину боргу, а решту цукерок знову з'їв. Кожного наступного дня він позичав у 2 рази більше цукерок, ніж попереднього дня, віддаючи з них цілу частину від половини боргу, а решту цукерок із задоволенням з'їдав. Скільки цукерок з'їсть Толя через N тижнів? Скільки у нього при цьому буде складати борг? Скільки цукерок встигне повернути за цей час Толя Миколці?

8. Компанія бабусь поїхала на мотоциклах на курси з комп'ютерної грамотності. Попереду на мотоциклі без глушника їхала одна бабуся, за нею - дві, потім - три і т.д. Скільки бабусь їхало на заняття, якщо приголомшені пішоходи всього нарахували N рядів? Чи змогли бабусі зайняти всі місця у класі, якщо там стояло k рядів по / комп'ютерів в кожному? Скільки вільних місць залишилось?

9. Два хлопчики одночасно стартували з однієї точки і побіг­ли - один по колу, а другий по сторонах квадрата. Якщо вважати, що радіус кола може бути лише цілим числом, а π == 3,14 , то при якому найменшому радіусі і при якій стороні квадрата вони знову одночасно зустрінуться в початковій точці?

10. Маленька Моська хоче помірятися зростом із Слоном і біжить за ним зі швидкістю у1 м/хв, а Слон утікає від неї зі швид­кістю y2 м/хв. У змореної Моськи швидкість через кожні 10 хв падає на h м/хв. Чи здійсниться Мосьчина мрія і, якщо так, то через скільки хвилин це станеться?

11. Василина Премудра грала в шашки зі Змієм Гориничем. Спо­чатку Василина з'їла у Горинича 3 шашки, а Горинич у Василини - 5 шашок, потім Василина у Горинича з'їла 9 шашок, а Горинич у Василини - 10 шашок, на третьому ході Василина проковтнула 15 шашок, а Горинич - 20. Ця серйозна гра тривала ще довго, аж поки Горинич не втомився і після Ν-το ходу не з'їв саму Василину Премудру. Скільки всього шашок проковтнув Змій Горинич?

12. Коли у кімнаті було вже N мух, Петро Петрович відкрив кватирку і, розмахуючи рушником, почав виганяти їх на вулицю. На виганяння однієї мухи у нього йшла 1 хв, але через кожні 5 хв до кімнати залітала муха. Коли у кімнаті ставало менше, ніж 10 % від початкової кількості мух, то процес виганяння мух уповільнювався вдвічі. Скільки мух залишилось у кімнаті через К хв? Через скільки хвилин Петро Петрович залишиться у кімнаті на самоті?

13. Капітан Флінт зі своїми піратами на безлюдному острові викопав величезний скарб із старовинних золотих монет. Спочатку Флінт взяв собі найбільшу кількість монет, яка не перевищувала половини скарбу, а решту віддав своїм розбійникам. Але тут на цю частину скарбу наклав лапу його заступник, який за прикладом свого начальника зробив те саме, а решту віддав підлеглим. Таким чином в кожній компанії, що залишалася, знаходився старший, який забирав свою частину скарбу, тобто найбільшу кількість монет, яка не перевищувала половини того, що ділили, залишаючи решту всім іншим. Скільки монет дісталося останньому розбійникові, якщо всього було К розбійників та Μ монет? Чи залишилися обділені розбійники?

 
Системи числення 23_09_2011 PDF Печать E-mail
Добавил(а) Administrator   
14.10.11 11:47

Переведення чисел з однієї системи числення в іншу

Десяткова

Двійкова

Відмітка про виконання

0

0

 

2

10

 

5

101

 

10

1010

 

32

100000

 

98

1100010

 

1024

1000000000

 

6783

1101001111111

 

98321

11000000000010001

 

2000000

111101000010010000000

 

1073741824

1000000000000000000000000000000

 

5000000000

100101010000001011111001000000000

 

 

Переведення чисел в різних системах числення

На приклад, якщо потрібно перемножити числа 101 і 1001 в двійковій системі, то він спочатку ці числа переводить в десяткову систему таким чином :

(101)2=1*22+0*21+1*20=4+0+1=5

(1001)2=1*23+0*22+0*21+1*20=8+0+0+1=9

Після чого множення чисел 5 і 9 Вася з легкістю виконує в десятковій системі числення і отримує число 45. Далі виконує переведення з десяткової системи числення в двійкову. Для цього потрібно ділити число 45 на 2 ( порядок системи числення ), запам'ятовує залишки від ділення, до тих пір поки в результаті не залишиться число 0:

Відповідь складається з одержаних залишків від ділення шляхом їх запису в зворотному  порядку . Таким чином одержуємо результат : (101)2 * (1001)2 = (101101)2.

 

1. Задача. Перевести число з  будь-якої системи числення в будь-яку іншу.

Протестувати самостійно

2. Задача  BINARY

Ім'я вхідного файлу:   BINARY.DAT

Ім'я вихідного файлу: BINARY.SOL

Максимальний час роботи на одному тесті: 3с

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число 1910 = 1×24+0×23+0×22+1×21+1×20 в двійковій  системі запишеться як 100112). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри буде число 1×24+1×23+1×22+0×21+0×20 = 28.

Оскільки придумана гра з числами все більше займає уяву учня, відволікаючи тим самим його від навчання і підготовки до олімпіади, Вас просять написати програму, яка б допомогла Дімі отримувати результат гри без важких ручних обчислень.

 

Вхідний файл містить одне ціле число N (0£N£32767).

Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне результату гри.

Приклад

BINARY.DAT

BINARY.SOL

19

28

3. Задача  Нулі

Ім'я вхідного файлу:   ZEROS.DAT

Ім'я вихідного файлу: ZEROS.SOL

Максимальний час роботи на одному тесті: 5с

Необхідно написати програму для знаходження кількості N-значних чисел в системі числення за основою K, таких що їхній запис не буде містити двох нулів підряд.

Формат вхідних даних.

Єдиний рядок вхідного файлу ZEROS.DAT містить два натуральних числа N та K, 2 <= K <= 10, N + K <= 18.

Формат вихідних даних.

Єдиний рядок вихідного файлу ZEROS.SOL повинен містити одне натуральне число - розв'язок задачі.

Приклад.

ZEROS.DAT:

4 2

ZEROS.SOL:

5

 

4. Задача. Міжнародна конференція

Вас найняли для того, щоб визначити місця дипломатів за столом обговорень міжнародної конференції. На конференцію запрошено по одному дипломату з N різних країн світу. Ко­жен дипломат знає від однієї до п'яти мов. Дип­ломати, які не знають спільної мови, не можуть розмовляти один з одним. До того ж, деякі краї­ни проголосили, що не будуть підтримувати дипломатичних стосунків з деякими іншими, тобто представники цих країн не будуть роз­мовляти один з одним. Ваше завдання полягає в розробці програми DIPLOMAT.pas/.c/.cpp, що визначає місця за столом для дипломатів таким чином, щоб кожен мав можливість розмовляти з обо­ма своїми сусідами, які сидять ліворуч та пра­воруч від нього.

Стіл, що використовується, - круглий і розрахований на N персон (N£20). Дипломат може спілкуватися з дипломатом, який сидить ліво­руч, однією мовою, а з дипломатом, що сидить праворуч, - іншою.

Технічні вимоги:

Вхідний файл: DIPLOMAT. DAT.

Вихідний файл: DIPLOMAT. SOL.

Програма: diplomat.pas/.c/.cpp

Формат вхідних даних. У першому рядку текстового файла DIPLOMAT. DAT - число N. Далі - N рядків, по одному рядку на диплома­та. Кожен рядок - послідовність слів. Сусідні слова відокремлені пробілом. Кожне слово - це послідовність великих латинських літер. Перше слово - код країни - складається з трьох літер. Друге слово має довжину від 1 до 5 літер і являє собою перелік мов, якими може спілкуватися дипломат. Кожна мова позначена однією літерою. Далі - список з не більш ніж N трилітерних слів - кодів країн, з якими уряд дипломата підтримує дипломатичні стосунки.

Формат вихідних даних. До файла DIPLOMAT. SOL треба вивести список дипломатів у порядку розміщення за столом (по одному дипломату в рядку). Кожен рядок складається з трьох слів: перше - код мови, якою дипломат може спілкуватися з сусідом ліворуч, друге - код країни дипломата, третє - код мови для спілкування з сусідом праворуч. Мож­ливе існування кількох розв'язків. Вам по­трібно знайти один. Якщо розв'язку не існує, то ваша програма має видати таке повідомлен­ня: «NO  SOLUTION EXIST»

Приклад:

DIPLOMAT. DAT

DIPLOMAT. SOL

4

USA EC UCR CHN

CHN GC USA GBR

GBR EG UCR CHN

UCR E USA GBR

C USA E

E UCR E

E GBR G

G CHN C

2

USA ER CHN

CHN CP USA

NO SOLUTION EXIST

 

 

Домашні задачі

 

1. Прості числа (решето Ератосфена).

2. Супер прості числа.

 
ЕТАПИ РОЗВ'ЯЗАННЯ ЗАДАЧ НА КОМП'ЮТЕРІ PDF Печать E-mail
Добавил(а) Administrator   
21.09.11 10:32

ЕТАПИ РОЗВ'ЯЗАННЯ ЗАДАЧ НА КОМП'ЮТЕРІ

 


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

1.Постановка задачі. Розв'язування будь-якої задачі починається з ЇЇ постановки, викладеної мовою чітко визначених математичних понять. На першому кроці необхідно добре уявити, в чому саме полягає дана задача, які необхідні початкові дані, яку інформацію вважати результатами розв'язання.

2. Побудова математичної моделі. Побудова математичної моделі алгоритму — дуже відповідальний етап. Не завжди умова сформульованої задачі містить в собі  математичну формулу, яку можна застосувати для розробки алгоритму задачі, не завжди розв'язок задачі вдається одержати в явному вигляді, що зв'язує вхідні дані га результат. Для цього створюється інформаційна математична модель  об'єкта, що вивчається. Вибір виду моделі залежить від інформаційної сутності об'єкта, а не від його фізичної природи. Тобто, настільки важливе прикладне значення задач, як однотипність методів, якими вони розв'язуються. Наприклад, логічні моделі використовуються як для моделювання словесних міркувань, так і для опису логічних схем автоматики. Розв'язуючи задачу про рух тіла під дією прикладених до нього сил, ми перш за все записуємо рівняння його руху на основі законів механіки. Проте, крім сили тяжіння, на тіло діє і сила опору повітря. Постає питання достовірності математичної моделі і реальної картини досліджуваного об'єкта. Іноді буває неможливо врахувати всі реальні фактори, що впливають на нього. Тому дуже  важливим є вміння виділити серед усіх факторів головні і другорядні, щоб останніми можна було знехтувати. При цьому може скластися ситуація, коли наперед невідомо, якими саме факторами можна знехтувати, і тому може бути кілька математичних моделей, які описують один і той самий об'єкт з різним ступенем достовірності. Відповідність моделі реальному об'єкту перевіряється практикою, комп'ютерним експериментом. Критерій застосування практики дає можливість оцінити побудовану модель і уточнити її за необхідності. Чим достовірніше математична модель відображає реальні сторони об'єкта, тим точніші одержувані результати.

3. Побудова алгоритму. Наступним етапом є розробка алгоритму обробки інформації на основі побудованої математичної моделі.  Тепер необхідно знайти спосіб розв'язування цієї задачі. Для цього можуть бути застосовані вже відомі методи, проведена їх оцінка, аналіз, відбір або розроблені нові методи. Наприклад, вибір методу розв'язування системи рівнянь, що описує дану математичну модель. Під час створення складних алгоритмів застосовується метод покрокової розробки. Сутність цього методу полягає в тому, що алгоритм розробляється «зверху донизу». На кожному етапі приймається невелика кількість рішень, що призводить до поступової деталізації, уточнення як виконуваної, так і інформаційної структури алгоритму. Такий підхід дозволяє розбити алгоритм на окремі частини — модулі, кожний з яких розв'язує свою самостійну підзадачу. Це дає можливість сконцентрувати зусилля на розв'язуванні кожної підзадачі, що реалізується у вигляді окремої процедури. Для кожного такого модуля визначаються свої методи реалізації алгоритму та структура даних, якими він оперує. Останнім етапом у методі покрокової розробки є об'єднання окремих незалежних модулів у єдине ціле. Для цього між модулями повинні бути встановлені зв'язки, тобто узгоджена передача інформації від одних модулів до інших: результати виконання одних модулів є вхідною інформацією для інших.

Якщо поставлена задача є складним завданням, то важливість розбиття алгоритму на окремі модулі неможливо переоцінити.

4. Вибір мови програмування. Алгоритм, призначений для виконання на комп'ютері, має бути записаний мовою програмування. Різноманітність існуючих мов програмування потребує від програміста реальної оцінки складності та характеру задачі. Тільки після цього він зможе здійснити оптимальний вибір мови програмування для реалізації поставленої задачі. Враховуючи можливість розбиття всього алгоритму на окремі модулі, для кожного з них вибір мови програмування можна здійснити окремо. Процес розробки програми, як і алгоритму, може здійснюватися за принципом «зверху донизу». Це дозволяє одержати добре структуровану програму, читання і розуміння якої значно полегшене.

5. Складання програми. Цей етап потребує лише знання вибраної мови програмування. Суть його полягає в тому, щоб на основі розроблених алгоритмів і структур даних створити програму для комп'ютера.

6. Компіляція програми. Переведення програми на машинну мову здійснюється за допомогою спеціальних програм — компіляторів. Однією з їх функцій є перевірка відсутності в програмі синтаксичних помилок. Не тіште себе надією, що ваша, навіть найпростіша, програма написана бездоганно. Серед програмістів побутує прислів'я:
«Якщо програма не має помилок, це означає, що у вас поганий компілятор!!!»

7. Налагодження програми, контрольний прорахунок. Виправлення усіх синтаксичних помилок у програмі на попередньому етапі .зовсім не позбавляє вас від помилок іншого типу — змістовних, логічних. Вони з'являються під час помилкового трактування умови поставленої задачі, через недосконалість математичної моделі або недоліки у побудованому алгоритмі, що призводить до одержання помилкового результату. Такі помилки не можуть бути усунені на стадії компіляції, тому що для їх виявлення необхідна інформація про сутність самої задачі. Це може зробити лише сам розробник. Процес налагодження програми полягає втому, що готується система тестів, за допомогою якої перевіряється робота програми в різних можливих режимах. Кожний тест містить набір вхідних даних, для яких відомий результат. Для більшості програм виникає необхідність добору не одного, а серії тестів, щоби перевірити якнайбільше можливих ситуацій, які можуть виникнути в процесі роботи програми. Якщо для всіх тестів результати роботи програми збіглися з розрахунками, то можна вважати, що логічних помилок немає.

9. Експлуатація програми. Тепер програму можна тиражувати і пропонувати іншим користувачам, доповнивши її відповідною документацією для користувачів. Документація повинна містити опис виконуваної задачі, опис середовища, в якому може працювати
програма, обмеження на вхідні дані, формат вхідних та вихідних даних. Більшість розглянутих етапів розв'язування задач на комп'ютері виконуються людиною і носять творчий, евристичний характер.

Караванова Т.П., Основи алгоритмізації та програмування. 750 задач з рекомендаціями та прикладами (посібник)

 

 
РОЗВ'ЯЗОК ВСТУПНОЇ РОБОТИ 2011 PDF Печать E-mail
Добавил(а) Administrator   
21.09.11 10:25

3.

!2 л

8 л

 5 л

12

0

0

4

8

0

0

8

4

8

4

0

3

4

5

3

8

1

11

1

0

6

1

5

6

6

0

 

5. Вгадати число можна за 4 спроби, використовуючи метод поділу по полам.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

2

 

 

 

 

 

3

 

 

 

3

 

 

 

3

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

4

 

4

 

4

 

4

 

4

 

4

 

4

 

 

7.

http://ega-math.narod.ru/Quant/Shestpl.htm

9.Ідея. Розв’язком задачі є числовий ряд Фібоначі.

Кількість сходинок

Варіанти

Кількість способів

1

1

1

2

11, 2

2

3

111, 12, 21

3

4

1111, 112, 121, 211, 22

5

5

 

8

6

 

13

7

 

21

12.Наявна матриця розміру M*N, що являє собою деякий лабіринт. Одна клітинка лабіринту є входом а інша виходом. Знайти найкоротший шлях від входу до виходу, якщо він існує.

Вхідні данні : файл Labirint.dat, де першим рядком йде два числа N та M (0<N,M<100), а далі M рядків по N чисел відокремлених пробілами. Всі числа Amn можуть приймати значення 1,2,3,4. 1 - ділянка, що можна пройти. 2 - стіна. 3 - вхід. 4 - вихід.

Вихідні данні: число T>0, яке дорівнює довженні найкоротшого шляху, або -1, якщо такого шляху не існує.

Аналіз задачі.

По-перше треба відмітити, що максимальний розмір лабіринту, не перевищує 104 елементів, тобто весь набір даних можна розмістити в статичній пам'яті.

Одним з найбільш ефективних алгоритмів пошуку найкоротшого шляху є алгоритм хвилі. Хвильовий алгоритм полягає в наступному:

1.        кожної клітинок i приписується число T - тимчасова мітка.

2.        заводяться два списки "фронту хвилі" NF і OF, а також перемінна T (поточний час);

3.        OF:={u1}; NF:={}; T:=1;

4.        для кожної з вершин i, що входять у OF, проглядаються сусідні вершини j, і якщо T[j] = -2, то T[j]=T, NF=NF + {j}.

5.        якщо NF = {}, то шлях не існує, перехід до кроку 8.

6.        якщо одна з вершин збігається з u2, то знайдений найкоротший шлях довжини T, перехід до кроку 8;

7.        OF:=NF; NF:={}; T:=T+1; повернення до кроку 4.

8.        Відновлюємо шлях проходячи масив P, шукая серед сусідів даної клітинки таку, щоб номер ітерації хвилі у неї був найменшим.

 

Джерела інформації

 

http://www.problems.ru

http://olympiads.ru

 

 
Мова програмування С, С++ » PDF Печать E-mail
Добавил(а) Administrator   
21.09.11 09:55

«Мова програмування С, С++ »

методист лабораторії інформатики ВІППО Гісь Ігор Володимирович

Мета спецкурсу:

·         розвиток логічного, аналітичного мислення та основних видів розумової діяльності: уміння використовувати індукцію, дедукцію, аналіз, синтез, робити висновки, узагальнення;

·         розвиток уміння розв’язувати змістовні задачі різного рівня складності, олімпіадні задачі, користуючись відомими теоретичними положеннями, математичним апаратом, літературою та комп’ютерною технікою;

·         навчити учнів правильному розв’язуванні задач для підготовку учнів до участі в олімпіадах.

Тема

План

Засоби

1.

Розділ «Алгоритмізація і програмування»

-                      кількість годин на вивчення за програмою

-                      «+» і «-» вивчення розділу

-                      тематика вивчення: 1) базові структури алгоритмів; 2)методика складання алгоритмів та їх аналіз; 3) об’єктно-орієнтоване програмування, візуальне програмування.

-                      принцип IPO (input procedure output): визначення місцезнаходження і введення даних; задання операцій над даними; виведення результуючих даних

-                      етапи розв’язування задач з використанням ЕОМ.

презентація «Алгоритмізація і програмування»

 

мозковий штурм

 

аналіз схеми «людина-задача-алгоритм-програма-комп’ютер»

 

додаток: Етапи розв’язування задач

2.

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

-          структуровані мови програмування

-          С – Деніс Рітчі (1972)

-          C++ - 80-ті роки, Бьяртні страус труп (1979)

-          середовище Borland C++ 3.1

завантаження і робота в середовищі

3.

Лексеми мови програмування

-          алфавіт мови і ключові слова

-          директиви препроцесора (#include)

-          сталі (const назва=значення)

-          змінні і їх типи; (цілі: int спиок змінних; дійсні: float  змінна=значення; символьний char с1=’A’, c2=65; логічний bool false, true)

-          коментарі // ...

         /* ... */

-          перша програма (структура програми)

приклад структури програми

4.

Присвоєння, вирази, функції

-          = аналіз виразів

-          функції math.h

приклади виразів

5.

Введення і виведення даних

-          stdio.h: scanf (“%d”, &a) &змінна – адреса даних puts (“рядок”); %d –int %f – float %c –char %s – рядок символів

-          conio.h: cin >> змінна; cout << «текст»<< p

приклади рядків введення і виведення

6.

Базові структури

-          слідування

-          розгалуження (==, !=, ! – не, && - і, || - або, IF (логічний вираз) команда 1; else команда 2)

-          вибір (switch (вираз) {case ознака 1: команда 1; break; default: команда}

-          цикл: for ( ) {}, while (умова) {}, do команда while (вираз);

-          підпрограми

додаток з задачами:

приклади розв’язаних задач і задачі для самостійного розв’язування

 

7.

Типи даних

-          масиви

-          рядки

-          вказівники

-          файли

 

Єдиний спосіб вивчати нову мову програмування –

писати на ній програми.
Брайен Керніган

 

Мова формує наш спосіб мислення і визначає те, про що ми можемо думати. Прогрес комп'ютерних технологій визначив процес появи нових різноманітних знакових систем для запису алгоритмів – мов програмування.

C++ - універсальна мова програмування, задумана так, щоб зробити програмування приємнішим для серйозного програміста.  C++ є надмножиною мови програмування C.

 

 

ЗАДАЧІ

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

#include <stdio.h>

void main()

{

puts("Okey");

}

 

#include <iostream.h>

void main()

{

cout <<"Okey";

}

Слідування

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

2.     Обчислити  відстань  між двома точками з координатами X1,Y1 і X2,Y2  за формулою L=

#include <stdio.h>

#include <math.h>

void main()

{

float x1,y1,x2,y2;

puts("Zadayte x1,y1,x2,y2\n");

scanf("%f%f%f%f",&x1,&y1,&x2,&y2);

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

printf("L=%f\n",l);

}

 

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

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

#include <stdio.h>

void main()

{

int s,r,n,t;

puts("Zadayte s,r,n, t\n");

scanf("%d%d%d%d",&s,&r,&n, &t);

int a=s*r*n;

printf("A=%d\n",a);

int b=a/t;

printf("B=%d\n",b);

int g,h;

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

printf("%d:%d",g,h);

}

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

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

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

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

#include <stdio.h>

void main()

{

int a,b,max;

printf("a=");

scanf("%d",&a);

printf("b=");

scanf("%d",&b);

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

printf("max=%d",max);

}

 

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

#include <stdio.h>

void main()

{

int a,b,c,max;

printf("a=");

scanf("%d",&a);

printf("b=");

scanf("%d",&b);

printf("c=");

scanf("%d",&c);

 

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

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

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

printf("max=%d",max);

}

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

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

10. За трьома сторонами перевірити, чи трикутник прямокутний.

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

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

 

 

 


 

 

Цикл

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

#include <stdio.h>

#include <conio.h>

 

void main()

{

clrscr();

for (int i=1;i<20;i++)printf("%2d*%2d=%4d\n",i,i,i*i);

}

 

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

#include <stdio.h>

void main()

{

int n;

printf("n=");

scanf("%d",&n);

int i=48;

int s=0;

while (i>=n)

{

s+=i;

i-=3;

}

printf("S=%d",s);

}

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

#include <stdio.h>

#include <math.h>

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

printf("x=%f y=%f\n",x,y);

x=x+h;

}

}

15.  За заданою формулою члена ряду з номером  k  скласти  програму  обрахунку суми всix членiв ряду , не менших заданого числа  E.

                                      1

                                ───────

                                (2k-1)(2k+1)

16. Скласти програму обчислення добутку членів послідовності D=-1*(1/2)*(-1/3)*(1/4)*(-1/5)*...*(-1/2N-1)*(1/2N).

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

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

19. Написати таблицю відповідності між вагою в фунтах  і  вагою  в кг для значень від 1 до 30 фунтів з кроком 3 фунт (1 фунт = 0.4 кг.)

 

Підрограми

20. Знайти площу чотирикутника заданого сторонами і діагоналлю.

21. Знайти площу чотирикутника заданого координатами вершин.

#include <stdio.h>

#include <conio.h>

#include <math.h>

 

float l(int x0, int y0, int x, int y)

{return sqrt(pow((x-x0),2)+pow((y-y0),2));}

 

float geron(float a, float b, float c)

{ float p=(a+b+c)/2;

return sqrt(p*(p-a)*(p-b)+(p-c));}

 

void main()

{

clrscr();

int x1,y1,x2,y2,x3,y3,x4,y4;

scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);

float a,b,c,s;

a=l(x1,y1,x2,y2);

b=l(x2,y2,x3,y3);

c=l(x1,y1,x3,y3);

s=geron(a,b,c);

a=l(x3,y3,x4,y4);

b=l(x4,y4,x1,y1);

c=l(x1,y1,x3,y3);

s+=geron(a,b,c);

printf("s=%f\n",s);

}

22. Знайти площу многокутника заданого координатами вершин а) вершини задані по порядку; б) вершини задані в довільному порядку.

Площа трикутника: 1)Формула Герона; 2)S=1/2*|(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)|

23.Використовуючи функцію сумування двох чисел, обчислити суму трьох чисел.

#include <stdio.h>

#include <math.h>

 

float suma(int x, int y)

{return x+y;}

 

void main()

{

int a,b,c,s;

scanf("%d%d%d",&a,&b,&c);

s=suma(suma(a,b),c);

printf("%d+%d+%d=%d",a,b,c,s);

}

24.Використовуючи функцію максимального з двох, визначити максимальне з чотирьох чисел.

 

Масив

 

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

#include <stdio.h>

void main()

{

int a[100];

int i,n,s;

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++){printf("a[%d]=",i);scanf("%d",&a[i]);}

s=0;

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

printf("s=%d",s);

}

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

#include <stdio.h>

void main()

{

int a[100];

int i,n,k,s;

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++){printf("a[%d]=",i);scanf("%d",&a[i]);}

printf("k=");

scanf("%d",&k);

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

n--;

for (i=1;i<=n;i++) printf("a[%d]=%d\n",i,a[i]);

}

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

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

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

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

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

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

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

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

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

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

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

Рядки

 

38. Знайти подвійні пропуски і знищити їх.

39. Знайти найдовше слово, слова  заданої  довжини  N,  слова  які  містять літеру M.

40. В заданому тексті знищити частину тексту поміщену в дужках.

41. Із тексту вибрати а) цифри; б)числа і вивести їх по порядку.

 

Операції над адресами. Вказівники.

 

Задача 1.

Змінна - 25

Адреса – 0xfff4

 

#include <iostream.h>

void main()

{

int a=25;

cout <<”Zminna”<<a<<"\n";

cout <<”Adress”<<&a<<"\n";

 

}

 

Задача 2.

Порівння типів, стосовно використання пам’яті.

#include <iostream.h>

 

void main()

{

int *a;

float *b;

char *c;

cout <<"int    "<<sizeof(a)<<"\n";

cout <<"float  "<<sizeof(b)<<"\n";

cout <<"char   "<<sizeof(c)<<"\n";

 

 

int a1;

float b1;

char c1;

cout <<"int    "<<sizeof(a1)<<"\n";

cout <<"float  "<<sizeof(b1)<<"\n";

cout <<"char   "<<sizeof(c1)<<"\n";

}

 

Задача 3.

Введення і виведення змінної заданої вказівником.

#include <stdio.h>

void main()

{

float *a;

*a=3.14;

printf("a=%f\n",*a);

printf("a=%p\n",a);

scanf("%f",a);

printf("a=%f\n",*a);

}

Задача 4.

Виділення і вивільнення пам’яті.

#include <stdio.h>

void main()

{

int *a=new int;

*a=5;

int *b=new int(10);

printf("a=%d b=%d\n",*a,*b);

a=b;

printf("a=%d b=%d\n",*a,*b);

delete(b);

printf("a=%d \n",*a);

}

 

В С (tdlib.h, alloc.h ) malloc, calloc для надання динамічної пам’яті, free – вивільнення пам’яті.

 

Файли.

Задача  5. Обчислити суму.

#include <fstream.h>

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

}

Задача  6.

Рядок вивести в стовпчик і в зворотному порядку.

#include <fstream.h>

#include <string.h>

 

void main()

{

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

char a[100];

inp>>a;

inp.close();

strrev(a);

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

for (int i=1;i<=strlen(a);i++) out<<a[i]<<\n;

out.close();

}

 Задача  7. В таблиці NxM знайти суму кожного рядка і стовпця.

#include <stdio.h>

#include <fstream.h>

 

void main()

{

int n,m,i,j,s;

int a[100][100];

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

inp>>n>>m;

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

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

inp>>a[i][j];

inp.close();

 

 

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

{

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

printf("%d ",a[i][j]);

printf("\n");

}

Задача 4. Зчитати з файлу всі дані і вивести їх на екран.

#include <iostream.h>

 

void main()

{

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

while (!inp.eof())

{

char *a=new char[1000];

inp>>a;

cout <<a<<"\n";

delete [] a;

}

inp.close();

}

 

 
Вступна робота 2011 PDF Печать E-mail
Добавил(а) Administrator   
09.09.11 13:09

Вступна робота

1. Хто сидить поруч з мамою Марії?

На лавці сидить Марія, її мама, бабуся і лялька. Бабуся сидить поруч з внучкою, але не поруч з лялькою. Лялька не сидить поруч з мамою. Хто сидить поруч з мамою Марії?

2. Що виросте у розгубленої господарки?

У розгубленої господарки є 3 ящики для розсади з надписами:” Огірки”, „Квіти”, „Ромашки”. Вона посадила насіння ромашки, огірків і дзвіночків в ці ящики так, що всі надписи на ящиках виявились невірними. Що виросте в ящику з надписом” Ромашки”?

3. Переможці олімпіад.

П’ятеро однокласників: Ірина, Тарас, Катя, Сергій і Микола стали переможцями олімпіад школярів з фізики, математики, інформатики, літератури та географії. Відомо, що:

- переможець олімпіади з інформатики вчить Іірину і Тараса працювати на комп’ютері;

- Катя і Сергій також зацікавились інформатикою;

- Тарас завжди побоювався фізики;

- Катя, Тарас і переможець олімпіади з літератури займаються плаванням;

- Тарас і Катя привітали переможця олімпіади з математики;

- Іра шкодує, що в неї залишається мало часу на літературу.

Переможцем якої олімпіади став кожен з учнів?

4. Як за допомогою скляних трилітрової і п’ятилітрової банок відміряти об’єм рідини що дорівнює 1) 7 л; 2)12 л; 3)14 л; 4) 1 л.

5. Початкове розташування чорних та білих шашок таке:

Поміняти місцями білі та чорні шашки, враховуючи, що їх можна пересувати лише на сусідню порожню клітинку, або перестрибувати через одну зайняту. Скласти схему алгоритму, визначить його тип.


6. Записати у вигляді схеми алгоритм вгадування задуманого
числа в проміжку:

1) від 0 до 7; 2) від 0 до 15; 3) від 0 до 31; 4) від 0 до 100.

Під час вгадування можна задавати лише одне із запитань типу: «Ваше число менше за ...?» або ж «Ваше число більше за ...?» Відповіддю на запитання може бути «Так» або «Ні». За яку найменшу кількість кроків можна це зробити? Визначити тин цього алгоритму.

7. Серед трьох монет одна фальшива (вона легше, ніж дві інші однакової ваги). За допомогою одного зважування на терезах (без гир) знайти фальшиву монету.

8. Є 12 монет, серед яких одна фальшива. За 3 зважування на терезах без гирок визначити фальшиву монету і відповісти на запитання: «Фальшива монета легша чи важча?» Скласти схему алгоритму, визначити його тип.

9. Фальшива монета

З 60- ти однакових за виглядом монет одна відрізняється від інших за масою. За допомогою двох зважувань без гир визначити: важча вона чи легша від справжніх?

10. Скількома способами хлопчик може піднятися по сходах на 5 сходинку, якщо він може підніматися на наступну сходинку, або переступати через одну чи дві сходинки? Сформулювати алгоритм визначення кількості способів сходження на N-ну сходинку.

11. З’ясувати, яка з двох дат передує іншій.

12. За координатами вершин опуклого чотирикутника встановити:

а) його вид (квадрат, ромб, прямокутник, паралелограм, трапеція);

б) чи є він вписаним;

в) описаним.

13. Написати алгоритм пошуку виходу в лабіринті.

14. Плитка шоколаду складається з 35 квадратиків (7 5). Ламають по прямих, які ділять квадратики до тих пір, поки не одержать окремі 35 квадратиків. Скільки разів потрібно поділити шоколадку?

14. Трьом учням в темній кімнаті одягли на голову по чорній шапці. Перед ними поставлено завдання відгадати, хто в якій шапці, якщо всього шапок 15, причому 2 з них - сірі, а 3 - чорні. Сірі шапки сховали перед тим, як у кімнаті запалили світло. Через деякий час один учень відгадав, що він стоїть в чорній шапці. Як він це зробив?

16. Яку найбільшу кількість слонів можна розташувати на шаховій дошці, щоб ані один із слонів не був під подвійною бійкою?

17. Задача про вісім ферзів. На шаховій дошці розміром 8x8
розташувати вісім ферзів так, щоб вони не загрожували один
одному.

18. «Ханойські башти». Є три стержні А, В, С та п дисків різного розміру, перенумерованих від 1 до я в порядку зростання їх розмірів. Спочатку всі диски насаджені на стержень А таким чином, що на кожному диску зверху лежить менший за розміром диск. Необхідно перенести всі диски із стержня А на стержень С, враховуючи такі умови: диски можна переносити лише по одному і більший диск не можна ставити на менший. Для цієї операції необхідно скористатися стержнем В. Надрукувати послідовно в сі кроки, вказуючи пари стержнів, які в них використовуються (першим — стержень, з якого знімається диск, другим — стержень, на який він перекладається). Напишіть для N=4.


 
Задачі 09.09.2011 (заняття 1) PDF Печать E-mail
Добавил(а) Administrator   
09.09.11 13:04

Задача 1. Затори на дорогах (JAMMING)

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

Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць.

Визначте, скільки існує різних за послідовністю типів машин (легкова - вантажна) заторів між мерією міста та моїм будинком, якщо вони на одній вулиці, а відстань між ними S.

Формат вхідних даних:

Вхідний файл містить єдине число S (1<=S<=10000) – задана відстань.

Формат вихідних даних:

Єдиний рядок вихідного файла повинен містити відповідь – кількість розстановок тур.

Достеменно відомо, що кількість цифр у відповіді не перевищує 700.

Приклад вхідних та вихідних даних:

JAMMING.DAT

JAMMING.RES

2

4

 

 

 

Задача 2. Збирання мита (TALLAGE) -70 балів.

Король країни Аріїв завоював N міст на території сусідніх держав.

Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N – кількість міст у країні, а також цілі числа X та Yкоординати столиці.

Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.

Вихідні дані:

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

Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі:

<номер міста> => <номер міста>

При цьому столицю позначте номером 0.

Якщо відповідей декілька, виведіть одну довільну з них.

Приклади:

TALLAGE.DAT

TALLAGE.SOL

6 0 0

1 1

-1 1

0 2

1 -1

-1 -1

0 -2

8.485

2 3

3 1

1 0

0 4

4 6

6 5

Последнее обновление 09.09.11 13:08
 


Страница 22 из 27

Статистика

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

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

Нет