Практика 4
Оценка сложности эвристических алгоритмов 

1. Для двух заданных списков определить общие элементы, записать их в новый список. Каждый из трех списков вывести в строку, отделяя от других пустой строкой.

2. Из элементов заданного списка, больших заданного числа, образовать новый список.

3. В списке из 2n чисел найти сумму квадратов элементов с четными индексами и сумму кубов элементов с нечетными индексами.

4. Определить для заданного числа частоту (в долях от общего количества чисел), с которой оно встречается в списке.

5. Главная диагональ матрицы Вам дается целое число n. Выведите матрицу размера nxn, в которой все элементы 0, кроме главной диагонали, на которой стоят 1. (Главная диагональ квадратной матрицы состоит из элементов с индексами i и j, в которых i=j. То есть это элементы с индексами 00, 11, 22 и т.д.)

Входные данные: 5
Выходные данные:
[1, 0, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]

n = int(input())
matrix = []
#ваш код
for i in range(n):
  print(matrix[i])

6. Раскраска шахматной доски В этом задании вам предстоит раскрасить шахматную доску размера nхn в черный и белый цвета. Элемент с индексом [0][0] раскрасьте в белый цвет, а далее в шахматном порядке. Для обозначения черного цвета используйте символ "b", для обозначения белого цвета — символ "w".

Входные данные: 4
Выходные данные:
['w', 'b', 'w', 'b']
['b', 'w', 'b', 'w']
['w', 'b', 'w', 'b']
['b', 'w', 'b', 'w']
Код
matrix = []
n = int(input())
for i in range(n):
  matrix.append([])
  for j in range(n):
    matrix[i].append("")
# место для вашего кода
# Не удаляйте код ниже, он нужен для проверки
for i in range(n):
    print(matrix[i])

7. Обратная диагональ матрицы. Мы решали задание с заполнением главной диагонали, а теперь нам предстоит сделать аналогичную вещь для обратной (побочной) диагонали. Выведите матрицу размера nхn с такими элементами: все значения, стоящие на обратной (побочной) диагонали, равны 1, остальные - 0. (Побочная диагональ квадратной матрицы размера nхn состоит из элементов с индексами ij, в которых i+j=n-1. То есть в данном случае это элементы с индексами 04, 13, 22, 31, 40.)

Входные данные: 5
Выходные данные:
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 1, 0, 0, 0]
[1, 0, 0, 0, 0]

Код
matrix = []
n = int(input())
# Не удаляйте код ниже, он нужен для проверки
for i in range(n):
  print(matrix[i])

Классы задач P и NP. 
Основы теории графов. 
Представления графов: матрица смежности, весовая матрица.
Задача Прима — Краскала. 
Задача коммивояжёра. 
Метод грубой силы.
«Жадные» алгоритмы. 
Локальный поиск. 
Алгоритм Дейкстры. 
Метод ветвей и границ. 
Алгоритм Литтла. 
Метод случайных перестановок. 
Алгоритм Флойда — Уоршелла. 
Подготовка тестового набора данных. 
Запись алгоритмов псевдоалгоритмическом языке и на языке программирования. 
Количество элементарных операций в алгоритме. 
Временная и асимптотическая сложности алгоритмов. 
Сравнение алгоритмов по сложности. 

• Перейти — Стандартный документ «Описание программы»