Алгоритмический анализ - 1 2014-2015

МТ-103

1.1
Написать выражение, которое возводит число в квадрат (Лямбда калькулятор cs.usu.edu.ru/home/akazakov/lambda.jar)

1.2
Написать выражение, которое вычисляет остаток от деления x на y

1.3
Написать выражение, которое вычисляет последнюю цифру числа

1.4
Написать выражение, которое вычисляет предпоследнюю цифру числа.

1.5
Написать выражение, которое проверяет год на високосность (http://ru.wikipedia.org/wiki/Високосный_год)

1.6
Написать выражение, которое вычисляет минимум из двух чисел

1.7
Написать выражение, которое вычисляет максимум из двух чисел

1.8
Написать выражение, которое принимает два натуральных числа (<= 999) и вычисляет их конкатенацию

2.1
Написать лямбда-выражение для вычисления факториала заданного числа.

14.10.2014 -- 6
21.10.2014 -- 3
28.10.2014 -- 2

2.2
Написать лямбда-выражение для вычисления суммы цифр заданного числа.

14.10.2014 -- 6
21.10.2014 -- 3
28.10.2014 -- 2

2.3
Написать лямбда-выражение для вычисления максимальной цифры заданного числа.

14.10.2014 -- 6
21.10.2014 -- 3
28.10.2014 -- 2

2.4
Написать лямбда-выражение, которое переводит заданное число из 10 системы счисления в двоичную.

14.10.2014 -- 6
21.10.2014 -- 3
28.10.2014 -- 2

3.1
#Scheme
Напишите функцию, которая вычисляет среднее геометрическое двух положительных чисел, заданных в качестве параметров на входе. Средним геометрическим двух чисел называется квадратный корень из их произведения.

(geometric-mean 4.5 2)
3.0
(geometric-mean 2 2)
2

28.10.2014 -- 6
11.11.2014 -- 3
18.11.2014 -- 2

3.2
#Scheme
Напишите функцию, которая по заданному на входе числу определяет значение функции
                | 1, x > 0,
sign(x) = { 0, x = 0,
                | -1, x < 0

(sign 17)
1
(sign -2)
-1
(sign 0)
0

28.10.2014 -- 6
11.11.2014 -- 3
18.11.2014 -- 2

3.3
#Scheme
Проездной билет с шестизначным номером назовем счастливым по московской системе, если сумма первых трех цифр номера совпадает с суммой вторых трех цифр этого же номера. Назовем такой билет счастливым по питерской системе, если сумма цифр, стоящих на четных позициях (по расположению в номере, а не по значению цифры) в номере равняется сумме цифр, стоящих на нечетных позициях в номере.
Назовем билет с шестизначным номером абсолютно счастливым, если он является счастливым по обеим упомянутым выше системам.

Напишите функцию, которая по заданному на входе целому неотрицательному числу $n<10^6$ возвращает число 1, если билет является счастливым (только) по московской системе, возвращает число 2, если
билет является счастливым (только) по питерской системе, число 3, если билет является абсолютно счастливым и false, если билет не является счастливым.

(happy-ticket 444444)
3
(happy-ticket 268736)
1
(happy-ticket 276386)
2

28.10.2014 -- 6
11.11.2014 -- 3
18.11.2014 -- 2

3.4
#Scheme
Напишите функцию, которая по заданным величине a и координатам точки на плоскости x и y вычисляет расстояние от точки (x,y) до фигуры, изображенной на рисунке http://goo.gl/TNc1fD
Расстояние для точки, расположенной внутри фигуры, считается равным 0.

28.10.2014 -- 6
11.11.2014 -- 3
18.11.2014 -- 2

4.1
Напишите функцию complete-square?, проверяющую, является ли заданное число n полным квадратом натурального числа.

(complete-square? 25)
#t
(complete-square? 7)
#f

11.11.2014 -- 6
18.11.2014 -- 3
25.11.2014 -- 2

4.2
Напишите функцию ordered-digits?, которая проверяет, упорядочены ли цифры в числе.

(ordered-digits? 1479)
#t
(ordered-digits? 777)
#t
(ordered-digits? 952)
#t
(ordered-digits? 28457)
#f

11.11.2014 -- 6
18.11.2014 -- 3
25.11.2014 -- 2

4.3
Напишите функцию what-power-of-two, проверяющую, является ли заданное натуральное число степенью двойки и, если да, то какой.

(what-power-of-two 5)
#f
(what-power-of-two 8)
3

11.11.2014 -- 6
18.11.2014 -- 3
25.11.2014 -- 2

4.4
Напишите функцию show-factorize, которая по введённому натуральному числу выводит его разложение на простые множители на экран (через пробел). Если в разложении присутствует множитель кратности k, то он должен появиться на экране ровно k раз.

11.11.2014 -- 6
18.11.2014 -- 3
25.11.2014 -- 2

5.1
Напишите функцию, которая в списке ищет заданный элемент. Если элемент найден, функция возвращает номер позиции первого вхождения этого элемента в список. В противном случае функция должна вернуть #f.

(find '(1 2 3 4) 5)
#f
(find '() 5)
#f
(find '(5 1 2) 5)
0
(find '(1 2 5) 5)
2
(find '(1 2 5 1 5) 5)
2

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

5.2
Напишите функцию, подсчитывающую количество чётных элементов списка.

(count-even '(1 3 5))
0
(count-even '())
0
(count-even '(2 4))
2
(count-even '(1 2 3 4))
2

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

5.3
Напишите свою реализацию функции разворота списка.

(my-reverse '(1 2 3 4))
'(4 3 2 1)
(my-reverse '())
'()
(my-reverse (list (list 1) (list 2) (list 3)))
'((3) (2) (1))

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

5.4
Задан список. Нужно найти хотя бы один элемент, который встречается в этом списке более одного раза или вернуть #f.

(find-met-several-times '(1 2 3))
#f
(find-met-several-times '())
#f
(find-met-several-times '(1 2 3 1 2))
1
(find-met-several-times '(1 2 3 1))
1

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

5.5
Задан список натуральных чисел. Оставить в списке только числа с максимальным количеством цифр.

(filter-max-amount-of-digits '())
'()
(filter-max-amount-of-digits '(1 42 81 4))
'(42 81)
(filter-max-amount-of-digits '(1 215 3))
'(215)

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

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

(bin->dec 0)
0
(bin->dec 1)
1
(bin->dec 10)
2
(bin->dec 101)
5
(bin->dec 1010)
10

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

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

(dec->bin 0)
0
(dec->bin 1)
1
(dec->bin 2)
10
(dec->bin 5)
101

18.11.2014 -- 6
25.11.2014 -- 3
02.12.2014 -- 2

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

(count-different '())
0
(count-different '(1 2 3))
3
(count-different '(1 1))
1
(count-different '(1 2 2 1))
2
(count-different (build-list 100 values))
100
(count-different (build-list 100 (lambda (n) (remainder n 3))))
3
25.11.2014 -- 6
02.12.2014 -- 3
09.12.2014 -- 2

6.2
Напишите функцию, которая в заданном списке подсчитывает количество разных элементов и возвращает список пар (a_i . k_i), где a_i — элемент исходного списка, а k_i — количество его вхождений в исходный список.

(count-elements '())
'()
(count-elements '(1 2 3))
'((1 . 1) (2 . 1) (3 . 1))
(count-elements '(1 1))
'((1 . 2))
(count-elements '(1 2 3 2 1))
'((1 . 2) (2 . 2) (3 . 1))
(count-elements (build-list 100 (lambda (n) (remainder n 3))))
'((0 . 34) (1 . 33) (2 . 33))

25.11.2014 -- 6
02.12.2014 -- 3
09.12.2014 -- 2

6.3
По заданным на входе двум спискам вернуть список, в который попадут пары элементов исходных списков, стоящие на местах с одинаковыми номерами и являющиеся при этом взаимно простыми

(zipCoprime '(1 2 3 4 8 3) '(3 5 7 6 2))
'((1 . 3) (2 . 5) (3 . 7))

25.11.2014 -- 6
02.12.2014 -- 3
09.12.2014 -- 2

6.4
По заданному списку сгенерировать список всех его подсписков, начинающихся с первого элемента.

(prefixes '(1 2 3 4))
'((1) (1 2) (1 2 3) (1 2 3 4))

25.11.2014 -- 6
02.12.2014 -- 3
09.12.2014 -- 2

6.5
По заданному натуральному n сгенерировать список по правилу
(phi(0) phi(2) ... phi(n) ... phi(3) phi(1)),
где phi(k) — k-ое число Фибоначчи.

25.11.2014 -- 6
02.12.2014 -- 3
09.12.2014 -- 2

7.1
Напишите функцию, которая оставляет в списке только те элементы, которые делятся на свой номер.

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


02.12.2014 -- 6
09.12.2014 -- 3
16.12.2014 -- 2

7.2
Напишите функцию, которая по заданному натуральному числу n возвращает список с n-ой строчкой треугольника Паскаля.

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

02.12.2014 -- 6
09.12.2014 -- 3
16.12.2014 -- 2

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

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

'(1 23 456) '(654 32 1)
#t

'(1 23 456) '(456 23 1)
#f

02.12.2014 -- 6
09.12.2014 -- 3
16.12.2014 -- 2

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

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

'(1 23 456)
'(1 2 3 4 5 6)

02.12.2014 -- 6
09.12.2014 -- 3
16.12.2014 -- 2

8.1
Задан многочлен p(x) = a_n * x^n + a_{n-1} * x^{n-1} + ... + a_{1} * n + a_0 списком своих коэффициентов (a_n a_{n-1} ... a_{1} a_{0}). Напишите функцию, которая вычисляет производную p'(x), то есть возвращает список коэффициентов многочлена p'(x)

(derivative '(1 2 3))
'(2 2)
(derivative '(5))
'(0)
(derivative '(3 0 1 0))
'(9 0 1)


09.12.2014 -- 6
16.12.2014 -- 3
23.12.2014 -- 2

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

09.12.2014 -- 6
16.12.2014 -- 3
23.12.2014 -- 2

8.3
Напишите функцию, которая ищет номер элемента списка, который является максимальным простым числом. Если такого элемента нет, функция должна вернуть #f.

(index-of-max-prime '())
#f
(index-of-max-prime '(4 6 8 10))
#f
(index-of-max-prime '(6 1))
#f
(index-of-max-prime '(1 2 6))
1

09.12.2014 -- 6
16.12.2014 -- 3
23.12.2014 -- 2

8.4
Многочлен с целыми коэффициентами задан списком своих коэффициентов. Напишите функцию, которая возвращает список список его целых корней. Если таковых нет — функция должна вернуть пустой список. При этом имейте в виду теорему: если многочлен от одной переменной с целыми коэффициентами имеет рациональный корень, представленный несократимой дробью p / q, то p является делителем свободного члена, а q — старшего коэффициента.


09.12.2014 -- 6
16.12.2014 -- 3
23.12.2014 -- 2