Робота з масивами

1. Масиви

1. Дано масив A[1..15]. Скласти програму заміни всіх його  елементів, що більші 10 на нулі.

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

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

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

5. Дано  масив  A[1..2N].  Скласти  програму   знаходження   різниці   сум елементів першої та другої половини масиву.

6.  Дано  лінійну  таблицю  із  n  дійсних  чисел.  Замінити  від'ємні елементи їх квадратами.

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

8. Із елементів масиву (a1,a2,...,a20) складіть масив B, елементи якого по модулю більші деякого значення С(|a|>c).

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

10. Провірити, чи є в одномірному числовому масиві  хоча  б  одна  пара сусідніх чисел, які ї протилежними.

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

12. Визначити в одномірному числовому масиві число сусідства із двох чисел різного знаку.

13. Для заданого масиву A(N) знайти  суму  всіх  елементів,  не  більших заданого числа N.

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

15. Визначити в одномірному числовому масиві суми додатних і  від'ємних елементів.

16. Провірити, чи ї в даному одномірному числовому масиві хоча  б  одна пара чисел, які співпадають по величині.

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

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

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

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

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

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

23. Дано лінійний масив A[1..M].Скласти програму заміни елементів з  непарними номерами на їх квадрати.

24. Скласти програму заміни в прямокутному масиві A[1..k] всіх елементів, що більші від 10 на нулі.

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

26.  Визначити  в  одномірному  числовому  масиві  число   сусідств   з взаємо-обернених чисел.

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

29. Даний одномірний  числовий  масив.  Визначити  суму  всіх чисел.

2.Масиви (Серйозні розважалки)

1. Барон Мюнхаузен, вийшовши на екологічно чисте по­лювання, зарядив свою рушницю кісточками вишень. Після того як він вдало влучив поміж роги оленям, в яких влучило відповідно k₁,k₂,...,k_N кісточок, у них на головах виросли чудові молоді вишеньки. Скільки нових саджанців зміг подарувати барон Мюнхаузен садівникам-дослідникам?

2. Мама розвела оранжерею кактусів, деякі з яких були колючі, а інші - ні. Маленька донечка Яринка вирішила, що голки на кактусах - це надто зухвало, і тому старанно поголила їх бритвою. Добре, що у мами залишився записник, в якому всі кактуси були позначені кількістю голочок α₁,α₂,..., α_N (голі кактуси були позначені 0). Скількох кактусів не торкнулася рука юної перукарки?

3. Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від'ємними числами, а дівчаток - додатними у вигляді цілих значень α₁,α₂,..., α_N ? Окрім того, у всіх дівчаток на голівках зав'язані бантики заввишки 10 см, а висота паркану H см.

4. Маленький онучок вирішив допомогти бабусі підстригти квіти у її дорогоцінному квітнику, зрізавши лише бутони та квіточки на них. На щастя, кмітливий хлопчик зрізав лише ті квіти, які були заввишки від h₁ см до h₂, см від землі. Скільком квіточкам пощастило бути підстриженими, якщо висота їх у сантиметрах становить α₁,α₂,..., α_N ?

5. Коли барон Мюнхаузен вирішив пообідати, він прив'язав до довгої мотузки шматок сала і закинув його у повітря. Зграя диких гусей, що пролітала тим часом над помешканням барона, заціка­вилася незвичним предметом і найстарший гусак, що очолював зграю, проковтнув його. Не встиг він насолодитися відчуттям ситості, як шматок сала проскочив через нього і зник у дзьобі другого гусака і т.д. Тепер доля обіду барона Мюнхаузена залежала лише від довжини мотузки! Скільки кілограмів підсмаженої гусятини було подано на обід барона Мюнхаузена, якщо довжина мотузки становила L см, N гусей летіли на відстані h см один від одного, довжина кожного з них дорівнює k см, а вага цих гусей у кілограмах становила m₁,m₂,...,m_N ?

6. Маленький Дмитрик щомісяця виростає на 2 cм, а у бабусі в комірчині облаштовано полички з різними ласощами - варенням, джемом, повидлом. Акуратистка бабуся записувала висоту і наступний порядковий номер у свій записник кожної нової полички в тій послідовності, як вона з'являлася у комірчині завдяки дідусеві. Висота цих поличок була а1, а2, ... аN, см. Нові полички дідусь прибивав, де йому заманеться - вище, нижче і між тими, що вже були. З'ясувати, через скільки місяців до яких поличок, враховуючи їх порядок запису в бабусиній книжці, добереться Дмитрик (наприклад, спочатку до п'ятої, занотованої у записнику, потім до другої і т.д.), якщо він відкрив для себе бабусину комірчину, коли його зріст був Н1 см, а доросте Дмитрик до H2 см.

7. Велосипедист-початківець Павлуша виїхав на широку дорогу. Але їхати інакше, ніж за законом синусоїди, йому ніяк не вдавалося. Юний спортсмен стартував у точці Х0 на осі ОХ, а центри основ стовпів знаходяться у точках х1,х2,...,хn на цій же осі, яку перетинає синусоїда руху велосипедиста. Скільки стовпів трапляться на шляху Павлуші, якщо шириною стовпа можна знехтувати?

8. Завзятий водій Василь Іванович вирішив поставити рекорд пе­регонів між містом Мляшем та містом Пляшем. Спочатку він придбав карти розташування заправок пальним на шляху між Мляшем та Пляшем, де відстань між заправками була позначена числами а1,а2,...,аN а потім побився об заклад зі своїми друзями, що вста­новить рекорд за Т год. Одна проблема турбувала Василя Івановича: об'єм бака для пального складав К л, а запасної каністри у нього не було. Витрати пального в дорозі становили 1л на 10 км шляху. Для еко­номії часу Василь Іванович на кожній заправці визначав, чи варто вит­рачати 10 хв. на дозаправку, чи можна доїхати до наступної заправки на залишках пального у баці. Чи зможе Василь Іванович встановити рекорд, якщо перша заправка знаходиться у місті Мляші, остання - у місті Пляші, а сам Василь Іванович їде зі сталою швидкістю ν км/год? Чи може таке статися, що Василь Іванович взагалі не доїде до міста Пляша?

9. Лікар-психіатр призначив Сергійкові лікування від лайливих слів. Виконуючи поради психіатра, хворий повинен був записувати у таблицю по днях упродовж місяця кількість використаних ввічливих слів «Дякую», «Пробачте», «Прошу». У який день місяця друзям Сергійка повезло на ввічливі слова найбільше? Якого дня місяця у хлопчика був найгірший настрій? Які ввічливі слова Сергійкові найбільше до вподоби?

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;

}

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

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

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 м² площі острова? Скільком новим Робінзонам ще вистачить місця на острові, якщо поблизу трапиться ще одна аварія?

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

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

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

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

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

(101)₂=1*2²+0*2¹+1*2⁰=4+0+1=5

(1001)₂=1*2³+0*2²+0*2¹+1*2⁰=8+0+0+1=9

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

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

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

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

2. Задача  BINARY

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

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

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

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число 19₁₀ = 1×2⁴+0×2³+0×2²+1×2¹+1×2⁰ в двійковій  системі запишеться як 10011₂). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри буде число 1×2⁴+1×2³+1×2²+0×2¹+0×2⁰ = 28.

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

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

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

Приклад

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»

Приклад:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.

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

7.

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

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

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, якщо такого шляху не існує.

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

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

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

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