öλÔÓéÀֵǼÈë¿ÚÏÂÔØ

2005Äê±±¾©½»Í¨´óѧ¼ÆËã»úöλÔÓéÀֵǼÈë¿ÚÏÂÔØöλÔÓéÀÖ¹Ù·½appÏÂÔظ¨µ¼°à±Ê¼Ç
        £¨05ÄêÓкöàÄÚÈݺÍ04ÄêÒ»Ñù£¬04ÄêÓв»Í¬ÎÒ»áÌرðÓÃÀ¶É«×¢Ã÷£©
µÚÒ»Õ£º¸ÅÂÛ£¨05Ä꣩
1. ÉèÓÐÁ½¸öËã·¨ÔÚͬһ»úÆ÷ÉÏÔËÐУ¬ÆäÖ´ÐÐʱ¼ä·Ö±ðΪ100*n**2ºÍ2**n£¬ÒªÊÇÇ°Õß¿ìÓÚºóÕߣ¬nÖÁÉÙÒª¶à´ó£¿
        Çó²»µÈʽ 100n**2<2**n,  n>=15
2. Ëã·¨µÄʱ¼ä¸´ÔӶȽöÓëÎÊÌâµÄ¹æÄ£Ïà¹ØÂð£¿
ÊÂʵÉÏ£¬Ê±¼ä¸´ÔӶȲ»½öÓëÎÊÌâµÄ¹æÄ£ÓйØ£¬»¹ÓëÎÊÌâµÄ³õʼ״̬Ïà¹Ø£¬ÈçÆðÅÝÅÅÐòÀïʱ¼ä¸´ÔӶȾÍÓëÅÅÐòµÄ³õʼ״̬ÓйØ¡£
3. ÈôËùÐè¶îÍâ¿Õ¼äÏà¶ÔÓÚÊäÈëÊý¾ÝÁ¿Êdz£Êý£¬Ôò³ÆË㷨ΪԭµØ¹¤×÷£¡£¨ÕÆÎÕ¸ÅÄ
ÓпÉÄܳöÕâÑùµÄÌ⣺¸øÄã¸öËã·¨ÈÃÄãÅжÏËüÊÇ·ñÊÇÔ­µØ¹¤×÷¡£ È磺¼òµ¥ÅÅÐò£¬ÆðÅÝÅÅÐòµÈ£¡
   ×ܽ᣺µÚÒ»Õ¿¼µÄÄÚÈݲ»¶à£¬Ö÷ÒªÊǸ´ÔÓ¶ÈÎÊÌâ
¸ÅÂÛ£¨04Ä꣩
   Ç¿µ÷µÄÄÚÈݺÍ05Äê²î²»¶à£¬µ«×ÅÖؽ²ÁËËã·¨¸´ÔӶȵļÆËã¡£ÈçÏ£º
1. £¨1£©x=0; y=0;  1´Î
(2)  for (k=1;k<=n;k++)   n+1´Î
(3)  x++;                n´Î
(4) for(k=1;k<=n;k++)  n+1´Î
(5)  for(j=1;j<=n; j++)  n(n+1)´Î
(6)    y++            n**2´Î
   2.  x=1                    1´Î
for(k=1;k<=n;k++)        n+1 ´Î
  for(j=1;j<=i; j++)     ¡Æ(i+1) (ÇóºÍÏÂÏÞi=1,ÉÏÏÞn+1)
    for(k=1; k<==j;k++)
      x++;            ¡Æ¡Æj(µÚÒ»¸öÇóºÍÏÂÏÞi=1,ÉÏÏÞn£»µÚ¶þ¸öÇóºÍÏÂÏÞj=1,ÉÏÏÞΪi )
                    =¡Æ(i+1)/2 (ÇóºÍÏÂÏÞi=1,ÉÏÏÞ n)
                    =(n(n+1)(2n+1))/12+(n(n+1))/4
3.¼òµ¥Ñ¡ÔñÅÅÐòºÍÆðÅÝÅÅÐòµÄ±È½Ï´ÎÊý
µÚ¶þÕ£º ÏßÐÔ±í£¨05Ä꣩
1. ÊìϤÏßÐÔ±íµÄÂß¼­½á¹¹¼°ÆäÐÔÖÊ£¨ÊéÉÏÓУ©
2. Àí½â²åÈ룬ɾ³ý£¬¶¨Î»ÕâÈý¸öËã·¨¼°¹ý³Ì£¨Ë³Ðò±í£¬¸÷ÖÖÁ´±íÓ¦ÊìϤ£©
3. Ñ­»·Á´±íµÄÓ÷¨£¨Ô¼Éª·ò»·£¬ºï×ÓÑ¡´óÍõ£¨²Î¿´04ÄêÌî³ÌÐòµÚ¶þÌ⣩×Ô¼º±àһϳÌÐò£©
4. Ë«ÏòÑ­»·Á´±íÅпգ¨head->next=head»ò head->pre=head ´øÍ·½áµã£©£¬ÅÐÂúµÄÌõ¼þ
ÒÔ¼°ËüµÄ²åÈëºÍɾ³ý½áµãµÄ²Ù×÷¡£
   5£®ÔÚ˳Ðò±íÖвåÈë»òɾ³ýÒ»¸ö½áµãÐèƽ¾ùÒƶ¯¶àÉÙ¸ö½áµã£¿¾ßÌåµÄÒƶ¯´ÎÊýÈ¡¾öÓÚÄÄÁ½¸öÒòËØ£¿
      ´ð£º²Î¿´ÊéP25
          È¡¾öÓÚ˳Ðò±íµÄ³¤¶Èn£¬ºÍÐèÒª²åÈëºÍɾ³ýµÄλÖÃi (iÔ½½Ó½ünÐèÒªÒƶ¯µÄ½áµãÔ½ÉÙ)
5. ÎªÊ²Ã´ÔÚµ¥Ñ­»·Á´±íÖÐÉèβָÕë±ÈÉèÍ·Ö¸ÕëºÃ£¿
´ð£ºÓÃβָÕë¿ÉÒÔʹµÃ²éÕÒÁ´±íµÄ¿ªÊ¼½áµãºÍÖն˽áµã¶¼ºÜ·½±ã¡£ÉèÒ»´øÍ·½áµãµÄµ¥Ñ­»·Á´±í£¬ÆäβָÕëΪ rear Ôò¿ªÊ¼½áµãºÍÖն˽áµãµÄλÖ÷ֱðrear->next->next ºÍ rear.²éÕÒʱ¼ä¶¼ÊÇO(1). ÈôÓÃÍ·½áµã±íʾÔò²éÕÒÖն˽áµãµÄʱ¼äÊÇO(n);
6. ÔÚµ¥Á´±í£¬Ë«Á´±íºÍµ¥Ñ­»·Á´±íÖУ¬ÈôÖ»ÖªµÀÖ¸ÕëpÖ¸Ïòij½áµã£¬²»ÖªµÀÍ·Ö¸Õ룬ÄÜ·ñ½«½áµã*p´ÓÖÐɾ³ý£¿
´ð£º µ¥Á´±í      ²»ÐÐ
Ë«Á´±í      ¿ÉÒÔ O(1)
µ¥Ñ­»·      ¿ÉÒÔO(n) ´Óp¿ªÊ¼Íùºó£¬×Ü¿ÉÒÔÕÒµ½pÇ°ÃæµÄÒ»¸ö½áµã¡£
7. ÏÂÊöËã·¨µÄ¹¦ÄÜÊÇʲô£¿
Linklist Demo(linklist L)
 {  //LÊÇÍ·½áµã
   listNode  *q, *p;
   if (L&&L->next)  //±£Ö¤ÓÐÁ½¸ö½áµã
{ q=L; L=L->next; p=L;
  while (p->next) p=p->next;
  p->next=q; q->next=Null;
}   return L;
}//¸Ã³ÌÐòÊǰѵÚÒ»¸ö½áµãŲµ½×îºó£¬µÚ¶þ¸ö½áµã±äΪµÚÒ»£¬·µ»ØµÄLΪÐÂÁ´±íµÄÍ·Ö¸Õë
´ð£ºÈôLÖ¸ÏòµÄµ¥Á´±íÖÁÉÙÓÐÁ½¸ö½áµã£¬½«µÚÒ»¸ö½áµãÒƵ½Öն˽áµãÖ®ºó³ÉΪеÄÖն˽áµã¡£¶øLÖ¸ÏòÔ­À´µÄµÚ¶þ¸ö½áµã£¬Ê¹Æä³ÉΪеĿªÊ¼½áµã£¬²¢·µ»ØÐÂÁ´±íµÄÍ·Ö¸Õ룻·ñÔòÖ±½Ó·µ»ØLÖµ²»×÷Èκα䶯
   £¨ÀÏʦǿµ÷ÁËÔÚ×öÔĶÁ³ÌÐòµÄÌâĿʱ£¬Ò»¶¨Òª°ÑÆäÃèдµÃ¾ßÌåЩ£¬ÕâÑù²ÅÄܱ£Ö¤¶àÄ÷֣©
8. ÊÔ·Ö±ðÓÃ˳Ðò±íºÍµ¥Á´±í×÷Ϊ´æ´¢½á¹¹£¬Ð´³ÌÐò¶ÔÆä¾ÍµØÄæÖã¬ÒªÇó¸¨Öú¿Õ¼äΪO(1).
9. Ë³Ðò±íLÊǵÝÔö£¨»òµÝ¼õ£©ÓÐÐò±í£¬½«x²åÈëºó£¬Ê¹ÆäÈÔÈ»ÓÐÐò¡£
10. ÒÑÖªL1,L2·Ö±ðÖ¸ÏòÁ½¸öµ¥Á´±íµÄÍ·½áµã£¬ÊÔдһËã·¨½«Á½¸öÁ´±íÁ¬½ÓÔÚÒ»Æ𣬲¢·ÖÎöËã·¨µÄʱ¼ä¸´ÔӶȣ¨min(m,n)¶ÌµÄ·ÅÇ°Ã棬 °ÑµÚ¶þ¸öÁ´±íµÄÍ·½áµãÈ¥µô¡£´Ó¶ÌµÄÍ·½áµã¿ªÊ¼Ò»Ö±ÕÒµ½Î²²¿£¬²¢ÈÃβ½áµãÖ¸Ïò³¤Á´±í£¨last->next=L2->next£©£©
11. Éè A,BÁ½¸öµ¥Á´±í£¬Æä±íÖÐÔªËصÝÔöÓÐÐò¡£ÊÔдһËã·¨½«A,B¹é²¢³ÉÒ»¸öµÝ¼õµÄC£¬ÒªÇó¸¨Öú¿Õ¼äΪO(1),²¢Çóʱ¼ä¸´ÔÓ¶È £¨²Î¿´P21£©
12. Ô¼Éª·ò»·Ó¦ÓÃ
   ÒÔÉÏÌâÄ¿Ï£Íû´ó¼ÒÄÜ×Ô¼º¶¯ÊÖ×ö×ö
µÚÈýÕ ջºÍ¶ÓÁÐ(05Äê)
1. Õ»ºÍ¶ÓÁУºÊÜÏÞµÄÏßÐÔ±í¡£
Ò»°ãµÄÏßÐÔ±íÓУº ²åÈëµãn+1¸ö£¬É¾³ýµãn¸ö
Õ»£¬¶ÓÁУº       ²åÈëµã1¸ö£¬  ɾ³ýµã1¸ö
2. ÈëÕ»£¬³öÕ»£¬Èë¶Ó£¬É¾³ý¶ÓÍ·µÄ²Ù×÷¾ùÓ¦ÕÆÎÕ£¨°üÀ¨Ëã·¨£©
3. ÕÆÎÕÑ­»·¶ÓÁÐ
4. ÀýÌâ P48 ÊýÖÆת»»
5. À¨ºÅÆ¥Åä  ÖªµÀÊÇÔõô»ØʾÍÐÐ
6. ÃÔ¹¬Çó½â  ¼ÒôÀïÓÐÀÏʦÏêϸ½²½â
7. »ØÎÄÓÎÏ·  ˳¶ÁÓëÄæ¶Á×Ö·û´®Ò»Ñù£¨²»º¬¿Õ¸ñ£©
£¨1£© ¶ÁÈë×Ö·û´®  £¨2£©È¥¿Õ¸ñ  £¨3£© ѹÈëÕ»  £¨4£©ÒÀ´Î³öÕ»ÓëÔ­×Ö·û´®±È½Ï
 Èô²»µÈÔò·Ç»ØÎÄ£¬ÈôÖ±µ½Õ»¿Õ¶¼ÏàµÈÔòΪ»ØÎÄ¡£
      ¿¼ÂÇÁíÒ»ÖÖ·½·¨£ºÈô×Ö·û´®µÄ³¤¶ÈΪÆæÊý£¬Ôò²»Ðè±È½ÏΪ·Ç»ØÎÄ¡£·ñÔò¿ÉÏȶÁÈëÒ»°ë×Ö·ûÈëÕ»£¬È»ºóÒÀ´Î³öÕ»ºÍʣϵÄ×Ö·û±È½Ï£¡×Ô¼º¿ÉÓÃÕâÖÖ·½·¨±àдһÏ¡£
8. µØͼËÄȾɫÎÊÌ⣨δ¿¼¹ý£©
ʹµØͼÖÐÏàÁڵIJ»ÖØÉ«£¬×îÉÙÓÃ4ÖÖÑÕÉ«¿ÉÒÔʵÏÖ¡£ÀûÓÃÕ»»ØËÝ¡£
ÉèÒ»¸öÁÚ½Ó¾ØÕóR[][]£¬Ö÷¶Ô½ÇÏßÉϵÄÔªËؾùΪÁã¡£ÆäÓÚÔªËØÈçR1,3, Èç¹ûµÚÒ»¸öÇøÓòºÍµÚÈý¸öÇøÓòÏàÁڵĻ°ÔòR1,3Ϊ1£¬·ñÔòΪ0¡£ÔÙʹÓÃÒ»¸ö¹¤×÷Êý×éS[]ÓÃÀ´´æ·ÅÒÑÌîÉ«ÇøÓòµÄºÅÂë¡£
Void  mapcolor (int R[][], int n, int S[])  // n±íʾµØͼ¹²ÓÐn¸öÇø
  { S[1]=1;  //1 ºÅÇøÌî1ºÅÉ«
a=2;j=1;  //aΪÇøºÅ£¬jΪɫºÅ
while (a<=n)  //a>n±íʾÌîÉ«Íê³É
  { while ((j<=4)&&(a<=n))
        { k=1;     //k±íʾÒÑÌîÉ«µÄÇøÓò
          while ((k<a)&&(s[k]*R[a-1][k-1]!=j))  k=k+1;
            //Èô²»ÁÚ£¬»òÏàÁÚÇÒ²»ÖØÉ«£¬¶ÔÏÂÒ»¸öÇø½øÐÐÅжÏ
           if (k<a) j=j+1;  //ÏàÁÚÇÒÖØÉ«£¬É«ºÅ¼Ó1
           else { s[a]=j; a=a+1; j=1;} //ÏàÁÚ²»ÖØÉ«£¬ÓÖ´Ó1ºÅÇø×ÅÉ«
        }
     if (j>4) { a=a-1; j=s[a]+1;} //¶Ôµ±Ç°Ðè×ÅÉ«ÇøÓòa À´Ëµ£¬1-4ÖÖÑÕÉ«¶¼²»ÐУ¬Ôò˵Ã÷ÉÏÒ»¸ö´íÁË£¬¶ÔÉÏÒ»¸ö½øÐÐÖØÌî
         }
9. ËĻʺóÎÊÌâ
#include<stdio.h>
#define  n  4   // nÊǻʺóµÄ¸öÊý
int m=0, a[n]; //a[i]´æ·ÅµÚi ¸ö»Êºó·ÅÖõÄÐкŠ
int ok(int i, int j)   //¼ì²é(i,j)ÄÜ·ñ·ÅÆå×Ó
 { int j1, i1,ok1;
   j1=j; i1=i; ok1=1;
   while ((j1>1)&&ok1)  {j1--;  ok1=a[j1]!i;} //²é×ó±ßÄÇÁиÃÐÐÊÇ·ñÓлʺó
   j1=j; i1=i;  //¼ì²é¶Ô½ÇÏßÉÏÄÜ·ñ·Å
   while((j1>1)&&(i1>1)&&ok1)   {j1--;  i1--; ok1=a[j1]!i1 ;}
   j1=j; i1=i; //¼ì²éÁíÒ»¶Ô½ÇÏßÄÜ·ñ·Å
          while ((j1>1)&&(i1<n)&&ok1)   {j1--;  i1++; ok1=a[j1]!i1 ;}
          return  ok1;
         }
        void  queen(int j) //´ÓµÚjÁпªÊ¼ÊÔ̽
          {  int i;
if (j>n) //·ÅÍêÁË£¬´òÓ¡°Ú·¨¼ÆÊý
  { m++;  printf(¡°m=%d   ¡°, m);