Текстовые файлы. Факторизация, простые числа, разные задачи.

 

 

       С помощью языка Haskell можно писать компактные и изящные решения довольно сложных задач. В данной лабораторной работе в заданиях 2 и 3 предлагается решить задачи с сайта http://projecteuler.net/problems, посвященному различным интересным задачам программирования. Разберем несколько подзадач, которые могут вам пригодиться при выполнении работы.

В работе [1] приводятся следующие функции для получения бесконечного списка чисел Фибоначчи:

1) fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

2) fibbs = 1 : 1 : next fibbs where

next (x:y:xs) = x + y : next (y:xs)

3) fibbbs = next 0 1 where

next x y = y : next y (x+y)

Там же приведены следующие способы получения списка простых чисел:

1) primes = map head $ iterate sieve [2..] where

sieve (x:xs) = [y | y <-xs, y `mod` x /= 0]

2) primes = 2 :

filter (\x -> all (\p -> x `mod` p /= 0) $

             takeWhile (\p -> p^2 <= x) primes) [3..]

 

 

Задание на лабораторную работу 4.

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

Подробный пример рассмотрен в пособии Макеева Г.А.

 

2. 3. Перевести текст задачи и написать решение. При желании любую задачу своего варианта можно заменить двумя другими задачами с сайта http://projecteuler.net/problems, не встречающимися в других вариантах и имеющими номер >50. Проверить полученные ответы на указанном сайте. В скобках указан номер задачи на сайте.

 

 

Вариант 1.

1. Строки исходного файла, отсортированные по возрастанию длины. 

 

2. (34) 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

 

3.(250) Find the number of non-empty subsets of {1¹, 2², 3³,..., 250250²⁵⁰²⁵⁰}, the sum of whose elements is divisible by 250. Enter the rightmost 16 digits as your answer.

 

 

Вариант 2.

1. Строки исходного файла, содержащие заданное слово. 

 

2. (50) The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

 

3. (171) For a positive integer n, let f(n) be the sum of the squares of the digits (in base 10) of n, e.g.

f(3) = 3² = 9,

f(25) = 2² + 5² = 4 + 25 = 29,

f(442) = 4² + 4² + 2² = 16 + 16 + 4 = 36

Find the last nine digits of the sum of all n, 0 < n < 10²⁰, such that f(n) is a perfect square.

 

Вариант 3.

1. Строки исходного файла, выровненные справа.

 

2. (21) Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

 

3. (200) We shall define a sqube to be a number of the form, p²q³, where p and q are distinct primes.

For example, 200 = 5²2³ or 120072949 = 23²61³.

The first five squbes are 72, 108, 200, 392, and 500.

Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.

Find the 200th prime-proof sqube containing the contiguous sub-string "200".

 

 

Вариант 4.

1. Строки исходного файла, из которых удалены все символы-цифры.

2. (32)We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital. The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital. Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital. HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

3. (73). Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

 

Вариант 5.

1. Слова исходного файла, не начинающиеся с заглавной буквы и не повторяющиеся.

 

2. (20). n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,

and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

3. (303)

For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits ≤ 2.

Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.

Also, .

Find .

 

Вариант 6.

1. Все встречающиеся гласные буквы и количество их вхождений в исходный файл, отсортированный по убыванию вхождений.

2. (4) A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

 

Find the largest palindrome made from the product of two 3-digit numbers.

 

3. (63) The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

 

 

Вариант 7.

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

 

2. (7) By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

 

3. (145) Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10⁹)?

 

 

Вариант 8.

1. Выводит отсортированные по количеству слов в предложении строки исходного файла.

 

2. (25) The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

 

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

 

3. (160) For any N, let f(N) be the last five digits before the trailing zeroes in N!.

For example,

 

9! = 362880 so f(9)=36288

10! = 3628800 so f(10)=36288

20! = 2432902008176640000 so f(20)=17664

 

Find f(1,000,000,000,000)

 

 

Вариант 9.

1. Выводит знаки препинания и количество их вхождений в исходный файл, отсортированные по убыванию вхождений.

2. (35) The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

 

3.(87) The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

 

28 = 2² + 2³ + 2⁴

33 = 3² + 2³ + 2⁴

49 = 5² + 2³ + 2⁴

47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

 

Вариант 10.

1. Строки исходного файла, выровненные по центру.

2. (29) Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

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

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

3. (120) Let r be the remainder when (a−1)ⁿ + (a+1)ⁿ is divided by a².

For example, if a = 7 and n = 3, then r = 42: 6³ + 8³ = 728 ≡ 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that r_max= 42.

For 3 ≤ a ≤ 1000, find ∑ r_max.

 

Пример выполнения работы

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

Строки исходного файла, выровненные по центру.

Решение.

       В данной функции предполагается, что длина строки равна 80.

Исходный файл:

Выходной файл:

 

2. Перевести текст задачи и написать решение.

Bouncy numbers

Problem 112.

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Перевод :

Задача 112.

       Если при просмотре слева направо не имеется цифр, превосходящих цифры, расположенные левее, то число называется возрастающим, например, 134468.

Аналогично, если нет цифр, превосходящих цифры правее, то число называется убывающим, например, 66420.

Назовем целое положительное число, не являющееся ни возрастающим, ни убывающим, «прыгучим» числом, например, 155349.

Ясно, что не существует прыгучих чисел, меньших сотни, но уже более половины чисел, меньших тысячи (525) являются прыгучими. Действительно, наименьшее число, для которого доля прыгучих чисел впервые достигает 50%, есть число 538.

Удивительно, но прыгучие числа становятся все более и более распространенными и к моменту достижения 21780 доля прыгучих чисел равна 90%.

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

Решение .

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

Проверка заключается в совпадении числа, преобразованного в строку, с отсортированной строкой – для возрастающих чисел, или с перевернутой отсортированной строкой – для убывающих. Проверка прыгучести, согласно определению, состоит в невыполнении обоих предыдущих проверок.

       Далее можно попробовать написать функцию, которая разбивает все числа, не превышающие заданного аргумента, на кортеж двух списков – прыгучих и всех остальных чисел, такая функция у нас определена в модуле List:

.

Тогда основная функция должна брать числа подряд, начиная с некоторого числа (логично выбрать начальное число равным 100), проверять длины полученных списков и останавливаться, когда доля прыгучих чисел достигнет заданного значения в 99%:

К сожалению, можно убедиться, что хотя эта программа работает правильно и даже вычисляет верно промежуточные числа для 50% и 90%, результата для 99% представляется невозможным дождаться в разумное время.

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

       Более эффективный алгоритм должен запоминать число прыгучих и непрыгучих чисел, меньших текущего проверяемого числа и переходить к следующему числу, пока не достигнута требуемая доля. Вот соответствующая программа:

Основная функция main имеет один аргумент p, соответствующий значению во сколько раз число прыгучих должно быть больше числа непрыгучих чисел, то есть, при р=1 доля прыгучих составляет 50%, при р=9 - 90%, при р=99 – 99%. Функция main вызывает функцию foo с начальными значениями текущего проверяемого числа – 100 и кортежем, в котором хранятся количества непрыгучих и прыгучих чисел, меньших проверяемого числа. Функция foo сначала проверяет, достигнута ли требуемая доля и в случае положительного ответа выдает текущее число, точнее, уменьшенное на единицу. Если же доля пока не достигнута, то проверяем, является ли число прыгучим и вызываем рекурсивно (причем рекурсия хвостовая) функцию с увеличенным на единицу текущим числом и увеличенным на единицу значением одного из аккумуляторов в кортеже. Вот пример выполнения функции с промежуточными результатами для проверки и требуемым ответом:

Зарегистрируемся на сайте и найдем нашу задачу по адресу  https://projecteuler.net/problem=112. Введем ответ 1587000:

 

Лабораторная работа 5.

---

Дата добавления: 2019-03-09; просмотров: 623; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!