Вячеслав Пупышев - 50 задач по началам программирования
Вычислить максимальное значение R(x,y) для заданных целых x,y ( y<50 ).
Внимание, «функция» R -неоднозначная (может давать разные значения на одинаковых аргументах).
ПРИМЕР.
X=3
Y=4
Максимальное значение R(3, 4)=16
48. DOI1995. Сравнение с образцом.
Образец имеет вид:
образец ::= <PT>
<PT> ::= <A><PT> | <A>
<A> ::= '['<PT>']' | <ST>
<ST> ::= <символы>
Часть образца, заключенная в квадратные скобки показывает, что эту часть можно исключать. Таким образом, образец описывает множество строк. Образец всегда правильный. Например:
образец: [a[b]]c
описывает строки: a, ab, abc
Слово подходит под образец, если оно совпадает с одним из слов, описываемых образцом. Задача написать программу, которая по заданному образцу и слову печатает «НЕТ », если слово подходит под образец, и «ДА », если не подходит.
ПРИМЕР:
образец: [a[b]]c
слово: ab
ответ: ДА
49*. MARK1997. Уравнение f(X) = A
Решить уравнение вида f(X) = A, где A -строка из маленьких латинских букв, X -переменная строка, f -функция на строках, построенная с помощью операций * и + над строками. Операция + обозначает конкатенацию[6] строк. Например, adbc + 123 = abcd123. Результатом операции A * B будет стро ка, где после каждого символа A записана B; если A или B - пустые строки, то результат будет также пустой строкой. На пример, ab * cd = acdbcd. Операции выполняются в порядке их следования.
ТЕХНИЧЕСКОЕ ЗАДАНИЕ.
Программа должна запросить уравнение и напечатать одно из решений.
ПРИМЕР.
Уравнение: X * ab + c * X = aabcabcac
X = ac
В СЛЕДУЮЩЕЙ ЗАДАЧЕ ПРИМЕНЯЕТСЯ ПРИЁМ, КОТОРЫЙ НАЗЫВАЕТСЯ динамическим программированием ПРИЁМ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ЗАПОМИНАЮТ ТЕ ПРОМЕЖУТОЧНЫЕ РЕЗУЛЬТАТЫ, КОТОРЫЕ УЖЕ ВЫЧИСЛЕНЫ, А ПОТОМ ИСПОЛЬЗУЮТ ИХ.
50*. MARK1997. Квадрат чисел
Задана квадратная таблица чисел. Размер таблицы нечётный. Движение начинается из центра. Двигаться можно вправо, влево, вверх и вниз. По ходу движения суммируются числа, записанные в клетках пути следования. Движение заканчивается на стороне квадрата.
Написать программу, которая сообщит минимальную сумму.
ТЕХНИЧЕСКОЕ ЗАДАНИЕ.
Заданный квадрат хранится в файле. Файл устроен следующим образом:
<Размер квадрата>
<Число> <Число> . . . <Число>
<Число> <Число> . . . <Число>
. . .
<Число> <Число> . . . <Число>
Все числа натуральные, не больше 200. Разделителями являются пробелы. Количество чисел в строке и количество строк совпадает с размером квадрата. Размер таблицы не больше 100.
Программа должна запросить имя файла с описанием квадрата и напечатать длину кратчайшего пути.
ПРИМЕР.
В файле:
5
20 13 23 12 18
6 14 3 17 11
21 2 1 4 25
7 15 5 16 10
22 8 19 9 24
Ответ: 23
Тесты
Метод использования тестов
Тесты надо проверять с первого до поседнего, подряд. Программа на каждом тесте должна работать не более указанного времени. Если время тестирования ограничено 0 секунд, это значит, что программа должна работать мгновенно.
Для каждого теста приведена его стоимость в процентах.
После проверки можно сложитьпроценты всех пройденных тестов и получить процент решения задачи.
По способам оценки можно выделить две основные группы тестов и по две разновидности в этих группах.
Первая группа. К первой группе можно отнести тесты, в которых сложность оценивается после тестирования программы (чаще нескольких программ). Тест считается более сложным, если программа (лучше несколько) проходит его с большими трудностями. Разновидности отличаются оценкой сложных и простых тестов.
Вторая группа. Тесты, ценность которых определяется до тестирования. Разновидности отличаются так же, как и в первой группе, но не по сложности, а по общности.
В этом задачнике тесты, очевидно, относятся ко второй группе. Наиболее общие тесты оценены выше.
1.Привет
ответ очевиден.
2.здравствуй
ответ очевиден.
3. Арифметика
а)14; б)5202;
в)12254; г)-19961;
д)4293; е)-3878;
ж)19812; з)-1031.
4. Вежливое приветствие
ответ очевиден.
5. Вежливое приветствие с восклицательным знаком
ответ очевиден.
6. Сумма
N
Вход
Выход
Ценность в процентах
0
15
12
27
1%
1
2
3
5
33%
2
1
-1
0
33%
3
-10
-20
-30
33%
Время работы программы 0 секунд.
7.Сумма чисел.
N
Вход
Выход
Ценность в процентах
0
15 12
15 + 12 = 27
1%
1
3 2
3 + 2 = 5
33%
2
-1 1
-1 + 1 = 0
33%
3
-100 -32
-100 + -32 = -132
33%
Время работы программы 0 секунд
8. Длинна строки
N
Вход
Выход
Ценность
в процентах
0
Мама мыла раму
В строке:
"Мама мыла раму" символов: 14
1%
1
Тест
В строке:
Тест символов: 4
25%
2
Test only
В строке:
Test only сим волов: 9
25%
3
В строке:
символов: 0
24%
4
1
В строке:
1 символов: 1
25%
Время работы программы 0 секунд
Пупышев Вячеслав Викторович
50 задач по началам программирования
в авторской редакции
корректор Е. Ф. Осипова
http://ulm.uni.udm.ru/~pvv/packst/
ЛР № 020411 от 16.02.97. Сдано в производство 01.03.99.
Формат 60 х 84 1/18. Печать офсетная.
Уч. изд. л. 3,9. Усл. печ. л. Заказ № 34. Тираж 300.
Издательский дом Удмуртский университет.
426011, г. Ижевск, ул. Майская 23.
Примечания
1
Если программа выдаёт правильный результат, но не укладывается в отведённое время, то, скорее всего, ошибка в алгоритме.
2
Число называется чётным, если делится на 2 без остатка.
3
Шестнадцатеричные числа записываются с использованием обычных десятичных цифр 0, 1, ..., 9 и ещё букв A, B, C, D, E, F, обозначающих 10, 11, 12, 13, 14, 15, соответственно.
4
Большие -- могут не поместиться в оперативной памяти.
5
читается <ка факториал>
6
Т.е. сцепление строк, приписывание одной строки к другой.
