Масиви

          7.34. Визначити функцію для обчислення суми:

а) компонент з парними номерами;

б) компонент з непарними номерами;

в) додатніх компонент;

г) від’ємних компонент

дійсного вектора.

          7.35. Визначити процедури для

а) введення ;

б) виведення дійсного вектора.

          7.36. Визначити функції обчислення

а) середнього арифметичного компонент дійсного вектора;

б) норми дійсного вектора;

в) відстані між двома точками в n-вимірному евклідовому просторі;

г) скалярного добутку двох дійсних векторів.

          7.37. Визначити функції обчислення кількості компонент дійсного вектора

а) більших заданого числа;

б) які належать заданому відрізку прямої.

          7.38. Визначити функції обчислення

а) похідної від многочлена  в заданій точці х;

в) інтеграла многочлена Р_n(х) на заданому відрізку.

          7.39. Використавши підпрограму обчислення значення многочлена Р_n(х) з завдання 7.38 а) в заданій точці х, скласти алгоритм обчислення значень двох многочленів P(x)=1+x+x²+...+x²⁰, Q(x)=1-x+x²-...-x¹⁵.

          7.40. Скласти підпрограми для обчислення функцій

          

          

          

          

          

          

          

          

          

          

          

          7.41. Слід квадратної матриці - це сума її діагональних елементів. Визначити функцію обчислення сліду матриці .

          7.42. Визначити функцію для обчислення

а) визначника квадратної матриці;

б) ранга квадратної матриці.

Розв’язок а). Розв`язувати задачу будемо зведенням матриці до трикутного вигляду. Якщо в і-му рядку a_ii=0, то будемо шукати такий рядок j, в якомуa_ii<>0 Якщо такий рядок відсутній, то визначник дорівнює нулю, інакше міняємо місцями і-ий та j-ий рядки. Маємо

          функція  Визначник(А: масив[1..n,1..n] із дійсн): дійсн це

                   змін i,j,k,l:ціл ;c,p,b:дійсн;

          поч

                   р¬1; і¬0;

                    поки (p<>0)&(i<n) повт

                             i¬i+1; j¬n;

                             якщо А[і,і]=0 то

                                       поки (A[j,i]=0)&(j>i) повт

                                                j¬j-1

                                       кц;

                                       якщо j>i то

                                                 для l¬i до n повт

                                                           b¬A[i,l]; A[i,l]¬A[j,l]; A[j,l]¬b

                                                 кц

                                       кр

                             кр;

                             для k¬i+1 до j повт               {цикл до j}

                                       c¬A[k,i]/A[i,i];

                                      для l¬i до n повт

                                                 A[k,l]¬A[k,l]-A[i,l]*c

                                       кц

                             кц;

                             p¬p*A[i,i]

                    кц;

                    Визначник¬p

          кф;

Цикл, відмічений коментарем, виконується до j, а не до n, оскільки у рядках з номерами більшими, ніж j (якщо є такі), в i-му стовпчику стоїть нульовий елемент.

          7.43. Визначити функції для обчислення

а) суми усіх недіагональних елементів матриці;

б) кількості нульових елементів матриці.

          7.44. Визначити функції для обчислення:

а) суми двох векторів;

б) добутку вектора на число.

          7.45. Розглядаючи вектори А та В як послідовності цифр десяткового запису деяких невід`ємних цілих чисел, отримати вектор С - аналогічне представленя для суми цих двох чисел.

          7.46. Циклічним k-зсувом вектора (a₁,a₂,...,a_n) вліво називається вектор (a_k+1,...,a_n,a₁,...,a_k). Визначити функцію для його обчислення.

          7.47. Визначити циклічний k-зсув вправо та функцію для його обчислення.

          7.48. Скласти підпрограми

а) обміну значень двох векторів;

б) перестановки компонент вектора в зворотньому порядку.

          7.49. Визначити функцію обчислення вектора В за формулами , де а_і-компоненти заданого вектора А.

          7.50. Визначити функції для обчислення

а) суми; б) добутку

двох многочленів A(x)=a₀+a₁*x+...+a_n*xⁿ  i B(x)=b₀+b₁*x+...+b_m*x^m .

          7.51. Задано многочлен Р(х) з нульовим вільним членом. Знайти перші n коефіцієнтів розкладу 1/P(x) в ряд Тейлора в нулі.

          7.52. Скласти підпрограму обчислення частки Q(x) та залишку R(x) від ділення многочлена

          P(x)=p₀+p₁*x+...+p_n*xⁿ

на многочлен

          T(x)=t₀+t₁*x+...+t_m*x^m

P(x)=T(x)*Q(x)+R(x), deg(R)<deg(T), де deg - степінь много­члена.

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

          7.54. Задана дійсна матриця розміру m´n. Знайти вектор В, k-та компонента якого b_k це:

а) сума абсолютних величин елементів k-го рядка матриці;

б) добутку елементів k-го рядка;

в) значення середнього арифметичного елементів k-го рядка;

г) число від`ємних елементів в k-му рядку;

д) добутку квадратів тих елементів k-го рядка, модулі яких належать відрізку [1;1,5] (якщо таких елементів немає, то покласти b_k=1);

е) значення першого по порядку додатнього елемента k-го рядка (якщо таких елементів немає, то покласти b_k =10);

є) сума елементів, які знаходяться за першим від`ємним елементом в k-му рядку (якщо таких елементів немає, то покласти b_k=100).

          7.55. Скласти алгоритм “швидкого” обчислення числа Фібоначі (див. задвдання 3.10 з розд. 3) за його номером n, досліджуючи матричне відображення

          , n³2.

          Вказівка. Довести співвідношення

          ,

яке дозволяє звести задачу обчислення чисел Фібоначі до задачі обчислення степені заданої матриці 2-го порядку. Для швидкого обчислення степені використати метод, який було розглянуто у завданні 4.9 (розд. 4), замінюючи операцію множення чисел векторно-матричними операціями.

          7.56. Визначити підпрограми:

а) транспонування матриці;

б) множення матриці на вектор;

в) перестановки двох заданих рядків (стовпчиків) матриці;

г) перестановки заданого рядка матриці з заданим її стовпчиком;

д) побудови цілочисельної квадратної матриці порядку 7, елементами якої є числа 1, 2, ..., 49, розташовані в ній по спіралі;

е) видалення із матриці заданого рядка і заданого стовпчика.

          7.57. Задана дійсна квадратна матриця порядку 2n. Побудувати нову матрицю, переставляючи її блоки розміру n´n

а)                                    б)

Мал. 7.1

а) відповідно мал. 7.1 а);

б) відповідно мал. 7.1 б).

          7.58. Задані натуральне число m, цілі числа а₁, а₂,..., а_m і цілочисельна квадратна матриця порядку m. Рядок з номером і матриці назвемо відміченим, якщо a_і>0, і невідміченим у протилежному випадку.

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

б) підрахувати кількість від’ємних елементів матриці, розташованих у відмічених рядках.

          7.59. Задано дійсні матриці A, В, С, N порядку n, причому N - нульова матриця. Побудувати за цими матрицями матрицю D розміру 2n´3n  у вигляді

          D=.

          7.60. Побудувати функцію, яка виконує теоретико-множинні операції над підмножинами скінченної  універсальної множини, що складається з nелементів (n - задана константа).

Вказівка. Підмножини скінченної універсальної множини представити у вигляді бульового вектора Х довжини n, поклавши X(i)=Іст тоді і тільки тоді, коли, iÎX.

          7.61. Визначити процедуру пошуку заданого елемента матриці.

          7.62. Визначити процедуру пошуку

а) максимальної ; б) мінімальної

компоненти вектора.

          7.63. Визначити процедуру пошуку в заданому векторі компоненти:

а) більшої за задане число;

б) такої, що належить заданому відрізку на прямій.

          7.64. Визначити процедуру підрахунку кількості максимальних і мінімальних компонент вектора.

          7.65. Визначити процедуру одночасного обчислення максимальної і мінімальної серед компонент з парними і непарними номерами.

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

          7.67. Задані координати n точок на площині (x₁,y₁),...,(x_n,y_n). Знайти номери двох точок, відстань між якими найбільша (вважати, що така пара точок єдина).

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

          7.69. Визначити процедуру пошуку спільної компоненти двох векторів.

          7.70. Визначити процедуру пошуку в заданому векторі

а) двох компонент, що дорівнюють заданому числу;

б) двох нульових компонент, які йдуть підряд;

в) двох рівних компонент;

г) двох рівних компонент, які йдуть підряд;

д) компонент, що є числами Фібоначі.

          7.71. Визначити процедуру обчислення кількості інверсій в заданому векторі (тобто таких пар компонент, в яких більше число знаходиться зліва від меншого: x_i>x_j при i<j).

          7.72. Визначити функцію, яка перевіряє впорядкованість вектора за зростанням. (Вектор (a₁,a₂,...,a_n) впорядкований за зростанням, якщоa₁<a₂<...<a_n.).

          7.73. Визначити процедуру пошуку спільної компоненти двох впорядкованих векторів.

          7.74. Визначити процедуру перетворення дійсного вектора за наступним правилом: всі від'ємні компоненти вектора перенести в його початок, а всі інші - в кінець, зберігаючи початкове взаємне розташування як серед від'ємних, так і серед інших компонент.

          7.75. Визначити два впорядкованих за неспаданням вектори. Визначити процедуру об'єднання

а) всіх компонент;

б) спільних компонент

цих двох векторів у третій, щоб він знову став впорядкованим за неспаданням.

          7.76. Задана цілочисельна квадратна матриця порядку n і цілочисельний вектор довжини m. Замінити нулями в матриці ті елементи, для яких існують рівні серед компонент даного вектора.

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

а) що є в кожному магазині;

б) кожен з яких є хоча б в одному магазині;

в) яких немає в жодному магазині.

          7.78. Заданий вектор ГРУПА, компонентами якого ГРУПА(x) є множини імен людей із вказаного списку тих, що були в гостях у людини з ім'ям X(XÏГРУПА[X]).

Визначити процедуру пошуку хоча б одної людини, яка була в гостях в усіх інших людей, імена яких містяться в компонентах вектора ГРУПА.

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

          7.80. Заданий вектор ГР, компонентами якого ГР(х) є записи, що містять дані про людину з іменем Х із вказаного списку. Кожне дане складається з вказаної статі людини та її зросту. Визначити підпрограми для

а) обчислення середнього зросту жінок з групи ГР;

б) пошуку найвищого чоловіка;

в) перевірки, чи є в групі ГР дві людини, однакові на зріст.

          7.81. Заданий вектор ГР розмірності n, компонентами якого є записи, що містять анкети службовців деякого закладу. В кожній анкеті вказується прізвище службовця, його стать, дата народження у вигляді: число, місяць, рік. Визначити процедуру пошуку

а) найстаршого з чоловіків групи ГР;

б) людей з групи ГР, прізвища яких починаються з заданої літери.

          7.82. Заданий вектор розмірності n, компоненти якого містять інформацію про студентів деякого вузу. Відомості про кожного студента складаються з указання його прізвища, ім'я, по батькові, статі, віку, курсу. Визначити процедуру пошуку

а) найбільш поширених чоловічих та жіночих імен;

б) прізвищ та ініціалів усіх студентів, вік яких є найбільш поширеним.

          7.83. Заданий вектор розмірності n, компонентами якого є відомості про складання іспитів студентами деякого вузу. Інформація про кожного студента задана в слідуючому вигляді: прізвище, номер групи, оцінка_1, оцінка_2, оцінка_3. Визначити процедуру пошуку

а) студентів, що мають заборгованості хоча б з одного з предметів;

б) предмета, який було здано краще за усі інші;

в) студентів, що склали всі іспити на 5 і 4.

          7.84. Задано вектор С розміру n, компонентами якого є відомості про мешканців деяких міст. Інформація про кожного мешканця містить його прізвище, назву міста мешкання; адреси мешкання у вигляді: вулиця, будинок, квартира. Визначити процедуру пошуку двох будь-яких жителів із спискуС, що мешкають в різних містах за однаковою адресою.

          7.85. Задано вектор Рейс, компонентами якого Рейс(х) є множини міст із вказаного списку, в які можна за один рейс доїхати автобусом з міста х.Визначити процедуру пошуку множини міст, в які можна дістатися автобусом (за один рейс або через інші міста) із заданого міста.

          7.86. Визначити функцію обчислення норм дійсної матриці порядку n

          а), б) 

          7.87. Визначити процедуру обчислення у матриці

а) найменшого елемента;

б) найбільшого елемента;

в) суми елементів рядка, в якому розташований елемент з найменшим значенням;

г) суми найбільших значень елементів її рядків;

д) суми елементів рядків з від'ємним елементом головної діагоналі.

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

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

          .

Розв'язок. Оформимо підпрограму у вигляді функції, аргумент якої - дійсна матриця А

          функція Мін_Макс(А:масив [1..n,1..n] із дійсн): дійсн це

                   змін i,j:1..n; min,max:дійсн;

          поч

                   для i ¬ 1 до n повт

                             max¬ A[i,1];

                             для j¬ 2 до n повт

                                      якщо А[i,j]>max то

                                                max¬A[i,j]

                                      кр

                             кц;

                             якщо i=1 то min¬ max кр;

                             якщо min>max то

                                      min¬max

                             кр

                   кц;

                   Мін_Макс¬ min

          кф;

          7.90. Визначити процедуру пошуку в матриці

а) індексів усіх її ненульових елементів;

б) кількості усіх її різних елементів.

          7.91. Дана дійсна матриця розміру m´n. Визначити підпрограму побудови вектора, компонентами якого є

а) найменше значення елементів рядків;

б) різниці між найбільшим і найменшим значеннями елементів рядків;

в) найбільші із значень елементів рядків від початку до головної діагоналі включно.

          7.92. Елемент матриці називається "особливим", якщо:

          1) він більший за суму інших елементів свого стовпчика;

          2) в його рядку зліва від нього знаходяться елементи, менші за нього, а справа - більші.

Визначити процедуру пошуку числа "особливих" елементів матриці.

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

Визначити процедуру обчислення кількості сильних і слабких максимумів матриці.

          7.94. Визначити функцію перевірки матриці на симетричність.

Розв'язок. Умова симетричності квадратної матриці має вигляд: a_ij=a_ji для всіх i<j, i=1, 2, ..., n-1; j=i+1, i+2, ..., n. Тому задачу можна розглядати як задачу пошуку таких i, j, що a_ij¹a_ji. Якщо таких індексів немає, то матриця симетрична. Одержуємо

          функція Сим_матр (А: масив [1..n,1..n] із дійсн): бул це

                   змін i,j: ціл; Q: бул;

          поч

                   Q¬ і; i¬ 0;

                   поки Q & (i<n-1) повт

                             i¬ i+1; j¬ i;

                             поки Q & (j<n) повт

                                      j¬ j+1;

                                      Q¬A[i,j]=A[j,i]

                             кц

                   кц;

                   Сим_матр¬ Q

          кф;

          7.95. Визначити процедуру побудови за заданою матрицею А цілочисельного вектора b, присвоївши його k-ій компоненті значення 1, якщо виконується вказана нижче умова, і значення 0 в протележному випадку:

а) всі елементи k-го стовпчика однакові;

б) елементи k-го рядка матриці впорядковані за спаданням;

в) k-ий рядок матриці симетричний;

г) елемент k-го рядка, що належить головній діагоналі, симетричний;

д) елементи k-го рядка не перебільшують заданого числа x;

е) в k-му рядку матриці є хоча б один від’ємний елемент.

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

Вказівка. Знаходимо номер рядка k і номер стовпчика l, що містять найбільший елемент матриці. Потім міняємо місцями 1-ий і k-ий рядки, 1-ий і l-ий стовпчикі матриці.

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

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

          7.99. Визначити функцію, яка перевіряє, чи є задана цілочисельна квадратна матриця ортонормованою, тобто. такою, в якій скалярний добуток кожної пари різних рядків дорівнює 0, а скалярний добуток кожного рядка на себе дорівнює 1.

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

          7.101. Дана бульова матриця. Відомо, що множина істинних елементів є об’єднанням прямокутників, що не перетинаються. Скласти процедуру пошуку їхньої кількості.

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

          7.103. Задане деяке розташування чорних і білих пішаків (в довільній кількості) на шаховій дошці. Скласти процедуру підрахунку

а) кількості можливих ходів білими;

б) кількості взять білими;

в) кількості чорних і білих пішаків під боєм.

          7.104. Задані n точок площини. Провести коло, на якому лежить найбільша кількість точок даної множини.

          7.105. Задані n точок площини. Визначити процедуру підрахунку кількості рівнобічних трикутників з вершинами у ціх точках.

          7.106. Задані n точок площини. Визначити процедуру вибору трьох з них таких, щоб периметр трикутника з вершинами в цих точках був найбільшим.

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

а) знаходження кількості команд, що мають перемог більше, ніж поразок;

б) визначення номерів, що пройшли чемпіонат без поразок;

в) пошуку команд, що виграли більше половини ігор.

          7.108. Задана бульова матриця СУСIДИ, елементи якої СУСIДИ(a,b) рівні істині, якщо країни a і b мають спільний кордон, і хибності - в протилежному випадку. Скласти процедуру пошуку країни, що має найбільшу кількість сусідів серед перелічених країн.

          7.109. Задана дійсна матриця Т, елементи якої Т(x,y) означають середньомісячну температуру на острові x в місяці y. Скласти процедуру, що визначає який місяць і на якому острові серед переліченіх островів є найхолоднішим.

          7.110. Задана непротирічна таблиця спорідненості ТС, елементи якої ТС(x,y) можуть приймати значення із списку (син, дочка, батько, мати, ні). Наприклад, ТС(x,y)=ні, якщо y не є ні одним з батьків, ні родичем, ні дитиною x'_a, ТС(x,y)=син, якщо y - син x’_a і т.п. Скласти процедуру пошуку

а) будь-якої з онучок;

б) будь-якого з дядьків;

в) кількості двоюрідних братів і сестер

людини з ім'ям n із заданого списку.

          7.111. Знайти символ, який входить у рядок S найбільшу кільксть разів.

Вказівка: визначити масив з індексами символьного типу та елементами натурального типу, в якому обчислити та зберегти кількість входжень кожного символу у рядок S; знайти максимальний елемент цього масиву.