Информатика

1z1rwqg-001

5 класс

Информатика 5 класс Л.Л.Босова, А.Ю.Босова (скачать)

Информатика 5 класс учебник читать онлайн

Рабочая тетрадь Информатика 5 классЛ.Л.Босова, А.Ю.Босова

6 класс

Информатика 6 класс Л.Л.Босова, А.Ю.Босова (скачать)

Рабочая тетрадь Информатика 6 класс Л.Л.Босова, А.Ю.Босова

7 класс

Информатика, Учебник для 7 класса, Босова Л.Л., Босова А.Ю

Информатика, Рабочая тетрадь, 7 класс, Босова Л.Л., Босова А.Ю.

8 класс

Информатика, Учебник для 8 класса, Босова Л.Л., Босова А.Ю

О проекте Эйлер

Леонард Эйлер (1707-1783)

Antique illustration of scientist: Leonhard Euler

Leonhard Euler

Что такое проект Эйлер?
Проект Эйлера-это серия сложных задач математического/компьютерного программирования, для решения которых потребуется нечто большее, чем просто математическое понимание. Хотя математика поможет вам найти элегантные и эффективные методы, для решения большинства проблем потребуется использование компьютера и навыки программирования.

Мотивация для запуска проекта Эйлера и его продолжения состоит в том, чтобы предоставить платформу для пытливого ума, чтобы погрузиться в незнакомые области и изучить новые концепции в веселом и развлекательном контексте.
На кого направлены эти проблемы?
Предполагаемая аудитория включает студентов, для которых базовая учебная программа не утоляет их жажду учиться, взрослых, чье образование не было связано в первую очередь с математикой, но интересовалось математикой, и профессионалов, которые хотят, чтобы их решение задач и математика были на переднем крае.

В настоящее время у нас зарегистрировано 1036839 участников, которые решили по крайней мере одну проблему, представляющих 220 мест по всему миру и в совокупности использующих 108 различных языков программирования для решения проблем.
Может ли кто-нибудь решить эти проблемы?
Проблемы варьируются по сложности, и для многих опыт является индуктивным цепным обучением. То есть, решив одну проблему, вы познакомитесь с новой концепцией, которая позволит вам решить ранее недоступную проблему. Таким образом, решительный участник будет медленно, но верно прокладывать свой путь через каждую проблему.

Все задания решены при помощи языка программирования Python 

Задания
1 (1)
Числа, кратные 3 или 5
Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.

Найдите сумму всех чисел меньше 1000, кратных 3 или 5.
Решение:
def compute():
ans = sum(x for x in range(1000) if (x % 3 == 0 or x % 5 == 0))
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ: 233168

2 (2)
Четные числа Фибоначчи
Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2, первые 10 элементов будут:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона.
Решение:
f1, f2, s = 0, 1, 0
while f2 <= 4000000:
s = s + f2 if f2 % 2 == 0 else s
f1, f2 = f2, f1 + f2
print(s)

Ответ:
4613732

3 (4)
Наибольшее произведение-палиндром
Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99.

Найдите самый большой палиндром, полученный умножением двух трехзначных чисел.
Решение:
def compute():
ans = max(i * j
for i in range(100, 1000)
for j in range(100, 1000)
if str(i * j) == str(i * j)[ : : -1])
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ:906609

4 (5)
Наименьшее кратное
2520 — самое маленькое число, которое делится без остатка на все числа от 1 до 10.

Какое самое маленькое число делится нацело на все числа от 1 до 20?
Решение:
import math
def compute():
answer = 1
for i in range(1, 21):
answer *= i // math.gcd(i, answer)
return answer
if __name__ == «__main__»:
print(compute())

Ответ:232792560

5 (6)
Разность между суммой квадратов и квадратом суммы
Сумма квадратов первых десяти натуральных чисел равна

12 + 22 + … + 102 = 385
Квадрат суммы первых десяти натуральных чисел равен

(1 + 2 + … + 10)2 = 552 = 3025
Следовательно, разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640.

Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел.
Решение:
# s = N(N + 1) / 2.
# s2 = N(N + 1)(2N + 1) / 6.
# Поэтому s^2 — s2 = (N^4 / 4) + (N^3 / 6) — (N^2 / 4) — (N / 6).
def compute():
N = 100
s = sum(i for i in range(1, N + 1))
s2 = sum(i**2 for i in range(1, N + 1))
return str(s**2 — s2)
if __name__ == «__main__»:
print(compute())

Ответ: 25164150

6 (8)
Наибольшее произведение в последовательности
Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Найдите наибольшее произведение тринадцати последовательных цифр в данном числе.
Решение:
from functools import reduce
NUMBER = f»7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615″ \
f»6078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557668966489504″ \
f»4524452316173185640309871112172238311362229893423380308135336276614282806444486645238749303589072962904915″ \
f»6044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202″ \
f»3542180975125454059475224352584907711670556013604839586446706324415722155397536978179778461740649551492908″ \
f»6256932197846862248283972241375657056057490261407972968652414535100474821663704844031998900088952434506585″ \
f»4122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426″ \
f»0769004224219022671055626321111109370544217506941658960408071984038509624554443629812309878799272442849091″ \
f»8884580156166097919133875499200524063689912560717606058861164671094050775410022569831552000559357297257163″ \
f»6269561882670428252483600823257530420752963450″
LENGTH = 13
def compute():
answer = max(reduce(lambda a, b: a * b, map(int, NUMBER[i: i + LENGTH])) for i in range(len(NUMBER) — LENGTH + 1))
return answer
if __name__ == «__main__»:
print(compute())

Ответ: 23514624000

7 (9)
Особая тройка Пифагора
Тройка Пифагора — три натуральных числа a < b < c, для которых выполняется равенство

a2 + b2 = c2
Например, 32 + 42 = 9 + 16 = 25 = 52.

Существует только одна тройка Пифагора, для которой a + b + c = 1000.
Найдите произведение abc.
Решение:
# brute-force решение
def compute():
PERIMETER = 1000
for a in range(1, PERIMETER + 1):
for b in range(a + 1, PERIMETER + 1):
c = PERIMETER — a — b
if a * a + b * b == c * c:
return str(a * b * c)
if __name__ == «__main__»:
print(compute()

Ответ: 31875000

8 (20)
Сумма цифр факториала
n! означает n × (n − 1) × … × 3 × 2 × 1

Например, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
и сумма цифр в числе 10! равна 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Найдите сумму цифр в числе 100!.
Решение:
import math
# Используем только функции классной встроенной библиотеки math
def compute():
n = math.factorial(100)
ans = sum(int(c) for c in str(n))
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ: 648

9 (21)
Дружественные числа
Пусть d(n) определяется как сумма делителей n (числа меньше n, делящие n нацело).
Если d(a) = b и d(b) = a, где a ≠ b, то a и b называются дружественной парой, а каждое из чисел a и b — дружественным числом.

Например, делителями числа 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, поэтому d(220) = 284. Делители 284 — 1, 2, 4, 71, 142, поэтому d(284) = 220.

Подсчитайте сумму всех дружественных чисел меньше 10000.
Решение:
def compute():
# Compute sum of proper divisors for each number
divisorsum = [0] * 10000
for i in range(1, len(divisorsum)):
for j in range(i * 2, len(divisorsum), i):
divisorsum[j] += i

# Find all amicable pairs within range
ans = 0
for i in range(1, len(divisorsum)):
j = divisorsum[i]
if j != i and j < len(divisorsum) and divisorsum[j] == i:
ans += i
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ: 31626

10 (23)
Неизбыточные суммы
Совершенным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 28 равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что число 28 является совершенным числом.

Число n называется недостаточным, если сумма его делителей меньше n, и называется избыточным, если сумма его делителей больше n.

Так как число 12 является наименьшим избыточным числом (1 + 2 + 3 + 4 + 6 = 16), наименьшее число, которое может быть записано как сумма двух избыточных чисел, равно 24. Используя математический анализ, можно показать, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Эта граница не может быть уменьшена дальнейшим анализом, даже несмотря на то, что наибольшее число, которое не может быть записано как сумма двух избыточных чисел, меньше этой границы.

Найдите сумму всех положительных чисел, которые не могут быть записаны как сумма двух избыточных чисел.
Решение:
def compute():
LIMIT = 28124
divisorsum = [0] * LIMIT
for i in range(1, LIMIT):
for j in range(i * 2, LIMIT, i):
divisorsum[j] += i
abundantnums = [i for (i, x) in enumerate(divisorsum) if x > i]

expressible = [False] * LIMIT
for i in abundantnums:
for j in abundantnums:
if i + j < LIMIT:
expressible[i + j] = True
else:
break

ans = sum(i for (i, x) in enumerate(expressible) if not x)
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ:4179871

11 (24)
Словарные перестановки
Перестановка — это упорядоченная выборка объектов. К примеру, 3124 является одной из возможных перестановок из цифр 1, 2, 3 и 4. Если все перестановки приведены в порядке возрастания или алфавитном порядке, то такой порядок будем называть словарным. Словарные перестановки из цифр 0, 1 и 2 представлены ниже:

012 021 102 120 201 210

Какова миллионная словарная перестановка из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?
Решение:
import itertools, sys
# We initialize a list as the lowest permutation of the given digits, which is the sequence
# (0,1,2,3,4,5,6,7,8,9). Then we call a Python library function that generates a stream of
# all permutations of the values, seek to the 999 999th element (0-based indexing), and stringify it.
def compute():
arr = list(range(10))
temp = itertools.islice(itertools.permutations(arr), 999999, None)
return «».join(str(x) for x in next(temp))
if __name__ == «__main__»:
print(compute())

Ответ: 2783915460

12 (25)
1000-Значное число Фибоначчи
Последовательность Фибоначчи определяется рекурсивным правилом:

Fn = Fn−1 + Fn−2, где F1 = 1 и F2 = 1.
Таким образом, первые 12 членов последовательности равны:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
Двенадцатый член F12 — первый член последовательности, который содержит три цифры.

Каков порядковый номер первого члена последовательности Фибоначчи, содержащего 1000 цифр?
Решение:
#
# Решение задачи Проекта Эйлера номер 25
#
import itertools
# Т.к желаемое число не такое и большое то мы просто идем простым циклом
def compute():
DIGITS = 1000
prev = 1
cur = 0
for i in itertools.count():
# На этом шаге, prev = fibonacci(i — 1) и cur = fibonacci(i)
if len(str(cur)) > DIGITS:
raise RuntimeError(«Not found»)
elif len(str(cur)) == DIGITS:
return str(i)

# Пересчитываем prev и cur по формуле чисел Фибоначчи
prev, cur = cur, prev + cur
if __name__ == «__main__»:
print(compute())

Ответ: 4782

13 (28)
Диагонали числовой спирали
Начиная с числа 1 и двигаясь дальше вправо по часовой стрелке, образуется следующая спираль 5 на 5:

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

Можно убедиться, что сумма чисел в диагоналях равна 101.

Какова сумма чисел в диагоналях спирали 1001 на 1001, образованной таким же способом?
Решение:
# Мы имеем n * n квадрат, где n — нечетное.
# Правый верхний угол равен n * n
# Если идти против часовой стрелки, то верхний левый угол равен n^2 — (n — 1).
# Нижний левый угол равен n^2 — 2(n — 1) и нижний правый равен n^2 — 3(n-1)
# Собрав все это, сумму на внешнем кольце можно выразить формулой 4n^2 — 6(n — 1).
#
# Между прочим , общая формула для такой задачи(4m^3 + 3m^2 + 8m — 9) / 6, где m — это размер спирали. В нашем случае это 1001
def compute():
SIZE = 1001 # Must be odd
ans = 1 # Special case for size 1
ans += sum(4 * i * i — 6 * (i — 1) for i in range(3, SIZE + 1, 2))
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ:669171001

14 (29)
Различные степени
Рассмотрим все целочисленные комбинации ab для 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
Если их расположить в порядке возрастания, исключив повторения, мы получим следующую последовательность из 15 различных членов:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

Сколько различных членов имеет последовательность ab для 2 ≤ a ≤ 100 и 2 ≤ b ≤ 100?
Решение:
# Мы генерируем все возможные степени в диапазоне до 100, помещаем эти значения в множество set и позволяем функции set посчитать количество уникальных значений.
def compute():
seen = set(a**b for a in range(2, 101) for b in range(2, 101))
return str(len(seen))
if __name__ == «__main__»:
print(compute())

Ответ: 9183

15 (30)
Пятые степени цифр
Удивительно, но существует только три числа, которые могут быть записаны в виде суммы четвертых степеней их цифр:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
1 = 14 не считается, так как это — не сумма.

Сумма этих чисел равна 1634 + 8208 + 9474 = 19316.

Найдите сумму всех чисел, которые могут быть записаны в виде суммы пятых степеней их цифр.
Решение:
import sys
if sys.version_info.major == 2:
range = xrange
def compute():
# Исключаем 1 = 1^5
# Если число имеет как минимум n >= 7 цифр, тогда даже если цифр 9, n * 9^5 все равно меньше чем число(которое минимум 10^n).
ans = sum(i for i in range(2, 1000000) if i == fifth_power_digit_sum(i))
return str(ans)
def fifth_power_digit_sum(n):
return sum(int(c)**5 for c in str(n))
if __name__ == «__main__»:
print(compute())

Ответ: 443839

16 (31)
Суммы монет
В Англии валютой являются фунты стерлингов £ и пенсы p, и в обращении есть восемь монет:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) и £2 (200p).
£2 возможно составить следующим образом:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
Сколькими разными способами можно составить £2, используя любое количество монет?
Решение:
# Порядок номинала монет не имеет значения, но номинал должен быть уникальным
def compute():
TOTAL = 200
ways = [1] + [0] * TOTAL
for coin in [1, 2, 5, 10, 20, 50, 100, 200]:
for i in range(len(ways) — coin):
ways[i + coin] += ways[i]
return str(ways[-1])
if __name__ == «__main__»:
print(compute())

Ответ: 73682

17 (32)
Пан-цифровые произведения
Каждое n-значное число, которое содержит каждую цифру от 1 до n ровно один раз, будем считать пан-цифровым; к примеру, 5-значное число 15234 является пан-цифровым, т.к. содержит цифры от 1 до 5.

Произведение 7254 является необычным, поскольку равенство 39 × 186 = 7254, состоящее из множимого, множителя и произведения является пан-цифровым, т.е. содержит цифры от 1 до 9.

Найдите сумму всех пан-цифровых произведений, для которых равенство «множимое × множитель = произведение» можно записать цифрами от 1 до 9, используя каждую цифру только один раз.

ПОДСКАЗКА: Некоторые произведения можно получить несколькими способами, поэтому убедитесь, что включили их в сумму лишь единожды.
Решение:
# Given integer x, this returns the integer floor(sqrt(x)).
def sqrt(x):
assert x >= 0
i = 1
while i * i <= x:
i *= 2
y = 0
while i > 0:
if (y + i)**2 <= x:
y += i
i //= 2
return y
def has_pandigital_product(n):
for i in range(1, sqrt(n) + 1):
if n % i == 0:
temp = str(n) + str(i) + str(n // i)
if «».join(sorted(temp)) == «123456789»:
return True
return False
def compute():
ans = sum(i for i in range(1, 10000) if has_pandigital_product(i))
return str(ans)
if __name__ == «__main__»:
print(compute())

Ответ: 45228

18 (33)
Дроби, сократимые по цифрам
Дробь 49/98 является любопытной, поскольку неопытный математик, пытаясь сократить ее, будет ошибочно полагать, что 49/98 = 4/8, являющееся истиной, получено вычеркиванием девяток.

Дроби вида 30/50 = 3/5 будем считать тривиальными примерами.

Существует ровно 4 нетривиальных примера дробей подобного типа, которые меньше единицы и содержат двухзначные числа как в числителе, так и в знаменателе.

Пусть произведение этих четырех дробей дано в виде несократимой дроби (числитель и знаменатель дроби не имеют общих сомножителей). Найдите знаменатель этой дроби.
Решение:
import fractions
def compute():
numer = 1
denom = 1
for d in range(10, 100):
for n in range(10, d):
n0 = n % 10
n1 = n // 10
d0 = d % 10
d1 = d // 10
if (n1 == d0 and n0 * d == n * d1) or (n0 == d1 and n1 * d == n * d0):
numer *= n
denom *= d
return str(denom // fractions.gcd(numer, denom))
if __name__ == «__main__»:
print(compute())

Ответ: 100

19 (34)
Факториалы цифр
145 является любопытным числом, поскольку 1! + 4! + 5! = 1 + 24 + 120 = 145.

Найдите сумму всех чисел, каждое из которых равно сумме факториалов своих цифр.

Примечание: поскольку 1! = 1 и 2! = 2 не являются суммами, учитывать их не следует.
Решение:
import math, sys
if sys.version_info.major == 2:
range = xrange
def compute():
# 1=1! и 2= 2! исключаем. Если число имеет n >=8 цифр, то даже если цифр 9, n * 9! все равно меньше, чем число (которое как минимум 10^n).
ans = sum(i for i in range(3, 10000000) if i == factorial_digit_sum(i))
return str(ans)
def factorial_digit_sum(n):
result = 0
while n >= 10000:
result += FACTORIAL_DIGITS_SUM_WITH_LEADING_ZEROS[n % 10000]
n //= 10000
return result + FACTORIAL_DIGITS_SUM_WITHOUT_LEADING_ZEROS[n]
FACTORIAL_DIGITS_SUM_WITHOUT_LEADING_ZEROS = [sum(math.factorial(int(c)) for c in str(i)) for i in range(10000)]
FACTORIAL_DIGITS_SUM_WITH_LEADING_ZEROS = [sum(math.factorial(int(c)) for c in str(i).zfill(4)) for i in range(10000)]
if __name__ == «__main__»:
print(compute())

Ответ: 40730