двовимірні масиви
Обробка і висновок вкладених списків
Часто в задачах доводиться зберігати прямокутні таблиці з даними. Такі таблиці називаються матрицями або двовимірними масивами. У мові програмування Пітон таблицю можна представити у вигляді списку рядків, кожен елемент якого є в свою чергу списком, наприклад, чисел. Наприклад, створити числову таблицю з двох рядків і трьох стовпців можна так:
Тут перший рядок списку A [0] є списком з чисел [1, 2, 3]. Тобто A [0] [0] == 1. значення A [0] [1] == 2. A [0] [2] == 3. A [1] [0] == 4. A [1 ] [1] == 5. A [1] [2] == 6.
Для обробки і виведення списку як правило використовується два вкладених циклу. Перший цикл по номеру рядка, другий цикл по елементах всередині рядка. Наприклад, вивести двовимірний числовий список на екран через підрядник, розділяючи числа пробілами всередині одного рядка, можна так:
Те ж саме, але цикли не по індексу, а за значеннями списку:
Природно для виведення одного рядка можна скористатися методом join.
Використовуємо два вкладених циклу для підрахунку суми всіх чисел в списку:
Або те ж саме з циклом не по індексу, а за значеннями рядків:
створення списку
Нехай дано два числа: кількість рядків n і кількість стовпців m. Необхідно створити список розміром n × m. заповнений нулями.
Очевидне рішення виявляється невірним:
У цьому легко переконатися, якщо присвоїти елементу A [0] [0] значення 1. а потім вивести значення іншого елемента A [1] [0] - воно теж дорівнюватиме 1! Справа в тому, що [0] * m повертає Посилання на список з m нулів. Але подальше повторення цього елемента створює список з n елементів, які є посиланням на один і той же список (точно так само, як виконання операції B = A для списків не створює новий список), тому всі рядки результуючого списку насправді є однією і тієї ж рядком.
Таким чином, двовимірний список можна створювати за допомогою операції повторення одного рядка. Що ж робити?
Перший спосіб: спочатку створимо список з n елементів (для початку просто з n нулів). Потім зробимо кожен елемент списку посиланням на інший одновимірний список з m елементів:
Інший (але схожий) спосіб: створити порожній список, потім n раз додати в нього новий елемент, який є списком-рядком:
введення списку
Нехай програма отримує на вхід двовимірний масив, у вигляді n рядків, кожен з яких містить m чисел, розділених пробілами. Як їх рахувати? Наприклад, так:
Або, без використання складних вкладених викликів функцій:
Складний приклад обробки масиву
Нехай дано квадратний масив з n рядків і n стовпців. Необхідно елементів, що знаходяться на головній діагоналі, що проходить з лівого верхнього кута в правий нижній (тобто тих елементів A [i] [j]. Для яких i == j) присвоїти значення 1. елементів, що знаходяться вище головної діагоналі - значення 0, елементів, що знаходяться нижче головної діагоналі - значення 2. тобто отримати такий масив (приклад для n == 4):
Розглянемо кілька способів вирішення цього завдання. Елементи, які лежать вище головної діагоналі - це елементи A [i] [j]. для яких i
Даний алгоритм поганий, оскільки виконує одну або дві інструкції if для обробки кожного елемента. Якщо ми усложним алгоритм, то ми зможемо обійтися взагалі без умовних інструкцій.
Спочатку заповнимо головну діагональ, для чого нам знадобиться один цикл:
Потім заповнимо значенням 0 всі елементи вище головної діагоналі, для чого нам знадобиться в кожній з рядків з номером i привласнити значення елементів A [i] [j] для j = i + 1. n-1. Тут нам знадобляться вкладені цикли:
Аналогічно присвоюємо значення 2 елементам A [i] [j] для j = 0. i-1.
Можна також зовнішні цикли об'єднати в один і отримати ще одне, більш компактне рішення:
А ось таке рішення використовує операцію повторення списків для побудови чергового рядка списку. i -я рядок списку складається з i чисел 2. потім йде одне число 1. потім йде n-i-1 число 0.
вправи
A: Максимум
Знайдіть індекси першого входження максимального елемента. Виведіть два числа: номер рядка та номер стовпчика, в яких варто найбільший елемент в двовимірному масиві. Якщо таких елементів декілька, то виводиться той, у якого менше номер рядка, а якщо номери рядків рівні то той, у якого менше номер стовпчика.
Програма отримує на вхід розміри масиву n і m. потім n рядків по m чисел в кожній.
K: Поміняти дві діагоналі
Дан квадратний масив. Поміняйте місцями елементи, які стоять на головній і побічної діагоналі, при цьому кожен елемент повинен залишитися в тому ж стовпці (тобто в кожному стовпці потрібно поміняти місцями елемент на головній діагоналі і на побічної діагоналі).
Рішення оформите у вигляді функції SwapDiagonals (A).
L: Кінотеатр
В кінотеатрі n рядів по m місць в кожному. У двовимірному масиві зберігається інформація про продані квитки, число 1 означає, що квиток на дане місце вже продано, число 0 означає, що місце вільно. Надійшов запит на продаж k квитків на сусідні місця в одному ряду. Визначте, чи можна виконати такий запит.
Програма отримує на вхід числа n і m. Далі йде n рядків, що містять m чисел (0 або 1), розділених пробілами. Потім дано число k.
Програма повинна вивести номер ряду, в якому є k поспіль вільних місць. Якщо таких рядів кілька, то виведіть номер найменшого відповідного ряду. Якщо відповідного ряду немає, виведіть число 0.
M: Трикутник Паскаля - 1
Дано два числа n і m. Створіть масив n × m і заповніть його за такими правилами:
Числа, які стоять в рядку 0 або в стовпці 0 рівні 1 (A [0] [j] = 1. A [i] [0] = 1). Для всіх інших елементів масиву A [i] [j] = A [i-1] [j] + A [i] [j-1]. тобто кожен елемент дорівнює сумі двох елементів, що стоять зліва і зверху від нього.
Виведіть даний масив на екран, відводячи на висновок кожного елемента масиву рівно 6 символів (див. Приклад).
N: Трикутник Паскаля - 2
Трикутник Паскаля складається з чисел, де кожне число дорівнює двом числам, що стояв над ним. Якщо перенумерувати рядка трикутника Паскаля з нуля, то \ (i \) - я рядок містить \ (i + 1 \) число, які дорівнюють \ (C_i ^ j \), де \ (j \ in [0, i] \) .
За даним числу \ (n \) створіть список з \ (n \) рядків, де \ (i \) - й елемент списку повинен бути списком, що містить \ (i + 1 \) число - елементи \ (i \) - й рядки трикутника Паскаля.
Заповніть цей масив числами трикутника Паскаля. Виведіть результат на екран відводячи на висновок одного числа рівно 6 символів.
O: Ходи коня
На шахівниці стоїть кінь. Відзначте положення коня на дошці і всі клітини, які б'є кінь.
Програма отримує на вхід координати коня на шахівниці в шаховій нотації (тобто у вигляді "e4", де спочатку записується номер стовпця (буква від "a" до "h", зліва направо), потім номером рядка (цифра від 1 до 8 , знизу вгору).
Клітку, де стоїть кінь, відзначте буквою "K", клітини, які б'є кінь, відзначте символами "*", решта клітини заповніть точками.
Виведіть на екран зображення дошки.
P: Ходи ферзя
Вирішіть попередню задачу для ферзя. Ферзь позначається буквою "Q".
Q: Заповнення змійкою
За даними числах n і m заповніть двовимірний масив розміром n × m числами від 1 до n × m "змійкою", як показано в прикладі. Виведіть отриманий масив, відводячи на висновок кожного елемента рівно 4 символу.
R: Заповнення діагоналями
За даними числах n і m заповніть двовимірний масив розміром n × m числами від 1 до n × m "діагоналями", як показано в прикладі. Виведіть отриманий масив, відводячи на висновок кожного елемента рівно 4 символу.
V: Заповнення в шаховому порядку
Дано числа n і m. Заповніть масив розміром n × m в шаховому порядку: клітини одного кольору заповнені нулями, а іншого кольору - заповнені числами натурального ряду зверху вниз, зліва направо. У лівому верхньому кутку записано число 1.
Виведіть отриманий масив на екран, відводячи на висновок кожного елемента рівно 4 символу.