 |
 |
darkstone007
驢手小試
． 積分： 7
． 文章： 32
． 收花： 38 支
． 送花： 220 支
． 比例： 5.79
． 在線： 35 小時
． 瀏覽： 2490 頁
． 註冊： 7279 天
． 失蹤： 4069 天
|
|
|
 |
|
 |
|
| #2 : 2005-11-18 01:03 AM
只看本作者
|
 送花
(9)
 送出中...
|
|
|
1.試分析下列程式的複雜度。
fun(int a[],int n)
{
int i,j;
a[1]=0;
for(i=2; i < n; i++) a[i]=1;
for(i=2; i < n/2; i++)
for(j=2; j < n/i; j++)
a[i*j]= 0;
for(i=1; i < n; i++)
if (a[i]) printf("%d\n",i);
}
{1}空間複雜度
由於使用了三個int變數n,i,j和一個int陣列
所以用了4byte*3(三個int變數)+4byte*int陣列a[]的元素數目+2byte(其實陣列是一個指標所以還要加一個指標的大小)
(2)時間複雜度
fun(int a[],int n)
{
int i,j;//0次(因為只有宣告所以只算空間複雜度)
a[1]=0;//1次
for(i=2; i < n; i++)
//for迴圈裡加一次
a[i]=1;1次
//for迴圈結束算一次,但是for裡面的要乘上n-2
for(i=2; i < n/2; i++)
//for迴圈裡加一次
for(j=2; j < n/i; j++)
//for迴圈裡加一次
a[i*j]= 0;//1次
//for迴圈結束算一次,但是for裡面的要乘上n/i-2
//for迴圈結束算一次,但是for裡面的要乘上n/2-2
for(i=1; i < n; i++)
//for迴圈裡加一次
if (a[i]) //if算一次
printf("%d\n",i);//當陣列a的元素不等於0的時候,printf算一次
//for迴圈結束算一次,但是for裡面的要乘上n-1
}
所以總共是0+1+(1+1)*(n-2)+1+(1+(1+1)*(n/i-2)+1)*(n/2-2)+1+(1+1)*(n-1)+1+(n-(1到(n/2-1)的所有質數個數))
2.有一一維陣列A[6000],及三維陣列B[30][20][10],試回答下列問題:
1) 若用以列為主(row major)的方式來排列三維陣列則A[2345]對應到B陣列的哪一個元素?
因為排的時候是[0][0][0],[0][0][1],...,[0][0][10],[0][1][0],.......
所以在二維裡每一面有(20+1)*(10+1)個
2345/((20+1)*(10+1))=10餘35
總共排滿10面剩35個,所以對應到B陣列的11面,但是陣列是從0開始的,所以第11面就是[10]
然後在35個在二維裡排的方法是[0][0],[0][1],...,[0][10],[1][0],.....
每條線有10+1個
35/(10+1)=3餘2
所以是排滿三條線,對應到第四條線,但是陣列是從0開始的,所以第四條線就是[3]
剩下2,但是陣列A[2345]也是從0開始的,所以其實還要加1,剩下三個
三個的話就是排到[2]
以列為主的方式來排的話是B[10][3][2]
2) 若用以行為主(column major)的方式來排列三維陣列則A[2345]對應到B陣列的哪一個元素?
行為主的話 沒想過....大概是倒過來吧
所以就是這樣排[0][0][0],[1],[0],[0],...,[30][0][0],[0][1][0],.....
所以在二維裡每一面有(30+1)*(20+1)個
2345/((30+1)*(20+1))=3餘392
所以就是[3]
然後在392個在二維裡排的方式是[0][0],[1][0],...,[20][0],[0][1],.....
每條線有20+1個
392/(20+1)=18餘14
所以是[18]
剩下14
就是[14]
寫出來就變成B[14][18][3]
3.有多項式定義如下:
F(X)=3x^4+5X^2+X+6,P(X)=2X^3-4X^2+19,Q(X)=10X^5-7X^3+19X+10,
試設計程式來計算F(X)+P(X)-Q(X)。
//因為三個多項式最高才五次,也不是稀疏的,簡單用array宣告吧
#include using namespace std;
int[] add(int[],int[]);
int[] sub(int[],int[]);
int main(){
int F[5]={6,1,5,0,3,0};
int P[5]={19,0,-4,2,0,0};
int Q[5]={10,19,0,-7,0,10};
int answer[5];
answer=sub(add(F,P),Q);
return 0;
}
int[] add(int a[],int b[]){
int temp[5];
for(int i=0;i<6;i++)
temp[i]=a[i]+b[i];
retrun temp;
}
int[] sub(int a[],int b[]){
int temp[5];
for(int i=0;i<6;i++)
temp[i]=a[i]-b[i];
retrun temp;
}
4.試利用堆疊的資料結構與運算,設計一程式來計算下列後序表示式。(參考課本3-26頁)
6 9 3 / - 8 6 2 - / +
#include using namespace std;
#define STACK_MAX 10
int stack[STACK_MAX];
bool IsFull();
bool IsEmpty();
int pop(int*);
void push(int,int*);
int top=-1;
int main(){
char postfix[11]={'6','9','3','/','-','8','6','2','-','/','+'};
int temp;
for(int i=0;i<12;i++){
if(postfix[i]=='0'){push(0);}
else if(postfix[i]=='1'){push(1);}
else if(postfix[i]=='2'){push(2);}
else if(postfix[i]=='3'){push(3);}
else if(postfix[i]=='4'){push(4);}
else if(postfix[i]=='5'){push(5);}
else if(postfix[i]=='6'){push(6);}
else if(postfix[i]=='7'){push(7);}
else if(postfix[i]=='8'){push(8);}
else if(postfix[i]=='9'){push(9);}
else if(postfix[i]=='+'){push(pop(&top)+pop(&top));}
else if(postfix[i]=='-'){
temp = pop(&top);
push(pop(&top)-temp);
}
else if(postfix[i]=='/'){
temp = pop(&top);
push(pop(&top)/temp);
}
}
int answer = pop(&top);
return 0;
}
bool IsFull(){
if(top>=STACK_MAX)
return true;
else
return false;
}
bool IsEmpty(){
if(top<0)
return true;
else
return false;
}
int pop(int *top){
if(IsEmpty())
cout<<"Stack is empty."<
else{
return stack[*top--];
}
}
void push(int item, int *top){
if(IsFull())
cout<<"Stack is full."<
else{
stack[++*top]=item;
}
}
5.現有一五層出租套房的各樓層房間圖,如下圖所示:
501 502 503
401 402 403
301 302 303
201 202 203
101 102 103
上述圖例中的每間套房租金是5000元,現在第201,402,303,102,501,302已經交過本月房租,寫一個程式輸入已經交租金的房間號碼,然後列印出未交房租的房間編號和全部已交,未交的房租款項。
//用一個二維陣列表示房租已交未交
#include using namespace std;
int main(){
bool rent[6][4];
rent[2][1]=true;
rent[4][2]=true;
rent[3][3]=true;
rent[1][2]=true;
rent[5][1]=true;
rent[3][2]=true;
int temp;
cout<<"請輸入已交房租號碼(輸入0則結束輸入程序):";
cin>>temp;
while(temp){
if((temp/100)<1||(temp/100)>5||(temp%100)<1||(temp%100)>3){
cout<<"無此房間"<
else{
rent[temp/100][temp%100]=true;}
cout<<"請輸入已交房租號碼(輸入0則結束輸入程序):";
cin>>temp;
}
cout<<"未交房租的房間編號:"
for(int i=1;i<6;i++){
for(int j=1;j<4;j++){
if(rent[i][j]==false)
cout<<"["<
}
}
cout<<"全部已交未交的房租款項:"<
for(int i=5;i>0;i--){
for(int j=1;j<4;j++){
cout<<"["<
}
cout<
}
return 0;
}
註:
我也是念資訊的
這門課也有修
修的....不是很好....orz
所以答案錯的機率很大.....
希望有標準答案的時候也寫上來唄
[darkstone007 在 2005-11-25 02:51 AM 作了最後編輯]
[如果你喜歡本文章，就按本文章之鮮花～送花給作者吧，你的支持就是別人的動力來源]
|
|
