辛几何&李代数

中医经络的终极秘密

中医经络的终极秘密

一直不太愿意把这个图发上来,尽管只是一个模式图,但经络的所有秘密全部包括在其中了,如果你有缘,从此可以领悟经络的终极奥秘。 这个模式图应该这样看:最下面二个框表示是二条腿;中间的框表示是躯干,左右二边的框表示为二手,顶部的二个框表示为头部,为理解上的方便分成左右头。中间躯干部黑色的线条表示... 阅读全文

 中医经络的终极秘密

 

       一直不太愿意把这个图发上来,尽管只是一个模式图,但经络的所有秘密全部包括在其中了,如果你有缘,从此可以领悟经络的终极奥秘。 

 中医经络的终极秘密
中医经络的终极秘密
       这个模式图应该这样看:最下面二个框表示是二条腿;中间的框表示是躯干,左右二边的框表示为二手,顶部的二个框表示为头部,为理解上的方便分成左右头。中间躯干部黑色的线条表示为任脉或督脉,其它小线条就是手、头、足的三阴或三阳经了。

      这里只给出了督脉的模式图,任脉同理。

      表里经的只给出了厥阴和少阳的模式图,其它的同理。各位可自行画出。

      任督主要的是在头部达成经气的左右交换。

      表里经最重要的基本活动是在头、手、足远端的经气交换,这是最核心的秘密,也是从医者唯一能干预的部分。各位要自行领悟了。

 中医经络原来如此简单中医经络的终极秘密

 

       最近几天,基本上把我领悟的经络系统做了比较全面的整理,当变成文字和图示后,发现中医的经络是如此简单!中医治疗也不用弄得那么复杂,完全可以用非常短的时间就可以入门。唯一的难点是如何从传统的思维里转到用“六经”辨证,只要把归经区域弄清楚,无论是针灸、按摩、药物均可信手拈来,解决一些认为是疑难病的痛苦。

        这些东西本来应该做为不传之秘,自己使用就好,但思之,67亿人为什么选择了我来悟透经络秘密?不敢藏私,发在博客里,供同好研究,各人如何阐发,即是机缘。

       这里所谈的“六经”,不是传统意义上的六经辨证,因为现在的六经的归经区域扩大了可能不止十倍,请各位自赏之。

       各位看后,有何感想,不必在此讨论,我无意做口舌之争,原则只有一个,你觉得有用就拿去,没用就别费神去看了。

       中医基本上掌握一个“开、合、升、降”就够了,只是开什么?如何开?闭什么?如何闭?升降亦如此,当你弄明白这些,中医大师非你莫属。

       任何一个理论,个人认为,要能完整解释按摩、针灸、药物、修练才是真正符合人体生理病理的,我期待着有比我这个理论更完善的解释。前提是你的解释要符合最基本的物理和常识。 

 

 

六经的阴阳虚实到底指什么?中医经络的终极秘密

 

 

       六经在受精后发育成人的过程中,会不断的形成一个类似“充电”的过程,让六经充满电荷,这个电荷的多少在出生时基本确定,是为先天虚实;出生后在女子第一次排卵,男子第一次遗精之前,卵母细胞和原精细胞还会转化成电荷继续通过肾经充实骨髓和脑髓,是为藏精。换过说法,从出生那一刻起,人体六经的电荷就基本确定了,这个电量决定了人体的先天身体素质。

       这个充电的过程是严格分开的,阴经的电量主要来自卵黄囊和母体,阳经的电量则来自季节的光热,正因为这样,在体表阳经分布的面积又最大,所过的部位最多,又处于外侧面,所以,人体与季节有一定的互动,如果季节反常,在体内相应不足的阳经就会起明显感应;如不能及时处理,因表里经的循环影响,又会影响到相应的里经。严重的就会通过经气的大循环影响到下一级或上一级表里经循环,从而发展成全身的疾病。

       出生后后天的补充主要通过食物直接吸收和阳光照射的光和热(包括储存的光热如电热,火热,食物也是储藏的热),这些光热会直接转化成阳经的“电量”和阴经的“电量”。如红光或红色食物转化的是阳经的“电量”,蓝光、黑光或黑色食物转化的就是阴经的“电量”。

      所以阴虚指的是三阴经“电量”不足,阳虚指的是三阳经“电量”不足。 

 

六经的基本运行原理中医经络的终极秘密

 

       六经是表里阴阳相配合的运行,太阴与阳明;少阴与太阳;厥阴与少阳,一共三对,分成左右两边,正常运行时,表里运行方向相反,左右运行也相反。交换的速度约为每秒一次(有资料说是每分钟64次,又与八卦的八八之数吻合,不知是巧合还是古人真的是从数理推医理或者从医理发现数理)。具体如下,左太阴经下行,左阳明经上行,同时右太阴经上行,右阳明经下行;左少阴经上行,左太阳经下行,同时右少阴经下行,右太阳经上行;左厥阴经上行,左少阳经下行,同时右厥阴经下行,右少阳经上行;简单总结,就是总有一侧的阴经在上,一侧在下,阳经也是如此。

       任、督脉在中间起到沟通左右两侧同名经的经气作用。

       这个运行的主要意义在于,通过这个上下运行过程进行阴阳经气的交换,在阳经下行时,通过在足部膝关节以下的络穴把阳经的经气一小部分交换到阴经,同时阴经在头端(严格来说是胸腹部的迷走神经)把阴经的部分经气交换到阳经,反运行时,足端交换一小部分经气到阳经,头端的阳经也交换一小部分经气到阴经。这样做的目的,是维持阴经不过寒,阳经不过热,达成一种平衡。如果因为某种原因,阴经在头端不能交换经气到阳经,但阳经却可以交换过来,也就是没有把位置空出来,就会造成该条阴经因上方没有位置不能上升的现象,这种现象累积一段时间后,相应的阳经因下端阻力太大,也不能再完成足端的交换,这时个表现的就是阳经升而不降,阴经降而不升,相应的疾病就发生了。这个现象已为武当山道医祝华英通过内视阐发了完整的内经运行,各位可参考他的著作《黄帝内经十二经揭秘》。

       本人在此把他的发现做了更进一步的发展而已,一方面把他没有说明白的十二经概括为六经,因为手的三阴三阳经其实是与足的三阴三阳经是相通并同步运行是,当你把手心向前,双手上举,就很容易明白我说的是真理。另外,本人把冲、带二脉去掉了,原因很简单,冲脉基本上是迷走神经的内容,上传下达的描述都一样,但迷走神经中间三阴经均有,所以说任、冲统三阴也不为过,只是多此一举了。带脉就是少阳胆的所过,不需要专论。其它奇经四脉阴阳跷、阴阳维除增加理解的难度外,都是后世拼凑之物,均在六经之内,不作专论。

       至于任脉、督脉只是三阴三阳经的交换通道,在实际应用时只有按摩、修练,艾炙用得较多,只略谈如下:

       任脉实际上浅表的分布在腹白线的两侧约二分处,可以这样说任脉是由左右二条构成的,这已为武当山的祝道长在练功中证实,这与现代解剖左右肋间和肋下神经在胸腹部没有交叉吻合,为什么会出现左右明显不同的表现原因就在于此。深层的任脉则是左右迷走神经,所以当要沟通左右任脉时为什么是在鸠尾穴,如果你注意解剖,这正是左右迷走神经走得最近的地方(胃的前、后支)。

       督脉在浅层也有左右督脉,其实与任脉一样,都是通过肋间神经联系。在腹部主要看到的督就在左右交感干,沟通左右督脉的穴位是尾闾穴,深层其实就是奇神经节。督脉的其它部分深层就要在脊髓里找了。

任督脉的主要作用是沟通左右的三阴三阳,主要的沟通位置是大脑的胼骶体,从解剖来看左侧的神经纤维从这里交换到右侧,右侧的神经纤维从这里交换到左侧。当然在脊髓各段的白质、灰质也有左右交换,这恰恰从解剖上支持中医的任、督是有物质基础的。因为左侧的阴阳表里经与右侧的阴阳表里经是相对独立运行的,如果没有任督的居中沟通,左右就会表现为明显的不同。

       只是各位要特别注意的是,任督是左右三阴阳经的居中通道,也就是三阴先交换到左右任脉,左右任脉再完成左右交换,督脉也是同样道理。所以任主三阴,督总三阳是不无道理的。三阴三阳相当于任督的二级机构。

       从这里我们很容易明白,大脑两半球其实就是左右三阴三阳的储能器,至于是大脑管阴,小脑管阳还是同时管,就有待各位去研究了。实际应用中意义不大,就不在我关注的范围了。 

基于六经的基本运行规律,有以下内容要强化:

       左肝右肺说:因为肝体在右,也就是储备在右,肝经更容易得到补充,所以在右侧的肝经上下行均不会太容易出问题,但左侧的肝经要经过头部的交换后才能补充电量,可能会出现滞后或不足的情况,表现为升降不足,尤其是要克服引力的升可能不足,容易表现出症状,所以左侧病常责之肝。

       肺是同样原理,虽然肺本身的储备大,但比较而言两侧差不多,但同是太阴的脾却在左,可以直接补充左侧太阴的电量不足,所以左侧太阴的升降会比较易趋于正常,但右侧的太阴却要通过头部的大脑向对侧交换后才能补充,所以右侧的毛病比较易见。

       左肝右胆说:肝胆储备均在右,按说弱方都应该在左才对;这是因为没有注意到肝阴胆阳,同侧肝经升时胆经却要降,肝右升降的力足,胆升降的力量就为肝所左右,自身的力量显得微不足道。左肝的原理如上。所以在右侧主要表现出来就是胆经的疾病。所以身体右侧的问题多从胆经着手,促降而获得疗效,左侧从肝经入手,促其升发而获得佳音。

       脾升肝亦升,肝升脾亦升:三阴经除肾经外迷走神经是主要上行通路,肾经还有一个重要路径是脊髓。

 

 关于三阴经

 

       太阴循行从脚到延髓到舌下,到手,内部有交感和迷走神经的部分神经来络脾和肺,胃及大肠,上达嗅神经,如果从体积和表面积来看,脾很小,肺的表面积很大,另外还有全身肌肉所过神经和末鞘(特别注意隔肌的隔神经),全身皮肤所过神经及末鞘,是全身最大的分布面积,当然细胞容量也最大,神经分布范围也最广。它们能充的电荷容量也是最大的。因为同属太阴系统,所以脾摄气,即是摄取食物的“电量”,肺主气,生宗气等均是同理,因为没有来源,其它经所需要均无来路。脾为生“痰”之源,肺为储“痰”之器,所谓“痰”就是食物化生的精华物质,用现代的可见物描述就是淋巴管乳糜池里的乳糜。要经过静脉回流到肝、肺的。经常吐痰的人和误用“吐痰”法太多为什么伤害身体,使人虚亏即是此理。脾气的升清升的就是这个“乳糜”,肺气要降也是降这个“乳糜”。因为有脾和肺作为储“电”的容器和充电器,比较而言,阳经没有这个“设备”,所以经常表现为“阳常不足,阴常有余”。

       少阴经循行从脚心至盆、腹、胸、脊髓到延髓到耳神经和舌咽神经,还有手上所过,内部通过迷走神经,交感神经等主干络心络肾;另外还有全身的骨、骨髓分布的神经和连接纤维,全身血管分布的神经及末鞘。同样骨髓和脑髓构成了少阴经的储藏设备,是藏“精”之所。精化“气”会从最远端的骨髓---小腿骨髓开始,所以为什么“肾虚”的病人会有小腿酸软无力的现象。心肾不交,水火不济都是骨髓所藏之精不能及时抽取气化补充少阴的电量所至;更严重的是已经抽取到没有储备的地步,要抽取脑髓时脑萎缩就出现了。少阴的腰骶神经丛连接生殖腺,卵巢膀胱并通过脊髓上行是少阴经的一个特殊性。

       厥阴经表浅循行从脚到盆、腹、胸、手,内部循行从交感干、迷走神经到脊髓上达视神经。其它是所有连接筋腱、内部的韧带和骨膜的神经及神经末鞘。这些筋膜包括了肛门括约肌,尿、生殖口括约肌,毛孔的微小肌肉等等环状的肌肉。还有所有连接除性腺之外所有腺体、油膜的神经。油膜主要指的是腹部的肠系统膜和腹膜,所以过度肥胖当从厥阴入手处理。肝是人体厥阴最大的一个储备库,其它还有如脑下垂体、肾上腺、甲状腺等腺体的储备。厥阴系统又是体内反应最快也是最强烈的系统,所有情志类的影响首先从厥阴开始,基本原理是“视”刺激会使厥阴肝经头端不断累积电荷,导致表经胆木不能上升,所以很快两肋有蹩胀感,其它厥阴系统的腺体反应是呼吸、血压、汗腺方面的改变。“听”的刺激同理,因听神经也同样通过延髓上传到下丘脑核,而这些脑核均受视交叉上核的统一控制,另少阳胆和三焦均在耳在丰富的神经连接,所以无论听还是嗅,触、尝产生的刺激,均可引起厥阴的改变而引发经气的偏差而致病。而七情均由五感(视、听、触、嗅、味)引发。

       三阴经与五脏直接维系,所以升降正常与否关系到五脏的功能是否正常。因肺升太过会导致咳喘等升而不降的症状,所以肺以降为用,多关注肺经的降一面;心经升而不降也会导致上部一片“火”象,也是下降为主,心包经同理;

       但对于脾经,因要升清,摄气,需以升为主,要关注升的一面;肝经也是同样,降而不升则害疏泄太过,导致“水”排出太多,同样注重的是升的一面;

       肾经就更特别,如降太过则封藏失司,表现为滑泄、遗精,所以特别注重升的一面。只要升肾水(脊液)才能上升,才能把头部的热量带下来,当然头部热的能量也能温暖腰部,在整个背部分布的膀胱经就能再吸收这些热量达到补阳的目的。(这就是水火既济,肾水上济心火) 

 

 

关于三阳经

 

 

       太阳经包括了左右太阳经,手足太阳经,头部太阳经,还有看不见的体内络属部分小肠和膀胱,都是人体循行范围最大,所过面积最多的阳经,所以所有的阳虚证最后都要归到太阳经,太阳经足可以说全身阳都足,如果不足,首当其冲的就是小肠部分,因在腹部所占面积最大,又分布在小腹部,在体表就可以摸到小腹是一片阴冷。热食、热药通过小肠的神经末鞘直接补充太阳经的电荷,在小腹艾炙或按摩为什么能强壮即是通过热电转换加强太阳经的电荷,均达到补阳作用。同样,你会发现当表现为心阳不足时,也是补太阳,药物都一样。经常食用寒冷食物或寒性的食物均会首先波及太阳经,因为太阳经在腹部所占面积最大,需要更多的阳性电荷去中和这些阴性电荷时,太阳经是首当其冲的。当然阳明经也会深受影响,但少阳相对影响会小一些,因为它处于“半表半里”,吸收的是二次能量。

       阳明经从脚到头,到手,内部络胃及大肠,上达三叉神经到面部和额部;循行面积是三阳经里最小的,对于整个“阳”的影响有限,所以为什么在讨论脾阳不足时,均从补肾阳着手,其实脾阳就是胃阳,肾阳就是膀胱的太阳经,因胃阳影响有限,不如从补太阳着手来得实际。脾阳虚时是背心巴掌大的一块寒冷,基本与心阳对应,但从经络论均为太阳经所辖。事实上,从生理结构上看,热食也好,热性药也好,进入肠胃,胃的面积吸收有限,远不及小肠的面积大,停留时间长,当然进入的阳热转换电荷是明显不同的,但都可以达到补阳明和太阳的目的,自然所反映的脾阳虚及肾阳虚都解决了。

       少阳经浅表的从脚到头,手,整个侧头面、侧胸、腹、盆面均为所过,内部络三焦和胆,三焦在这里可理解为是整个的胸、腹、盆腔的外膜,吸收的是整个胸腹盆部的热再散发的热;少阳胆是一个比较特别的系统,原因是胆囊很小,面积有限,吸热当然很小,而且胆囊并没有办法直接吸收到食物和药物的直接热量,跟三焦一样,只能吸收太阳、阳明吸收后散发到胸腹盆腔的剩余热量。这种热量当然是有限的,也正因为这样,尽管少阳所过总面积很大,但因热转换有限,对三阳的影响是很小的。在临床应用中,也很少会用到补充少阳的药物和方法,只有极少情况下,肝阳表现不足时(实际就是少阳不足),要用到些补肝阳(实际是补少阳)的药物。肝体阴而用阳指的就是这种情况。由于阴经除肝经上达视神经比较表浅外,均不到头部浅层,肝经的直达颠顶其实是少阳经所过,所以颠顶头痛责之少阳胆经即可。但因头顶表浅和颅内血管神经均为少阳胆所主,所以如果胆经上而不下(这时肝经下而不上),是为肝阳上亢,表现为高血压;由于左右肝胆的表里经是分开反向运动的,所以左侧不能正常则左则血管可能因高血压而破裂,是为脑出血而至偏瘫。

从三阳各部所循行部位和所过面积就可以知道,太阳经的容积是最大的,其次是少阳经,最少的是阳明经,所以太阳经的电荷量最多,少阳次之,阳明最少。阳明并太阴构成中气,电荷最少,也就是“气”最少,“中气”易虚即从此来。

       三阳经均上达头面,尤其是少阳胆经,控制了头部的很多重要的神经,特别是血管的神经,一旦出现“肝阳上亢”,也就是胆经上而不下,只升不降的时候,很容易造成血管意外。其它如眼突、流泪、失眠、耳痛、化脓,发胀,偏头痛等均为常见;即便是阳明经的上而不下,也会造成眉棱骨痛,额部胀痛等不适,至于口舌齿的“火”症(溃疡、疮、肿、痛等)更是让人痛不欲生。至于较轻点的太阳不降,也会有明显的太阳穴胀痛,后脑发胀,昏沉等症状。

       所以在实际临床时,要随时关注三阳经的降,尤其是少阳胆经的降更是重中之重。

 

 五脏五阴经主要功能

 

      其实应为六脏六阴经,但心包经一直没有单列出来,这里沿用旧习。

肝经主疏泄,凡全身水液不能外泄,体内废物不能外排的问题均在肝,与肺完成开合功能。

肺经主收敛,凡全身水液外泄太过责之肺;与肝相对应,完成一开一合的功能

肾经主收藏,凡全身精华物质和能量不能完成储藏的问题均在肾找,精华物质和能量的外泄找肾。

脾经主运化,凡外来物质不能让身体吸收利用,均在脾。

心经主血液,凡血液方面,部分组织失去营养方面的问题从心治。

心包主脂肪,凡全身脂肪代谢、腺体分泌问题责之心包。

阴经无非就两件事

       一、是“水”的“藏”问题,一个是“化”的问题;用现代语言来说就是水液代谢,高渗、低渗的问题,水是进入细胞还是流出细胞的问题。基本上为肝肺所主。

       二、“精”的吸收和收藏,食物精华的吸收、利用、储存问题。为心脾肾所主。

迷走神经走到大肠的上段,小肠的全部,胃更是有前后支的包绕,故三阴经可直接从食物中吸收负能量转化为电荷。光热中阳性能量,只从阳经吸取,阴经只吸取阴性电荷。任何食物均有阴性阳性二面,表现为阳性多为热性食物,阴性多为寒性食物;药物也是同理。你也可以理解为只吸取负电荷,所以阴经所过或成为主要控制对象会表现为一片寒凉。 

 

 

六腑六阳经的功能

 

 

       少阳胆,协助厥阴完成水的疏泄功能,同时间接吸收食物中青绿色光热的能量转化为少阳的电荷,以补少阳。

       少阳三焦,同样是协助完成心包经的代谢、分泌功能。同时间接吸收食物中青绿色光热的能量转化为少阳的电荷,以补少阳。

       阳明胃,协助脾完成吸收功能,同时吸收食物中橙色、黄色的光热能量,补充阳明电荷,补充经气。

阳明大肠经,协助肺完成水的收敛功能,同时吸收食物中橙色、黄色的光热能量,补充阳明电荷,补充经气。

       太阳膀胱,协助肾完成藏的功能,间接吸收食物中紫色、红色的光热能量来补充太阳经的电荷。

太阳小肠,协助心完成血液的生成运输功能。直接吸收食物中紫色、红色的光热能量来补充太阳经的电荷。

阳经主要解决的是“火“的问题,凡全身阳热不足,寒冷;反之,发热、上火等均在阳经找答案。阳经只吸收阳性的能量来转换,你当然可以理解为只吸取正电荷,所以阳经控制为主时,因主要释放的是阳电荷,表现为一派热象。至于是何经控制就要看所循行所过部位了。 

 

 

相对独立的六大经络体系,中间主要靠任脉督串在一起中医经络的终极秘密

 

 

        经络体系(不叫系统,以免混淆)细分可以分成三大块,左右加在一起,可以叫六大经络体系,具体表述如下:

       手体系、脚体系,头体系,它们运行时是相对独立的,尤其是左右两侧更是严格分清独立运行,但左右总是要串在一起的,交换的部分现在解剖支持的就是左右大脑半球的胼骶体相互交换,实际上还要通过左右迷走神经在腹部进行另一个方向的交换。

       由于手体系和脚、脑体系还有一个双向的运动,就是阴、阳经的反向运行。但无论手、脚、头部的阳经因为串接紧密,所以经常是同时向同一个方向运行,基本分不出运行时间的差异。阴经则有一个时间滞后的问题,手、脚、头在异常运行时,几个体系还是有一个比较明显的差别,但也不会区别十分大,只是时间的相对滞后,没有同步而已。

       手、脚的经络无论是循行还是经络经过,均已有明显区分,头体系的经络却被强行归到手、脚的三阳经上,阴经则基本上没有描述,其实头部也是有阴经的,只是都在脑部深层运行,除厥阴可以在眼部明显表现外,基本在头部体表看不到。

 

 

收起全文

辛几何&李代数

免平方字符串

免平方字符串

字符串hello当中连续出现了两个l。字符串prototype当中连续出现了两个ot。字符串nonsense当中连续出现了两个nse。如果某个字符串中连续出现了两个相同的片段,换句话说这个字符串里面含有形如XX的模式(其中X代表一个子串),我们就说这个字符串中含有一个&平方&(square)。如果某个字符串中没有平方出现,我们就说这个字符串是&免平方&的(s... 阅读全文

字符串 hello 当中连续出现了两个 l 。字符串 prototype 当中连续出现了两个 ot 。字符串 nonsense 当中连续出现了两个 nse 。如果某个字符串中连续出现了两个相同的片段,换句话说这个字符串里面含有形如 XX 的模式(其中 X 代表一个子串),我们就说这个字符串中含有一个平方square)。如果某个字符串中没有平方出现,我们就说这个字符串是免平方的(square-free)。

如果只使用两种字符,比方说字符 0 和字符 1 的话,我们只能构造出一些长度非常有限的免平方字符串。事实上,我们只能构造出以下 6 个免平方字符串: 0 、 1 、 01 、 10 、 010 、 101。然而,如果允许使用三种字符,比方说字符 0 、 1 、 2 的话,我们不但能够构造出任意长的免平方字符串,还能构造出无限长的免平方字符串。在继续阅读下去之前,你不妨先自己试试看。

让我们先来看一个与刚才的讨论似乎毫不相关的问题。你能找出下面这个序列的规律吗?(考虑到字符串本质上就是一个字符序列,因此下面我们会经常混用字符串序列这两个概念。)

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 …

答案:它们分别表示 0, 1, 2, 3, 4, … 的二进制表达中有多少个数字 1 ,其中 0 代表有偶数个数字 1 , 1 代表有奇数个数字 1 。如果我还没说清楚的话,看看下表你应该就明白了。

十进制数

0

1

2

3

4

5

6

7

8

9

10

11

二进制数

0

1

10

11

100

101

110

111

1000

1001

1010

1011

1 的个数

偶数

奇数

奇数

偶数

奇数

偶数

偶数

奇数

奇数

偶数

偶数

奇数

序列

0

1

1

0

1

0

0

1

1

0

0

1

我们不妨把这个序列用 t 表示。序列 t 还有很多等价的定义,比方说,我们可以递归地定义,当n 为偶数时, t(n) = t(n/2) ,当 n 为奇数时,t(n) = 1 – t(n-1) ;最后再规定 a(0) = 0,整个序列就唯一地确定了。你会发现,定义方式虽然是新的,但是背后的实质仍然没变。如果 n是偶数,那么 n 的二进制表达的最后一位就是数字 0 ,除以 2 其实就相当于是去掉这个数字 0,数字 1 的个数的奇偶性显然没变。如果 n 是奇数,那么 n 的二进制表达的最后一位就是数字1,而 n – 1 的二进制表达的最后一位则是数字 0 ,这两个二进制数仅在最后一位有所不同,因此数字 1 的个数的奇偶性肯定是相反的。因而,不断这样递推下去,最后得到的序列与刚才的序列 t 一模一样。由于对于所有的偶数 n , t(n) = t(n/2) 始终成立,因此这个序列还有一个非常炫的性质:把序列中的 t(1), t(3), t(5), … 都去掉,仅保留 t(0), t(2), t(4), … ,由此得到了一个新的无穷序列,它和原来的序列完全相同!另外,由于对于所有的奇数 n , t(n) = 1 – t(n-1) = 1 – t((n-1)/2) 始终成立,你也可以选择去掉 t(0), t(2), t(4), … ,保留t(1), t(3), t(5), … ,由此得到一个新的无穷序列,它和原序列的每一项都正好相反。

在介绍序列 t 时,很多地方会采用另一种等价的定义方式:从 0 出发,不断执行取反并后置的操作,最终得到的序列就是序列 t 。所谓取反,就是把所有的 0 全部变成 1 ,把所有的 1 全部变成 0 ;所谓后置,就是把所得的字符串接在当前字符串的后面。从 0 出发,取反后得 1 ,把它加在 0 后面便得到 01 ; 01 取反后得 10 ,把它加在 01 后面便得到 0110; 0110 取反后得到 1001 ,把它加在 0110 后面便得到 01101001 ……不断这样下去,我们就会得到序列 t 。

 01  0110  01101001  0110100110010110  …

为什么?因为这种序列生成法的本质仍然是在统计二进制数的数字 1 的个数。我们不断地根据二进制数的规律,利用 t(0) 到 t(2n – 1) 的值,推出 t(2n) 到 t(2n+1 – 1) 的值。比方说,序列 t 的前 4 个数分别代表 00, 01, 10, 11 这 4 个二进制数中数字 1 的个数的奇偶性,那么序列 t 接下来的 4 个数就应该分别代表 100, 101, 110, 111 这 4 个二进制数中数字 1 的个数的奇偶性。前 4 个二进制数与后 4 个二进制数的区别仅仅在于最前面的那个数字 1 ,因而它们所含的数字 1 的个数的奇偶性应该正好相反。因此,如果序列 t 的前 4 个数分别是 0, 1, 1, 0,那么序列 t 接下来的 4 个数就应该完全反过来,分别是 1, 0, 0, 1 了。

 

从 1906 年到 1914 年,挪威数学家 Axel Thue 发表了一系列论文,第一次对这个序列进行了细致的研究,成为了 combinatorics on words 这个新的数学分支的开山之作。 1921 年,美国数学家 Marston Morse 把 Thue 提出的序列用在了微分拓扑上,因而这个序列最终被命名为了 Thue-Morse 序列。

Thue-Morse 序列有很多非常漂亮的性质。如果某个字符串中连续出现了两个相同的片段,但它们有一个字符的交叉,换句话说这个字符串当中出现了形如 aXaXa 的模式,其中 X 代表一个子串,a 代表一个字符,那么我们就说 aXa 在这个字符串当中发生了重叠overlap)。例如,单词banana 当中的 ana 就出现了重叠,单词 Mississippi 中的 issi 也出现了重叠。如果某个字符串中没有重叠出现,我们就说这个字符串是免重叠的(overlap-free)。下面我们就来证明Thue-Morse 序列的一个最为重要的性质:它是免重叠的。

我们采用反证法。假如 Thue-Morse 序列存在重叠子串,那么在所有的重叠子串中一定有一个最短的重叠子串。这意味着, Thue-Morse 序列将会包含 aXaXa 的模式,其中 X 表示某个子串, a表示某个字符,并且 X 的长度已经达到最小。首先我们证明, X 的长度不可能是奇数。否则,三个 a 的位置编号的奇偶性相同,因而如果我们从第一个 a 开始,间隔地读出各个字符,就会得到形如 aX’aX’a 的结果,其中 X’ 就是从 X 当中抽出的字符串,长度是 X 的一半(取下整)。然而,前面我们已经提到过 Thue-Morse 序列的性质了:间隔地抽取字符,得到的新字符串要么就是 Thue-Morse 序列,要么取反后就是 Thue-Morse 序列。这说明, aX’aX’a ,或者它取反后的结果,其实就是 Thue-Morse 序列的子串。因而, Thue-Morse 序列当中存在比 aXaXa 更短的重叠现象,这与 X 的长度的最小性矛盾。

接下来我们证明, X 的长度也不可能是偶数。首先注意到, 4n, 4n + 1, 4n + 2, 4n + 3 的二进制表达中,只有最后两位数字不一样,它们依次是 00, 01, 10, 11 。因此, t(4n), t(4n + 1), t(4n + 2), t(4n + 3) 的值要么依次是 0, 1, 1, 0 ,要么依次是 1, 0, 0, 1 。所以,如果我们把 Thue-Morse 序列四个数四个数地看作一组,你会发现 Thue-Morse 序列就是由一个一个的 (0, 1, 1, 0)  (1, 0, 0, 1) 组成的。

如果 X 的长度是大于等于 4 的偶数,那么不管 aXaXa 在 Thue-Morse 序列中的什么地方出现,前一个 aXa 里必然会包含某个四元组的中间两项,不妨假设这是 aXa 中的第 i 项和第 i + 1项。另外,别忘了 X 的长度是一个偶数,因此前一个 aXa 需要向右移动奇数个单位才能和后一个aXa 重合。这就矛盾了:向右移动奇数个单位后, aXa 的第 i 项和第 i + 1 项将会对应于另一个四元组的前面两项或者后面两项,于是前一个 aXa 的第 i 项和第 i + 1 项是两个相同的数字,后一个 aXa 中的第 i 项和第 i + 1 项是两个不同的数字,这显然是荒谬的。

免平方字符串

如果 X 的长度等于 2 , aXa 的长度会非常短,以至于会发生这样的情况:没有任何一个四元组的中间两项落在了前一个 aXa 的范围里,此时前面的推理就失效了。不过没关系,如果真的发生了这种情况, aXaXa 的位置只可能像下图这样,此时前一个 aXa 的第 1 项和第 2 项对应于某个四元组的后两项,但后一个 aXa 的第 1 项和第 2 项就会对应于下一个四元组的中间两项,矛盾依然存在。

免平方字符串

最后,如果 X 的长度为 0 呢?这就更不可能了。在 Thue-Morse 序列中,任意三个连续的字符都会涵盖到某个四元组的前面两项或者后面两项,因而包含两个不同的数字。因此,在 Thue-Morse序列中绝不可能有形如 aaa 的子串出现。

综上所述, Thue-Morse 序列中不可能包含形如 aXaXa 的子串,即 Thue-Morse 序列是免重叠的。

 

有了这个结论之后,我们就能解决本文最初提到的问题了。借助 Thue-Morse 序列,我们可以得到一个无限长的免平方字符串,其中只含 0 、 1 、 2 三种字符。方法很简单:只需要依次列出Thue-Morse 序列中相邻两个 0 之间有多少个 1 即可。在 Thue-Morse 序列中,第 1 个数字 0和第 2 个数字 0 之间夹着 2 个数字 1 ,第 2 个数字 0 和第 3 个数字 0 之间夹着 1 个数字1 ,第 3 个数字 0 和第 4 个数字 0 之间夹着 0 个数字 1 ,第 4 个数字 0 和第 5 个数字 0之间夹着 2 个数字 1 ……于是,我们就得到了一个以 2, 1, 0, 2 开头的无限字符串。注意,由于 Thue-Morse 序列中不可能出现三个或者三个以上的连续数字 1 ,因此所得字符串中不会出现大于等于 3 的数字,只有数字 0 、 1 和 2 。

Thue-Morse 序列: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0…
新的序列:2, 1, 0, 2, 0, 1, 2, …

为什么由此得到的序列是免平方的呢?很简单。如果新的序列里面出现了某个平方,比如 a1a2a3…ana1a2a3…an ,这就意味着 Thue-Morse 序列里出现了 0 1a1 0 1a2 0 1a3 0 … 0 1an 0 1a1 0 1a20 1a3 0 … 0 1an 0 (其中 1a1 表示连续 a1 个数字 1 ,以此类推),于是形成了重叠子串,与Thue-Morse 序列的免重叠性矛盾。

 

从 Thue-Morse 序列的免重叠性出发,我们还能得出很多有趣的推论。例如, Thue-Morse 序列一定是免立方的,即 Thue-Morse 序列中不存在形如 XXX 的子串。原因很简单:不妨假设 X = aX’,那么 XXX 实际上就是 aX’aX’aX’ ,其中 aX’aX’a 形成了重叠子串,又与 Thue-Morse 序列的免重叠性矛盾了。由此可以进一步推出, Thue-Morse 序列永远不会发生循环。原因很简单:如果 Thue-Morse 序列从某处开始发生循环,这就直接与 Thue-Morse 序列的免立方性矛盾了。

同时, Thue-Morse 序列是一个复现序列recurrent sequence),意即 Thue-Morse 序列中的每一个子串都会出现无穷多次。这个事实背后的原因也很简单。比方说,我们在 Thue-Morse序列当中取出 t(6)  t(10) 这么一段,它们是 0, 1, 1, 0, 0 ,表示二进制数 0110, 0111, 1000, 1001, 1010 的数字 1 的个数的奇偶性。那么, 0, 1, 1, 0, 0 今后一定会出现无数多次。在数到二进制数 110110, 110111, 111000, 111001, 111010 时,我们会再一次得到 0, 1, 1, 0, 0 ;在数到二进制数 1010110, 1010111, 1011000, 1011001, 1011010 时,我们会再一次得到 0, 1, 1, 0, 0 。这样的机会显然还有无穷多,例如,在数到二进制数 1101001000110,1101001000111, 1101001001000, 1101001001001, 1101001001010 时,我们会再一次得到 0, 1, 1, 0, 0 

构造一个复现序列很简单,任何一个循环序列即满足要求,比如 0, 1, 0, 1, 0, 1, … 。而Thue-Morse 序列则告诉了我们:存在不是循环序列的复现序列。

 

最后,我们再不加证明地给出两个与 Thue-Morse 序列有关的神奇结论。对于哪些正整数 k ≥ 2,存在两个大小相等的整数集合 A = {a1, a2, a3, …, an B = {b1, b2, b3, …, bn,使得

a1 + a2 + a3 + … + an = b1 + b2 + b3 + … + bn
a12 + a22 + a32 + … + an2 = b12 + b22 + b32 + … + bn2
……
a1k + a2k + a3k + … + ank = b1k + b2k + b3k + … + bnk

即集合 A 里的所有数与集合 B 里的所有数从 1 次方和到 k 次方和全都相等?当然,集合 A 和集合 B 必须是两个不同的集合。答案是,对于所有的正整数 k ≥ 2 ,满足要求的解都是存在的。利用 Thue-Morse 序列,我们可以得出一种 n = 2^k 的构造解,方法如下:取出 Thue-Morse序列的前 2k+1 位,即 t(0), t(1), …, t(2^(k+1) – 1),如果 t(i) = 0 ,就把 i 放进集合 A里,如果 t(i) = 1 ,就把 i 放进集合 B 里。

i

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

t(i)

0

1

1

0

1

0

0

1

1

0

0

1

0

1

1

0

 k = 3 时,如上表所示,根据规则,我们应该把 0, 3, 5, 6, 9, 10, 12, 15 分为一组,把1, 2, 4, 7, 8, 11, 13, 14 分为另一组。神奇的事情出现了:下面三个等式真的是成立的!

0 + 3 + 5 + 6 + 9 + 10 + 12 + 15 = 1 + 2 + 4 + 7 + 8 + 11 + 13 + 14
02 + 32 + 52 + 62 + 92 + 102 + 122 + 152 = 12 + 22 + 42 + 72 + 82 + 112 + 132 + 142
03 + 33 + 53 + 63 + 93 + 103 + 123 + 153 = 13 + 23 + 43 + 73 + 83 + 113 + 133 + 143

Thue-Morse 序列还能帮忙构造幻方。 1977 年, Adler Allan 和 Shuo-Yen Robert Li 给出了一种算法,可以利用 Thue-Morse 序列构造 2^n × 2^n的幻方(其中 n ≥ 2 )。首先,从左至右从上至下地把 1 到 2^2n的数填入 2^n × 2^n的方格里。然后,如果 Thue-Morse 序列中的第 i个数是 0 (即 t(i – 1) = 0 ),就把 i 从方格里拿出来。最后,把所有拿出来的数倒序放回方格,我们就得到了一个幻方。下图所示的是 n = 2 时的例子。由于 Thue-Morse 序列中的第 1, 4, 6, 7, 10, 11, 13, 16 个数是 0 ,因而我们把这些数从 4 × 4 的方阵中取出来;把它们以相反的顺序放回去后,可以验证,方阵中的每一行、每一列和两条对角线上的数字之和都是 34 。

i

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

t(i – 1)

0

1

1

0

1

0

0

1

1

0

0

1

0

1

1

0

免平方字符串

收起全文

小崔说刊

近年来最受欢迎的文学文艺学术期刊推荐: 《中国文艺家》【中州期刊联盟】

近年来最受欢迎的文学文艺学术期刊推荐: 《中国文艺家》【中州期刊联盟】

《中国文艺家》杂志创刊于1954年,为新中国著名刊物之一。 本刊高屋建瓴、全面细致地聚焦文艺界风云人物、反映文艺家的生存状态与艺术行为,追踪文艺界的热点事件,解读各种文艺现象,关注各种文艺潮流;倡导积极的价值取向,发出自己富有批判精神的声音。本刊涉及范围为所有在文学、戏剧、音乐、美术、书法、电影、电视、杂技及民间艺术各个领域有一定成就并具一定影响的华裔人物。... 阅读全文

 《中国文艺家》杂志创刊于1954年,为新中国著名刊物之一。 本刊高屋建瓴、全面细致地聚焦文艺界风云人物、反映文艺家的生存状态与艺术行为,追踪文艺界的热点事件,解读各种文艺现象,关注各种文艺潮流;倡导积极的价值取向,发出自己富有批判精神的声音。本刊涉及范围为所有在文学、戏剧、音乐、美术、书法、电影、电视、杂技及民间艺术各个领域有一定成就并具一定影响的华裔人物。我们将坚持客观、理性,对人物、对事件的反映与描述,将做到不媚俗、不炒作、不捕风捉影。我们要富有批判精神,对人物、事件的判断与批评,将做到不朋党、不怨怼、不哗众取宠。

工作QQ2853937373编辑)【推荐QQ投稿,审稿更快】

 近年来最受欢迎的文学文艺学术期刊推荐: 《中国文艺家》【中州期刊联盟】

期刊名称:中国文艺家
主管单位:文学艺术界联合会
主办单位:中国文联出版社
国际刊号:1006-3978
国内刊号:11-3887/J
邮发代号:80-142

主要栏目板块:
第一版块 特别关注
焦点 焦点人物的报道。
热点 文艺界的热门话题、重大事件追踪。
导向 对文艺界高层领导的访谈。
市场 对文化产业、艺术市场的报道、解读。
第二版块 人物 主流 对主流文艺家艺术行为、作品的描述。
孤旅 对非主流的艺术家生存状态和艺术行为、艺术作品的客观描摹。
对话 文艺界人物的访谈。
流年 文艺家的老照片老故事。
星光 介绍文艺界的新秀。
第三版块 纪录
现象 对文艺思潮、文艺流派的关注。
冲突 对文艺观念与理论的探讨。
第四版块 情趣生活
写真 名人撰写的名人逸事。
情节 名人生活化、不同寻常的情趣图片故事。
第五版块 声音
来自文艺界各方面的声音

收稿范围:
本刊涉及范围为所有在文学、戏剧、音乐、美术、书法、电影、电视、杂技及民间艺术各个领域有一定成就并具一定影响的华裔人物。

收录情况:
本刊为中国核心期刊(遴选)数据库收录期刊,中国学术期刊综合评价数据库来源期刊,中国期刊数据库全文收录期刊,“万方数据-数字化期刊群”全文上网,中国学术期刊(光盘版)收录期刊。 

读者定位:
文化艺术圈内的业内人士,全国各地的文化厅局、文联、作协、各艺术院校、艺术团体、演出团体、电台、电视台、电影制片厂、电影公司、影剧院、群艺馆、文化馆、文化站、文化宫、博物馆,以及企事业单位的专家学者,宣教工作者以及具有一定水平并爱好艺术的广大读者。

工作QQ2853937373编辑)【推荐QQ投稿,审稿更快】

投稿邮箱:shougaovip@126.com

咨询电话:0373-5864044332211

参考网站:http://www.zzqklm.com/w/wy/10931.html

收起全文

★·°遇見、堇色年華 ﹏

【十里桃花】念

【十里桃花】念

喜欢以昏黄书页的方式被记住/ 辞海里蛰伏一只过冬的蝉/ 绿灯等三秒红灯以前/ 长发和短发结为连理/ 无忧无虑的走向消亡/ 天在落下/ 我在枯井里等血液涌动的喷泉/ 额头被石头吻住/ 人影远去,不念西天不念梵/... 阅读全文

【十里桃花】念

喜欢以昏黄书页的方式被记住/

辞海里蛰伏一只过冬的蝉/

绿灯等三秒红灯以前/

长发和短发结为连理/

无忧无虑的走向消亡/

天在落下/

我在枯井里等血液涌动的喷泉/

额头被石头吻住/

人影远去,不念西天不念梵/

收起全文

辛几何&李代数

感知机(python实现)

感知机(python实现)

感知机(perceptron)是二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别(取+1和-1)。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机旨在求出该超平面,为求得超平面导入了基于误分类的损失函数,利用梯度下降法 对损失函数进行最优化(最优化)。感知机的学习算法具有简单而易于实现的优点,分为原始形式和对偶形式。感知机预测是用学习得... 阅读全文

 

 

     感知机(perceptron)是二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别(取+1和-1)。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机旨在求出该超平面,为求得超平面导入了基于误分类的损失函数,利用梯度下降法 对损失函数进行最优化(最优化)。感知机的学习算法具有简单而易于实现的优点,分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的实例进行预测的,因此属于判别模型。感知机由Rosenblatt于1957年提出的,是神经网络和支持向量机的基础。

行文脉络

  1. 感知机模型
  2. 感知机学习策略
  3. 感知机学习算法
    • 原始形式
    • 对偶形式

      4. Github地址

1. 感知机模型

定义

假设输入空间(特征向量)为X⊆Rn,输出空间为Y={-1, +1}。输入x∈X表示实例的特征向量,对应于输入空间的点;输出y∈Y表示示例的类别。由输入空间到输出空间的函数为

                                                 f(x)=sign(w·x + b)                                      (1)

称为感知机。其中,参数w叫做权值向量,b称为偏置。w·x表示w和x的内积。sign为符号函数,即

                                                感知机(python实现)                                    (2)

 

 

几何解释    

感知机模型是线性分类模型,感知机模型的假设空间是定义在特征空间中的所有线性分类模型,即函数集合{f|f(x)=w·x+b}。线性方程 w·x+b=0对应于特征空间Rn中的一个超平面S,其中w是超平面的法向量,b是超平面的截踞。这个超平面把特征空间划分为两部分。位于两侧的点分别为正负两类。超平面S称为分离超平面,如下图:

                                                感知机(python实现)

 

 

学习与预测

感知机学习即由训练数据集T={(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈X=Rn,yi∈Y={-1, +1},i=1,2...N)求得感知机模型(1),即求得参数w,b;感知机预测即根据得到的感知机模型(1),对新的输入实例给出对应的类型。

 

2. 感知机学习策略

    假设训练数据集是线性可分的,感知机学习的目标是求得一个能够将训练数据的正负实例点完全分开的分离超平面,即最终求得参数w、b。这需要一个学习策略,即定义(经验)损失函数并将损失函数最小化。

    损失函数的一个自然的选择是误分类的点的总数。但是这样得到的损失函数不是参数w、b的连续可导函数,不宜优化。损失函数的另一个选择是误分类点到分里面的距离之和。

    首先,对于任意一点xo到超平面的距离为

                                                   感知机(python实现)                                     (3)

    其次,对于误分类点(xi,yi)来说 -yi(w·xi+b)>0

    这样,假设超平面S的总的误分类点集合为M,那么所有误分类点到S的距离之和为

                                                感知机(python实现)                           (4)

不考虑1/||w||,就得到了感知机学习的损失函数。

经验风险函数

    给定数据集T={(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈X=Rn,yi∈Y={-1, +1},i=1,2...N),感知机sign(w·x+b)学习的损失函数定义为

                                            感知机(python实现)                     (5)               

其中M为误分类点的集合,这个损失函数就是感知机学习的经验风险函数。                           

    显然,损失函数L(w,b)是非负的。如果没有误分类点,那么L(w,b)为0,误分类点数越少,L(w,b)值越小。一个特定的损失函数:在误分类时是参数w,b的线性函数,在正确分类时,是0.因此,给定训练数据集T,损失函数L(w,b)是w,b的连续可导函数。

 

3. 感知机学习算法

    最优化问题:给定数据集T={(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈X=Rn,yi∈Y={-1, +1},i=1,2...N),求参数w,b,使其成为损失函数的解(M为误分类的集合):

                                     感知机(python实现)                 (6)

3.1 感知机学习的原始形式

    感知机学习是误分类驱动的,具体采用随机梯度下降法。首先,任意选定w0、b0,然后用梯度下降法不断极小化目标函数(6),极小化的过程不知一次性的把M中的所有误分类点梯度下降,而是一次随机选取一个误分类点使其梯度下降。

    假设误分类集合M是固定的,那么损失函数L(w,b)的梯度由(7)(8)给出

                                       感知机(python实现)                                  (7)

                                           感知机(python实现)                                      (8)

随机选取一个误分类点(xi,yi),对w,b进行更新:

                                                感知机(python实现)                                            (9)

                                                  感知机(python实现)                                              (10)

式中η(0≤η≤1)是步长,在统计学是中成为学习速率。步长越大,梯度下降的速度越快,更能接近极小点。如果步长过大,有可能导致跨过极小点,导致函数发散;如果步长过小,有可能会耗很长时间才能达到极小点。

 

算法(感知机学习算法的原始形式)

class="hot-view"感知机(python实现)

                输入:T={(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈X=Rn,yi∈Y={-1, +1},i=1,2...N,学习速率为η) 输出:w, b;感知机模型f(x)=sign(w·x+b) (1) 初始化w0,b0 (2) 在训练数据集中选取(xi, yi) (3) 如果yi(w xi+b)≤0 w = w + ηyixi b = b + ηyi (4) 转至(2

感知机(python实现)

直观解释:当一个实例点被误分类时,调整w,b,使分离超平面向该误分类点的一侧移动,以减少该误分类点与超平面的距离,直至超越该点被正确分类。

例1

对于训练数据集,其中正例点是x1=(3,3)T,x2=(4,3)T,负例点为x3=(1,1)T,用感知机学习算法的原始形式求感知机模型f(x)=w·x+b。这里w=(w(1),w(2))T,x=(x(1),x(2))T

:构建最优化问题:

                  感知机(python实现)

按照算法求解w, b。η=1

(1)取初值w0=0, b0=0

(2)对于(3,3):-(0+0)+0=0未被正确分类。更新w,b

               w1=w0+1*y1·x1 = (0,0)T+1(3,3)T=(3,3)T

               b1=b0+y1=1

         得到线性模型w1x+b1 = 3x(1)+3x(2)+1

(3)返回(2)继续寻找yi(w·xi+b)≤0的点,更新w,b。直到对于所有的点yi(w·xi+b)>0,没有误分类点,损失函数达到最小。

分离超平面为x(1)+x(2)-3=0

感知机模型为 f(x)=sign(x(1)+x(2)-3)

    在迭代过程中,出现w·xi+b=-2,此时,取任意一个点,都会是其小于0,不同的取值顺序会导致最终的结果不同,因此解并不是唯一的。为了得到唯一的超平面,需要对分离超平面增加约束条件,这就是支持向量机的想法。

实现代码

感知机(python实现) View Code

  

3.2 感知机学习的对偶形式

对偶形式的基本想法是,将w,b表示成为实例xi和标记yi的线性组合的形式,通过求解其系数而得到w和b。不失一般性,将初始值w0,b0设为0.对误分类点(xi,yi)通过

                                                  w = w + ηyixi                                                  b = b + ηyi

的转换逐步修该w,b,设修改了n次,则w,b关于(xi,yi)的增量分别为aiyixi和aiyi,这里ai=niη最终学习到的w,b可以表示为

                                                                   感知机(python实现)

实例点更新次数越多,意味着它距离分离超平面越近,也就越难正确分类。换句话说,这样的实例对学习结果影响很大。

算法(感知机学习算法的对偶形式)

感知机(python实现)

输入:T={(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈X=Rn,yi∈Y={-1, +1},i=1,2...N,学习速率为η)输出:a,b;感知机模型f(x)=sign(w·x+b)(1) 初始化w0,b0(2) 在训练数据集中选取(xi, yi)(3) 如果 
感知机(python实现)
                

ai = ai + η
                 b = b + ηyi (4) 转至(2)

感知机(python实现)

对偶形式中训练数据仅以内积的形式出现,为了方便可以预先把训练数据间内积计算出来并以矩阵的形式存储起来,这个矩阵就是所谓的Gram矩阵。

实现代码

感知机(python实现) View Code

 

4. GitHub地址

https://github.com/jihite/Perceptron-python-

收起全文

辛几何&李代数

Android开源项目分类汇总

Android开源项目分类汇总

目前包括: Android开源项目第一篇&&个性化控件(View)篇 包括ListView、ActionBar、Menu、ViewPager、Gallery、GridView、ImageView、ProgressBar、TextView、ScrollView、TimeView、TipView、FlipView、ColorP... 阅读全文

目前包括:

Android开源项目第一篇——个性化控件(View)篇
  包括ListViewActionBarMenuViewPagerGalleryGridViewImageViewProgressBarTextViewScrollViewTimeViewTipViewFlipViewColorPickViewGraphViewUI Style其他
Android开源项目第二篇——工具库篇
  包括依赖注入图片缓存网络相关数据库ORM工具包Android公共库高版本向低版本兼容库多媒体事件总线传感器安全插件化文件其他
Android开源项目第三篇——优秀项目篇
  比较有意思的完整的Android项目
Android开源项目第四篇——开发及测试工具篇
  包括开发效率工具开发自测相关测试工具开发及编译环境其他
Android开源项目第五篇——优秀个人和团体篇
  乐于分享并且有一些很不错的开源项目的个人组织,包括JakeWharton、Chris Banes、Koushik Dutta等大牛

第一部分 个性化控件(View)

主要介绍那些不错个性化的View,包括ListView、ActionBar、Menu、ViewPager、Gallery、GridView、ImageView、ProgressBar、TextView、ScrollView、TimeView、TipView、FlipView、ColorPickView、GraphView、UI Style等等。
、其他

一、ListView

  1. android-pulltorefresh
    一个强大的拉动刷新开源项目,支持各种控件下拉刷新,ListView、ViewPager、WevView、ExpandableListView、GridView、ScrollView、Horizontal ScrollView、Fragment上下左右拉动刷新,比下面johannilsson那个只支持ListView的强大的多。并且他实现的下拉刷新ListView在item不足一屏情况下也不会显示刷新提示,体验更好。
    项目地址:https://github.com/chrisbanes/Android-PullToRefresh
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/pull-to-refreshview-demo.apk?raw=true
    APP示例:新浪微博各个页面

  2. android-pulltorefresh-listview
    下拉刷新ListView
    项目地址:https://github.com/johannilsson/android-pulltorefresh
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/pull-to-refresh-listview-demo.apk?raw=true
    PS:这个被很多人使用的项目实际有不少bug,推荐使用上面的android-pulltorefresh

  3. DropDownListView
    下拉刷新及滑动到底部加载更多ListView
    项目地址:https://github.com/Trinea/AndroidCommon
    Demo地址:https://play.google.com/store/apps/details?id=cn.trinea.android.demo
    文档介绍:http://www.trinea.cn/android/dropdown-to-refresh-and-bottom-load-more-listview/

  4. DragSortListView
    拖动排序的ListView,同时支持ListView滑动item删除,各个Item高度不一、单选、复选、CursorAdapter做为适配器、拖动背景变化等
    项目地址:https://github.com/bauerca/drag-sort-listview
    Demo地址:https://play.google.com/store/apps/details?id=com.mobeta.android.demodslv
    APP示例:Wordpress Android

  5. SwipeListView
    支持定义ListView左右滑动事件,支持左右滑动位移,支持定义动画时间
    项目地址:https://github.com/47deg/android-swipelistview
    Demo地址:https://play.google.com/store/apps/details?id=com.fortysevendeg.android.swipelistview
    APP示例:微信

  6. Android-SwipeToDismiss
    滑动Item消失ListView
    项目地址:https://github.com/romannurik/Android-SwipeToDismiss
    支持3.0以下版本见:https://github.com/JakeWharton/SwipeToDismissNOA
    Demo地址:https://github.com/JakeWharton/SwipeToDismissNOA/SwipeToDismissNOA.apk/qr_code

  7. StickyListHeaders
    GroupName滑动到顶端时会固定不动直到另外一个GroupName到达顶端的ExpandListView,支持快速滑动,支持Android2.3及以上
    项目地址:https://github.com/emilsjolander/StickyListHeaders
    APP示例:Android 4.0联系人
    效果图:Android开源项目分类汇总

  8. pinned-section-listview
    GroupName滑动到顶端时会固定不动直到另外一个GroupName到达顶端的ExpandListView
    项目地址:https://github.com/beworker/pinned-section-listview
    效果图:Android开源项目分类汇总

  9. PinnedHeaderListView
    GroupName滑动到顶端时会固定不动直到另外一个GroupName到达顶端的ExpandListView
    项目地址:https://github.com/JimiSmith/PinnedHeaderListView

  10. QuickReturnHeader
    ListView/ScrollView的header或footer,当向下滚动时消失,向上滚动时出现
    项目地址:https://github.com/ManuelPeinado/QuickReturnHeader
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/quick-return-header-demo.apk?raw=true
    APP示例:google plus

  11. IndexableListView
    ListView右侧会显示item首字母快捷索引,点击可快速滑动到某个item
    项目地址:https://github.com/woozzu/IndexableListView
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/indexable-listview.apk?raw=true
    APP示例:微信通讯录、小米联系人

  12. CustomFastScrollView
    ListView快速滑动,同时屏幕中间PopupWindows显示滑动到的item内容或首字母
    项目地址:https://github.com/nolanlawson/CustomFastScrollViewDemo
    效果图:Android开源项目分类汇总

  13. Android-ScrollBarPanel
    ListView滑动时固定的Panel指示显示在scrollbar旁边
    项目地址:https://github.com/rno/Android-ScrollBarPanel
    效果展示:https://github.com/rno/Android-ScrollBarPanel/raw/master/demo_capture.png

  14. SlideExpandableListView
    用户点击listView item滑出固定区域,其他item的区域收缩
    项目地址:https://github.com/tjerkw/Android-SlideExpandableListView
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/slide-expandable-listView-demo.apk?raw=true

  15. JazzyListView
    ListView及GridView item以特殊动画效果进入屏幕,效果包括grow、cards、curl、wave、flip、fly等等
    项目地址:https://github.com/twotoasters/JazzyListView
    Demo地址:https://play.google.com/store/apps/details?id=com.twotoasters.jazzylistview.sample
    效果展示:http://lab.hakim.se/scroll-effects/

  16. ListViewAnimations
    带Item显示动画的ListView,动画包括底部飞入、其他方向斜飞入、下层飞入、渐变消失、滑动删除等
    项目地址:https://github.com/nhaarman/ListViewAnimations
    Demo地址:https://play.google.com/store/apps/details?id=com.haarman.listviewanimations
    APP示例:Google plus、Google Now卡片式进入、小米系统中应用商店、联系人、游戏中心、音乐、文件管理器的ListView、Ultimate、Light Flow Lite、TreinVerkeer、Running Coach、Pearl Jam Lyrics、Calorie Chart、Car Hire、Super BART、DK FlashCards、Counter Plus、Voorlees Verhaaltjes 2.0

  17. DevsmartLib-Android
    横向ListView
    项目地址:https://github.com/dinocore1/DevsmartLib-Android
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/horizontal-listview-demo.apk?raw=true

  18. HorizontalVariableListView
    支持Item宽度不一致的ListView
    项目地址:https://github.com/sephiroth74/HorizontalVariableListView

  19. LinearListView
    用LinearLayout实现的ListView,可解决多个ListView并且等问题。目前自己也有需要,等亲自尝试过后会再具体介绍
    项目地址:https://github.com/frankiesardo/LinearListView

  20. MultiChoiceAdapter
    支持多选的ListView Adapter
    项目地址:https://github.com/ManuelPeinado/MultiChoiceAdapter
    Demo地址:https://play.google.com/store/apps/details?id=com.manuelpeinado.multichoiceadapter.demo

  21. EnhancedListView
    支持横向滑动滑动删除列表项以及撤销删除的ListView,该项目的前身是SwipeToDismissUndoList
    项目地址:https://github.com/timroes/EnhancedListView
    Demo地址:https://play.google.com/store/apps/details?id=de.timroes.android.listviewdemo&rdid=de.timroes.android.listviewdemo

  22. ListBuddies
    自动滚动的双列ListView ,两个ListView滚动速度不一致,有视差效果
    项目地址:https://github.com/jpardogo/ListBuddies
    Demo地址:https://play.google.com/store/apps/details?id=com.jpardogo.android.listbuddies
    效果展示:Android开源项目分类汇总
    Android开源项目分类汇总

二、ActionBar

  1. ActionBarSherlock
    为Android所有版本提供统一的ActionBar,解决4.0以下ActionBar的适配问题
    项目地址:https://github.com/JakeWharton/ActionBarSherlock
    Demo地址:https://play.google.com/store/apps/details?id=com.actionbarsherlock.sample.demos
    APP示例:太多了。。现在连google都在用

  2. ActionBar-PullToRefresh
    下拉刷新,ActionBar出现加载中提示
    项目地址:https://github.com/chrisbanes/ActionBar-PullToRefresh
    Demo地址:https://play.google.com/store/apps/details?id=uk.co.senab.actionbarpulltorefresh.samples.stock
    APP示例:Gmail,Google plus,知乎等

  3. FadingActionBar
    ListView向下滚动逐渐显现的ActionBar
    项目地址:https://github.com/ManuelPeinado/FadingActionBar
    Demo地址:https://play.google.com/store/apps/details?id=com.manuelpeinado.fadingactionbar.demo
    APP示例:google music,知乎

  4. NotBoringActionBar
    google music下拉收缩的ActionBar
    项目地址:https://github.com/flavienlaurent/NotBoringActionBar
    Demo地址:http://flavienlaurent.com/blog/2013/11/20/making-your-action-bar-not-boring/
    APP示例:Google音乐

  5. RefreshActionItem
    带进度显示和刷新按钮的ActionBar
    项目地址:https://github.com/ManuelPeinado/RefreshActionItem
    Demo地址:https://play.google.com/store/apps/details?id=com.manuelpeinado.refreshactionitem.demo
    APP示例:The New York Times,DevAppsDirect.

  6. GlassActionBar
    类似玻璃的有一定透明度的ActionBar
    项目地址:https://github.com/ManuelPeinado/GlassActionBar
    Demo地址:https://play.google.com/store/apps/details?id=com.manuelpeinado.glassactionbardemo
    APP示例:google music
    Android开源项目分类汇总

三、Menu

  1. MenuDrawer
    滑出式菜单,通过拖动屏幕边缘滑出菜单,支持屏幕上下左右划出,支持当前View处于上下层,支持Windows边缘、ListView边缘、ViewPager变化划出菜单等。
    项目地址:https://github.com/SimonVT/android-menudrawer
    Demo地址:http://simonvt.github.io/android-menudrawer/
    APP示例:Gmail、Google Music等大部分google app

  2. SlidingMenu
    滑出式菜单,通过拖动屏幕边缘滑出菜单,支持屏幕左右划出,支持菜单zoom、scale、slide up三种动画样式出现。
    项目地址:https://github.com/jfeinstein10/SlidingMenu
    Demo地址:https://play.google.com/store/apps/details?id=com.slidingmenu.example
    APP示例:Foursquare, LinkedIn, Zappos, Rdio, Evernote Food, Plume, VLC for Android, ESPN ScoreCenter, MLS MatchDay, 9GAG, Wunderlist 2, The Verge, MTG Familiar, Mantano Reader, Falcon Pro (BETA), MW3 Barracks
    MenuDrawer和SlidingMenu比较:SlidingMenu支持菜单动画样式出现,MenuDrawer支持菜单view处于内容的上下层

  3. ArcMenu
    支持类似Path的左下角动画旋转菜单及横向划出菜单、圆心弹出菜单
    项目地址:https://github.com/daCapricorn/ArcMenu
    APP示例:Path
    效果图:Android开源项目分类汇总
    https://dl.dropboxusercontent.com/u/11369687/preview1.png
    https://dl.dropboxusercontent.com/u/11369687/raymenu.png

  4. android-satellite-menu
    类似Path的左下角动画旋转菜单
    项目地址:https://github.com/siyamed/android-satellite-menu
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/satellite-menu-demo.apk?raw=true
    APP示例:Path

  5. radial-menu-widget
    圆形菜单,支持二级菜单
    项目地址:https://code.google.com/p/radial-menu-widget/
    效果图:http://farm8.staticflickr.com/7377/11621125154_d1773c2dcc_o.jpg

  6. Android Wheel Menu
    圆形旋转选取菜单
    项目地址:https://github.com/anupcowkur/Android-Wheel-Menu
    效果图:Android开源项目分类汇总

  7. FoldingNavigationDrawer
    滑动并以折叠方式打开菜单
    项目地址:https://github.com/tibi1712/FoldingNavigationDrawer-Android
    Demo地址:https://play.google.com/store/apps/details?id=com.ptr.folding.sample
    效果图:Android开源项目分类汇总

  8. AndroidResideMenu
    仿 Dribbble 的边栏菜单
    项目地址:https://github.com/SpecialCyCi/AndroidResideMenu
    效果图:Android开源项目分类汇总
    Android开源项目分类汇总

四、ViewPager 、Gallery

  1. Android-ViewPagerIndicator
    配合ViewPager使用的Indicator,支持各种位置和样式
    项目地址:https://github.com/JakeWharton/Android-ViewPagerIndicator
    Demo地址:https://play.google.com/store/apps/details?id=com.viewpagerindicator.sample
    APP示例:太多了。。

  2. JazzyViewPager
    支持Fragment切换动画的ViewPager,动画包括转盘、淡入淡出、翻页、层叠、旋转、方块、翻转、放大缩小等
    项目地址:https://github.com/jfeinstein10/JazzyViewPager
    Demo地址:https://github.com/jfeinstein10/JazzyViewPager/blob/master/JazzyViewPager.apk?raw=true
    效果类似桌面左右切换的各种效果,不过桌面并非用ViewPager实现而已

  3. Android-DirectionalViewPager
    支持横向和纵向(垂直)的ViewPager
    项目地址:https://github.com/JakeWharton/Android-DirectionalViewPager
    Demo地址:https://market.android.com/details?id=com.directionalviewpager.sample

  4. android-pulltorefresh
    支持下拉刷新的ViewPager
    项目地址:https://github.com/chrisbanes/Android-PullToRefresh
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/pull-to-refreshview-demo.apk?raw=true
    APP示例:新浪微博各个页面

  5. FancyCoverFlow
    支持Item切换动画效果的类似Gallery View
    项目地址:https://github.com/davidschreiber/FancyCoverFlow
    Demo地址:https://play.google.com/store/apps/details?id=at.technikum.mti.fancycoverflow.samples
    效果图:Android开源项目分类汇总

  6. AndroidTouchGallery
    支持双击或双指缩放的Gallery(用ViewPager实现),相比下面的PhotoView,在被放大后依然能滑到下一个item,并且支持直接从url和文件中获取图片,
    项目地址:https://github.com/Dreddik/AndroidTouchGallery
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/touch-gallery-demo.apk?raw=true
    APP示例:类似微信中查看聊天记录图片时可双击放大,并且放大情况下能正常左右滑动到前后图片

  7. Android Auto Scroll ViewPager
    Android自动滚动 轮播循环的ViewPager
    项目地址:https://github.com/Trinea/android-auto-scroll-view-pager
    Demo地址:https://play.google.com/store/apps/details?id=cn.trinea.android.demo
    文档介绍:http://www.trinea.cn/android/auto-scroll-view-pager/

  8. Salvage view
    带View缓存的Viewpager PagerAdapter,很方便使用
    项目地址:https://github.com/JakeWharton/salvage

  9. Android PagerSlidingTabStrip
    配合ViewPager使用的Indicator,支持ViewPager Scroll时Indicator联动
    项目地址:https://github.com/astuetz/PagerSlidingTabStrip
    Demo地址:https://play.google.com/store/apps/details?id=com.astuetz.viewpager.extensions.sample

  10. ViewPager3D
    ViewPager3D效果
    项目地址:https://github.com/inovex/ViewPager3D
    Android开源项目分类汇总

  11. AnimaTabsview
    仿网易云音乐标签切换的动画,带透明小三角
    项目地址: https://github.com/wuyexiong/transparent-over-animtabsview
    在线演示:http://v.youku.com/v_show/id_XNzA4MjY5NjA0.html

五、GridView

  1. StaggeredGridView
    允许非对齐行的GridView,类似Pinterest的瀑布流,并且跟ListView一样自带View缓存,继承自ViewGroup
    项目地址:https://github.com/maurycyw/StaggeredGridView
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/staggered-gridview-demo.apk?raw=true
    APP示例:Pinterest等

  2. AndroidStaggeredGrid
    允许非对齐行的GridView,类似Pinterest的瀑布流,继承自AbsListView
    项目地址:https://github.com/etsy/AndroidStaggeredGrid
    APP示例:Pinterest等

  3. PinterestLikeAdapterView
    允许非对齐行的GridView,类似Pinterest的瀑布流,允许下拉刷新
    项目地址:https://github.com/GDG-Korea/PinterestLikeAdapterView
    APP示例:Pinterest等

  4. DraggableGridView
    Item可拖动交换位置的GridView,实际是自己继承ViewGroup实现,类似桌面的单屏效果,可屏幕自动上下滚动进行Item移动交换,多屏效果见下面PagedDragDropGrid
    项目地址:https://github.com/thquinn/DraggableGridView
    Demo地址:https://github.com/thquinn/DraggableGridView/blob/master/bin/DraggableGridViewSample.apk?raw=true

  5. StickyGridHeaders
    GroupName滑动到顶端时会固定不动直到另外一个GroupName到达顶端的GridView
    项目地址:https://github.com/TonicArtos/StickyGridHeaders
    效果图:Android开源项目分类汇总

  6. PagedDragDropGrid
    Item可拖动交换位置、拖动删除的自定义控件,实际是自己继承ViewGroup实现,类似桌面的多屏效果,可拖动到屏幕边缘,屏幕自动左右滚动进行Item移动交换,可拖动进行删除,单屏效果见上面DraggableGridView
    项目地址:https://github.com/mrKlar/PagedDragDropGrid
    在线演示:http://youtu.be/FYTSRfthSuQ

  7. Android-DraggableGridViewPager
    Item可拖动交换位置的GridView,实际是自己继承ViewGroup实现,类似桌面的多屏效果,可屏幕自动左右滚动进行Item移动交换,单屏效果见上面DraggableGridView
    项目地址:https://github.com/zzhouj/Android-DraggableGridViewPager
    Demo地址:https://github.com/Trinea/trinea-download/blob/master/draggable-grid-viewpager-demo.apk?raw=true
    Android开源项目分类汇总

六、ImageView

  1. PhotoView
    支持双击或双指缩放的ImageView,在ViewPager等Scrolling view中正常使用,相比上面的AndroidTouchGallery,不仅支持ViewPager,同时支持单个ImageView
    项目地址:https://github.com/chrisbanes/PhotoView
    Demo地址:https://play.google.com/store/apps/details?id=uk.co.senab.photoview.sample
    APP示例:photup

  2. android-gif-drawable
    支持gif显示的view,用jni实现的,编译生成so库后直接xml定义view即可,而且本身不依赖于其他开源项目所以相对下面的ImageViewEx简单的多
    项目地址:https://github.com/koral--/android-gif-drawable

  3. ImageViewEx
    支持Gif显示的ImageView
    项目地址:https://github.com/frapontillo/ImageViewEx
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/imageviewex-demo.apk?raw=true
    依赖很多,编译过程很繁琐!|_|!

  4. RoundedImageView
    带圆角的ImageView
    项目地址:https://github.com/vinc3m1/RoundedImageView
    效果图:Android开源项目分类汇总

  5. ColorArt
    根据图片的均色设置背景色显示文字和图片,类似itune11中效果
    项目地址:https://github.com/MichaelEvans/ColorArt
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/color-art-demo.apk?raw=true

  6. CircleImageView
    圆形的ImageView
    项目地址:https://github.com/hdodenhof/CircleImageView
    效果图:Android开源项目分类汇总

  7. ImageViewZoom
    支持放大和平移的ImageView
    项目地址:https://github.com/sephiroth74/ImageViewZoom
    APP示例:https://play.google.com/store/apps/details?id=com.aviary.android.feather

  8. KenBurnsView
    实现Ken Burns effect效果,达到身临其境效果的ImageView
    项目地址:https://github.com/flavioarfaria/KenBurnsView

  9. CustomShapeImageView
    各种形状的ImageView, 相比上面的圆形ImageView,多了更多形状
    项目地址:https://github.com/MostafaGazar/CustomShapeImageView
    效果图:Android开源项目分类汇总
    Android开源项目分类汇总

七、ProgressBar

  1. SmoothProgressBar
    水平进度条
    项目地址:https://github.com/castorflex/SmoothProgressBar
    Demo地址:https://play.google.com/store/apps/details?id=fr.castorflex.android.smoothprogressbar.sample

  2. ProgressWheel
    支持进度显示的圆形ProgressBar
    项目地址:https://github.com/Todd-Davies/ProgressWheel
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/progress-wheel-demo.apk?raw=true

  3. android-square-progressbar
    在图片周围显示进度
    项目地址:https://github.com/mrwonderman/android-square-progressbar
    Demo地址:https://play.google.com/store/apps/details?id=net.yscs.android.square_progressbar_example
    APP示例:square
    效果图:Android开源项目分类汇总

  4. HoloCircularProgressBar
    Android4.1 时钟App样式
    项目地址:https://github.com/passsy/android-HoloCircularProgressBar
    APP示例:Android4.1时钟App
    效果图:Android开源项目分类汇总

  5. ProgressButton
    通过图钉的不同状态显示进度
    项目地址:https://github.com/f2prateek/progressbutton
    文档介绍:http://f2prateek.com/progressbutton/
    效果图:Android开源项目分类汇总

  6. GoogleProgressBar
    类似google 多个圆形卡片翻转的progressBar
    项目地址:https://github.com/jpardogo/GoogleProgressBar
    效果图:Android开源项目分类汇总

  7. TH-ProgressButton
    带圆形进度显示的按钮
    项目地址;https://github.com/torryharris/TH-ProgressButton
    效果图:Android开源项目分类汇总Android开源项目分类汇总Android开源项目分类汇总Android开源项目分类汇总

  8. NumberProgressBar
    带数字进度的进度条
    项目地址:https://github.com/daimajia/NumberProgressBar
    效果图:Android开源项目分类汇总
    Android开源项目分类汇总

八、TextView

包括TextView及所有继承自TextView控件,如EditText、Button、RadioButton

  1. android-flowtextview
    文字自动环绕其他View的Layout
    项目地址:https://code.google.com/p/android-flowtextview/
    效果图:http://i949.photobucket.com/albums/ad332/vostroman1500/1.png

  2. Android Form EditText
    验证输入合法性的编辑框,支持输入、英文、ip、url等多种正则验证
    项目地址:https://github.com/vekexasia/android-edittext-validator
    Demo地址:https://play.google.com/store/apps/details?id=com.andreabaccega.edittextformexample

  3. Emojicon
    支持emojis的TextView和EditText
    项目地址:https://github.com/rockerhieu/emojicon
    文档地址:http://rockerhieu.com/emojicon/

  4. android-circlebutton
    Android圆形按钮,实际实现是继承自ImageView
    项目地址:https://github.com/markushi/android-circlebutton
    Demo地址:https://github.com/markushi/android-circlebutton/blob/master/example/example.apk

  5. Segmented Radio Buttons for Android
    iOS’s segmented controls的实现
    项目地址:https://github.com/vinc3m1/android-segmentedradiobutton
    Demo地址:https://github.com/thquinn/DraggableGridView/blob/master/bin/DraggableGridViewSample.apk?raw=true
    效果图:Android开源项目分类汇总

  6. Chips EditText Library
    支持国家名字联想从而选择显示该国国旗的EditText,实际就是通过SpannableStringBuilder实现
    项目地址:https://github.com/kpbird/chips-edittext-library
    Demo地址:https://github.com/kpbird/chips-edittext-library/tree/master/ChipsEditTextDemo/bin

  7. AutoFitTextView
    可固定边界内容字体大小自适应的TextView
    项目地址:https://github.com/grantland/android-autofittextview

  8. Shimmer for Android
    文字发淡光的TextView
    项目地址:https://github.com/RomainPiel/Shimmer-android

  9. Titanic
    可以显示水位上升下降(不知道该怎么描述 囧)的TextView
    项目地址:https://github.com/RomainPiel/Titanic
    效果图:Android开源项目分类汇总

  10. android-iconify
    提供带Icon的TextView,Menu,Button等
    项目地址:https://github.com/JoanZapata/android-iconify

  11. Calligraphy
    让我们在android开发中使用自定义字体变得更加简单
    项目地址 :https://github.com/chrisjenx/Calligraphy
    效果图:Android开源项目分类汇总

  12. CreditsRoll
    类似星球大战字幕效果的TextView
    项目地址:https://github.com/frakbot/CreditsRoll

  13. android-process-buton
    带加载或提交进度的Button
    项目地址:https://github.com/dmytrodanylyk/android-process-buton

  14. FButton
    扁平化的Button
    项目地址:https://github.com/hoang8f/android-flat-button
    Demo地址:https://play.google.com/store/apps/details?id=info.hoang8f.fbutton.demo
    Android开源项目分类汇总

九、ScrollView

  1. Discrollview
    支持滚动时Item淡入淡出,平移,缩放效果的ScrollView
    项目地址:https://github.com/flavienlaurent/discrollview
    Demo地址:https://github.com/flavienlaurent/discrollview/raw/master/sample.apk

  2. PullScrollView
    仿照新浪微博Android客户端个人中心的ScrollView,下拉背景伸缩回弹效果。
    项目地址:https://github.com/MarkMjw/PullScrollView
    效果图:Android开源项目分类汇总

  3. ParallaxScrollView
    支持视差滚动的ScrollView ,背景图片的滚动速度小于ScrollView中子控件的滚动速度
    项目地址:https://github.com/chrisjenx/ParallaxScrollView
    Demo地址:http://cloud.github.com/downloads/chrisjenx/ParallaxScrollView/ParallaxScrollViewDemo-v1.0.5.apk
    Android开源项目分类汇总

十、TimeView

包括TimePicker、DatePicker、CalendarView、Clock等时间相关控件

  1. android-times-square
    Android日历时间部件,支持选取单个日期,多个日期,及日期区间段和对话框形式显示
    项目地址:https://github.com/square/android-times-square
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/times-square-demo.apk?raw=true

  2. android-calendar-card
    日历
    项目地址:https://github.com/kenumir/android-calendar-card
    Demo地址:https://play.google.com/store/apps/details?id=com.wt.calendarcardsample
    效果图:Android开源项目分类汇总

  3. AndroidWheel
    Android Wheel支持城市、多种日期时间、密码、图片
    项目地址:https://code.google.com/p/android-wheel/
    效果图:Android开源项目分类汇总

  4. GoogleDateTimePickers
    时间选择部件
    项目地址:https://github.com/Mirkoddd/GoogleDateTimePickers
    文档地址:https://play.google.com/store/apps/details?id=com.mirko.sample&hl=it
    Android开源项目分类汇总

十一、TipView

包括Toast、角标、UndoBar等提示性控件

  1. Crouton
    丰富样式的Toast,允许alert、comfirm、info样式及点击消失样式,允许设置Toast显示时间,允许自定义View。 本文32. SuperToasts为其扩展版
    项目地址:https://github.com/keyboardsurfer/Crouton
    Demo地址:http://play.google.com/store/apps/details?id=de.keyboardsurfer.app.demo.crouton

  2. supertooltips
    带动画效果的Tips显示
    项目地址:https://github.com/nhaarman/supertooltips
    Demo地址:https://play.google.com/store/apps/details?id=com.haarman.supertooltips

  3. Android ViewBadger
    为其他View添加角标等
    项目地址:https://github.com/jgilfelt/android-viewbadger
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/android-viewbadger.apk?raw=true
    效果图:Android开源项目分类汇总

  4. SuperToasts
    更丰富样式的toast,支持Button、Progress、Horizontal Progress样式、支持进入动画、支持撤销及其动画设置
    项目地址:https://github.com/JohnPersano/SuperToasts
    Demo地址:https://play.google.com/store/apps/details?id=com.supertoastsdemo
    效果图:Android开源项目分类汇总

  5. UndoBar
    屏幕底部显示取消或是确认的PopupWindows
    项目地址:https://github.com/soarcn/UndoBar
    效果图:Android开源项目分类汇总

  6. UndoBar
    屏幕底部显示取消或是确认某操作
    项目地址:https://github.com/jenzz/Android-UndoBar
    效果图:Android开源项目分类汇总
    Android开源项目分类汇总

十二、FlipView

  1. android-flip
    类似Flipboard翻转动画的实现
    项目地址:https://github.com/openaphid/android-flip
    Demo地址:https://github.com/openaphid/android-flip/blob/master/FlipView/Demo/APK/Aphid-FlipView-Demo.apk?raw=true
    APP示例:flipboard

  2. FlipImageView
    支持x、y、z及动画选择的翻转动画的实现
    项目地址:https://github.com/castorflex/FlipImageView
    Demo地址:https://play.google.com/store/apps/details?id=fr.castorflex.android.flipimageview

  3. FoldableLayout
    Flip翻转效果的ListView,目前还不支持ListView缓存
    项目地址:https://github.com/alexvasilkov/FoldableLayout
    Demo地址:http://play.google.com/store/apps/details?id=com.alexvasilkov.foldablelayout.sample
    Android开源项目分类汇总

十三、ColorPickView

  1. ColorPickerView
    颜色选择器,支持PopupWindows或新的Activity中打开
    项目地址:https://code.google.com/p/color-picker-view/
    效果图:Android开源项目分类汇总

  2. HoloColorPicker
    颜色选择器
    项目地址:https://github.com/LarsWerkman/HoloColorPicker
    Demo地址:https://docs.google.com/file/d/0BwclyDTlLrdXRzVnTGJvTlRfU2s/edit

  3. ColorPickerPreference
    颜色选择器
    项目地址:https://github.com/attenzione/android-ColorPickerPreference
    效果图:Android开源项目分类汇总
    Android开源项目分类汇总

十四、GraphView

  1. achartengine
    强大的图表绘制工具,支持折线图、面积图、散点图、时间图、柱状图、条图、饼图、气泡图、圆环图、范围(高至低)条形图、拨号图/表、立方线图及各种图的结合
    项目地址:https://code.google.com/p/achartengine/
    官方网站:http://www.achartengine.org/
    效果图:Android开源项目分类汇总
    http://www.achartengine.org/dimages/sales_line_and_area_chart.png
    http://www.achartengine.org/dimages/temperature_range_chart.png
    http://www.achartengine.org/dimages/combined_chart.png
    http://www.achartengine.org/dimages/budget_chart.png
    APP示例:Wordpress Android,Google Analytics

  2. GraphView
    绘制图表和曲线图的View,可用于Android上的曲形图、柱状图、波浪图展示
    项目地址:https://github.com/jjoe64/GraphView
    Demo地址:https://play.google.com/store/apps/details?id=com.sothree.umano
    Demo项目:https://github.com/jjoe64/GraphView-Demos
    APP示例:Wordpress Android,Google Analytics

  3. HoloGraphLibrary
    绘制现状图、柱状图、饼状图
    项目地址:https://bitbucket.org/danielnadeau/holographlibrary/src
    文档介绍:https://bitbucket.org/danielnadeau/holographlibrary/wiki/Home
    Android开源项目分类汇总

十五、UI Style

不同样式的系统UI风格,如IOS、Bootstrap风格

  1. UITableView
    ios风格控件,包括Button、ListView、TableView
    项目地址:https://github.com/thiagolocatelli/android-uitableview
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/ui-tableview-demo.apk?raw=true

  2. ATableView
    ios风格控件
    项目地址:https://github.com/dmacosta/ATableView
    Demo地址:https://play.google.com/store/apps/details?id=com.nakardo.atableview.demo

  3. Cards-UI
    卡片式View,支持单个卡片,item为卡片的ListView
    项目地址:https://github.com/afollestad/Cards-UI
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/cards-ui-demo.apk?raw=true

  4. cardslib
    卡片式View,支持单个卡片,item为卡片的ListView和GridView
    项目地址:https://github.com/gabrielemariotti/cardslib
    Demo地址:https://play.google.com/store/apps/details?id=it.gmariotti.cardslib.demo

  5. Android-Bootstrap
    Bootstrap 风格的按钮
    项目地址: https://github.com/Bearded-Hen/Android-Bootstrap
    效果图:Android开源项目分类汇总
    Android开源项目分类汇总

十六、其他

  1. SwipeBackLayout
    左右或向上滑动返回的Activity
    项目地址:https://github.com/Issacw0ng/SwipeBackLayout
    Demo地址:https://play.google.com/store/apps/details?id=me.imid.swipebacklayout.demo
    APP示例:知乎

  2. android-styled-dialogs
    可自定义样式的dialog,默认与Holo主题样式一致,在Android2.2以上同一样式
    项目地址:https://github.com/inmite/android-styled-dialogs
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/styled-dialogs-demo.apk?raw=true

  3. Android Sliding Up Panel
    可拖动的View,能在当前Activity上扶起一个可拖动的Panel
    项目地址:https://github.com/umano/AndroidSlidingUpPanel
    Demo地址:https://play.google.com/store/apps/details?id=com.sothree.umano
    APP示例:Google Music精简播放栏

  4. AndroidWheel
    Android Wheel支持城市、多种日期时间、密码、图片
    项目地址:https://code.google.com/p/android-wheel/
    效果图:Android开源项目分类汇总

  5. TableFixHeaders
    第一列固定的Table
    项目地址:https://github.com/InQBarna/TableFixHeaders
    Demo地址:http://bit.ly/13buAIq

  6. Inscription
    可用于展示应用change和new feature信息
    项目地址:https://github.com/MartinvanZ/Inscription

  7. ActivityTransition
    Activity切换动画,包括渐变、flip、某个位置进入等等
    项目地址:https://github.com/ophilbert/ActivityTransition
    使用介绍:https://github.com/jfeinstein10/JazzyViewPager/blob/master/JazzyViewPager.apk?raw=true
    效果图:类似桌面左右切换的各种效果,不过桌面并非用ViewPager实现而已

  8. GlowPadBackport
    将Android4.2的锁屏界面解锁扩展到Android1.6及1.6+
    项目地址:https://github.com/rock3r/GlowPadBackport
    Demo地址:https://play.google.com/store/apps/details?id=net.sebastianopoggi.samples.ui.GlowPadSample
    效果图:Android开源项目分类汇总

  9. GlowPadView
    Android4锁屏界面解锁
    项目地址:https://github.com/nadavfima/GlowPadView
    效果图:https://raw.github.com/nadavfima/GlowPadView/master/example.png

  10. android-lockpattern
    Android的图案密码解锁
    项目地址:https://code.google.com/p/android-lockpattern/
    Demo地址:https://play.google.com/store/apps/details?id=group.pals.android.lib.ui.lockpattern.demo
    使用介绍:https://code.google.com/p/android-lockpattern/wiki/QuickUse
    APP示例:Android开机的图案密码解锁,支付宝的密码解锁

  11. RangeBar
    类似于SeekBar,不同的是可以选择一个范围内的值而不是单个值
    项目地址:https://github.com/edmodo/range-bar
    Demo地址:https://github.com/Trinea/TrineaDownload/blob/master/range-bar-demo.apk?raw=true
    效果图: Android开源项目分类汇总

  12. ChromeView
    利用Chromium实现的WebView,解决各个Android版本WebView不同的问题,同时利用最新Chrome代码
    项目地址:https://github.com/pwnall/chromeview

  13. Android Slider Preference Library
    可添加到设置中的基于对话框的RankBar小部件
    项目地址:https://github.com/jayschwa/AndroidSliderPreference

  14. ShowcaseView library
    用于高亮显示应用程序的特定部分,从而突出突出重点
    项目地址:https://github.com/amlcurran/ShowcaseView

  15. android-segmented-control
    Android上的Segmented Controls,相当于RadioButton组
    项目地址:https://github.com/hoang8f/android-segmented-control

  16. Swipeable Cards
    类似Tinder的卡片效果,可以加载图片并动画效果展示,向左滑动表示喜欢,向右表示不喜欢
    项目地址:https://github.com/kikoso/Swipeable-Cards
    Demo地址:https://play.google.com/store/apps/details?id=info.hoang8f.fbutton.demo

  17. EdgeEffectOverride
    改变ScrollView, ListView, ExpandableListView, GridView, ViewPager等滚动控件滚动到边缘的颜色效果
    项目地址:https://github.com/AndroidAlliance/EdgeEffectOverride
    Android开源项目分类汇总

收起全文

辛几何&李代数

康威常数2

康威常数2

六、具体的应用:&1&,&2&和&3&的比例先解释一下这里&应用&的意思。许多读者看到这个理论的第一个(或第二个第三个……)反应也许会是&那这个理论在实际中有什么用途呢&?边说边看理论中的&说&&看&过程其实是一种被称为&游程编码&的编码方式。这种编码方式有时被用作数据压缩的方式,如在一些图像格式中。也许因为是这个原因,康威的论文在第二次发表时,刊登在一本和... 阅读全文

六、具体的应用:“1”,“2”和“3”的比例

先解释一下这里“应用”的意思。许多读者看到这个理论的第一个(或第二个第三个……)反应也许会是“那这个理论在实际中有什么用途呢“?

边说边看理论中的“说”“看”过程其实是一种被称为“游程编码”的编码方式。这种编码方式有时被用作数据压缩的方式,如在一些图像格式中。也许因为是这个原因,康威的论文在第二次发表时,刊登在一本和通信有关的学术论文集上。(第一次发表在剑桥大学数学学会的会刊Eureka上。)如果要强调边看边说理论有什么实际应用,也许这是个好的切入点。

不过我觉得这理论其实并没有什么实际用途,至少到目前为止没看见它有。它的价值在于它的美,而它的美源于它起源的质朴和内容的(相对)深刻以及形式的奇诡之间的强烈对比。一个数学理论,它是美的,这就是很好的价值了。

本节和后面所说的“应用”,是用康威的理论去回答一些问题。这些问题并不依赖于理论而存在;从原则上说,以直接产生边看边说序列再作观察的方式也能回答这些问题;但从现实上这样做非常困难,或根本不可能。本节想问的问题就是,从1开始的边看边说序列,它的第100,或是第1000000项有多少个数字,其中分别有多少“1”,“2”和“3”?

用直接写出每一项的方法,我们很容易计算出这个序列的前面几项的长度:

 

1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, ……

 

但是这个直接生成数字串并作统计的方法会变得越来越困难,所需要的计算量和储存空间越来越大。根据算术定理,序列长度以指数增长。取康威常数为1.3,以非常粗略的方式估计,它的第100项的长度大约会是1.3100≈2×1011,也就是千亿这个数量级,生成新数字串的计算量变得非常大。而它的第1000项的长度则要超过10100,此时光是储存数字串也变得不可能,因为可观测宇宙内的原子总量据估计也仅有1080个。如果我们想知道第1000000项数字串有多长,其中分别有多少“1”,“2”和“3”,靠直接生成数字串的方法是完全不可行的。

但通过康威理论,这个问题就容易解决了。

我们知道,从数字串1开始的边看边说序列在第8项演化成由一个72铪元素和一个50锡元素组成的化合物。从这一天起,通过查询元素列表中的“一天后衰变物”一栏,每天演化出来的化合物中的各元素数量都可以通过前一天化合物中各元素的数量来计算:比如说,如果前一天的化合物中有100个31镓元素,那么次日的化合物中就会因此产生100个1氢元素,200个20钙元素,100个30锌元素,100个63铕元素和100个89锕元素。由分割的原理,化合物中的每一个元素都可以看作是在独立演化而不和化合物中其他(同种或不同种的)元素的演化过程相互干扰。92种元素中的每一种都可如此算出次日产生的元素数量,求和后就可得出次日产生的化合物中每种元素的含量。下面给出了第8项到第20项以及第99和第100项的结果:

康威常数2

接下来当然就很简单了,统计一下每种元素里“1”,“2”和“3”的数量,乘以化合物中此种元素的数量,再分别相加,就得到了化合物中“1”,“2”和“3”的数量。计算的结果是,第100项有511247092564个数字,其中有253103530928个"1",63796211233个"2"和94347350403个"3"。“1”,“2”和“3”在此项中的比例大约分别是49.507084658%,32.038560926%和18.454354416%。(上面这三个百分比相加不严格等于100%,因为分别有尾数的四舍五入。下同。) 注意到这个结果和我们上面粗略的估计千亿这个数量级是相符的。

对第100项可以这样算,对第1000000项也同样可以这样算,没有什么原则上的不同。只是对第1000000项来说,其中所含的元素数量实在太多,如果在编程时使用普通的32位或64位甚至128位的整数类形来表示是远远不够的,必须使用支持任意长度整数的数据类型,比如Java语言中的BigInteger。不过在此无法将这些数字具体写出来:第1000000项的长度以十进制数表示出来的话会有115137位,写出来将是一本中篇小说的篇幅。“1”,“2”和“3”的数量也一样无法具体写出,它们在此项中的比例分别约为49.507077868%,32.038585700%和18.454336321%。

看来当项数比较大时,“1”,“2”和“3”在数字串中的比例会趋向定值。这其实是算术引理的推论。因为随着项数趋于无穷,各元素在数字串中的比例趋近于它的丰度。以每种元素中“1”,“2”和“3”的数目乘以它的丰度,再分别相加能得到三个数字a,b和c,将它们归一化操作(即分别除以a+b+c)后就得到了当项数趋于无穷时“1”,“2”和“3”的比例的理论值,结果是约49.507077857%,32.038585734%和18.454336411%,和上面的结果相符。

我们可以问,为什么上面使用的计算长度的方法要比直接产生此项数字串再统计其长度的暴力法的计算速度快得多。因为在这种方法中,元素之间的顺序这个信息被省略而不参与计算。在前面的表中,我们只知道每一项化合物中每种元素有多少,但不知道它们分别处于化合物的什么位置。依照化学中表示物质组成的化学式来作比方的话,直接产生某项数字串类似于要知道物质的结构式,而上面的计算则只是得到了物质的实验式。而我们要知道数字串的长度或是其中“1”,“2”和“3”的数量,却恰恰并不需要知道元素之间的顺序。

 

七、具体的应用:第1000000项的某位数字

前面一节中的计算因省略计算元素之间的信息而变得迅速,但康威的理论也同样能帮助我们快速地知道,以1开始的边说边看序列的某项数字串的某个具体位置的数字是什么。

比如我们可以计算出,序列的第1000000项是以“132113213221133112”开始的。这我们甚至可以用手算:它的第8项以72铪开头,于是第9项以71镥开头,然后依次以70镱,69铥,68铒,67钬,66镝,65铽开头,第16项又以67钬开头,我们发现了67钬→66镝→65铽→67钬……这个循环,所以此后所有3n的项都以65铽开头,3n+1的项都以67钬开头,3n+2的项都以66镝开头,于是第999999项以65铽开头,而第1000000项以65铽一天后的衰变物,也就是6764钆开头。要计算第1000000项是以什么结尾的可用类似办法。这其实是起首引理和结尾引理的推论。

任意给定自然数n,要计算第1000000项数字串的第n位是什么数字则比较麻烦一点,但原则上来说也不难,当然一般不能用手算。序列在第8项演化成7250锡。而按照前面的方法,我们可以精确计算72铪演化1000000-8=999992天后产生的化合物的长度d;如果d大于等于n,那么原问题就转化为72铪演化999992天后数字串第n位是什么数字,反之则转化为50锡演化999992天后数字串第n-d位数字是什么。这种方法可以一直继续下去直到求出结果:当化合物中有超过一个元素时,我们求出第一个元素最终产物的长度,以便知道我们感兴趣的那一位数字是否由它产生,如果不是,则可以抛弃这个元素(并修正所求数字所在的位数);当化合物中只有一个元素,则将其代换为它一天后的衰变物,再重复这个步骤。

上面的算法的具体实现则需要一点技巧,因为单独一次计算某元素在若干天后产物的长度虽然并不耗时,但如果每次使用都需要重新计算的话,所用的总时间也是惊人的。所以可以预先计算,要用时再查表。可是如果所有计算结果都储存的话,需要的空间相当大(大概超过2To)。笔者采用折衷的方式,储存每隔1000天的结果,将所需空间削减为原需的千分之一,中间结果则在需要时再当场计算填充。具体的程序实现属于编程和算法问题,在此就不详细介绍了。在一台并不很新的个人电脑上,笔者的程序用大约20分钟生成上面所说的元素产物长度表格,每回答一个“第1000000项数字串中间第n位是什么”的问题则需要大约10分钟。计算结果:序列从第1040000位开始的几个数字是3222112,它其实是一个3锂元素的结尾部分;第1090000位开始的几个数字是312,它其实是一个23钒元素的结尾部分。

八、线性代数的语言

现在我们来讨论本文最有意思的部分,关于算术定理的证明。这部分证明必须用到线性代数的知识,所以从现在起我假设读者了解线性代数的一般知识。

根据元素列表中的“一天后衰变物”一栏,我们定义一个92×92的矩阵M,它在第i行第j列处的值为第j号普通元素一天后衰变物中的第i号普通元素的数量。比如说1氢的一天后衰变物仍是1氢,于是矩阵的第1列只有在第1行处的值为0,其余均为0;而31镓的一天后衰变物是63208912030锌,于是M的第31列在第1、30、63和89行处的值为1,在第20行处的值为2,在其余行处的值为0。我们把这个矩阵称为边看边说矩阵

矩阵M的规模比较大,在网页上不容易完整地表示出来。好在它的元素很简单,大多数是0,其余的基本都是1,只有一个值是2,所以我们可以用下图中点阵的方式来表示这个矩阵,其中每个白点表示此处值为0,黑点表示1,红点表示2。

康威常数2

M的点阵表示

矩阵M包含了普通化合物演化的几乎所有信息。说“几乎”是因为它和第六节中的计算一样,忽略了演化过程中各元素间顺序的信息。对任意一个普通化合物C,我们都可以写出一个有92个分量的列向量u来,它的第i个分量是C中第i号普通元素的数量,我们称它为普通化合物C对应的向量

任何一个普通化合物C,如果它在次日演化成C',那么容易看出,C'对应的向量u'=Mu,也就是说“左乘M”代表了“演化1天”的操作(但是忽略了元素次序)。想知道C'再过一天的演化结果所对应的向量,只要在u'左边再乘以一个M,所以是M2u,这是C演化2天后所得化合物对应的向量。如此下去,C在第n天的演化结果所对应的向量就是Mnu这就把(忽略了元素顺序的)普通化合物演化过程完全地用线性代数的语言表述出来

比如第六节中那个表格现在就可以用矩阵的语言相当简明地表达。令u是第50、72分量为1,其余分量为0的列向量(对应于第8天的普通化合物7250锡),“化合物中元素个数”一栏表述的其实就是向量Mn-8u的各个分量,其中n是以1开始的边看边说序列的项数。

于是我们可以用线性代数的语言和工具来表述和研究边看边说序列的演化问题。算术定理叙述的,实际上就是当n趋向于无穷时,矩阵Mn的性质。康威在论文中提到的Perron–Frobenius定理,就是这样一个阐述矩阵的幂的极限性质的定理。我们先来看一下它的经典形式。

 

九、Perron–Frobenius定理

如果A是一个其中元素都是正实数的m阶正方矩阵。Perron–Frobenius定理断言,A的特征多项式必定有一个单的正实根μ,而且它严格大于所有其他的根的绝对值(其他的根有可能是复数)。我们知道这个根μ是A的一个特征值,Perron–Frobenius定理说,它必定有一个所有分量都是正实数的特征向量v。因为μ是单根,所以它的特征空间是1维的,就是由v生成的。

当我们说一个矩阵的“特征向量”时,我们通常指的是它的特征向量,也就是说Avvv是一个列向量(或可以说是一个m×1的矩阵)。但A同样也有关于μ的特征向量w,它可以看作是A的转置矩阵tA的(右)特征向量的转置,是一个行向量(或可以说是一个1×m的矩阵),满足wAww当然也可取成其中分量都是正实数的,而且我们还增加一个要求,要求wv=1(行向量乘以列向量的结果可以看作是一个数,也叫这两个向量的内积),这可以通过将w乘以合适的系数做到。

 

Perron–Frobenius定理进一步说,当自然数n趋向于无限时,矩阵序列{(1/μn)An}的极限是矩阵vw(不要和上面的wv=1的要求搞混了,列向量乘以行向量的结果是m阶正方矩阵)。

这实在是一个非常漂亮的定理!要是它适用于边看边说矩阵M的话,Mn在n趋于无穷时的性质就可以通过计算M的特征值和特征向量得到,算术定理也就唾手可得了。

很遗憾,至少是在康威写作论文的那个时代,Perron–Frobenius定理对M并不适用——它的系数充满了不是正数的0。Perron–Frobenius定理也存在着其他一些形式。在某些形式里,条件被放宽为矩阵的元素可以是大于或等于0的实数,但矩阵必须是不可约的或是对称的,或是存在某个k使得Mk的元素都严格大于0,这些也是M所不能满足的——因为M显然不对称,而由于1氢元素的性质,M的第一列除了第一项外都等于0,这使得它是可约的,而且对任何自然数n,Mn的第一列除了第一项外也都等于0。

在这里岔开去说一点,Perron–Frobenius定理是相当有用的一个定理。在实际当中我们常会碰到元素均大于0或是均大于等于0的矩阵,最常见的有马尔科夫链的状态转移矩阵和图论中的邻接矩阵。Google公司搜索引擎的核心技术PageRank(网页排名)就是基于转移矩阵理论和对上面所说的那个特征值的计算,而Perron–Frobenius定理则保证了这个特征值的存在性。从理论上来说,Google要对付的那个矩阵的行和列数,和它搜集的网页数相等,是当之无愧的巨无霸矩阵。如何对它作特征值计算,大概是Google最重要的商业秘密之一,当然这是本文的题外话了。

十、加强版算术定理

因为前面所说的那些形式的Perron–Frobenius定理都不能应用于边看边说矩阵M,于是康威就在论文中用直观的方法证明了一个猴版的结论,也就是前面介绍的算术定理。之所以称它是“猴版”,是因为其结论是不完全的。它只是说,从任何一个普通化合物开始,每一步演化得到的数字串的长度和上一步相比,越来越趋近于康威常数λ,却没有对演化n天后的数字串的长度作直接的估算。下面这幅11钠,29铜和62钐开始演化后30天内序列中数字串长度的统计图很直观地显示了这个定理的正确性。注意到图中纵轴是对数坐标轴,指数函数在这样的坐标系中的图像是直线。随着项数的增长,图中的三条曲线很快都近似直线。三条直线的斜率都一样,通过算术定理我们知道这斜率就是康威常数λ。

康威常数2

长度的增长

但是算术定理无法说明的是,三条直线高低不同的位置是由什么决定的。如果把三条直线所对应的指数函数写成y=cλn的形式,我们就要问:对于每种不同的普通化合物,它所对应的c是由什么决定的,如何计算呢?下面的表中,我们对若干项n计算了以上述三种普通元素开始的边看边说序列的“演化n天后数字串的长度/λn”的值,也即上述c的经验值:

演化天数112962
09.00000006.00000006.0000000
19.20543826.13695886.1369588
28.23862014.70778299.4155658
38.12572596.32000909.0285843
48.31120756.92600638.3112075
57.43830765.313076910.094846
66.92880356.521226810.596994
76.56586336.87852359.3798047
86.23604325.756347510.553304
95.51976066.255728710.855529
105.22232546.77490879.5977873
205.29914806.12589489.9309221
505.29850206.050634010.037356
1005.29939126.050388710.035343
10005.29939036.050390710.035341
100005.29939036.050390710.035341
1000005.29939036.050390710.035341

看来,与11钠,29铜,62钐相对应的c值应该分别大约是5.2993903,6.0503907和10.035341。29铜和62钐的长度都是6,可是对应的c值却差许多;11钠的长度是9,可是对应的c值却反而小于29铜和62钐的。也就是说,从两个初始长度相同的化合物出发,接着用相同时间演化出来的化合物长度可以差许多,甚至有可能初始长度长的化合物,接下去演化出来的化合物的长度反而短。算术定理无法告诉我们这是为什么,更不能对每种化合物预言和它对应的c值。

康威的论文写于1980年代。二十多年后,代数学家们对Perron–Frobenius定理的研究更加深入,与其说现在我们有Perron–Frobenius定理,不如说我们有Perron–Frobenius理论,我们拥有了当年康威所没有的工具。文献[2]中的定理2.4简直就是为边看边说矩阵M量身定造的。它说,如果一个n阶实系数正方矩阵A有一个绝对值最大的正特征值,而且和它相关的左右特征向量都可以取分量非负的话,那么前面Perron–Frobenius定理中所叙述的“当自然数n趋向于无限时,矩阵序列{(1/μn)An}的极限是矩阵vw”的结论同样成立。

注意到在原版Perron–Frobenius定理中,关于存在绝对值最大的正特征值以及正分量的左右特征向量的命题,是结论的一部分,在上面的定理中则成了条件的一部分。对于矩阵M,这个条件是可以独立计算和验证的。关于矩阵的特征多项式、特征值和特征向量的理论,是线性代数的基础知识,在此我就不重复了。

康威证明了,M的92次的特征多项式可以被因式分解,去掉那些根为0或±1的因子,剩下的就是我们在算术定理中看到的那个71次多项式。下图是这个多项式的解的图示,最右方红点即康威常数λ。

康威常数2

71次多项式的解。图中心为原点,每一小格边长为0.5

在这里值得一提的是幂法求特征值的迭代算法(具体方法可以以“幂法 特征值”为关键词在网上查询)。本来这个算法有点鸡肋,因为它只能求绝对值最大的特征值(如果改变一下也可求绝对值最小的特征值,称为反幂法),所以如果要求所有的特征值就不适用了。可是这里我们恰恰只需要求绝对值最大的特征值,用求所有特征值的算法求出一堆特征值来到反而还得另去筛选出绝对值最大的来,反而麻烦。而且幂法能同时求出这个特征值和相关的特征向量。这简直是要睡觉就有人送上了枕头!笔者用这个方法轻松地就求出了M这个绝对值最大的特征值小数点后三百位的值和精确程度类似的相应的特征向量,虽然这么精确的数据其实没什么大用处。

于是我们就有了比原版算术定理更强的
加强版算术定理
1) 边看边说矩阵M有一个在其所有特征值中绝对值最大的特征值λ。λ为正实数,是M的特征多项式的单根。
2) M有一个关于λ的,分量都是正实数的,分量之和为1的(右)特征向量v,我们称v丰度向量
3) M有一个关于λ的,分量都是正实数的左特征向量w,满足wv=1。我们称w富度向量
4) 当自然数n趋向于无限时,矩阵序列{(1/λn)Mn}的极限为矩阵vw

事实上定理中的λ就是康威常数λ。在原版定理中它是一个神秘的71次多项式的根;而在加强版定理中,它被明确为边看边说矩阵的唯一的绝对值最大的特征值。下面我们来看看如何由上述加强版定理推导出原版算术定理。

注意到在文献[2]定理2.4中,v并不是被唯一确定的,而是可以被乘以任意一个正实数,而在上述加强版定理中,对丰度向量v有一个“分量之和为1”的附加要求,v就被唯一确定了。正如它的名字所暗示的,v的各个分量就是各普通元素的丰度:第1个分量对应着1氢的丰度,第2个分量对应着2氦的丰度,等等。

富度向量w因此也被唯一确定,我们可以定义第n号普通元素的富度w的第n个分量。从线性代数的观点来看,wv是相对于同一个特征值的左右特征向量,是对偶的数学对象,所以我们可以把丰度和富度看作是对偶的概念。丰度的英文为abundance,于是和它对偶的富度可以反译回去称作coabundance。

我们不仅可以对普通元素定义其富度,而且可以对一般的普通化合物定义它的富度:普通化合物的富度就是组成它的普通元素的富度之和(同一种元素多次出现则对其富度多次求和)。比如化合物63208912030锌的富度就等于63铕、89锕、1氢、30锌的富度加上两倍20钙的富度。上述定义可以用线性代数的语言简单地写为:令C是一种普通化合物,设它所对应的列向量是u,那么它的富度就是富度向量wu的内积wu

在讨论富度的实际意义前,我们先列出所有普通元素的长度、丰度和富度:

元素长度丰度富度
120.09179038325.6080827086
2320.00323729693.2519030758
3270.00422006662.4945994020
4420.00226388604.4173991800
5340.00295115043.3886745994
6280.00384705252.5995195528
7240.00501493021.9941430512
8180.00653734911.5297467197
9140.00852193971.1734990753
10120.01110900680.9002144354
1190.01448144880.6905723633
12100.01885044121.0642759581
13100.02457300670.8164272141
1470.03203281300.6262975226
15120.01489588671.5173799538
16100.01941793921.1640122836
1760.02531278420.8929369292
1840.03299717010.6849896438
1940.04301436090.5254691533
2020.05607254310.4030978184
21160.00930209742.2191977577
22140.01212600281.7023906526
2380.01580718161.3059376632
2450.02060588261.0018107052
25120.02686136021.2489541407
2680.03501585850.9580975139
2750.04564587730.7349756218
2880.01387112421.0277878559
2960.01808208220.7884364666
3030.02357139130.6048252645
31170.00144789062.3774502059
32230.00188743722.8607239388
33262.72462160762.7242698891
34203.55175479442.0898415106
35164.62998681521.6031589076
36146.03554556821.2298150218
37107.86780000890.9434155159
3871.02562852490.7237127697
3971.33698603150.7923865601
40231.74286459972.2353942193
41282.27195867522.9203125825
42202.96167368522.2402297523
43153.86077049431.7185247131
44213.28994805762.3970976690
45244.28870150422.8757958978
46185.59065379452.2060801198
47127.28784920561.6923278521
48109.50027456451.2982182892
4980.00123843420.9958890202
5050.00161439470.7639662365
5170.00210448821.1205778552
52130.00274336301.9384007646
53180.00357618562.5239203970
54140.00466183431.9361494381
5580.00607706121.4852586679
5660.00792191881.1393714076
5750.01032683330.8740344241
58100.01346182521.5435278845
5980.01754852931.1840708803
6060.02287586390.9083242769
6130.02982045620.6967935837
6260.01540811521.3077219948
6370.02008566871.0031795014
64110.02166297281.6425976370
65160.02823935892.2970039458
66120.03681218641.7620773240
6770.04798752941.3517244937
6890.00109859561.5714588817
69140.00120490842.0785360303
70100.00157069121.5944862492
7160.00204751731.2231620535
7250.00266909700.9383118918
73322.42077366663.2519030758
74273.15566552522.4945994020
75421.69288018084.4173991800
76342.20680012293.3886745994
77282.87673447752.5995195528
78243.75004567391.9941430512
79184.88847429831.5297467197
80146.37250397551.1734990753
81128.30705132930.9002144354
8290.00108288830.6905723633
83100.00141162861.0642759581
84100.00184016700.8164272141
8570.00239879980.6262975226
86120.00312702091.5173799538
87100.00407631341.1640122836
8860.00531378950.8929369292
8940.00692693520.6849896438
9040.00758190470.5254691533
9120.00988359860.4030978184
9211.02562852490.3092243383

任取一种普通化合物C,设它所对应的列向量是u,那么n天后C演化成的化合物所对应的列向量就是Mnu。根据加强版算术定理的3),我们知道当n趋于无穷时,(1/λn)Mnu会趋于vwu。所以对Mnu在n充分大时的性质的研究可以转化为对vwu的性质的研究。

因为矩阵的乘法满足结合律,所以vwu=v(wu),而上面我们已经知道,wuwu的内积,即化合物C的富度,它是一个实数,令它为d,则vwu=dv。这证明了从任何一种普通化合物出发,Mnu在n充分大时和λndv差不多;也就是说,经过足够长时间后,它里面的各元素的百分比就会趋近于丰度向量的各分量。这就是原版算术定理中“每种元素在这些数字串中的比例越来越趋近一个大于0的常数值”这一部分。

我们定义量长向量是这样的行向量,它的各分量分别为各普通元素长度:(2, 32, 27, 42, ……),记它为r。那么容易看出u所对应的化合物的数字串长度就是ru。所以量长向量有测量化合物长度的功能。r和丰度向量v的内积则是一个常量,记它为L,我们可称其为量长常数。(如果滥用一下术语,我们可以说L是丰度向量v所对应的化合物的数字串长度。当然不可能真有哪种化合物所对应的向量会是v,因为v的分量都不是整数,甚至不是有理数。)根据上面的表格容易计算出L≈7.6739102369。对应于Mnu的化合物的长度为rMnu,它约等于rvwuλn=drvλn=dLλn。换句话说,当n相当大时,dLλn是C在n天后演化结果的长度的很好的估计。

这下我们看出来了,dL就是对本节开始想求的c,即化合物的富度乘以量长常数。对11钠,29铜和62钐来说,其富度乘以量长常数的值分别约为5.2993903280,6.0503906721和10.0353412031。这三个数字和前面计算的经验值完全符合。

严格地写成命题的话就有:
量长推论)令普通化合物C的富度为d,它在第n天后演化结果的长度为hn,那么当n趋向于无穷时,dLλn/hn趋向于1,其中L为量长常数。

从这个结论很容易推出原版算术定理中“从任何一个普通化合物开始,每一步演化得到的数字串的长度和上一步相比,越来越趋近于固定常数λ”这部分。于是原版算术定理完全得证。

十一、更多的推论

一件有趣的事情是,如果我们将上面的r由量长向量换成每个分量都是1的行向量(1, 1, 1, 1, ……),那么ru就是u所对应的化合物中的元素个数(于是这个向量我们可以类似地称为计件向量,即以“件数”来称呼化合物中元素的个数),而rv精确地等于1(可称其为计件常数,滥用一下术语的话,丰度向量v所对应的化合物中恰好有1件元素)。对应于Mnu的化合物中的元素件数为rMnu,它约等于rvwuλn=drvλn=dλn。即在n相当大时,dλn是C在n天后演化结果中元素件数的很好的估计。

严格地写成命题的话就有:
计件推论)令普通化合物C的富度为d,它在第n天后演化结果中的元素件数为sn,那么当n趋向于无穷时,dλn/sn趋向于1。

如果再翻译回原版定理的说法,那就是“从任何一个普通化合物开始,每一步演化得到的元素个数和上一步相比,越来越趋近于固定常数λ。”事实上,这才是原版中的原版。康威的论文中的算术定理就是以化合物中元素个数为对象论证的,而不是象在本文上篇中那样,以化合物长度为对象。

这下我们达到了思路广的境界——量长和计件向量只是两个特定的向量而已,而每给定一个92个分量的行向量,上面的论证都可以被照葫芦画瓢地小小改编一下得到一个相应的推论。当然,这个行向量如果随便给就太没意思了,我在下面提几个有某种实际意义的例子。

令C是一个普通化合物,我们定义它的重量是它的所有数字之和。比如1氢的重量是2+2=4,11钠的重量是1+2+3+2+2+2+1+1+2=16。那么我们可以定义称重向量为各分量是各元素重量的行向量(4, 56, 47, 72, ……),定义称重常数则是称重向量和丰度向量v的内积,约等于12.964860969。我们有
称重推论)令普通化合物C的富度为d,它在第n天后演化结果的重量为wn,那么当n趋向于无穷时,dLλn/hn趋向于1,其中L为称重常数。

类似地我们可以引入“计1向量”、“计2向量”和“计3向量”,其分量分别是各元素中的“1”、“2”和“3”的个数,同样可定义“计1常数”、“计2常数”和“计3常数”,得到类似上面推论的“计1推论”、“计2推论”和“计3推论”。

十二、附记

如果对照康威原论文和本文内容的话,读者会发现在定理和引理的叙述方面有一些不同,最明显的是本文的化学定理变成是完全关于普通化合物的命题了,原本其中关于包含任意字符的数字串的部分,被移动到宇宙学定理中。这样的改动主要是出于科普文介绍的方便,康威从文章一开始就考虑包含任意字符的数字串,而笔者则需要注意循序渐进,以及将不同难度的问题分开。



收起全文
人人小站
更多热门小站
X