Гульня жыцця Конвея ў адну лінію с APL

2015-11-11 13:21:04 / author: sharkov views 772Total views: 772 / 9Views for 7 days: 9
Thanks to Best cliparts
source article: http://www.catpad.net/michael/apl/

Конвей гульня жыцце ў адну лінію АПЗ

Тлумачэнне

Калі Вы не знаемыя з перадаць гульні "жыцце" або APL мова праграмавання, я рэкамендую азнаеміцца з вельмі кароткім апісаннем apl і апісанне гульні Конвея "жыцце". Акрамя таго, на гэтай старонцы вы знойдзеце кампаніі IBM APL2 інтэрпрэтатар і некалькі спасылак мовы.

Гэта падрабязнае тлумачэнне опл праграму, якая выводзіць N пакаленняў першапачатковай канфігурацыі М гульні жыцця будзе таксама служыць у якасці кароткага і вельмі неафіцыйны курс у АИП.

Перш чым мы пачнем расшыфроўваць (гэта, здаецца, правільнае слова тут) у жыцце праграму, давайце паспрабуем выпрацаваць стратэгію, як напісаць гэтую праграму ў адну радок, як ні немагчыма гэта гучыць.

Жыцце-гэта цыклічная гульня у сілу сваей прыроды і - вядома - алгарытм, які рэалізуе гэтую гульню, мабыць, павінна складацца з некалькіх цыклаў. Такім чынам, асноўны цыкл праграмы-гэта паток пакаленняў. Іншая пятля-гэта той, які скануе матрыцу для вылічэнні клетак, якія памерлі, жывыя або нованароджанага. Яшчэ адзін цыкл вылічаецца лік суседзяў кожнай дадзенай суполкі. Цяпер, думаеш, вось яно: мы не можам выкарыстоўваць нават адну пятлю ўнутры адной лініі, не кажучы ўжо пра трох укладзеных цыклаў!

Але пачакайце - APL дазваляе пераадолець практычна любой, нават самай бязвыхаднай сітуацыі.

Па-першае, нам не патрэбен цыкл сканавання матрыцы, паколькі APL дазваляе нам працаваць з усей матрыцы, як правіла, з дапамогай адной функцыі. Тое ж самае тычыцца і колькасці суседзяў. Як для галоўнага цыклу, што govenrs змены пакаленняў - няма такога паняцця наогул!

Няхай N колькасць пакаленняў мы хочам вылічыць. Мы можам запісаць усе завесы (то есць падпраграм, якія складаюць цела цыклу) як адна вельмі доўгая радок. Цяпер усе, што нам трэба зрабіць-гэта выканаць гэтую радок.

Гэта не вельмі добра, - кажа чытач. - Што калі нам спатрэбіцца 1000 пакаленняў ? Мы павінны запісаць 1000 цыклаў, якія робяць тое ж самае тады ? Абсалютна няма! Як мы ўжо казалі раней, усе гэтыя завесы робяць тое ж самае, так што мы будзем проста запісваць толькі адзін цыкл, а затым опл дапаможа нам памножыць N раз, выкарыстоўваючы ρ (РО) функцыя, для гэтага есць функцыя, якая стварае масівы любой памернасці. Пасля гэтага мы будзем называць дзіўнае опл

функцыю для выканання - Конвей гульня жыцце ў адну лінію АПЗ. Гэтая функцыя выконвае радок, разглядаючы яго як дзеючую лінію APL праграмы. (Амаль роўныя аператара ў Лиспе называецца функцыя eval). Гэтая функцыя будзе адказваць за выкананне "вельмі доўгая радок" з счэпленых цела цыклу.

Нарэшце, мы павінны разлічыць ўсе суседзі кожнай дадзенай ячэйкі нашай матрыцы. І гэта будзе галоўная "фішка" нашай праграмы.

Давайце прадстаўляць жывой клеткі жыцця як 1 і 0 пустыя вочкі. Для нашага прыкладу возьмем матрыцу 5х5 і кладзем у сярэдзіну вельмі просты, але цікавы арганізма называецца семафор:

Конвей гульня жыцце ў адну лінію АПЗ

Вось як паводзіць сябе семафор:

Конвей гульня жыцце ў адну лінію АПЗ

і г. д., і г. д.

РВП таму ў наступным пакаленні мы будзем чакаць наступнай матрыцай:

Конвей гульня жыцце ў адну лінію АПЗ

Што мы павінны зрабіць, каб знайсці суму ўсіх суседзяў кожнай клеткі дадзенай матрыцы ? Лік суседзяў роўна 8, таму, калі мы будзем пераносіць наша матрыцы 8 раз у кожным магчымым кірунку, а затым скласці разам усе 1С у атрыманыя ячэйкі - сума будзе роўная колькасць 1С (г. зн суседзі) вакол гэтай суполкі.

На наступным малюнку вы можаце ўбачыць усе 8 матрыц пасля такога пераходу:

Конвей гульня жыцце ў адну лінію АПЗ

Зараз давайце сумуецца ўсе гэтыя матрыцы, за выключэннем арыгінала:

Конвей гульня жыцце ў адну лінію АПЗ

Вось пільны погляд на некаторыя з клетак, якія паказваюць на сваіх суседзяў у зыходнай матрыцы:

Конвей гульня жыцце ў адну лінію АПЗ

Мы атрымалі матрыцу, дзе кожная вочка змяшчае лік суседзяў з жывых клетак у зыходнай матрыцы!

Цяпер, згодна з правіламі жыцця тыя клеткі, якія маюць 2 або 3 суседзяў будзе жыць у наступным пакаленні, а ўсе астатнія памруць. Пустыя клеткі роўна 3 суседа народзіцца ў наступным пакаленні.

Выконваючы некалькі нескладаных лагічных аперацый над матрыцай і суседзяў мы атрымаем наступны generaion нашага семафора.

Маючы план дзеянняў, мы зможам пачаць дэталевую прапрацоўку праграмы.

І вось гэта:

Конвей гульня жыцце ў адну лінію АПЗ

Расшыфраваць праграму мы будзем рухацца справа налева, таму што гэта шлях на APL інтэрпрэтатар рухаецца. Для выгоды (і толькі для зручнасці, бо няма нічога ў APL, якое дыктуе гэта) мы падзелім нашу праграму на лагічныя блокі так, як паказана на малюнку ніжэй:

Конвей гульня жыцце ў адну лінію АПЗ

Такім чынам будзе лягчэй сачыць за падзеямі.

Паміж апострафы есць радок, якая ўяўляе сабой "цела" нашага галоўнага цыклу (блок 1):

Конвей гульня жыцце ў адну лінію АПЗ

Першае, што адбываецца тут-гэта заключыць выкананая аперацыя пры зыходнай матрыцы М: ⊂М. складзеце функцыя ператварае масіў любы памернасці ў скалярны (то есць масіў губляе ўсе свае памеры, у той час як яго ўнутраны змест застаецца нязменным). Гэтая сітуацыя даволі спецыфічная, таму карцінка можа спатрэбіцца:

Конвей гульня жыцце ў адну лінію АПЗ

Наступнай выклікаецца функцыя павароту: Конвей гульня жыцце ў адну лінію АПЗ. Яна круціцца матрыцы ў зададзены лік раз па адносінах да яго гарызантальнай восі (як відаць з формы функцыі). Для таго каб зразумець сэнс гэтай функцыі і растлумачыць сімвал " на яго права, давайце спачатку паглядзім у левы аргумент паварот, а менавіта выраз: (V,вольт←1 -1).

Два дзеянні адбываюцца і тут: зменнай V прысвойваецца вектара 1 -1 (гэта прадстаўлена як V←1 -1), а затым гэтая пераменная выкарыстоўваецца адразу (на самай справе гэтая пераменная будзе выкарыстоўвацца шмат разоў у гэтай праграме). Тут мы сустракаем новую функцыю - , (коска), якая называецца Catenate і служыць для счаплення двух элементаў у адзіны вектар. Такім чынам, выраз для V,з V←1 -1 вяртае вектар, які складаецца з чатырох элементаў: 1 -1 1 -1. Як мы ўжо сказалі, пабочны эфект гэтага выказвання-ініцыялізацыі зменнай.

Такім чынам, мы маем наступнае (блок 2):

Конвей гульня жыцце ў адну лінію АПЗ

Аператар " (які называлі адзін) ўплывае на функцыю павароту такім чынам, што кожны элемент левы аргумент круціць атрымаеце аналаг адпаведнага элемента ў парадку орг аргумент паварот і кручэнне матрыцы М будзе пара на пару.

(Адно слова аб аператарах: у той час як функцыі працы з масівамі і скалярамі, аператары працуюць на самі функцыі, г. зн. калі аргумент функцыі-гэта заўседы масіў або скаляр, аргумент аператара-гэта заўседы функцыя).

Вядома, кожны аператар можа быць выкарыстаны з любой іншай функцыяй опл.

Заўвага: у выпадку, калі адзін з аргументаў функцыі з'яўляецца скаляром (а вы памятаеце, што ў зыходнай матрыцы м быў ператвораны ў скалярном па падкладаюць), гэта скалярны стане вектара з лікам элементаў роўным адпаведнае колькасць элементаў вектара, якое з'яўляецца адным з аргументаў функцыі. Гэта азначае, што мы можам бачыць нашы выразы, як:

Конвей гульня жыцце ў адну лінію АПЗ

Цяпер легка зразумець, што адбываецца. Матрыца М круціцца чатыры разы вакол сваей гарызантальнай восі: адну радок уверх, на адну радок ўніз, ізноў на адну радок уверх, і зноў на адну радок ўніз.

Вось вынік:

Конвей гульня жыцце ў адну лінію АПЗ

Што ў нас тут-гэта прамежкавы вынік, вядома. На самай справе, мы павінны перакласці кожную з гэтых матрыц злева і справа, каб атрымаць дыяганальныя зрухі пасля ўсіх. І паколькі мы ўжо маем усімі неабходнымі ведамі, мы можам зрабіць гэта з гэтым выразам:

Конвей гульня жыцце ў адну лінію АПЗ

Зноў, мы выкарыстоўваем функцыю павароту, аднак на гэты раз яна будзе паварот матрыцы вакол вертыкальнай восі (як сімвал мае на ўвазе). Аператар кожны будзе працаваць на ўсіх чатырох матрыц па левай аргумент павярнуць: налева, направа, направа, налева. Акрамя таго, каб атрымаць максімальную прыбытак ад зменнай V, то будзем выкарыстоўваць яго і тут, і замест вектара 1 -1 -1 1 мы напішам (V,Конвей гульня жыцце ў адну лінію АПЗV). Тут павярнуць зноў выкарыстоўваецца і прымяняецца да V сябе.

Можа быць, гэта выраз не дапамагаюць растлумачыць рэчы тут, але гэта так APL-падабаецца!

Цяпер мы ведаем, што вынік выразы

Конвей гульня жыцце ў адну лінію АПЗ

падобна на тое. Мы будзем называць блок 3:

Конвей гульня жыцце ў адну лінію АПЗ

Пасля матрыцы M зрушваецца ва ўсіх напрамках па дыяганалі ўсе прадумана-гэта зрушыць яго ўверх, уніз, налева і направа.

Такім чынам, вынік выразы

Конвей гульня жыцце ў адну лінію АПЗ

будзе:

Конвей гульня жыцце ў адну лінію АПЗ

І вынік выразы

Конвей гульня жыцце ў адну лінію АПЗ

будзе:

Конвей гульня жыцце ў адну лінію АПЗ

Нарэшце, матрыца перамяшчаецца ва ўсіх 8 напрамках. Знайсці колькасць суседзяў кожнай клеткі мы павінны зрабіць вектар, які складаецца з матрыц у нас да гэтага часу і прасумаваць ўсе элементы вектара. У APL мы можам зрабіць, гэта проста такі:

+/ (Блок 5) , (Блок 4) , (Блок 3)

Вось яшчэ адзін аператар прадставіў. Гэта называецца скарачэнне і выглядае як Слэш: / скарачэнне аператар ўстаўляе яго функцыі-аргументу (у дадзеным выпадку даданне функцыі) паміж усімі элементамі дадзенага вектара. Адзначым таксама Catenate функцыя, якая стварае вектар усе блокі. Вось што мы маем:

(матрыца 1 блока 5) + (матрыца 2 з блока 5) +

(матрыца 1 блока 4) + (матрыца 2 з блока 4) +

(матрыца 1 блок з 3) + (матрыца 2 блока 3) + (3 матрыцы блока 3) + (матрыца 4 блока 3).

І цяпер у нас есць матрыцы ўсіх суседзяў. Гэта вынік выразы, якія мы назвалі блок 6.

(Мы павінны дадаць тут, што існуе яшчэ адна функцыя, якую выконвае над атрыманай матрыцы - раскрываць: ⊃. Ен з'яўляецца поўнай супрацьлегласцю складзеце функцыю. Гэтая функцыя ператварае скалярны які змяшчае матрыцу назад у матрыцу з зыходнымі памерамі).

Наступны крок, як было сказана, - знайсці ўсе вочкі з лік суседзяў роўна 2 ці 3, Так што яны будуць працягваць жыць у наступным пакаленні, і знайсці пустыя клеткі лік суседзяў роўна 3, Так, што новыя клеткі будуць нараджацца там.

Па-першае, давайце параўнаем матрыцы суседзі з матрыцай, напоўненых 2С (блок 7), так што ў выніку мы атрымаем матрыцу з нулеў і адзінак такім чынам, што тыя, якія адпавядаюць вочках, якія маюць роўна два суседа:

2=т←матрыца ўсіх суседзяў (блок 6)

Тут зноў жа два дзеянні выконваюцца паралельна: зменная T атрымлівае значэнне матрыцы суседзямі і ў той жа час па параўнанні з матрыцай 2С (звярніце ўвагу, што скалярны "2" пашыраецца да матрыцы 2С памеры якой роўныя матрыца гэта па параўнанні з - вось як працуе АИП).

Вось як у параўнанні выглядае ў рэальнасці:

Конвей гульня жыцце ў адну лінію АПЗ

І вынік гэта:

Конвей гульня жыцце ў адну лінію АПЗ

Як вы бачыце, выніковая матрыца змяшчае ў кожнай клетцы ў выніку параўнання адпаведных клетках матрыцы аргумент. 1 азначае, што клеткі роўныя, 0 - У адваротным выпадку.

Калі мы будзем выконваць лагічную аперацыю і (кастрычніка∧) над гэтай і арыгінальнай матрыцы М (блок 8), то есць 1С застанецца толькі ў тых месцах, дзе абедзве матрыцы маюць 1С, мы атрымаем матрыцу, у якой толькі жывыя клеткі з'яўляюцца тыя, якія маюць роўна двух суседзяў:

Конвей гульня жыцце ў адну лінію АПЗ

Сапраўды, у зыходнай матрыцы М толькі Цэнтральная вочка мае роўна двух суседзяў.

Такім жа чынам мы можам знайсці ўсе ячэйкі, якія мае роўна трох суседзяў. Заўвага хітрасць тут у тым: не важна, ці з'яўляецца зыходная ячэйка пустая або мертвым: мы павінны дазволіць жывыя клеткі жыць і запоўніць пустыя клеткі з толькі што быцам нарадзіліся 1С.

Вынік выразы 3=т (блок 9), дзе T, як вы памятаеце, з'яўляецца матрыцай суседзяў, будзе:

Конвей гульня жыцце ў адну лінію АПЗ

Гэтыя клеткі павінны нарадзіцца ў наступным пакаленні.

Нарэшце, мы павінны дадаць лагічна (з дапамогай OR (∨) аперацыі) абедзве матрыцы з апошніх двух выразаў і - вуаля! - мы падлічылі, што наступнае пакаленне жыцця для матрыцы М!

Цяпер усе разам:

Блок 10 ← матрыца усе суседзі

(3=т)∨М∧2=т ← матрыца ўсіх суседзяў

дасць вынік:

Конвей гульня жыцце ў адну лінію АПЗ

якое па сутнасці з'яўляецца наступным пакаленнем семафора.

Цяпер трэба раздрукаваць атрыманую матрыцу і мы зробім гэта, выкарыстоўваючы APL вываду функцыя называецца квад: Конвей гульня жыцце ў адну лінію АПЗ(гэтага дастаткова, каб "прызначыць" матрыца гэтай функцыі).

Аднак, мы не скончылі.

Памятаеце, што да гэтага часу ўсе, што мы рабілі разлік аднаго пакалення. Акрамя таго, усе дзеянні па-ранейшаму "замарожаныя" паміж апострафы. Такім чынам, што ж адбываецца ў гэтым радку ?

Паглядзіце на блок 11. Зменнай s прысвойваецца радок пазначаецца блок 1. Звярніце ўвагу яшчэ раз: S не роўна сэнс (ці значэнне) радка s роўны самой радкі, г. зн паслядоўнасці знакаў паміж апострофами. Такім чынам мы адцягваем выкананне блока 1 да моманту, калі ўсе будзе гатова для вылічэнні N пакаленняў жыцця. (Памятаеце, што блок 1 вылічае толькі адно пакаленне).

У сваю чаргу s ад вектара знакаў у скалярную мы будзем выкарыстоўваць складзеце функцыі якія ўжо добра вядомыя нам. Рухаючыся налева, мы адкрыем новыя функцыі - змяніць (ρ) з левай параметр N, які прадстаўляе лік пакаленняў, мы хочам разлічыць. Гэтая функцыя ператворыць цяпер скалярно на вектар з N аднолькавых элементаў, кожны з якіх змяшчае блок 1, Што з'яўляецца "падпраграмы" для разліку аднаго пакалення. Так, у агульным, у нас есць вектар з скалярных велічынь, якая складаецца з вектара знакаў.

У канчатковай мэтамарфозу - яшчэ адна функцыя прымацаваць (∈) служыць для стварэння простых вектарных з масіва, якая складаецца з любой колькасці ўкладзеных элементаў. Такім чынам, наш "комплекс" вектар з N ўкладзеных элементаў стане адным вельмі доўга, але прамалінейны вектар знакаў. Давайце назавем гэта як-то выключна, каб падкрэсліць важнасць гэтага вектара, скажам Á, як матэматыкаў часта рабіць.

Вось на што трэба звяртаць увагу: кожная з падрадкоў (г. зн. кожны блок 1) вектара Á пачынаецца з сімвала М (арыгінальнай матрыцы) і заканчваецца аператар прысвойвання ← (як звычайна, пачатак і канец-злева). Гэта самы правы сімвал Á - з'яўляецца зыходнай матрыцы м, і сам вектар выглядае наступным чынам (ўнутранае ўтрыманне прапушчаны):

Конвей гульня жыцце ў адну лінію АПЗ

А вось і мы! Цяпер зразумела ў чым справа: калі радок Á выконваецца справа налева, кожнае зноў вылічанае значэнне матрыцы М (г. зн. кожнае новае пакаленне жыцця) будзе прызначаная адна і тая ж пераменная M як новыя арыгінальныя матрыцы для вылічэнні наступнага пакалення! І колькасць пакаленняў будзе роўная N.

Адзіная астатняя праблема-што рабіць з крайняй левай, што вісіць у паветры аператар прысвойвання ←. Паглядзіце на ўсю праграму яшчэ раз - у самым канцы стрэлку едзе прама ў сімвал - Конвей гульня жыцце ў адну лінію АПЗ квад - які звязваецца з вектарам Á коску (Catenate). Але ці не азначае гэта друкаваць усе ? Сапраўды, вось што нам трэба!

І нарэшце ў канцы гэтага грандыезнага акта мы сустракаемся функцыю Конвей гульня жыцце ў адну лінію АПЗ(выканаць) - у адной мы ўжо знаемыя. Гэтая функцыя выконвае знакавую радок, якая гэта аргумент функцыі. Натуральна, радок павінна змяшчае сінтаксічна правільныя выказвання з АИП. Такім чынам, што гэта за функцыя ? Гэта APL перакладчык сам замаскіраваны пад нявінную функцыю.

Ну, які будзе вынік выканання нашага вектара па перавазе Á ?

Пстрыкніце правай кнопкай матрыц надрукавана на экране, якія ўяўляюць N пакаленняў жыцця, пачынаючы з арыгінальнай матрыцы. М.

paper4pc
Add a comment:
Sign in

See also

Šakutės-prisijunkite prie Plėtros Java™ SE

Šakutės-prisijunkite prie Plėtros Java™ SE

2015-11-09 15:37:23

Šakutės-Prisijunk kasdien, multi-core Java™ programas Šakojimasis arba skaidant darbo krūvį į keletą užduočių, lygiagrečiai perdirbti ir įstojimo į rezultatus, kartu yra...

Genetic Algorithms

Кароткае Ўвядзенне Ў Генетычныя Алгарытмы

2015-11-09 17:11:42

by Moshe Sipper Ідэя прымянення біялагічных прынцып натуральнай эвалюцыі штучных сістэм, уведзеныя больш чым тры дзесяцігоддзі назад, назіраецца ўражлівы рост у...

Obtaining and Interpreting Image Data

Пятніца пытанні і адказы 2012-08-31: атрымання і інтэрпрэтацыі дадзеных выявы

2015-11-09 19:50:55

by Mike Ash Какава змяшчае некаторыя выдатныя абстракцыі для працы з выявамі. NSImage дазваляе апрацаваць выявы ў выглядзе непразрыстага шара, які...

Узрост Георга III

Эпоха Георга III

2015-11-09 17:52:09

Дзесяцігоддзе міністэрскай нестабільнасці 1760-1770 Георг III стаў каралем 25 кастрычніка 1760, пасля смерці свайго дзеда Георга II і быў каранаваны ў...

Art for designers dkcoin8.com (DesignerKit)