основы_программирования_на_языке_python. Министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего
 Скачать 208.8 Kb.
|
|
Задача 4: Коровы Дано число n<100. Закончите фразу “На лугу пасется…” одним из возможных продолжений: “n коров”, “n корова”, “n коровы”, правильно склоняя слово “корова”. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно натуральное число n, n<100. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести введенное число n и одно из слов: korov, korova или korovy. Между числом и словом должен стоять ровно один пробел. ПРИМЕРЫ
РЕШЕНИЕ Слово "коров" выводится, если n заканчивается цифрой 5, 6, 7, 8, 9, 0 или если число десятков в числе n равно 1. Слово "корова" выводится, если n заканчивается цифрой 1. Слово "коровы" выводится во всех остальных случаях. n = int(input()) if 5 <= n % 10 <= 9 or n % 10 == 0 or n // 10 == 1: print(n, "korov") elif n % 10 == 1: print(n, "korova") else: print(n, "korovy") Задача 5: Количество положительных элементов списка Напишите программу, которая подсчитывает количество положительных элементов в данном списке. ВХОДНЫЕ ДАННЫЕ Программа получает на вход несколько чисел (не более 100000), записанных в одной строке через пробел. Все числа по модулю не превосходят 109. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести единственное число - количество положительных чисел среди данных. ПРИМЕР
Конец формы РЕШЕНИЕ Присвоим переменной ans значение 0. Пройдем циклом по всем элементам списка. Если элемент больше нуля, то нужно увеличить переменную ans на 1. A = list(map(int, input().split())) ans = 0 for elem in A: if elem > 0: ans += 1 print(ans) Задача 6: Наименьший положительный элемент списка Напишите программу, которая находит в данном списке наименьший положительный элемент. ВХОДНЫЕ ДАННЫЕ Программа получает на вход несколько чисел (не более 100000), записанных в одной строке через пробел. Все числа по модулю не превосходят 109. Среди чисел есть хотя бы одно положительное. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести единственное число - наименьшее положительное число среди данных. ПРИМЕР
РЕШЕНИЕ Запишем в ans значение, которое не меньше всех элементов списка, например, 109. Пройдем циклом по всем элементам списка. Если элемент больше нуля и меньше ans, то запишем в переменную ans значение элемента списка. A = list(map(int, input().split())) ans = 10 ** 9 for elem in A: if 0 < elem < ans: ans = elem print(ans) Задача 7: Сумма чисел в файле (одно число в строке) Ограничение по времени работы программы: 1 секунда В каждой строке текстового файла записано одно целое число. Посчитайте сумму чисел в файле и выведите результат в другой файл. ВХОДНЫЕ ДАННЫЕ Входные данные к этой задаче записаны в файле input.txt. Файл содержит не более 100000 строк, в каждой строке записано одно целое число, не превосходящее по модулю 109. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести в файл output.txt сумму всех чисел во входном файле. ПРИМЕР
РЕШЕНИЕ Откроем файл на чтение. Считаем все строки файла при помощи метода readlines() в список. Пройдем циклом по всем элементам списка, преобразовывая элементы списка к типу int и подсчитывая их сумму. Выведем результат в файл output.txt. inf = open("input.txt", "r") A = inf.readlines() inf.close() s = 0 for elem in A: s += int(elem) ouf = open("output.txt", "w") ouf.write(str(s) + "\n") ouf.close() Задача 8: Сумма чисел в файле (несколько чисел в строке) Ограничение по времени работы программы: 1 секунда В каждой строке текстового файла записано одно или несколько целых чисел, разделенных пробелами. Посчитайте сумму чисел в файле и выведите результат в другой файл.[ CITATION Кир \l 1049 ] ВХОДНЫЕ ДАННЫЕ Входные данные к этой задаче записаны в файле input.txt. В каждой строке файла записано одно или несколько целых чисел, не превосходящее по модулю 109, через пробел. Общее количество чисел не превосходит 100000. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести в файл output.txt сумму всех чисел во входном файле. ПРИМЕР
РЕШЕНИЕ В этой задаче удобней считать файл целиком при помощи метода read() и разбить на отдельные числа при помощи метода split(). Затем преобразовать все элементы полученного списка в числа и подсчитать их сумму. inf = open("input.txt", "r") A = inf.read().split() inf.close() s = 0 for elem in A: s += int(elem) ouf = open("output.txt", "w") ouf.write(str(s) + "\n") ouf.close() Задача 9: Неправильные числа Фибоначчи Ограничение по времени работы программы: 1 секунда Зададим «неправильные» числа Фибоначчи, в которых n-е число равно сумме n−1-го и n−3-го. Более формально, F0=F1=F2=1, Fn=Fn−1+Fn−3, при n>2. Вычислите n-е «неправильное» число Фибоначчи. Попробуйте реализовать рекурсивную функцию, даже если вы знаете другие (более эффективные) способы вычисления. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно целое число n, 0≤n≤35. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно искомое число. ПРИМЕР
РЕШЕНИЕ Необходимо аккуратно запрограммировать рекуррентные соотношения. def fib(n): if n <= 2: return 1 else: return fib(n - 1) + fib(n - 3) print(fib(int(input()))) Задача 10: Функция Аккермана Ограничение по времени работы программы: 1 секунда В теории вычислимости важную роль играет функция Аккермана A(m,n) от двух параметров (неотрицательных целых чисел), определенная следующим образом: A(m,n)=n+1, при m=0, A(m,n)=A(m−1,1), при m>0, n=0, A(m,n)=A(m−1,A(m,n−1)), при m>0, n>0. По данным m и n вычислите A(m,n). ВХОДНЫЕ ДАННЫЕ Программа получает на вход два целых неотрицательных числа m и n, записанных в отдельных строчках. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести значение A(m,n). Известно, что результат не превосходит 100000. ПРИМЕР
РЕШЕНИЕ Необходимо аккуратно запрограммировать условия задачи. При решении на языке Python придется увеличить максимальную глубину рекурсии при помощи sys.setrecursionlimit. import sys sys.setrecursionlimit(5000) def A(m, n): if m == 0: return n + 1 if m > 0 and n == 0: return A(m - 1, 1) if m > 0 and n > 0: return A(m - 1, A(m, n - 1)) m = int(input()) n = int(input()) print(A(m, n)) Задача 11: k-е простое число Ограничение по времени работы программы: 1 секунда По данному числу k найдите k-е по счету простое число. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно целое число k, 1≤k≤1000. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести k-е простое число. ПРИМЕР
РЕШЕНИЕ Значение k невелико, поэтому задачу можно решить перебором. Будем перебирать все натуральные числа, начиная с 2, проверять каждое число на простоту и подсчитывать количество найденных простых чисел. Когда будет найдено k простых чисел, выведем последнее найденное простое число. def IsPrime(n): d = 2 while d * d <= n and n % d != 0: d += 1 return d * d > n k = int(input()) n = 2 while k > 0: if IsPrime(n): k -= 1 n += 1 print(n - 1) Задача 12: Гипотеза Гольдбаха Ограничение по времени работы программы: 1 секунда Гипотеза Гольдбаха утверждает, что любое чётное число (кроме 2) можно представить в виде суммы двух простых чисел. Эта гипотеза не доказана и не опровергнута до сих пор. Для данного чётного числа n выведите его представление в виде суммы двух простых. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно целое чётное число n, 2≤n≤106. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести два простых числа, дающих в сумме n. ПРИМЕР
РЕШЕНИЕ Данную задачу можно решить перебором возможных представлений числа n в виде суммы двух чисел. Будем перебирать все возможные представления числа n в виде двух слагаемых. Если одно слагаемое равно d, то другое слагаемое будет n−d. Перебор будем продолжать, пока оба слагаемых не станут простыми. Можно отдельно разобрать случай n=4, в этом случае выведем числа 2 2, а при n>4 будем перебирать только нечётные значения d. def IsPrime(n): d = 2 while d * d <= n and n % d != 0: d += 1 return d * d > n n = int(input()) if n == 4: print(2, 2) else: d = 3 while not IsPrime(d) or not IsPrime(n - d): d += 1 print(d, n - d) Задача 13: Количество простых чисел на отрезке Ограничение по времени работы программы: 1 секунда Определите количество простых чисел на отрезке [a,b]. ВХОДНЫЕ ДАННЫЕ Программа получает на вход два целых числа a и b, 1≤a≤b≤106. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести количество простых чисел p на отрезке [a,b] (то есть количество таких простых p, что a≤p≤b). ПРИМЕР
РЕШЕНИЕ Будем использовать решето Эратосфена. Создадим массив IsPrime, заполнив значениями True/False (или 1/0), отмечая простые числа. После этого посчитаем количество целых чисел среди элементов с индексами от a до b (включительно). N = 1000000 IsPrime = [True] * (N + 1) IsPrime[0] = False IsPrime[1] = False p = 2 while p * p <= N: if IsPrime[p]: for i in range(p * p, N + 1, p): IsPrime[i] = False p += 1 a = int(input()) b = int(input()) print(sum(IsPrime[a:b + 1])) Задача 14: Дружественные числа Ограничение по времени работы программы: 2 секунды Два различных числа n и m называются дружественными, если сумма делителей числа n (включая 1, но исключая само n) равна числу m и наоборот. Например, 220 и 284 — дружественные числа. По данному числу n найдите все пары дружественных чисел, не превосходящих числа n. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно целое число n, 1≤n≤20000. ВЫХОДНЫЕ ДАННЫЕ Выведите все пары дружественных чисел, каждое из которых не превосходит n. Пары необходимо выводить по одной в строке, разделяя числа в паре пробелом. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает). ПРИМЕР
РЕШЕНИЕ Будем перебирать все числа a, не превосходящие n. Посчитаем сумму делителей числа a и запишем её в переменную b. Если b≤n, то посчитаем сумму делителей числа b, если она равна a, то выведем пару a, b. Для того, чтобы каждая пара выводилась ровно один раз, нужно поставить условие a Также необходимо реализовать алгоритм определения суммы делителей числа a так, чтобы он работал за a√, для чего делители нужно перебирать до значения a√. def divisors(n): ans = 1 d = 2 while d * d < n: if n % d == 0: ans += d ans += n // d d += 1 if d * d == n: ans += d return ans n = int(input()) for a in range(2, n + 1): b = divisors(a) if a < b <= n and divisors(b) == a: print(a, b) Задача 15: Сортировка пузырьком: количество обменов Ограничение по времени работы программы: 1 секунда Дан список целых чисел. Какое количество обменов совершит пузырьковая сортировка (по не убыванию элементов), запущенная на этом списке? ВХОДНЫЕ ДАННЫЕ Программа получает на вход n целых чисел, записанных через пробел в одной строке, 1≤n≤100. Сами числа по модулю не превосходят 109 ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно число — искомое количество обменов. ПРИМЕР
РЕШЕНИЕ Модифицируем алгоритм пузырьковой сортировки так, чтобы он подсчитывал количество выполненных обменов. Заведем внутри алгоритма переменную count, которую будем увеличивать на 1 при выполнении обмена. В конце вернем значение count. def BubbleSort(A): count = 0 for j in range(len(A) - 1, 0, -1): for i in range(0, j): if A[i] > A[i + 1]: A[i], A[i + 1] = A[i + 1], A[i] count += 1 return count A = list(map(int, input().split())) print(BubbleSort(A)) |