Вячеслав Пупышев - 50 задач по началам программирования

47. Максимальное R(x,y)

Вычислить максимальное значение 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

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