Range[0,10*Pi,Pi/2]?
2.3. Определите убывающий и возрастающий факториал при помощи ко- манды Range.
2.4. Выведите всю видимую
159
часть ASCII-кода.
Решение.
Полезно знать, что видимая часть ASCII-кода состоит из 94
символов, от 33-го !, до 126-го , в десятичной нумерации
160
. Ее можно вывести посредством CharacterRange["!","
"].
Тот же прием работает и для второй половины кодовой таблицы.
2.5. Породите русский алфавит. Заодно узнайте, сколько в нем букв.
Решение.
Да чего уж, CharacterRange["а","я"], 32 буквы.
Буква ¨e выглядит плохо — зато звучит хорошо.
Перечисленные выше способы порождения списков далеко не исчерпы- вают всех предоставляемых системой возможностей. Вот еще несколько важнейших приемов генерации списков:
• Команды функционального программирования, связанные с компози- циями и итерациями функций ComposeList, FoldList, NestList, NestWhi- leList, FixedPointList.
159
По-английски — printable.
160
Программисты обычно нумеруют символы ASCII-кода не от 0 до 127, а в вось- меричной системе от 000 до 177. В этом случае видимые символы имеют номера от
041-го до 176-го. См., например, Д.Кнут, Все про TEX. — AO RDTEX, Протвино, 1993.
Приложение С: Символьные коды.
373
• Команда ReplaceList, порождающая список результатов всех возмож- ных применений правила к какому-то выражению.
• Восстановление списков по их производящим функциям или другим ал- гебраическим объектам CoefficientList, CoefficientArrays, FactorList,
и т.д.
• Формирование разреженного списка SparseArray. Обычный список может быть превращен в список правил формирования разреженного спис- ка посредством ArrayRules, а разреженный в обычный посредством Normal.
Кроме того, конечно, можно строить списки из других списков, в част- ности, при помощи следующих команд, которые изучаются частично в этой главе.
• Манипуляции с частями списка: извлечения, вычеркивания, вставки,
замены, выборки Part, Extract, Delete, Select, Cases, DeleteCases, Re- placePart, Insert, и многие другие.
• Структурные манипуляции: сортировки, перестановки, выравнивания,
разбиения, управление вложенностью: Sort, Reverse, RotateLeft, Rotate-
Right, Flatten, Partition, Split, Transpose и многие другие.
• Алгебраические и теоретико-множественные операции над нескольки- ми списками: Join, Union, Intersection, Complement и другие.
• Команды функционального программирования, Map, MapAll, MapAt,
Thread, MapThread, Outer и многие другие.
3. Биномиальные коэффициенты.
161
Выделение первого и последнего элементов списка встречаются в про- граммировании настолько часто, что заслуживают специальных названий.
x[[1]]
First[x]
первая компонента x
x[[Length[x]]]
Last[x]
последняя компонента x
Основной командой, выделяющей части списка, является команда Part,
которая может вызываться как в функциональной, так и в операторной форме.
x[[i]]
Part[x,i]
i-я компонента x
x[[i,j]]
Part[x,i,j]
компонента x в позиции (i, j)
x[[
{i,j}]]
Part[x,
{i,j}]
компоненты x в позициях i и j
x[[All,j]]
Part[x,All,j]
j-е компоненты всех компонент x
В некоторых ситуациях используется также команда Extract, которую можно рассматривать как вариант Part. Более того, для линейных списков
161
— Нужно хотя бы часть чести отстоять...
— Дура! Не часть чести, а честь части.
c
Николай Фоменко
374 Extract[x,i] и Part[x,i] тождественны. Extract[x,i] i-я компонента xExtract[x, {i,j }] компонента x в позиции ( i, j) Extract[x, {{i }, {j }}] компоненты x в позициях i и jГлавное видимое 162 отличие этих команд – чисто синтаксическое: для определения вложенных списков, лежащих на глубоких уровнях, в коман- ду Part вводится последовательность индексов, а в Extract — их список . В то же время Part трактует список индексов как предложение вывести список частей верхнего уровня. С другой стороны, Extract ожидает в этом месте увидеть индексы частей не на глубине один, а на глубине два! Породим для наших экспериментов какой-нибудь список глубины 2, ска- жем, матрицу. Вычисление xxx=Partition[ToExpression[CharacterRange["a","i"]],3] возвращает {{a,b,c }, {d,e,f }, {g,h,i }}Понятно, что Extract[xxx,2], как и Part[xxx,2] вернет {d,e,f }. Гораздо интересней, что происходит на уровне 2! 3.1. Скажите, не используя компьютер, что даст вычисление каждого из следующих восьми выражений: Part[xxx,2,3], Extract[xxx,2,3], Part[xxx, {2,3 }], Extract[xxx, {2,3 }], Part[xxx, {2 }, {3 }], Extract[xxx, {2 }, {3 }], Part[xxx, {{2 }, {3 }}], Extract[xxx, {{2 }, {3 }}], — и даст ли что-нибудь вообще! А теперь проверьте. Важно помнить, что некоторые функции работы со списками подчиня- ются тем же соглашениям индексации компонент, что Part, в то время как другие — тем же, что Extract. 3.2. Определите функцию, возвращающую m-й с конца элемент списка x. Решение. По замыслу Part[x,-m] или Extract[x, {-m }], но можно, ко- нечно, и как-нибудт иначе, хотя бы Last[Nest[Most,x,m]]. 3.3. Определите функцию, возвращающую элементы списка x от l-го до m-го. 3.4. Определите функции, возвращающие следующий и предыдущий эле- менты списка. 3.5. Определите функцию, возвращающую элементы списка с нечетными номерами. Решение. Проще всего использовать Part и Range: 162 Есть и другие более тонкие отличия, связанные с тем, как Part и Extract произ- водят эвалюацию.
375
oddpart[x ]:=Part[x,Range[1,Length[x],2]]
Впрочем, с таким же успехом можно использовать и Extract. Конечно, при этом нужно не забыть каким-то образом ввести дополнительный уровень вложенности. Существует 69 способов сложить песню племен, и все они по-своему хороши. Вот несколько самых простых:
oddpart[x ]:=Extract[x,Partition[Range[1,Length[x],2],1]]
oddpart[x ]:=Extract[x,Split[Range[1,Length[x],2]]]
oddpart[x ]:=Extract[x,Map[List,Range[1,Length[x],2]]
oddpart[x ]:=Extract[x,Table[
{i},{i,1,Length[x],2}]]
oddpart[x ]:=Extract[x,Position[Table[(-1)^i,
{i,1,Length[x]}],-1]
oddpart[x ]:=Extract[x,NestList[(#+2)&,
{1},
Floor[Length[x]/2]-1]
Тем не менее, в природных условиях мы всегда используем конструкцию с
Part — она синтаксически проще и поэтому естественнее.
3.6.
Определите функцию, возвращающую элементы списка с четными номерами.
3.7. Породите списки букв латинского алфавита с четными и с нечетными номерами.
3.8. Породите список букв латинского алфавита через 7 начиная с a, счи- тая, что после z снова идет a.
Решение.
Проще всего использовать изученную в Модуле 1 функцию деления с отступом:
Part[ToExpression[CharacterRange["a","z"]],
Mod[Range[1,182,7],26,1]]
— кстати, почему 182? Вот получающийся список:
{a,h,o,v,c,j,q,x,e,l,s,z,g,n,u,b,i,p,w,d,k,r,y,f,m,t}
3.9. Выделите из списка его элементы в позициях 1, 4, 9, 16, . . .
Решение. Можно так squarepart[x ]:=Part[x,Table[i^2,
{i,1,Floor[Sqrt[Length[x]]]}]]
3.10. Выберите случайный элемент списка.
Решение. Например, при помощи внутреннего генератора случайных чи- сел randomelem[x ]:=Part[x,Random[Integer,
{1,Length[x]}]]
4. Выборки и вычеркивания.
Один из основных способов построения списков, который мы уже щедро использовали в Главе 7, таков: возьмем большой список и выберем или вычеркнем из него какие-то элементы. Выборка и вычеркивание могут быть
• либо чисто позиционными,
• либо зависеть от свойств самих элементов.
376 Во втором случае условие на элемент может выражаться • либо как критерий, которому этот элемент должен удовлетворять, • либо как соответствие этого элемента некоторому паттерну. Вот несколько простейших команд вычеркивания, в которых роль игра- ют не сами элементы, а только их позиция в списке. Две следующие команды настолько часто используются в рекурсивных программах, что заслуживают специальных названий. Rest[x] выбросить первую компоненту xMost[x] выбросить последнюю компоненту xКоманды Take и Drop чаще всего используются как обобщения Rest и Most, когда вычеркивание производится только с начала или с конца спис- ка. Но на самом деле при помощи них можно выбирать/вычеркивать части списка, индексы которых образуют арифметические прогрессии. Take[x,r] взять первые r компонент xTake[x,-r] взять последние r компонент xTake[x, {r,s }] взять компоненты x с r-й до s-й Take[x, {r,s,d }] взять компоненты x с r-й до s-й с шагом dDrop[x,r] выбросить первые r компонент xDrop[x,-r] выбросить последние r компонент xDrop[x, {r,s }] выбросить компоненты x с r-й до s-й Drop[x, {r,s,d }] выбросить компоненты x с r-й до s-й с шагом d4.1. Другим манером определите функцию, выбирающую элементы списка с нечетными номерами или вычеркивающую элементы четными номерами. Решение. Ну, конечно, так oddpart[x ]:=Take[x, {1,Length[x],2 }] oddpart[x ]:=Drop[x, {2,Length[x],2 }] Видимо, эти решения даже проще, чем решение с Part. Несколько большую свободу дает команда вычеркивания Delete, кото- рая использует те же соглашения, что и команда Extract. Delete[x,i] вычеркнуть i-ю компоненту списка xDelete[x, {i,j }] вычеркнуть компоненту ( i, j) списка xDelete[x, {{i }, {j }}] вычеркнуть i-ю и j-ю компоненты списка x4.2. А теперь еще раз определите функцию, вычеркивающую элементы списка с четными номерами. Решение. Да чего уж там, мы все это уже видели: oddpart[x ]:=Delete[x,Partition[Range[2,Length[x],2],1]] 377 oddpart[x ]:=Delete[x,Split[Range[2,Length[x],2]]] oddpart[x ]:=Delete[x,Map[List,Range[2,Length[x],2]] oddpart[x ]:=Delete[x,Table[ {i }, {i,2,Length[x],2 }]] и остальные 65 способов, которые мы использовали с Extract, но с заменой нечетных индексов на четные. 4.3. Определите функцию, вычеркивающую элементы списка с нечетными номерами. 4.4. Вычеркните из списка его элементы в позициях 1 , 4 , 9 , 16 , . . .Мы не будем здесь детально обсуждать команду Select, осуществля- ющую выбор по критерию. Конструкции с этой командой десятки раз использовались в Модуле 1, поэтому ограничимся несколькими примерами. Select[x,criterion] выбрать элементы x по критерию Select[x,criterion,n] выбрать первые n элементов x по критерию 4.5. Выберите из вложенного списка те элементы, которые являются упо- рядоченными списками. Решение. Например, так: Select[x,OrderedQ]. Отметим лишь следующий важнейший синтаксический момент. Исполь- зуемый в команде Select критерий не обязательно должен быть определен заранее. Он может определяться непосредственно в теле команды в фор- мате анонимной функции blabla[#]&. 4.6. Задайте функцию, выбирающую те части вложенного списка, в кото- рые не входит z. Решение. Проще всего так: Select[x,FreeQ[#,z]&]. Еще один важнейший способ построения подсписков, это выбор и вычер- кивание по соответствию паттерну. Cases[x,pattern] выбрать элементы, отвечающие паттерну DeleteCases[x,pattern] убрать элементы, отвечающие паттерну Count[x,pattern] число элементов, отвечающих паттерну Position[x,pattern] позиции элементов, отвечающих паттерну 4.7. Задайте функцию, которая выбирает из вложенного списка те части, которые сами являются списками. Решение. Ну, конечно, Cases[x, List]. Так как количество общих паттернов — Integer, Real, Complex, List, . . . , — крайне невелико, то, чтобы быть столь же гибким как Select, ко- манды, проверяющие соответствие паттерну, должны допускать модифи- кацию паттерна по критерию. Для этого используются две основные кон- струкции: • конструкция паттерн-тест = PatternTest в формате pattern?test. 378 • паттерн с условием = Condition в формате pattern /; test, В первом случае test либо должен уже иметь собственное имя, либо быть задан в формате анонимной функции blabla[#]&. При этом следует иметь в виду, что приоритет оператора ? = PatternTest настолько велик, что задание критерия в формате анонимной функции необходи- мо делимитировать круглыми скобками. Иными словами, паттерн, определяющий рациональные числа такие, что x2 < 2, должен выглядеть так Rational?(#^2<2&). При ограничении паттерна условием все фигурирующие в условии пе- ременные должны быть явным образом поименованы в паттерне. Иными словами, тот же паттерн, что и выше, задается теперь так x Rational /; x^2<2. Эта конструкция чуть менее эффективна с вычислительной точки зрения, но заметно проще для начинающего. 4.8. Задайте функцию, которая выбирает из списка все положительные элементы. Решение. Если с помощью Cases, то, например, так positiv[x ]:=Cases[x, ?Positive] 4.9. Задайте функцию, которая выбирает из списка все элементы меньшие m. Решение. Если с помощью Cases, то, например, так lowercone[x ,m ]:=Cases[x,y /; y 5. Подсписки.
5.1. Напишите программу, порождающую множество всех начальных/ко- нечных отрезков списка.
Решение. Это можно сделать миллионом способов. Вот решение в духе функционального программирования:
frontend[x ]:=ReplaceList[x,
{y ,v }->{y}]
backend[x ]:=ReplaceList[x,
{u ,y }->{y}]
5.2. Напишите программу, всевозможными способами разбивающую спи- сок на начальный и конечный отрезки.
Решение. Например, так partitio[x ]:=ReplaceList[x,
{u ,v }->{{u},{v}}]
Фрагмент списка состоит из идущих подряд элементов списка. В то же время подсписок состоит из элементов исходного списка, расположенных в том же порядке, что и в исходном списке, но, вообще говоря, не обя- зательно идущих подряд. Иными словами, фрагмент получается из спис- ка вычеркиванием начального и конечного отрезков (может быть пустых).
Подсписок получается произвольными вычеркиваниями. Например,
{b, c}
является фрагментом списка
{a, b, c, d}, а {a, d} является его подсписком,
но не фрагментом.
5.3. Напишите программу, выводящую список всех фрагментов списка x.
379 5.4. Напишите программу, порождающую список всех фрагментов длины n списка x. Решение. Можно так: frag[x ,n ]:=Table[Take[x, {i,i+n-1 }], {i,1,Length[x]-n+1 }] Но в действительности намного эффективнее воспользоваться внутренней функцией Partition, которая как раз и служит для этой цели: Partition[x,n,1]. 5.5. Напишите программу, выясняющую, является ли список y фрагмен- том списка x. Решение. Наивный подход состоит в том, чтобы породить список всех фрагментов списка x такой же длины и проверить, содержится ли там y: fragmQ[x ,y ]:=MemberQ[Partition[x,Length[y],1],y] 5.6. Напишите программу, порождающую по списку x список всех списков, получающихся из него вычеркиванием всевозможных фрагментов. Решение. Проще всего так bucato[x ]:=ReplaceList[list, {u ,y ,v }-> {u,v }] Следующие три заметно более сложные задачи, связанные с формиро- ванием подсписков, предлагались на экзамене на отличную оценку. 5.7. Напишите программу, выясняющую, является ли список y подсписком списка x. Как известно, палиндромом называется список, который одинаково читается как слева направо, так и справа налево. Подпалиндромом данного списка называется такой его подсписок, который является палиндромом. 5.8. Напишите программу, находящую в данном списке подпалиндром мак- симальной длины. 5.9. Напишите программу, порождающую все последовательности длины 2 n, состоящие из n штук +1 и n штук −1 такие, что количество +1 в каждом начальном отрезке не меньше, чем количество −1. 6. Основные структурные манипуляции. 163 Здесь мы учимся использовать простейшие структурные манипуляции над списками, не связанные с изменением уровней вложенности, а именно, вставки, замены, слияния, вращения и раздутия. Вставка элемента в начало или конец списка встречается в рекурсивных программах настолько часто, что заслуживает специального имени. Append[x,y] вставить y в конец списка xPrepend[x,y] вставить y в начало списка xAppendTo[x,y] вставить y в конец списка xPrependTo[x,y] вставить y в начало списка x163 Митек многое умеет. Митек может просчитать теодолитный ход, перевести под- питку котла с регулятора на байпас, раскурочить отбойным молотком мостовую — все это он сделать может. c Владимир Шинкарев, Митьки 380 Функции Append и Prepend, осуществляющие вставку элемента в конец или в начало списка, многократно встречались нам в Модуле 1 и их ис- пользование не представляет никаких трудностей. Функция AppendTo[x,y] является просто сокращенной формой присваивания x=Append[x,y], она требует, чтобы на момент присваивания x уже был списком. Основной командой вставки в Mathematica является Insert, а основной командой замены — ReplacePart. ReplacePart[x,y,r] заменить r-ю компоненту списка x на yInsert[x,y,r] вставить y на r-ю позицию в список xВопреки ожиданиям, команды ReplacePart и Insert используют те же соглашения относительно адресации частей, что и команды Extract и De- lete — отличающиеся от соглашений, используемых командой Part! Вот несколько типичных задач, которые решаются с помощью функций Repla- cePart и Insert. 6.1. Определите функцию, которая заменяет элементы списка на нечетных местах на z. 6.2. Определите функцию, которая заменяет элементы списка на четных местах на z. 6.3. Определите функцию, которая заменяет первые m элементов списка на z. 6.4. Определите функцию, которая заменяет первые m элементов списка на z. 6.5. Определите функцию, которая врисовывает z в начало и конец списка. Решение. Скажем, так Insert[x,z, {{1 }, {-1 }}]. 6.6. Определите функцию, которая врисовывает z в середину списка чет- ной длины и z, z в середину списка нечетной длины. Обратите внимание, что адресация, используемая командой Insert, все- гда относится к исходному списку, а не к тем спискам, которые получаются из него после того, как мы уже врисовали какие-то элементы. 6.7. Определите функцию, которая сопоставляет списку длины n список длины 2 n− 1, в котором между каждыми двумя членами исходного списка вписано z. Решение. Проще всего так: funny[x ]:=Insert[x,z,Map[List,Range[2,Length[x]]]] 6.8. Определите функцию, которая сопоставляет списку длины n список длины 2 n, в котором в самом начале и между каждыми двумя членами исходного списка вписано z. 6.9. Определите функцию, которая сопоставляет списку длины n список длины 2 n, в котором между каждыми двумя членами исходного списка и в самом конце вписано z. 381 Основной командой слияния списков в системе является Join. Вычис- ление Join[x,y] возвращает конкатенацию списков x и y. Иными слова- ми, в терминах следующего параграфа вычисляется Flatten[List[x,y],1] — никаких сортировок и исключений в получающемся списке не произво- дится. Join[x,y] слить списки x и yUnion[x,y] объединить списки x и y6.10. Составьте список, в котором вначале идут строчные буквы латин- ского алфавита от a до z, а потом прописные буквы от A до Z. Решение. Естественно, так Join[CharacterRange["a","z"],CharacterRange["A","Z"]] |
Скачать 4.43 Mb.