Однопроходные алгоритмы

Нужно обработать много чисел.

Если их можно не хранить все сразу, а брать по 1 числу и брать числа только 1 раз, то получим однопроходный алгоритм (single-pass algorithm)

Читаем числа и печатаем их

Даны числа через пробел. Прочитаем их и напечатаем по 1 числу на строке.

Вводим числа с клавиатуры:

50 20 100 120 70

Читаем числа и печатаем:

# будем читать много целых чисел через пробел
m = map(int, input().split())

# берем по 1 числу, читаем число в х
for x in m:
    print(x)    # печатаем 1 число

50
20
100
120
70

Нельзя прочитать эти числа 2 раза:

# будем читать много целых чисел через пробел
m = map(int, input().split())

# берем по 1 числу, читаем число в х
for x in m:
    print(x)    # печатаем 1 число

# этот цикл ничего печатать не будет. 
# Мы уже прочли числа. Второй раз их читать нельзя. 
for x in m:
    print(x)

Как удобно запускать задачи

Можно вводить числа не руками, а из файла. Это быстрее.

• Пусть программа в файле t1.py
• Сохраните числа в файле data.txt
• python3 t1.py < data.txt

БОЛЬШИЕ БУКВЫ

import turtle

# функция. Рисует большими буквами
def write(data):
    t.write(data, font=("*Sans", 24, "normal"))


t = turtle.Turtle()
t.width(5)

# рисуем большими буквами
write("Hello")

turtle.done()

Задача 1. Рисуем сколько надо пройти

Даны целые числа на 1 строке через пробел. Для каждого числа:

• прочитать число,
• передвинуть черепаху вперед на это число;
• написать сколько прошла черепаха

Задача 2. Сколько всего прошли от начала

Даны целые числа на 1 строке через пробел. Для каждого числа:

• прочитать число,
• передвинуть черепаху вперед на это число;
• написать сколько прошла черепаха от начала пути

Задача 3. Отдельные линии

Даны целые числа на 1 строке через пробел. Для каждого числа нарисовать отдельную линию и написать длину линии.

Задача 4. Средняя длина

Даны целые числа на 1 строке через пробел. Для каждого числа нарисовать отдельную линию и написать длину линии.

• найти среднее
• нарисовать другим цветом линию среднего размера и подписать ее длину

(50 + 40 + 100 + 120 + 70) / 5 = 380 / 5 = 76

Задача 5. Больше или меньше

Дано целое число. Нарисовать черную линию этой длины и написать длину.

На следующей строке даны целые числа на 1 строке через пробел. Для каждого числа нарисовать отдельную линию и написать длину линии.

Если эта линия равна или больше первой линии, то линия красная. Иначе линия синяя.

Задача 5b. Больше или меньше

В предыдущей задаче в конце напечатать сколько красных линий было нарисовано.

Как читать числа

все числа в 1 строке

• input() - прочитать 1 строку
• str.split() - разбить 1 строку str на последовательность слов
• map(функция, последовательность) - к каждому слову из последовательности применить функцию
• m = map(int, input().split())
  • прочитать строку;
  • разбить строку на последовательность слов;
  • к каждому слову применить функцию int();
  • полученную последовательность чисел записать в переменную m.

next - 1 элемент из последовательности

Функция next() берет 1 элемент из последовательности.

Этого элемента в последовательности больше нет.

m = map(int, input().split())   # m: 100 150 80 200
x = next(m)                     # m: 150 80 200      x:100
print('Первое число', x)
x = next(m)                     # m: 80 200          x:150
print('Второе число', x)
print('Остальные числа в цикле:')
for x in m:                     # m: 80 200
    print(x)

100 150 80 200

Первое число 100
Второе число 150
Остальные числа в цикле:
80
200

первая строка отдельно - None

a = None
m = map(int, input().split())   # m: 100 150 80 200

for x in m:                     # m: 80 200
    if a is None:
        print('Первое число', x)
        a = x
    else 
        print('Остальные числа в цикле:', x)

100 150 80 200

Первое число 100
Остальные числа в цикле: 150
Остальные числа в цикле: 80
Остальные числа в цикле: 200

Много строк через for

Если числа заданы по 1 числу на строку, то будем читать по 1 строке в цикле в переменную line и из line делать целые числа:

sys.stdin - это ввод с клавиатуры. В цикле перебираем до его конца.

Конец ввода с клавиатуры:

import sys
fp = sys.stdin
for s in fp:
    x = int(s)
    print(x)

Можно прочитать 1 строку s = next(fp)

import sys
fp = sys.stdin
s = next(fp)
print('Первая строка:', s)
for s in fp:
    x = int(s)
    print(x)

Много строк через readline

sys.readline() - прочитать 1 строку

import sys

fp = sys.stdin
s = fp.readline()
print('Первая строка:', s)
while s:
    print(s)
    s = fp.readline()

Отдельно первое число

Даны числа на 1 линии. Нарисовать первую линию green, остальные линии blue.

150 200 180 50 150 100 210

Длиннее предыдущей

Даны числа на 1 линии. Нарисовать первую линию green, остальные линии рисуем так:

• если эта линия больше предыдущей линии, то эта линия red
• иначе эта линия blue.

150 200 180 50 150 100 210

Самая длинная линия

Даны числа на 1 строке. Нарисовать первую линию green, остальные blue. Потом нарисовать самую длинную линию еще раз red.

150 200 180 50 150 100 210

Самая короткая линия

Даны числа на 1 линии. Нарисовать первую линию green, остальные blue. Потом нарисовать самую короткую линию еще раз red.

150 200 180 50 150 100 210

Находим максимум

Задача 6. max 2

Даны 2 целых числа на одной строке через пробел. Это длины линий.

• Первую линию - синим.
• первую линию - красным. (Сейчас она - самая длинная)
• Вторую линию - синим.
• Самую длинную - красным

Input	Рисунок
100 150
150 100

Задача 7. max 3

Даны 3 целых числа на одной строке через пробел. Это длины линий.

• Первую линию - синим.
• первую линию - красным. (Сейчас она - самая длинная)
• Вторую линию - синим.
• Самую длинную из уже нарисованных - красным
• Третью линию - синим.
• Самую длинную из уже нарисованных - красным
• Самую длинную из трех линий - зеленым.

Input	Рисунок
100 150 80

Задача 8. max

Даны целые числа на одной строке через пробел. Это длины линий.

• Для каждого числа
  • эту линию рисуем синим цветом
  • самую длинную линию рисуем красным цветом
• В конце рисуем самую длинную линию зеленым.

Input	Рисунок
100 150 80

Задача 9. min

Даны целые числа на одной строке через пробел. Это длины линий.

• Для каждого числа
  • эту линию рисуем синим цветом
  • самую короткую линию рисуем красным цветом
• В конце рисуем самую короткую линию зеленым.

Input	Рисунок
100 150 80

Задача 10. Читаем по строкам

Задача 3. Отдельные линии

Даны целые числа на 1 строке через пробел. Для каждого числа нарисовать отдельную линию и написать длину линии.

Задача для самостоятельной работы

Задача 1: отрезок [x1, x2] - сравнение с эталоном

Вариант 1a. Отрезки, меньше эталонного

Отрезки заданы Х координатами: начало и конец отрезка.

На одной строке даны х координаты начала и конца отрезка. Отрезков много.

• на первой строке задана ДЛИНА эталона. Рисовать не нужно.
• n - сколько дальше будет отрезков
• Для каждого следующего отрезка:
  • нарисовать отрезок синим, если он короче эталона
  • иначе нарисовать отрезок красным.
• (Дополнительно): написать сумму длин синих отрезков

Input:

100
4
50 100
-200 -50
-100 80
-50 50

Вариант 1.2. Сумма отрезков длинной не равной х

Отрезки заданы Х координатами: начало и конец отрезка.

На одной строке даны х координаты начала и конца отрезка. Отрезков много.

• на первой строке дана длина отрезка w0. Дальше даны отрезки
• Для каждого отрезка:
  • нарисовать отрезок красным, если его длина равна w0
  • иначе нарисовать отрезок синим.
• написать сумму длин синих отрезков

Input:

150
100 230
50 100
-200 -50
-70 80

Вариант 1.3. Отрезки, больше эталонного

Отрезки заданы Х координатами: начало и конец отрезка.

На одной строке даны х координаты начала и конца отрезка. Отрезков много.

• на первой строке задан эталон, нарисовать его черным.
• n - сколько дальше будет отрезков
• Для каждого следующего отрезка:
  • нарисовать отрезок синим, если он короче эталона
  • иначе нарисовать отрезок красным.
• (Дополнительно): сколько красных отрезков

Input:

100 230
4
50 100
-200 -50
-100 80
-50 50

Задача 2: положение относительно точки

Вариант 2.4. Сумма отрезков правее точки

Отрезки заданы Х координатами: начало и конец отрезка.

На одной строке даны х координаты начала и конца отрезка. Отрезков много.

• на первой строке дана точка х0. Нарисовать точку зеленым. t.dot(10)
• Дальше даны отрезки. Для каждого отрезка:
  • нарисовать отрезок красным, если он правее точки х0 (и начало и конец отрезка правее точки х0)
  • иначе нарисовать отрезок синим.
• написать сумму длин синих отрезков

Input:

30
100 230
50 100
-200 -50
-70 80

Вариант 2.2. Сколько отрезков левее точки

Отрезки заданы Х координатами: начало и конец отрезка.

На одной строке даны х координаты начала и конца отрезка. Отрезков много.

• на первой строке дана точка х0. Нарисовать точку зеленым. t.dot(10)
• Дальше даны отрезки. Для каждого отрезка:
  • нарисовать отрезок красным, если он левее точки х0 (и начало и конец отрезка левее точки х0)
  • иначе нарисовать отрезок синим.
• написать сколько синих отрезков

Input:

90
100 230
50 100
-200 -50
-70 80

Вариант 2.3. Сколько зеленых отрезков

Отрезки заданы Х координатами: начало и конец отрезка.

На одной строке даны х координаты начала и конца отрезка. Отрезков много.

• на первой строке дана точка х0. Нарисовать точку зеленым. t.dot(10)
• Дальше даны отрезки. Для каждого отрезка:
  • нарисовать отрезок красным, если он левее точки х0 (и начало и конец отрезка левее точки х0)
  • нарисовать отрезок синим, если он правее точки х0 (и начало и конец отрезка правее точки х0)
  • нарисовать отрезок зеленым, если он содержит точку х0
• написать сколько зеленых отрезков

Input:

90
100 230
50 100
-200 -50
-70 80

Задача 3: двигаем отрезки

Вариант 3.1. Выровнять по левому краю

Отрезки заданы Х координатами: начало и конец отрезка.

На 1 строке даны х координаты начала и конца отрезка. Отрезков много.

• Для каждого отрезка:
  • нарисовать синим отрезок
  • передвинуть отрезок так, чтобы его начало было в точке x=0, нарисовать отрезок красным.

Input:

3
100 230
-200 -50
-100 80

Вариант 3.2. Выровнять по правому краю

Отрезки заданы Х координатами: начало и конец отрезка.

На 1 строке даны х координаты начала и конца отрезка. Отрезков много.

• Для каждого отрезка:
  • нарисовать синим отрезок
  • передвинуть отрезок так, чтобы его КОНЕЦ было в точке x=0, нарисовать отрезок красным.

Input:

3
100 230
-200 -50
-100 80

Вариант 3.3. Выровнять по центру

Отрезки заданы Х координатами: начало и конец отрезка.

На 1 строке даны х координаты начала и конца отрезка. Отрезков много.

• Для каждого отрезка:
  • нарисовать синим отрезок
  • передвинуть отрезок так, чтобы его середина была в точке x=0, нарисовать отрезок красным.

Input:

100 230
-200 -50
-100 80

Часть 2

Задача 10. Ломанная одним цветом

Даны x, y координаты точки. По 1 точке на строку. 11 точек. Нарисовать линию от первой точки до последней.

Задача 11. Ломанная разными цветами

Даны x, y координаты точки. По 1 точке на строку. Всего 11 точек.

Нарисовать линию от первой точки до последней, менять цвет отрезка: "blue", "red", "gold", "green", "violet".

Без цикла for

Задача 12. Объемлющий отрезок

Даны координаты начала и конца отрезка по оси Х. 1 отрезок на 1 строке.

Нарисовать отрезки синим.

Нарисовать отрезок, который содержит все остальные отрезки. Напечатать его начало и конец.

Input:

100 230
50 100
-200 -50
-100 80

Задача 11. Максимальный квадрат

1 квадрат задан на 1 строке. х, y координаты верхней левой точки и длина стороны.

Дано много квадратов.

Нарисовать все квадраты линией.

Закрасить самый большой квадрат.

Задача 12. Минимальный квадрат

1 квадрат задан на 1 строке. х, y координаты верхней левой точки и длина стороны.

Дано много квадратов.

Нарисовать все квадраты линией.

Закрасить самый маленький квадрат.

Задача 13. Объемлющий прямоугольник x1, y1, x2, y2

1 прямоугольник задан на 1 строке. х, y координаты верхней левой точки и x, y координаты правой нижней точки.

Дано много прямоугольников.

Нарисовать синим все прямоугольники.

Нарисовать красным новый прямоугольник, в который входят все остальные прямоугольники.

Input:

-100 100 50 0
0 50 100 -100

Задача 14. Объемлющий прямоугольник x1, y1, w, h

1 прямоугольник задан на 1 строке. х, y координаты верхней левой точки, ширина и высота прямоугольника.

Дано много прямоугольников.

Нарисовать синим все прямоугольники.

Нарисовать красным новый прямоугольник, в который входят все остальные прямоугольники.

-100 100 300 100
0 50 100 300

Задача 15. Больше предыдущего

Даны высоты точек Y. Нарисуйте линию по этим точкам. Отрезок вверх рисуйте красным. Отрезок вниз синим. Горизонтальный отрезок черным.

Input:

100 150 120 200 220 220 190 170

Задача 16. Второй максимум

Даны числа через пробел. Найти максимальное число и второй максимум.

Задача 17. Правильные скобки

Дана строка из скобок.

Напечатать YES, если скобки расставлены правильно и NO, если неправильно.

• больше предыдущего:
  

Attachment	Action	Size	Date	Who	Comment
0path.png	manage	2.3 K	26 Sep 2018 - 20:47	TatyanaDerbysheva	задача 1
1sum.png	manage	2.7 K	26 Sep 2018 - 20:53	TatyanaDerbysheva	сумма чисел
2lines.png	manage	2.3 K	26 Sep 2018 - 21:07	TatyanaDerbysheva	отдельные линии
3avr.png	manage	3.0 K	26 Sep 2018 - 21:20	TatyanaDerbysheva	средняя длина
4more.png	manage	3.1 K	27 Sep 2018 - 14:24	TatyanaDerbysheva	больше меньше
4more2.png	manage	4.2 K	29 Sep 2018 - 19:42	TatyanaDerbysheva	больше меньше сколько
max2_1.png	manage	2.2 K	29 Sep 2018 - 19:43	TatyanaDerbysheva	max2 - 100 150
max2_2.png	manage	2.0 K	29 Sep 2018 - 19:43	TatyanaDerbysheva	max2 - 150 100
max3.png	manage	3.6 K	29 Sep 2018 - 19:58	TatyanaDerbysheva
min3.png	manage	3.5 K	29 Sep 2018 - 20:05	TatyanaDerbysheva
self_aling_left.png	manage	5.9 K	29 Sep 2018 - 21:14	TatyanaDerbysheva
self_align_center.png	manage	5.7 K	29 Sep 2018 - 21:18	TatyanaDerbysheva
self_short.png	manage	6.8 K	29 Sep 2018 - 21:40	TatyanaDerbysheva
segments.png	manage	2.9 K	06 Oct 2018 - 21:56	TatyanaDerbysheva
segments_color.png	manage	4.1 K	06 Oct 2018 - 22:00	TatyanaDerbysheva
self_eq.png	manage	3.9 K	06 Oct 2018 - 22:18	TatyanaDerbysheva
self_right.png	manage	4.5 K	06 Oct 2018 - 22:36	TatyanaDerbysheva
self_left.png	manage	4.5 K	06 Oct 2018 - 22:41	TatyanaDerbysheva
seg_enclose.png	manage	8.4 K	06 Oct 2018 - 22:55	TatyanaDerbysheva
15_increase.png	manage	4.6 K	09 Oct 2018 - 10:13	TatyanaDerbysheva	больше предыдущего