IvanKao的部落格

CPE一顆星考題:

35.GCD

題意：

給一數N，求出任由 1至 N的所有組合最大公因數之總和G

67↵\r\n
13015↵\r\n
442011↵\r\n

#include <iostream>
using namespace std;
int gcd(int x,int y){             //輾轉相除法求最大公因數
  while(x=x%y)
    swap(x,y);                      //swap互換值
  return y;
}
    
int main(){
  int ans[502]={0};                 //先建立陣列，初始化所有值為0           
  for (int i=1;i<502;i++){          //先選出i
    ans[i]=ans[i-1];                //讓ans[i-1]，以便對齊最後的cin值
    for (int j=1;j<i;j++){          //在將i跟j迴圈做輾轉相除
      ans[i]=ans[i]+gcd(i,j);
    }
  }
  int d;
  while(cin>>d,d){                 //d=0為第一項
    cout<<ans[d]<<endl;
  }
  return 0;
}



//另一種較易懂的寫法(運行時間會較久)
#include <iostream>
using namespace std;
int gcd(int x,int y){
  while(x=x%y)swap(x,y);
  return y;
}
int main(){
  int a;
  while(cin>>a && a!=0){
    int i,j;
    int sum=0;
    for (i=1;i<=a;i++){
      for (j=i+1;j<=a;j++){     //不能跟自己算公因數重複，故加1
        sum = sum + gcd(i,j);
      }
    }
    cout<<sum<<endl;
  }
  return 0;
}
      
    
 

38.Can You Solve It?

題意：

如圖，會按照箭頭的順序進行移動

給兩座標，求兩座標之間的要走的步數

解題想法：

(0,0)為第一層

x+y座標可得(層數-1)，再利用(首項+末項)項數/2 得出 該層數需要用到的步數(例如到(3,1)的層數就為3

最後加上x座)即可得從起點到該座標所需的總步數

算出從起點到座標的步數，再將兩個步數相減

Case 1: 809278↵\r\n

#include <iostream>
using namespace std;
int main(){
  int c;cin>>c;
  for(int i=1;i<=c;i++){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int pos1,pos2;
    pos1=(x1+y1+1)*(x1+y1)/2+x1;
    pos2=(x2+y2+1)*(x2+y2)/2+x2;
    cout<<"Case "<<i<<": "<<pos2-pos1<<endl;
  }
  return 0;
}

48.Cola

題意：

超商貼著3瓶可樂瓶可以換1瓶可樂，請計算出最多可以喝到多少瓶可樂。空瓶可以跟朋友借，但是需要歸還。

解題方向：

當N(可樂瓶子數量)<=1時，可以直接印出目前的可樂瓶數，因為你再怎麼借，也無法歸還空瓶給朋友。當N>1時，用個變數(ans)紀錄已經喝過的可樂，再重新計算可樂瓶子數量(N)，直到可樂瓶子數量(N)=2時，可以跟朋友借一個瓶子，即可換得最後1瓶可樂，喝完的可樂瓶剛好可以還給朋友。當可樂瓶子(N)=1時，結束迴圈，印出答案。

#include <iostream>
using namespace std;
int main(){
  int a;                         //a為買入的數量
  while(cin>>a){
    int sum=a,old=0;             //sum為總共可以喝多少，old紀錄剩餘無法換的空瓶子
    while(a>=3){
      old = a%3;
      a = a/3;
      sum = sum+a;
      a= a+old;

    }
    if(a==2)                     //如果a為2就可以借一瓶再還 
      sum++;
    cout<<sum<<endl;
  }
  return 0;
}