Материал из ProgSchool

Вступительное испытание в ШП-2010

Передо мной стояла задача. Придумать задание, позволяющее отобрать ребят, способных к программированию. Отбор проходил среди школьников с 7 по 10 класс, в том числе из тех, кто с программированием совсем не знаком.

В прошлом году мы составляли задание из расчёта, что математические способности связаны с программистскими. Поэтому тест был, в основном, по математике. Однако, несмотря на то, что часто школьник сильный в математике оказывается сильным в программировании, случаются абсолютные расхождения. Причём, как в ту, так и в другую стороны. Человек, способный проектировать большие и сложные программы может плохо разбираться в математике и наоборот.

Поэтому в этом году я попытался найти какой-нибудь другой подход к созданию вступительного задания. В итоге набрёл на чью-то заметку в блоге, где обсуждалась статья, касающаяся выявления программистских способностей. Суть сводится к тому, что программист способен читать написанное на языке программирования, даже если с этим языком не знаком. Оригиальную статью я читать поленился, но там описывалось, как студентам, которые не знали Java, по ошибке дали тест по этому языку. Итог был таким, что часть студентов успешно справлялась с заданиями, а часть, наоборот, крайне неуспешно.

Я воспринял эту заметку как руководство к действию. Взял за основу язык Lisp, потому что Яву некоторые знали, а Lisp вряд ли кто-то знал (а если и знал, то он нам точно подходит :-). Сочинил простеньких выражений и попросил найти результат каждого из них. Собственно вот само задание: Media:EntranceTest2010.pdf.

Последние две задачи (про калькулятор и черепаху) — это попытка учесть экспериментальность задания и спасти ситуацию в случае провала с основными задачами.

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

Но считаю, что это не опровергает гипотезы. Просто вариант был составлен не очень хорошо. Думаю, надо было дать побольше простых задач, чтобы ребёнок мог составить в голове более полную картину языка. То есть добавить задач не для оценки, не страшно, если их многие решат. И потом дать достаточное количество задач посложнее, а не две, как здесь. Тогда среди слабых школьников будет хаотичное распределение по решённым простым задачам, а сложные будут по нулям. Сильные же школьники простые задачи полностью решат и проявят себя в решении сложных.

Разбор задач

Многие в седьмьй задаче дали ответ 7. Видимо, рассуждая таким образом, что идёт вычисление (n-1)+(n+2)=(5-1)+(5-2)=7.

Однако давайте разберёмся с тем, что там действительно написано:

	(defun myfun(n)
		(
			if
			(or (= n 0) (= n 1))
			1
			(+ (myfun (- n 1)) (myfun (- n 2)))
		)
	)

Напоминаю, требуется найти значение выражения (myfun 5).

Теперь подробно разберём задачи.

Предполагалось, что за первые семь заданий все заметят, что вызов команды представляет из себя список в круглых скобочках с элементами, разделёнными запятыми:

	(+ 1 2)
	(mx 23 54)
	(myfun 5)
	(myfun (- n 1))
	(if (> a b) 2 5)

где первый элемент обозначает операцию, которую следует выполнять:

Остальные элементы обозначают аргументы над которыми следует провести операцию:

Даже определение новой функции соответсовует этим правилам:

(defun funName funArgs funBody)

Создаёт функцию funName с аргументами funArgs и телом funBody.

То есть, если кто-нибудь будет вызывать (funName arg1 arg2), то arg1 и arg2 подставятся вместо переменных, перечисленных в funArgs и выполнится тело funBody.

Если определено

(
 defun mx (n, m) ( if (> n m) n m )
)

То вызов (mx 3 4) подставляет вместо n тройку, вместо m четвёрку и выполняет (if (> 3 4) 3 4). Что вернёт четвёрку.

Теперь представьте такую функцию:

(
  defun someFun (n)
  (
    if (= n 0) 1 ( someFun (- n 1) )
  )
)

Вызов ( someFun 2 ) выполняет (if (= 2 0) 1 ( somefun (- 2 1)) ), три не равно нулю поэтому выполнится (somefun (- 2 1)), а это (somefun 1).
Аналогично, это вызов следующей операции: (if (= 1 0) 1 (somefun (-1 1))), один не равно нулю, поэтому (somefun 0),
что вызывает (if (= 0 0) 1 (somefun (- 0 1))), ноль равен нулю, поэтому выполняется первая часть ифа. Это единица.
Значит (somefun 0) вернёт единицу, а значит somefun 1 вернёт единицу и так далее. Т.е. результат функции somefun всегда равен единице.

Теперь предлагаю подумать над задачей номер 7 ещё раз.