经典c编程实例.pdf

《经典c编程实例.pdf》由会员分享，可在线阅读，更多相关《经典c编程实例.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.冒泡法：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:Si n c l u d e v o i d Bu b b l e So r t(i n t*p Da t a,i n t Co u n t)(i n t i Te m p;f o r(i n t i=l;i=i;j一)(i f(p Da t a j p Da t a j-l )(i Te m p =p Da t a j-1;p Da t a j-l =p Da t a j ;p Da t a j =i Te m p;)v o i d m a i n 0(i n t d a t a =10,9,8,7,

2、6,5,4;Bu b b l e So r t(d a t a,7);f o r (i n t i=0;i 7;i+)c o u t d a t a i z/c o u t 10,9,7,8-10,7,9,8-7,10,9,8（交换 3 次）第 二 轮:7,10,9,8-7,10,8,9-7,8,10,9（交换 2 次）第一轮：7,8,10,9-7,8,9,10（交换 1 次）循环次数：6次交换次数：6次其他：第 一 轮:8,10,7,9-8,10,7,9-8,7,10,9-7,8,10,9(交换 2 次)第二轮：7,8,10,9-7,8,10,9-7,8,10,9(交换 0 次)第 一 轮:

3、7,8,10,9-7,8,9,10(交换 1 次)循环次数：6次交换次数：3次上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+.+n-l o写成公式就是l/2*(n-l)*n。现在注意，我们给出0方法的定义：若存在一常量K和起点n 0,使当n=n 0时，有f (n)v o i d Ex c h a n g e So r t(i n t*p Da t a,i n t Co u n t)(i n t i Te m p;f o r(i n t i=0;i Co u n t-l;i+)

4、(f o r (i n t j=i+l;j Co u n t;j+)(i f(p Da t a j p Da t a i )(i Te m p =p Da t a i ;p Da t a i =p Da t a j ;p Da t a j =i Te m p;)v o i d m a i n ()i n t d a t a =10,9,8,7,6,5,4;ExchangeSort(data,7);for(int i=0;i9,10,8,7-8,10,9,7-7,10,9,8（交换 3 次）第二轮：7,10,9,8-7,9,10,8-7,8,10,9（交换 2 次）第 一 轮:7,8,10,9-

5、7,8,9,10（交换 1 次）循环次数：6 次交换次数：6 次其他：第 一 轮:8,10,7,9-8,10,7,9-7,10,8,9-7,10,8,9（交换 1 次）第二轮：7,10,8,9-7,8,10,9-7,8,10,9（交换 1 次）第 一 轮:7,8,10,9-7,8,9,10（交换 1 次）循环次数：6 次交换次数：3 次从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是l/2*（n T）*n,所以算法的复杂度仍然是0（n*n）。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。3.选择法

6、：现在我们终于可以看到 点希望：选择法，这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。include void SelectSort（int*pData,int Count）（int iTemp;int iPos;fo r（int i=0;iCount-l;i+）（iTemp=pD atai;iPos=i;for（int j=i+l;jCount;j+）if(pD a ta j iT e mp)(iT e mp=pD a ta j;iP os=j;)pD a ta iP os =pD

7、a ta i;pD a ta i =iT e mp;)void ma in()(int d a ta =1 0,9,8,7,6,5,4;S e le c tS ort(d a ta,7);f or(int i=0;i 7;i+)c out d a ta i，/;c out n；该排序法的图示如下；i=0 时：iT e mp=pD a ta 0 =1 0；iP os=i=0；j=l；pD a ta j pD a ta l=9 1 0;iT e mp=pD a ta 1 =9;ipos=j=l;j+=2j=2;pD a ta j pD a ta 2 =8 9;i T e mp=pD a ta 2

8、=8;ipos=j=2;j+=3j=6;pD a ta j pD a ta 6 =4 (iT e mp=9)1 0,9,8,7-(iT e mp=8)1 0,9,8,7-(iT e mp=7)7,9,8,1 0 (交换 1次)第二轮：7,9,8,1 0-7,9,8,1 0(iT e mp=8)-(iT e mp=8)7,8,9,1 0(交换 1 次)第 一 轮:7,8,9,1 0-(iT e mp=9)7,8,9,1 0 (交换 0 次)循环次数：6次交换次数：2次其他：第一轮:8,1 0,7,9-(iT e mp=8)8,1 0,7,9-(iT e mp=7)8,1 0,7,9-(iT e

9、mp=7)7,1 0,8,9(交换 1次)第二轮：7,1 0,8,9-(iT e mp=8)7,1 0,8,9-(iT e mp=8)7,8,1 0,9 (交换 1 次)第 一 轮:7,8,1 0,9-(iT e mp=9)7,8,9,1 0 (交换 1 次)循环次数：6次交换次数：3次遗憾的是算法需要的循环次数依然是l/2*(n-l)*n。所以算法复杂度为0(n*n)。我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所 以 f(n)=n所以我们有f(n)=0(n)。所以，在数据较乱的时候，可以减少一定的交换次数。4.插入法：插入法较为复杂，它的基本工作原理是抽出牌，在前面

10、的牌中寻找相应的位置插入，然后继续下一张#inc lud e void I nse rtS ort(int*pD a ta,int C ount)(int iT e mp;int iP os;f or(int i=l;i=0)&(iT e mp pD a ta iP os)(pD a ta iP os+l =pD a ta iP os;iP os一;pD a ta iP os+l =iT e mp;void ma inO(int d a ta =1 0,9,8,7,6,5,4;I nse rtS ort(d a ta,7);f or(int i=0;i 7;i+)c out =0&iT e m

11、p=9 =0&iT e mp=8 pD a ta 1 =1 0;pD a ta 2 =pD a ta l=1 0;ipos=1-1=0;9-1 0-1 0-7-6-5-4ipos=0 =0&i T e mp=8 =0&i T e mp=7 =0&i T e mp=8 =0&i T e mp=7 =0&i T e mp=6 =0&i T e mp=7 =0&i T e mp=7 =0&i T e mp=7 9,1 0,8,7 （交换 1 次）（循环 1 次）第 二 轮:9,1 0,8,7-8,9,1 0,7（交换 1 次）（循环 2 次）第一轮：8,9,1 0,7-7,8,9,1 0（交换 1

12、次）（循环 3 次）循环次数：6次交换次数：3次其他：第一轮：8,1 0,7,9-8,1 0,7,9（交换 0 次）（循环 1 次）第二轮：8,1 0,7,9-7,8,二,9（交换 1 次）（循环 2 次）第一轮：7,8,1 0,9-7,8,9,1 0（交换 1 次）（循环 1 次）循环次数：4次交换次数：2次上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，因为其循环次数虽然并不固定，我们仍可以使用0方法。从上面的结果可以看出，循环的次数f（n）=l/2*n*（n-l）=l/2*n*n。所以其复杂度仍为0（n*n）（这里说明一下,其实如果不是为了展示这些

13、简单排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是0（n）（推导类似选择法），但我们每次要进行与内层循环相同次数的操作。正常的一次交换我们需要三次而这里显然多了一些，所以我们浪费了时间。最终，我个人认为，在简单排序算法中，选择法是最好的。插入排序#i n c l u d e u s i n g n a me s p a c e s t d;v o i d c o u t s t r e a m(i n t a ,i n t n)f o r(i n t i=0;i!=n;i+)v o i d i n s e r t s o r t(i n t a ,i n t n)i

14、 n t t e mp;f o r(i n t i=l;i O&t e mp a j-l )(a j =a j-l ;J ；)a j =t e mp;)i n t ma i n()(i n t a 5 =l,6,4,8,4);i n s e r t s o r t (a,5);插入排序c o u t s t r e a m(a,5);/r e t u r n 0;)二、高级排序算法：高级排序算法中我们将只介绍这一种，同时也是目前我所知道(我看过的资料中)的最快的。它的工作看起来仍然象一个二叉树。首先我们选择一个中间值mi d d l e 程序中我们使用数组中间值，然后把比它小的放在左边，大的放

15、在右边(具体的实现是从两边找，找到一对后交换)。然后对两边分别使用这个过程(最容易的方法一递归)。1.快速排序：#in cl u de v o id r u n(in t*p D at a,in t l eft,in t r ight)in t i,j;in t m iddl e,iT em p;i=l eft;J =r ight;m iddl e=p D at a(l eft+r ight)/2;求中间值do w hi 1 e(p D at a im idd 1 e)&(i m iddl e)&(j l eft)从右扫描大于中值的数j；if(iC j)找到了一对值(交换iT em p =p

16、D at a i;p D at a i=p D at aEj;p D at a j=iT em p;i+；j；)w hil e(i=j);如果两边扫描的下标交错，就停止(完成一次)当左边部分有值(l eft j),递归左半边if(l eft i)r u n(p D at a,i,r ight);)v o id Q u ick s o r t(in t*p D at a,in t C o u n t)(r u n (p D at a,0,C o u n t-1);)v o id m ain()(in t dat a =10,9,8,7,6,5,4 ;Q u ick s o r t(dat a,7

17、);fo r (in t i=0;i7;i+)co u t dat a i/zco u t，z n，z;这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况1.数组的大小是2的幕，这样分下去始终可以被2整除。假设为2的 k次方，即 k=l o g2(n)。2 .每次我们选择的值刚好是中间值，这样，数组才可以被等分。第一层递归，循环n 次，第二层循环2*(n/2).所以共有 n+2 (n/2)+4 (n/4)+.+n*(n/n)=n+n+n+.+n=k*n=l o g2 (n)*n所以算法复杂度为0(l o g2(n)*n)其他的情况只会比这种情况差，最差的情况

18、是每次选择到的m iddl e都是最小值或最大值，那么他将变成交换法(由于使用了递归，情况更糟)。但是你认为这种情况发生的几率有多大？呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。如果你担心这个问题，你可以使用堆排序，这 是 种 稳 定 的 0(l o g2(n)*n)算法，但是通常情况下速度要慢于快速排序(因为要重组堆)。三、其他排序1.双向冒泡：通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为，也许我错了)。反正我认为这是

19、一段有趣的代码，值得一看。i ncl ude vo i d B ubbl e2So r t(i nt*p D ata,i nt C o unt)i nt i Tem p;i nt l eft=1;i nt r i g h t=C o unt-1;i nt t;do(正向的部分fo r(i nt i=r i g h t;i=l eft;i-)(i f(p D ata i p D at a i-1)(i Tem p =p D ata i;p D ata i=p D ata i-l;p D ata i-l =i Tem p;t=i;)l eft=t+1;反向的部分fo r (i=l eft;i r

20、i g h t+l;i+)i f(p D ata i p D ata i-1)i Tem p =p D ata i;p D ata i =p D ata i-l;p D ata i l =i Tem p;t=i;)r i g h t=t-1;wh i l e(l eft=r i g h t);)vo i d m ai n()(i nt data =10,9,8,7,6,5,4;B ubbl e2So r t(data,7);fo r (i nt i=0;i 7;i+)co utdata i/z;co ut n；快速排序#i ncl ude us i ng nam es p ace s td;c

21、l as s Qui ck s o r t(p ubl i c:vo i d q ui ck _s o r t(i nt*x,i nt l o w,i nt h i g h)(i nt p i vo tk ey;i f(l o w h i g h)(p i vo tk ey=p ar ti o n(x,l o w,h i g h);q ui ck _s o r t(x,l o w,p i vo tk ey-1);q ui ck _s o r t(x,p i vo tk ey+1,h i g h);)i nt p ar ti o n(i nt*x,i nt l o w,i nt h i g h)

22、(i nt p i vo tk ey;p i vo tk ey=x l o w;wh i l e(l o w h i g h)(wh i 1e(l o w=p i vo tk ey)h i g h;还有wh i l e循环只执行这一句x l o w=x h i g h;wh i l e(l o w h i g h&x l o w=p i vo tk ey)+l o w;还有wh i l e循环只执行这一句x h i g h=x l o w;)x l o w=p i vo tk ey;r etur n l o w;)；i nt m ai n()(i nt x 10=52,49,80,36,14,

23、58,61,97,23,65;Qui ck s o r t q s;q s.q ui ck s o r t(x,0,9);co ut 排好序的数字序列为：“endl;fo r (i nt i=0;i 10;i+)(p r i ntf(%d,x i);)r etur n 0;)2.SHELL 排序这个排序非常复杂，看了程序就知道了。首先需要一个递减的步长，这里我们使用的是9、5、3、1(最后的步长必须是1)。工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序以次类推。#i ncl ude vo i d Sh el l So r t(i nt*p D at

24、a,i nt C o unt)(i nt s tep 4;s tep 0=9;s tep l =5;s tep 2=3;s tep 3=1;i nt i Tem p;i nt k,s,w;fo r(i nt i=0;i 4;i+)(k =s tep i;s =-k;fo r (i nt j=k;j C o unt;j+)(i Tem p =p D ata j;w=j-k;求上s tep 个元素的下标i f(s =0)s =-k;s+;p D ata s =i Tem p;)wh i l e(i Tem p=0)&(w=C o unt)(p D ata w+k =p D ata w;w=w-k;

25、)p D ata w+k =i Tem p;)vo i d m ai n()(i nt data =10,9,8,7,6,5,4,3,2,1,-10,-1;Sh el l So r t(data,12);fo r (i nt i=0;i 12;i+)co utdata i z,co ut“n；)呵呵，程序看起来有些头疼。不过也不是很难，把 s=0的块去掉就轻松多了，这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：”由于复杂的数学原因避免使用2 的基次步长，它能降低算法效率 另外算法的复杂度为n

26、的 1.2次暴。同样因为非常复杂并“超出本书讨论范围”的原因(我也不知道过程)，我们只有结果了#i ncl ude us i ng nam es p ace s td;vo i d m ao p ao(i nt*l i s t,i nt n)(i nt i=n,j,tem p;bo o l exch ang e;当数据已经排好时，退出循环fo r (i=0;i n;i+)(exch ang e=fal s e;fo r (j=0;j l i s t j+U)(tem p=l i s t j;l i s t j=l i s t j+l;l i s t j+l=tem p;exch ang e=t

27、r ue;)i f(!exch ang e)(r etur n;i nt m ai n()(i nt a 7=32,43,22,52,2,10,30);m ao p ao(a,7);fo r(i nt i=0;i 7;i+)co ut a i z/r etur n 0;)s h el l 排序的思想是根据步长由长到短分组，进行排序，直到步长为1 为止，属于插入排序的一种。下面用个例子更好的理解一下无序数列：32,4 3,5 6,99,34,8,5 4,7 6 1.首先设定g ap=n/2=4 于是分组32,34 排 序 32,34 4 3,8 8,4 3 5 6,5 4 5 4,5 6 99,

28、7 6 7 6,99 数列变成 32,8,5 4,7 6,34,4 3,5 6,99 2.g ap=g ap/2=2 于是分组 32,5 4,34,5 6 排序 32,34,5 4,5 6 8,7 6,4 3,998,4 3,7 6,99 于是数列变成 32,8,34,4 3,5 4,7 6,5 6,99 3.g ap=g ap/2=l 于是分组 32,8,34,4 3,5 4,7 6,5 6,99 排序 8,32,34,4 3,5 4,5 6,7 6,99 g ap=l 结束 相应的 C语言代码引用K&R C程序设计一书中给出的代码v o i d s h e lls o r t(i n t

29、v,i n t n)i n t g ap,i,j,te mp;f o r (g ap=n/2;g ap 0;g ap/=2)/设定步长 f o r(i=g ap;i =O&v j v j+g ap ;j-=g ap)比较相距g ap 的元素，逆序互换 te mp=v j;v j=v j+g ap;v j+g ap=te mp;帕斯卡恒等式为 C(n,k)=C(n T,kT)+C(n T,k)lo n g f u n(lo n g n,lo n g r)(i f(r 0|n n)r e tu r n 0;i f (r=l|r=n T)根据组合定义，我们有 C(n,l)=C(n,n-l)=nr e

30、 tu r n n;i f (r=0|r=n)根据组合定义，我们有 C(n,0)=C(n,n)=lr e tu r n 1;r e tu r n f u n (n-1,r)+f u n(n-1,r T);帕斯卡组合公式选择法对数组排序的函数模板te mp late v o i d s e le cts o r t(T ar r,i n t s i z e)(T te mp;i n t i,j;f o r (i=0;i s i z e-l;i+)f o r (j=i+l;j ar r j j)(te mp二ar r i;ar r i=ar r j;ar r j=te mp;)/冒泡法对数组排序的

31、函数模板te mp late v o i d bu bble s o r t(T*d,i n t n)(i n t i,j;T t;f o r(1=0;i n-l;i+)f o r(j=0;j d j+l)t=d j;d j=d j+l;d j+l=t;)插入法对数组排序的函数模板te mp late v o i d I n s e r tSo r t(T A,i n t n)(i n t i,j;T te mp;f o r (i =1;i =0&te mp A j;j)Aj+l=Aj;Aj+1 =temp;)二分查找法的函数模板template int binary_search(T arr

32、ay,T value,int size)(int high=size-1,low=0,mid;while(low=high)(mid=(high+low)/2;if(value arraymid)low=mid+1;else return mid;)return-1;)将 2、36进制数与1 0进制数相互转换 将 2 36进制数转换成1 0进制数unsigned int OthToDec(char*oth,int base)base 为已知数的进制(unsigned int i=0,dec=0;while(othi)(dec*二 base;if(othi=0，&othi二 9)dec+=oth

33、i&1 5;/dec+=othi-48;else if(othi=A&othi=，a，&othi=，z)dec+=othi-87;i+；)return dec;)将 1 0进制(无符号)转2 36进制数char*DecToOth(char*oth,unsigned int dec,int base)/base 为要转换的数的进制ch ar ch,*le f t=o th,*r i g h t=o th,n u m=，/01234 5 6 7 8 9A B C D EFGH I J K L M N0PQRSTUVWXYZ/;d o*r i g h t=n u md e c%bas e;r i g

34、 h t+;w h i le (d e c/=bas e);*r i g h t=，0，;r i g h t;w h i le (le f tr i g h t)(ch=*le f t;*le f t=*r i g h t;*r i g h t=ch;le f t+;r i g h t一；)r e tu r n o th;)统计s u bs tr在s tr中的个数i n t f u n(ch ar *s tr,ch ar *s u bs tr)(i n t n=0;ch ar *q;q=s u bs tr;w h i le(*s tr!=，0J)(i f(*s tr二 二*s u bs tr)

35、(s tr+;s u bs tr+;i f(*s u bs tr=，0)n+;s u bs tr=q;)e ls e(s tr+;s u bs tr=q;)r e tu r n n;使用数组实现约瑟夫环：tti n clu d e#i n clu d e mai n()(i n t m,n,i=l,j,k=l,p e r,o;p r i n tf (请输入总共的人数，记为n n);s can f(/d，&n);i n t ar r ay n+1;i n t o r d e r n+1;p r i n tf (请输入几号出圈，记为m n)；s can f(%d，&m);p r i n tf(n*

36、n);f o r(;i n;i+)数组链表模拟ar r ay i=i+l;ar r ay n=l;p r i n tf(%d ,ar r ay n);i=l;j=l;p e r=n;w h i le(ar r ay i!=i)i f(k=m)o r d e r j=i;j+；ar r ay p e r=ar r ay i;k=0;f o r (o=l;o =j;o+)p r i n tf(%d*”,o r d e r o);)e ls e p r i n tf (，z%d ”,ar r ay i);p e r=i;i二ar r ay i;k+;)o r d e r n=i;p r i n tf

37、 (n*n);f o r(i=l;i =n;i+)p r i n tf(%d ，o r d e r i);s y s te m(/zp au s e，z);r e tu r n 0;输入正整数N,然后是N*N个正整数，表示边权邻接矩阵。输出求解过程。/*Pr o ble m:We i g h te d B i p ar ti te M atch i n gA lg o r i th m:H u n g ar i an A lg o r i th mRe f e r e n ce :D o u g las B.We s t,I n tr o d u cti o n to Gr ap hA u t

38、h o r :PCD ate :2005.2.23*/#i n clu d e#i n clu d e#i n clu d e#i n clu d e me mo r y.h i f s tr e ar n f i n(i n p u t.tx t)；#d e f i n e ci n f i nco n s t i n t max 二 5 0;bo o l Tmax,Rmax,v i s i te d max;i n t U max,V max,g t max max,x max,y max;i n t N;v o i d o u tp u t()(i n t i,j;f o r (i=0;

39、i N;i+)(f o r(j=0;j N;j+)(co u t s e tw(2)g ti j，;i f (Ri)co u t s e tw(2)，Rf);co u t e n d l;)f o r(i=0;i N;i+)i f (Ti)co u t s e tw(2)，V J;e ls e co u t s e tw(2)；co u te n d l;)Th e o r y,125-129i n t p ath(i n t u)int v;for(v=0;vN;v+)if(gtuv=0&!visitedv)(visitedv=l;if(yv0 path(yv)(xu=v;yv=u;Ru=l

40、;Tv=0;return 1;e lseTv=l;Ryv=0;)return 0;int main 0(for(;cinN;)int i,j,ans,sigma,step=0;for(i=0;iN;i+)(Ui=Vi=0;for(j=0;jN;j+)(c in g ti j ;if(Uigti j)U i=gti j ;)for(i=0;iN;i+)(for(j=0;jN;j+)(g tij=U i-g tij;/fo r(;)an s=O;s i g ma=O;me ms e t(x,-1,s i z e o f(x);me ms e t(y,-1,s i z e o f(y);me ms

41、e t(R,0,s i z e o f(R);me ms e t(T,0,s i z e o f(T);f o r(i=0;i N;i+)(i f(x i 0)(me ms e t(v i s i te d,0,s i z e o f(v i s i te d);an s+=p ath(i);)f o r(j=0;j N;j+)(i f(s i g ma g ti j&g ti j 0)s i g ma=g ti j;)co u tz，s te p z,+s te p =N)br e ak;f o r(i=0;i N;i+)(i f(!Ri)Ui-=s i g ma;i f(Ti)Vi+=s

42、i g ma;f o r(j=0;j N;j+)(i f(Tj)g ti j+=s i g ma;i f(!Ri)g ti j-=s i g ma;)/an s=0;cout，Result:，endl;for(i=0;iN;i+)ans+=Ui+Vi;for(j=0;jN;j+)(if(xi=j&y j=i)coutsetw(2)Ui+Vj,else coutsetw(2)0J ;)coutendl;cout，zMaximum:，ansendl;)return 0;)input,txt:54 1 6 2 35 0 3 7 62 3 4 5 83 4 6 3 44 6 5 8 654 4 4 3

43、 6114 3 41 4 5 3 55 6 4 7 95 3 6 8 357 8 9 8 78 7 6 7 69 6 5 4 68 5 7 6 47 6 5 5 551 2 3 4 56 7 8 7 21 3 4 4 53 6 2 8 74 1 3 5 4/*Pr o ble m:We i g h te d B i p ar ti te M atch i n gA lg o r i th m:H u n g ar i an A lg o r i th mRe f e r e n ce :D o u g las B.We s t,I n tr o d u cti o n to Gr ap h T

44、h e o r y,125-129A u th o r :PCD ate :2005.2.23*/#i n clu d e#i n clu d e#i n clu d e#i n clu d e i f s tr e am f i n(i n p u t.tx t);#d e f i n e ci n f i nco n s t i n t max=5 0;bo o l Tmax,Rmax,v i s i te d max;i n t Umax,Vmax,g tmax max,x max,y max;i n t N;v o i d o u tp u t()(i n t i,j;f o r (i

45、=0;i N;i+)(f o r(j=0;j N;j+)(co u t s e tw(2)g ti j,;)i f (Ri)co u t s e tw(2),R ;co u te n d l;f o r(i=0;i N;i+)i f (Ti)co u t s e tw(2),T*?;e ls e co u t s e tw(2);co u te n d l;)i n t p ath(i n t u)i n t v;f o r(v=0;v N;v+)if(Uu+Vv-gtuv=0&!visitedv)(visitedv=l;if(yv0|path(yv)(xu=v;yv=u;Ru=l;Tv=O;

46、return 1;else Tv=l;Ryv=O；)return 0;int main()(int i,j,ans,sigma,step=0;for(;cinN;)for(i=0;iN;i+)(Ui=Vi=0;for(j=0;jN;j+)(cingti j;if(Uigtij)Ui=gtij：)/for(;)(ans=0;sigma=0;memset(x,-1,sizeof(x);memset(y,-1,sizeof(y);memset(R,0,sizeof(R);memset(T,0,sizeof(T);for(i=0;iN;i+)if(xi0)memset(visited,0,sizeof

47、(visited);ans+=path(i);)for(i=0;iN;i+)(if(!Ri)for(j=0;jN;j+)(if(!TjJ&(sigmaUi+Vj-gtij&Ui+Vj-gtij0)sigma=Ui+Vj-gtij;)cout*step”+step:n”;output();if(ans=N)break;for(i=0;iN;i+)(if(!Ri)Ui-=sigma;if(Ti)Vi+=sigma;)/ans=0;coutz，Result:vendl;for(i=0;iN;i+)(ans+=Ui+Vxi：for(j=0;j;else coutsetw(2)0);cout src)考

48、虑覆盖情况 d=(char*)dst+len-1;s=(char*)src+len-1;while(len=4)循环展开，提高执行效率*d-=*s-;*d-=*s-;*d-=*s-;*d-=*s-;len _=4;while(len一)*d=*s-;else if(dst=4)*d+=*s+;*d+=*s+;*d+=*s+;*d+=*s+;len _=4;while(len一)*d+=*s+;return dst;出现次数相当频繁1.常用的算法设计方法：L 1 迭代法 1.2穷举搜索法 1.3递推法 1.4递归法 1.5贪婪法 1.6分治法 1.7动态规划法 1.8回溯法算法基础部分：算法是对

49、特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下5 个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：-个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。所以对应的算法设计的要求：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性

50、：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。般这两者与问题的规模有关。L 1迭代法：迭代法是用于求方程或方程组近似根的一 种 常 用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行：(1)选一个方程的近似根，赋给变量x0；(2)将 x0的值保存于变量x l,然后计算g(xl),并将结果存于变量xO；(3)当 xO与 xl的差的绝对值还小于指定的精度要求时，重复步骤(2)的计算。若方程有根，并且用上述方法计算