zj:97-北縣賽-D227, D231~D233

第1題d227. 97北縣賽-1-正弦三角函數

// 本題 ZJ上輸入的角度 -900 ~ 900 不需轉成較小的同界角，但可當練習

#include <iostream>

#include<iomanip>

#include<cmath>

using namespace std;

int main( )

{

   int a , s;

   double pi180 = 3.1415926 / 180;

   double f , p , x , pdf ;

   double limit = 0.01;

   while( cin >> a )

   {

//   a 縮約 ==> a=(a+1080) % 360 ; a>180=>sin為負 ,  sin(a) = sin(90-abs(a-90)%90)

//   a=(a+1080) % 360 ; 

//   bool sgn=(a>180);

//   a=90-abs(a-90)%90;     

//    本題 d227 不需縮約 a 值 

      x = a * pi180 ;

      f = 1.0;     // k!

      p = x;     // x^k;

      s = 1;     // * 1 或 * -1

      double sin = 0.0;

      int k;

      for(k = 1 ;  ; k += 2 )

      {

         pdf =  p / f;    // x^k / k!         

         sin += ( s * pdf );

 //  cout << k << ":" <<p <<"/" << f << "=" << pdf <<"sin="<<sin<<endl; 

         if ( abs(pdf) <= 0.01 ) break;

         p = p * x * x ;

         f = f * ( k+1) * (k+2) ;

         s = -s;

      }

      cout << "N = " << k << endl;

//      cout << (sgn?"-":"");   有縮約  a 值 才需 加印  負號 

      cout << fixed << setprecision(6) << sin << endl;

   }

    return 0 ; 

}

第2題d231. 97北縣賽-2-基因序列密碼問題

// 參考 gj d003 "99年台中區複賽第三題"    LCS  

#include <iostream>  

using namespace std;  

int main( )  

{  

   int i,j, m,n,t;  

   string x,y,z;  

   while ( cin >> x >> y )  

   {  

      m = x.size();  

      n = y.size();  

      int b[m+1][n+1] , c[m+1][n+1];  

      for(i=0; i<=m; ++i ) c[i][0]=0;  

      for(j=0; j<=n; ++j ) c[0][j]=0;  

   // 開始由 c[1][1]開始設定，至c[m][n]即為 LCS 長度  

   // 由b[m][n]往回找若 b[i][j]==0 印出 { 0左上、1上、2左 }   

      for(i=1; i<=m; ++i )  

      {   

         for(j=1; j<=n; ++j )  

         {  

            if(x[i-1]==y[j-1])   // 字串從 0 開始   

              { c[i][j]=c[i-1][j-1]+1 ;  b[i][j]=0; }   // 左上   

            else if(c[i-1][j]<c[i][j-1]) 

              { c[i][j]=c[i][j-1] ;  b[i][j]=2; }       // 左  

            else   { c[i][j]=c[i-1][j] ;  b[i][j]=1; }  // 上  

         }              

      }  

   // 印出 LCS  

    //  cout << x << " " << y << " = ";   

      if( c[m][n]==0 ) { cout << "E" << endl; continue; }  

      i=m; j=n;  z="";  

      while ( i && j )  

      {  

         if( b[i][j]==1) --i;  

         else if( b[i][j]==2) --j;  

         else if( b[i][j]==0 )  

         {  

            --i; --j;  

            z = x[i] + z;  

         }  

      }  

      cout << z <<endl;  

   }  

   return 0 ;   

}

第3題d232. 97北縣賽-3-資料統計問題

/*

d232  97-北縣賽-3-資料統計問題 

*/

#include <iostream>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

struct ntyp

{

   string nam;   // 姓名

   int psum;         // 購書總額

   int age;          // 年齡 

}  cus[101];

bool cmp(ntyp a, ntyp b)

{

   if( a.psum == b.psum )

      return (a.nam<b.nam);

   else return (a.psum>b.psum);

}

int main( )

{

   int t , i , j , cnt , ci ;

   string nam;

   char sex , typ;

   int age, pay;

   int tsum[5];  // A~E 五類的 總銷售金額

   int sta[10][10];  // 金額10級、年齡10級

   map <string , int> mp;

   while( cin >>t )   // 筆數 t 

   {

      memset ( tsum , 0 , sizeof(tsum) );

      memset ( sta , 0 , sizeof(sta) );

      mp.clear();

      for(cnt=0 , i=0 ; i<t ; ++i)

      {

         cin >> nam >> sex >> typ >> age >> pay;

         tsum[typ-65] += pay;    // 某類書 + 購買金額 

         if( mp.count(nam) ) // 已出現過，取 ci

         { 

            ci = mp[nam];

            cus[ci].psum += pay;

         }

         else  // mp 內沒有，新 ci=c++; 

         {

            mp[nam] = cnt;  ci = cnt++ ;

            cus[ci].nam = nam;

            cus[ci].age = age;

            cus[ci].psum = pay;

         }

      }

      sort(cus, cus+cnt , cmp);   // 自訂比較函式 cmp

// 依金額、年齡 分類統計

      for( i=0; i<cnt ; ++i )

      {

         sta[ (cus[i].psum-1)/1000 ][ (cus[i].age-1)/10 ] += 1;         

      } 

      int mx=tsum[0] , mi=0;

      for(i=1; i<5; ++i)

         if(tsum[i]>mx) { mx=tsum[i] ; mi=i ; } 

      cout << char( mi+65 ) << endl;

      for( i=0; i<10; ++i )

      {

         cout << sta[i][0] ;

         for( j=1; j<10; ++j)

            cout <<" "<< sta[i][j];

         cout << endl;

      }

      for ( i=0 ; i<cnt && i<5 ; ++i )

         cout << cus[i].nam << " " << cus[i].psum <<endl;

      // 與第5名 金額同的都要印

      for (  ; i<cnt && cus[i].psum==cus[i-1].psum ; ++i )

         cout << cus[i].nam << " " << cus[i].psum <<endl;

   }

   return 0 ; 

}

第4題d233. 97北縣賽-4-金幣問題

// 作法:DFS  搜尋的終止條件很重要

#include <iostream>

#include <cstring>

using namespace std;

int mp[256][256];

int mt [256];

int fg [256];

int mx = 0 , n ;

void DFS(int now,int time)

{  

   int i,find=0;

   if( time > mx )  mx = time;

     if( now > n || ( (n-now+1)/2 + time + 2 ) <= mx ) return;

   for(i=0 ; i < mt[now] ; ++i)

      if( fg[ mp[now][i] ] == 1 )

         {find=1;break;}

   if(find==0)

   {

      fg[now]=1;

      DFS(now+1,time+1);

      fg[now]=0;

   } 

   DFS(now+1,time);

}

main()

{

   int  x , y;

   cin >> n;

   int  wy[n];

   memset ( mp , 0 , sizeof(mp) );

   memset ( mt , 0 , sizeof(mt) );

   memset ( fg , 0 , sizeof(fg) );

   while( cin >> x , x)  // x==0 結束 

   {

       cin >> y;

       mp[x][ mt[x] ]=y;

       ++ mt[x] ;

       mp[y][ mt[y] ] = x;

       ++ mt[y] ;

   } 

   mx=0;

   DFS(1,0);    

   cout << mx << endl;

   return 0;

}