金匮要略Z第二次作业

1 Divide and ConquerA group of n Ghostbusters is battling n ghosts. Each Ghostbuster is armed with a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with the ghosts, forming n Ghostbuster-ghost pairs, and then simultaneously each Ghostbuster will shoot a stream at his chosen ghost. As we all know, it is very dangerous to let streams cross, and so the Ghostbusters must choose pairings for which no streams will cross. Assume that the position of each Ghostbuster and each ghost is a fixed point in the plane and that no three positions are collinear.i Argue that there exists a line passing through one Ghostbuster and one ghost such the number of Ghostbusters on one side of the line equals the number of ghosts on the same side. Describe how to find such a line in O(n log n) time.ii Give an O(n2 log n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.Answer:i -ii: We assume that all the points in the plane are not in same X or Y axis using mark to stand for ghostbuster or ghosts(mark 0 stand for ghostbuster and mark 1 stand for ghosts).(This can not affect the problem because when we get the same X or Y , we can add or minus a very little value to let all points’ X or Y are not same). First we get the deepest point (in other word, the minimum Y value). Also we compute the other points with this point ‘s angle in X axis and sort these other points with this angle. Then we iterate in this order, and get another mark which is different from the deepest point's mark also we line this twopoint ,and compute the bottom mark 0 's number and mark 1's number, they are the same , then we find the pair which is the deepest point and the iterate point. So we use this line to divide all points into two parts and recursive do the same above operation until the points' number is only 2 then we only get the line to connect this two points.Algorithm:Get_Pair(points[1-2N])if N>1initial a array points[1-2N] stand for the points of ghostbusters and ghostsfind the deepest point min_Point in the array pointsinitial the pair_Point and the index with 0get the other 2N-1 points with this min_Point 's angle in X axis and sort these anglesinitial num1 with 0 stand for the number of the other 2N-1 points which's mark is same with min_Pointinitial num2 with 0 stand for the number of the other 2N-1 points which's mark is not same with min_Pointfor i=1 to 2N-1if min_Point's mark is same with points[i]'s marknum1++elsenum2++endifif num1+1==num2get this point pair_Pointindex=ibreak;endifendforprint this pair (min_Point,pair_Point)using pair_Point to divide points into two parts point_one[1-index-1] andpoint_two[index+1-2*N]Get_Pair(point_one[1-index-1])Get_Pair(point_two[index+1-2*N])elseget the line to connect this two pointsendifWe will prove this algorithm is O(n log n) time, first we get the deepest point in O(n) time, next we compute the other points with this deepest point 's angle in X axis in O(n) time, we use quick_sort to sort these n angles in O(n log n). Last we iterator these angles in O(n) to find the pair. So all time we consume is only O(n log n) time.Next we will prove this algorithm always can find the pair. Now we assume the deepest point stand for the Ghostbusters using mark=0, so above this point, we have n-1Ghostbusters(mark=0) and n Ghosts(mark=1). So we can sort n-1 0 and n 1 in whole arrangement, no matter how we sort, we can get a index in 1 , which before this 1 we have the same number of 0 and 1. We can replace this problem with a new problem, we have a road for (0,0) point to (n-1,n) point , we only can move the one step in the X or Y direction. No matter which road we have, we must cross the line Y=X it means we must get the Ghost. Before this ghost, we have the same number of ghosts and ghostbusters.Last, we will prove that solving this problem is O(n2 log n).Easily, we get the T(n)=2*T(n/2)+O(n log n).We use mathematical induction for assuming that T(n)<= O(n2 log n)n=1, T(1)=O(n log n)<=O(n2 log n)assume n<k T(n)<=O(n2 log n)then n=k, T(k)=2*T(k/2)+O(k log k)<=2*O(k2 log (k/2)/ 4)+O(k log k)=O(k2 log(k/2) /2)+O(k log k)<=O(k2 log k)2 Divide and ConquerYou are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values-so there are 2n values total-and you may assume that no two values are the same. You’d like to determine the median of this set of 2n values, which we will define here to be the n th smallest value.However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the k th smallest value that it contains. Since queries are expensive, you would liketo compute the median using as few queries as possible.Give an algorithm that finds the median value using at most O(log n) queries.Answer:First we can assume the two arrays are in ascending order because in this question we can specify a value k to one of the two arrays, and this system will return the k’t h smallest value that it contains. So in the following two arrays: An and Bn. (each array contains n different value and is in ascending order)So we get the median of two arrays: A[n/2] and B[n/2]. Before the A[n/2] value, there are only n/2-1 values, the same , before the B[n/2] value, there are only n/2-1values.(A[n/2]!=B[n/2] because all 2n values are not same). So we only have two conditions: i: A[n/2]<B[n/2] , before the B[n/2] value, there must be at least n/2-1+n/2-1+1=n-1values(n/2-1 before A[n/2] and n/2-1 before B[n/2] and 1 stand for A[n/2] itself). The same , before the A[n/2] value, there must be at most n/2-1+n/2-1=n-2. So the two arrays’ median value must be in the interval A[n/2+1] to A[n] and in the interval B[1] to B[n/2]. We can divide this problem into one small problem . At last , A and B only have one value , we get the small one which is the result.ii: A[n/2]>B[n/2] , the same, the two arrays’ median value must be in the interval A[1] toA[n/2] and in the interval B[n/2+1] to B[n].Algorithm:Get_Median(A[1-n],B[1-n])If the A and B only have one element thenReturn the small oneElseGet the median a and b stand for A and BIf a<bReturn Get_Median(A[n/2+1-n],B[1-n/2])ElseReturn Get_Median(A[1-n/2],B[n/2+1-n])EndifEndifNow , we will prove this algorithm is O(log n) time.In algorithm: we can have T(n)=T(n/2)+c when n>1 and T(1)=c (c is the constant value) , So we get T(n)=clog n. Then this algorithm is O(log n) time.3 Divide and ConquerGiven a convex polygon with n vertices, we can divide it into several separated pieces, such that every piece is a triangle. When n = 4, there are two different ways to divide the polygon; When n = 5, there are five different ways.Give an algorithm that decides how many ways we can divide a convex polygon with n vertices into triangles.Answer:We get the f(n) to stand for : the number of different ways to divide the n-polygon.f(1)=1;f(n)=f(1)*f(n-1)+f(2)*f(n-2)+....+f(n-1)*f(1) n>1;So the algorithm is:int f(int n)If n==1return 1;Elseint result=0;for i=1 to n-1result+=f(i)*f(n-i);Endforreturn result;Endif4 Counting InversionsRecall the problem of finding the number of inversions. As in the course, we are given a sequence of n numbers a1, ..., a n, which we assume are all distinct, and we define an inversion to be a pair i < j such that a i > a j .We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure i s too sensitive. Let’s call a pair a significant inversion if i < j and a i > 3a j .Given an O(n log n) algorithm to count the number of significant inversions between two orderings.Answer:Given a sequence of n numbers , we use a array D[1-n] which contains this n numbers. We can use Sort_Count function in the normal CountingInversions. Assume we divide D[1-n] into two half array D1[1-n/2] for D[1-n/2] and D2[1-n/2] for D[n/2+1-n], and we have already sort the two arrays D1 and D2 and computed the inversions’ numbers. Now what we only should do is to get the D1[i] and D2[j] (i and j is 1-n/2) and look whether this two number is inversed and at the same time we should merge this two sorted array.Now let us describe this problem: we already get two sorted arrays D1[1-n/2] and D2[1-n/2], we set three indexes i and j1 and j2, i and j2 is to iterate D1 and D2, j1 is to .D2[j1-j2-1]<D1[i] in other word, it means the current i’th value is bigger th an j1 to j2-1’s all values. When we iterate i’th number in D1 and j’th number in D2, we have two conditions : (because all numbers are distinct , so D1[i]!=D2[j2])i: D1[i]<D2[j2]. We look whether D1[i] is treble than D2[j1] , if D1[i]>3*D2[j1] then we add InverseCount with the number of D1 remaining arrays . (InverseCount stand for the current number of inversions) and at the same time, we add j1 to look the next element in D2. Else, we insent D1[i] value into new sorted array and add i to look the next element in D1.ii: D1[i]>D2[j2]. We insert D2[j2] value into new new sorted array and add j2 to look the next element in D2.Algorithm:Merge_and_Count(D1[1-n],D2[1-n])Initial InverseCount , i, j1, j2 with 0Initial new array NEW_D which contains all elements in ascending orderWhile D1 and D2 all is not emptyIf D1[i]<D2[j2]If D1[i]>3*D2[j1]Add InverseCount with the number of D1’s remaining’s elementsIncrement j1ElseInsert D1[i] into NEW_DIncrement iEndifElseInsert D2[j2] into NEW_DIncrement j2EndifEndWhileWhile D2 is not emptyInsert D2[j2] into NEW_DIncrement j2EndWhileWhile D1 is not emptyIf j1 is not iterate to the end of D2If D1[i]>3*D2[j1]Add InverseCount with the number of D1’s remaining’s elementsIncrement j1ElseInsert D1[i] into NEW_DIncrement iEndifElseInsert D1[i] into NEW_DIncrement iEndifEndWhileReturn InverseCountSort_and_Count(l,r)If l<rGet middle m between l and rGet RCL is Sort_and_Count(l,m) which stand for the left half array ‘s inversion’s numberGet RCR is Sort_and_Count(m+1,r) which stand for the right half array’s inversion’s numberGet RLR is Merge_and_Count(D1[l-m],D2[m+1-r]) which stand for the left and right ‘s inversion’s numberReturn RCL+RCR+RLREndif5 Counting InversionsThe attached file Q5.txt contains 100,000 integers between 1 and 100,000 (each row has a single integer), the order of these integers is random and no integer is repeated.1. Write a program to implement the SORT-AND-COUNT algorithms in your favorite lan-guage, find the number of inversions in the given file.2. In the lecture, we count the number of inversions in O(n log n) time, using the MERGE-SORT idea. Is it possible to use the QUICK-SORT idea instead ?If possible, implement the algorithm in your favorite language, run it over the given file, and compare its running time with the one above. If not, give a explanation.Answer:1: C++ Code:#include<iostream>#include<fstream>#include<memory.h>#include<stdlib.h>using namespace std;int N=100000;int data[100000];ofstream out("res.txt");long long merge_count(int l,int m,int r){int count=0;int* L=(int*)malloc((m-l+1)*sizeof(int));int* R=(int*)malloc((r-m)*sizeof(int));//memcpy(L,data+l*sizeof(int),(m-l+1)*sizeof(int));//memcpy(R,data+(m+1)*sizeof(int),(r-m)*sizeof(int));for(int i=l;i<=m;i++)L[i-l]=data[i];for(int i=m+1;i<=r;i++)R[i-m-1]=data[i];int i=0,j=0,k=l;for(;i<m-l+1&&j<r-m;){if(L[i]>R[j]){data[k++]=R[j++];count+=m-l-i+1;}else{data[k++]=R[i++];}}for(;i<m-l+1;){data[k++]=L[i++];}for(;j<r-m;){data[k++]=R[j++];}return count;}long long inversion_Counting(int l,int r){if(l<r){int m=(l+r)>>1;long long L=inversion_Counting(l,m);long long R=inversion_Counting(m+1,r);long long LR=merge_count(l,m,r);out<<L+R+LR<<endl;return L+R+LR;}elsereturn 0;}int main(){ifstream in("Q5.txt");for(int i=0;i<N;i++)in>>data[i];cout<<inversion_Counting(0,N-1);return 0;}The result is 1693706111.2. We cannot use QUICK_SORT idea to implement the InverseCounting. Because we cannot have the two sorted half array. When we use Merge_Sort, we first get two sorted half array and can compute one number in left array and another number in right array. In fact, we do the Merge_Sort function is the same with visiting tree in postorder. But we do the Quick_Sort function is the same with visiting tree in preorder. Only in postorder, we first get the two half arrays(the node's two children) in order, so we can visit thenode itself.6 SortingThe M ERGE-S ORT, Q UICK-S ORT and M ODIFIED-Q UICK-S ORT algorithms in the lecture slides are all recursive. However, by using a stack, all of them can be implemented in a iterative way. 1. Implement both the recursive version and iterative version of the three algorithms inyour favorite language.2.Run your implementation over three integer arrays whose sizes are 100, 000, 1, 000, 000,10, 000, 000 respectively. Record their running times and make a comparison.Answer:with C++ code in Linux System using Eclipse:M ERGE-S ORT Q UICK-S ORT100, 00040ms 50ms1, 000, 000980ms 422ms10, 000, 00011486ms 4980msM ERGE-S ORT-Itr Q UICK-S ORT-Itr100, 000114ms 46ms1, 000, 0001306ms 547ms 10, 000, 00014765ms 6429ms。

历史第二次课作业
1．秦阳陵虎符(见下图)，中分为二，左右各有十二铭文：“甲兵之符，右才(在)______，左才阳陵。

”将帅发兵时必须左、右半符验合后方能生效。

上文“右才”后面的空缺部分应是( )
A．皇帝B．太尉C．御史大夫D．丞相
2．秦始皇在全国范围内确立了中央集权的政治制度，中央集权指( ) A．全国有统一的货币、度量衡
B．全国有通行的统一文字
C．以皇权至高无上为最基本的原则
D．中央机构对地方机构实行直接有效的行政管理
3．秦始皇建立的专制主义中央集权制度与分封制相比，主要的特点是( )
①确立了皇权的至高无上②官职世袭制③确立了中央和地方的行政机构
④中央和地方的主要官员都由皇帝任免
A．①②③④B．①②③C．①④D．①③④
解答题：
材料一“褒姒不好笑，幽王欲其笑万方，故不笑。

幽王为烽燧大鼓，有寇至则举烽火。

诸侯悉至，至而无寇，褒姒乃大笑。

” 这就是“烽火戏诸侯”的闹剧。

材料二幽王时边境空虚，犬戎东侵，周师大败。

但幽王竟不顾犬戎的进犯，于幽王十年与诸侯会盟兴兵讨伐申国，企图杀害宜臼。

申后的父亲申侯于幽王十一年联合犬戎、吕、缯等国举兵攻周。

周幽王急“举烽火征兵”，诸侯不至。

犬戎攻破镐京，杀幽王于骊山下，西周灭亡。

请回答：
(1)材料一中周幽王烽火戏诸侯，为什么“诸侯悉至”？
(2)从“诸侯悉至”到“诸侯不至”说明了什么？。

五脏六腑皆病痰饮，非独脾也摘要：从“仲景三法”和“无择三因”简单的分析痰饮病症的病因病机，从内因、外因、不内外因三个方面证明了“五脏六腑皆病痰饮，非独脾也”这一论题。

痰饮由来与概念：在内经中曾云：“太阴在泉，湿淫所生，民病积饮。

”又云：“岁土太过，雨湿流行，甚则饮发。

”且古时“痰”字本作“淡”，如《脉经》、《千金翼》中均作“淡饮”。

唐•玄应在《一切经音义》中云：“淡饮，谓膈上液也”。

而汉代张仲景在《金匮要略・痰饮咳嗽病脉证并治第十二》篇中明确指出了“痰饮”的名称，并按其停留部位的不同分别名之，如《痰饮咳嗽病脉证并治第十二》篇中“一，问曰：夫饮为四，何谓也？师曰：有痰饮，悬饮，有溢饮，有支饮”。

“二，问曰：四饮何以为异？师曰：其人素盛今瘦，水走肠间，沥沥有声，谓之痰饮。

饮后水流胁下，咳唾引痛，谓之悬饮。

饮水流行，归于四肢，当汗出而不汗出，身体痛重，谓之溢饮，咳逆倚息，短气不得卧其形如肿，谓之支饮”。

自此痰饮病名沿用至今。

众所周知，痰饮病症分之为广义与狭义之分。

广义之痰饮，人体脏腑阳气衰微，水液运化输布失常停积于某部位，而致水饮内停。

张仲景所论之痰饮，重点在“饮”而不是“痰”，“饮”者，即水液停留于人体局部者，因为它所停留的部位和所表现症状的不同而有不同的名称。

而“痰”的作用我认为主要是推类及之。

因此可见张仲景提出的痰饮病应是广义的痰饮病症。

那么既然痰饮病症是由于水液运化输布失常所致，我们就会不由自主地想到的便是“脾”这一个脏腑，我们都知道脾主运化水湿，《素问.至真要大论》又云：“诸湿肿满，皆属脾也。

”脾胃受伤，运化无权，水湿内停，则可聚集成痰；脾阳素虚，复加外感寒湿、饮食劳欲之伤等，导致脏腑功能失调，水液在体内不得输化，停聚或流注于某一部位则为饮。

那么痰饮这样一个多样且多变的疾病难道仅仅只是由于脾的功能失常而造成的吗？我们都学过《中医基础理论》，绪论就说过中医诊治应遵循整体原则，人体表面与内部、结构和功能上密不可分，应时刻注意到人体整体联系的统一性，整体与整体，整体与部分，部分与部分之间均存在着联系。

第二次作业：1、出卫生部发布的药食同源药。

并写出各药的主要功效。

（提示：共77种）2、根据上述药食同源药，对于湿热下注的淋证，外寒直中的胃痛，阴虚燥热的咳嗽，津枯肠燥的的便秘，食积胃肠的呕吐，肾虚不足的脱发，心脾两虚的失眠，邪热蕴肺的发热等应选用哪些药物进行调护。

要求如前。

A4纸打印，小四字体，单倍行距。

丁香功效;温中、暖肾、降逆八角茴香功效：散寒止痛，理气和胃刀豆功效：将其之二，温肾助阳小茴香功效：散寒止痛，理气和胃小蓟功效：凉血止血，散瘀解毒消痈山药功效：益气养阴，补脾肺肾，固精止带山楂功效：消食化积，行气散瘀马齿苋功效：清热解毒，散血消肿乌梅功效：敛肺止咳，涩肠止泻，安蛔止痛，生津止渴木瓜功效：消食，驱虫，清热，祛风、火麻仁功效：润肠通便代代花功效：行气宽中，消食，化痰玉竹功效：养阴，润燥，除烦，止渴甘草功效：补脾益气，除痰止咳，缓急止痛，清热解毒，调和诸药白芷功效：解表散寒，祛风止痛，通鼻窍，燥湿止带，消肿排脓白果功效:敛肺定喘、止带、缩尿胡荽功效：发表透疹，开胃消食白扁豆功效:健脾化湿，利尿消肿，清肝明目白扁豆花功效、健脾和胃，清暑化湿龙眼肉功效：补益心脾，养血安神决明子功效:清肝，明目，利水，通便百合功效：养阴润肺，清心安神肉豆蔻功效:温中，行气，消食，除痰，固肠，醒酒解毒肉桂功效:补元阳，暖脾胃，除积冷，通血脉佛手功效：疏肝解郁，理气和中，燥湿化痰杏仁功效:祛痰止咳；平喘；润肠牡蛎功效:敛阴，潜阳，止汗，涩精，化痰，软坚芡实功效:固肾涩精，补脾止泄花椒功效:温中止痛；除湿止泻；杀虫止痒赤小豆功效:除热毒，散恶血，消胀满，利小便，通乳阿胶功效补中滋阴，润肺止血鸡内金功效：消食健胃，涩精止遗麦芽功效：消食健胃，回乳消胀昆布功效：消痰软坚、泄热利水、止咳平喘、祛脂降压、散结抗癌大枣功效;补中益气，养血安神罗汉果功效:润肺止咳，生津止渴郁李仁功效:润燥，滑肠，下气，利水金银花功效：清热解毒，疏散风热青果功效：清肺利咽、生津止渴、解毒鱼腥草功效：清热解毒，利尿消肿生姜功效：解表散寒，温中止呕，温肺止咳干姜功效：温中散寒，回阳通脉，温肺化饮枳椇子功效：除烦渴，解酒毒，利小便枸杞子功效：补肾益精，养肝明目，补血安神，生津止渴，润肺止咳栀子功效：泻火除烦，清热利尿，凉血解毒砂仁功效：化湿开胃，温脾止泻，理气安胎胖大海功效：清热润肺，利咽解毒，润肠通便。