2014年10月30日 星期四
2014年9月13日 星期六
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;
}
zj:94-北縣賽-D249~D252
第1題d249: 94北縣賽-1-心意相通的指數(Match)
以下程式碼在 ZJ 沒有 AC ，只有60分
討論區有人說測資與題意不符
http://zerojudge.tw/ShowThread?postid=2568&reply=2567#2568
測資解的順序不是像題目所說的任意解皆可。
當LCS的dp[a-1][b] == dp[a][b-1]時要取dp[a][b-1]，
這樣解的順序才會跟測資一樣，
另有morris的 AC 請查 下列網址
http://mypaper.pchome.com.tw/zerojudge/post/1322395974
我覺得我以下的小珠部份旋轉方向改一下、取dp[a][b-1]部份改一下應可以過，但還沒仔細試
下週再補
#include <iostream>
#include <sstream>
#include <iomanip>
#include<cstring>
using namespace std;
string LCS( string x , string y )
{
string z;
int i,j, m,n,t;
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 字串 z
// cout << x << " " << y << " = ";
i=m; j=n; z="";
if( c[m][n]==0 ) return z; //{ cout << 0 << endl; continue; }
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;
}
}
return z;
}
int main( )
{
string a , a2 , b , c , d , e;
int an , abn , m , i;
cin >> a >> b; // 讀兩字串 ，求 LCS
an = a.size(); // 串成環的長度
a2 = a + a.substr(0,an-1);
abn = an + b.size();
for ( m=0 , i=0; i<an; ++i)
{
c = a2.substr( i , an ); // a2 循環 取 a 長度
d = LCS( c , b ); // 找出 c , b 的 lcs 字串傳回 d;
if( d.size() > m )
{
m = d.size();
e = d;
}
}
if ( m==0 ) cout << "no" << endl;
else
{ cout << e << endl;
cout << fixed << setprecision(2) << 2.0*m / abn << endl;
}
return 0 ;
}
第2題d250: 94北縣賽-2-數獨問題 (Sudoku)
#include <iostream>
using namespace std;
int main( )
{
string s;
bool m[10];
int i;
while(cin>>s) {
bool m[10]={false};
for(i=0;i<9;i++) if(s[i]) m[s[i]-'0']=true;
for(i=1;i<=9;i++) if( !m[i] ) cout<<i<<endl;
}
return 0 ;
}
第3題d251: 94北縣賽-3-羅馬數字 (Roman)
#include <iostream>
using namespace std;
// ----------------------------------------
string rtb="IVXLCDM";
int ntb[]={1,5,10,50,100,500,1000};
int rton(string s) // 羅馬字串轉數字
{
int i,j,n=s.size();
int v1,v2,sum=0;
for (i=0;i<n;i++) {
j=i+1;
v1= ntb[rtb.find(s[i])];
sum+=v1;
if(j>=n) return sum;
else {
v2= ntb[rtb.find(s[j])];
if(v1<v2) { sum+=(v2-v1-v1); i++; }
}
}
return sum;
}
// -------------------------------------------
string r,ms[]={"IV","IX","XL","XC","CD","CM"};
int m[]={4,9,40,90,400,900};
string ntor(int n) // 數字轉羅馬字串
{
int ti;
//千
r="";
while(n>=1000) {r+='M'; n-=1000; }
for(ti=5;ti>=0;ti--) {
if(n>=m[ti]) { r+=ms[ti]; n-=m[ti]; }
while(n>=ntb[ti]) { r+=rtb[ti]; n-=ntb[ti]; }
}
return r;
}
// -------------------------------------------
int b2t(int m)
{
return (m+450)%1440; //部落總分鐘數+7小時30分的總分鐘數
}
// ----------------------------------------------------
int main( )
{
string rh , rm ; //羅馬數字 時rh 、 分rm
int bhm , thm ; // 轉成數字的部落總分鐘bhm , 台灣的總分鐘 thm
cin >> rh >> rm ;
thm = b2t( rton( rh ) * 60 + rton( rm ) );
cout << ntor( thm/60 ) << endl;
cout << ntor( thm%60 ) << endl;
return 0 ;
}
第4題d252: 94北縣賽-4-字串處理問題 (String)
/*
輸入：
hellol, I am a frog.
$-----xxxxipieirisioin0u++xs
hellol, I am a frog.
0uuuxxxxssss----++++uuuussssxxxxuuuuipipipipipipip
範例輸出 ：
Hello, I am a person.
HEL I AFROGppppppp.
*/
#include <iostream>
#include <cctype>
using namespace std;
int main( )
{
string data , cmd ; //資料、指令
getline( cin , data );
getline( cin ,cmd );
int dn = data.size();
int cn = cmd.size();
if( data[dn-1] == 13 ) { --dn; data.erase(dn); } //若最後1字為換行，刪
string dd=data;
if( cmd[cn-1] == 13 ) { --cn; cmd.erase(cn); } //若最後1字為換行，刪
int p=0; // 游標在第1個字{索引值0}
char c , t;
for(int i=0; i<cn; ++i)
{
c=cmd[i];
switch( c )
{
case '0' : p=0; break; // 行首
case '$' : p=data.size(); break; // 行尾
case 'x' : if( (p < data.size()) && (data.size()>0) ) data.erase(p,1) ; break; // 刪1字元
case 's' : if( p < data.size()-1 ) // p , p+1 兩字元交換
{ t=data[p]; data[p]=data[p+1] ; data[p+1]=t; } break;
case 'i' : if(i+1<cn) // 游標前插入1字元
{ ++i ; data.insert(p,1,cmd[i]); ++p; } break;
case 'u' : if( (p < data.size()) ){ data[p]=toupper(data[p]); ++p; } break; // 轉大寫
case '+' : ++p; break; // 右移if( p < data.size() )
case '-' : --p; break; // 左移if( p > 0 )
}
}
cout << data << endl;
return 0 ;
}
2014年8月7日 星期四
給商三孝-小考6前練習計算參考解
103H-小考6前練習-ch6-1+計算參考解
二、計算題： 佔40分
１、將二進位 101010.1101 轉十進位
Ans: 42.8125
２、將八進位 537.64 轉十進位
Ans: 351.8125
３、將十六進位 5E6.C8 轉十進位
Ans: 1510. 78125
４、將二十進位 2H7.DB 轉十進位
Ans: 1147. 6775
５、將十六進位 DA7.B8 轉八進位
Ans: 6647.56
６、將十進位 145.8125 轉二進位
Ans: 10010001.1101
７、將十進位 325.6875 轉八進位
Ans: 505.64
８、將十進位 1234.84375 轉十六進位
Ans: 4D2.D8
９、將十進位 123.88 轉五進位
Ans: 443.42
10、將八進位 732.56 轉十六進位
Ans: 1DA. B8
發表文章
