Y7M2 P2A 練習-2

100北二區資訊複賽

1.圈叉連線數問題(zj:a817)

2.藏寶問題(zj:a824)                ✔

3.小四數學(zj:a825)

4.天氣預測問題(zj:a826)

5.俄羅斯方塊問題(zj:a827)

101北二區資訊複賽

1.解碼問題(zj:a818)                 ✔

2.小三資優數學(zj:a819)

3.小精靈吃數字(zj:a820)

4.王者之路(zj:a821)

5.滾球遊戲(zj:a822)

藏寶問題(zj:a824) ================ 

#include <iostream>
using namespace std;
int main(void)
{
    int a,b,c,i,ans;

    cin >> a >> b >> c;
    
    for(i=1,ans=0; i<=c; i++)
        if( i%a==0 || i%b==0 )
            ans += i;
    
    ans = (ans-1)%26;
    cout << char ( 'A'+ans );
    return 0;
}
/*
a824 北二區 100年-2 寶藏問題
=== 輸入
3 5 9
2 6 12
=== 輸出
W
P
*/

解碼問題(zj:a818) ================ 

#include <iostream>  
using namespace std;
int main()  
{  
   int n , m , i , j , k , num , seq[20];
   while(cin >> n)
   {
      string s(n,' '),t(n,' ');  //s,t 長度為n個空白
      for(i=0; i<n; ++i)  
      {
         cin >> j;
         seq[i]=j-1;    //陣列 索引號從 0
      }  
      cin >> s >> k; ;
      while(k--)
      {
         for(i=0; i<n ; ++i)
         {
             t[i]=s[seq[i]];
         }
         s=t;
      } 
      cout << s << endl;
   } 
   return 0;  
}


/*
 zj:a818 1.解碼問題 -- 101學年度桃竹苗區資訊學科能力競賽

輸入 
10
8 9 5 7 10 1 2 4 6 3
as*Ittca*i
2
輸出
Itis*a*cat 
*/

Z2AY7M2練習-2

105正-F5P22 最大公約數計算    ✔(上一篇已傳)

105正-F5P11 計算字數               ✔(上一篇已傳)

105正-F5P12 摩斯電碼

105正-F4P21 網段ID

105模-M5P11 質數                          ✔ 

105模-M5P22 行、字數、字元數    ✔ 

105模-M5P41 尋找對稱字串

105模-M5P42 十進制轉二進制        ✔  

105模-M5P21 前綴字串and後綴字串

補充大數 N! (0<N<1000)            ✔(上一篇已傳)

內建函式整理： ======================

1．Math.Sqrt(x)：內建數學類函式，算出數值 x 的正平方根後傳回
2．EOF(fn)：檔案類函式，判斷是否已讀至檔案尾端，是則傳回 True
3．StrReverse(s)：將字串 s 的內容反轉後傳回
   例 s="120" 則傳回 "021"

======================================

105模擬 P11：質數  ================================

  Function P11(ByVal x As Integer) As String

     '傳入一個整數 x ，判斷是否為質數，是傳回字串T，否傳回F

        p11 = "T"

        If x < 2 Then Return "F"

        For k = 2 To Math.Sqrt(x)

            If x Mod k = 0 Then Return "F"

        Next

  End Function

105模擬 P22：行、字數、字元數  ======================

   Function P22(ByVal fn As Integer) As String

    '傳入一個整數 fn 為要讀入的 檔案編號

      Dim a, b, c As Integer

      Do Until EOF(fn)

          Dim line = LineInput(fn)

          a += 1

          c += line.Length

          Dim dat() = line.Split(" ")

          b += dat.Length

      Loop

      Return a & "," & b & "," & c

    End Function

105模擬 P42：十進制轉二進制  ========================

    Function P42(ByVal s As String) As String
        Dim dat() = s.Split(",")  
        Dim a As Integer = StrReverse(dat(0))
        Dim b As Integer = StrReverse(dat(1))
        Dim sum As Integer = StrReverse((a + b) & "")
        P42 = d2b(sum)   ' 呼叫自訂函式d2b將十進位轉二進位
    End Function

    Function d2b(ByVal sum As Integer) As String
     '將傳入的十進位數值 sum 傳為二進位後傳回 字串
        d2b = ""
        If sum = 0 Then Return "0"
        Do Until sum = 0
            d2b = sum Mod 2 & d2b
            sum \= 2
        Loop
    End Function

Y7M2 P2A 練習-1

大數相加    ✔

大數相乘    ✔

n階乘           ✔


大數相加================ 最多 1000位的兩個非負整數相加

#include <iostream>  // cin , cout

#include <cstring>   // memset

#include <algorithm>  // min, max

using namespace std;

const int MaxN = 1000+5;  // 10^999 有1000位，相加可能1001位

void print(int x[], int xn)   // 將 整數陣列x[] 倒著印出

{

        for(int i=xn-1; i>=0; --i)    cout << x[i];

        cout << endl;            // 加換行，若不加需在 呼叫後處理

}

void s2n(string s, int x[], int& xn)   // 將大整數(以字串傳入) 倒轉成整數陣列 x[]，設定長度xn

{

        xn = s.size();

        for(int i=xn-1, j=0;  i>=0; --i, ++j)     x[j] = s[i]-'0';

}

void badd(int x[], int xn , int y[], int yn , int z[], int& zn)

{

        zn = max(xn,yn);

        for(int i=0 ; i<zn; ++i) z[i] = x[i]+y[i];

        for(int i=0; i<zn; ++i)

          if( z[i]>=10 )

          {

                z[i+1] ++;   // 大數相乘的進位  應是 z[i+1] += z[i]/10

                z[i] -=10;   // 應是 z[i]%=10 ，但兩個<10的數字相加<20

          }

          if(z[zn]!=0) zn++;   // 大數相減或可能前導不只一個0時應 while(  ) zn--

}

int main(void)

{

        string sa,sb;

        int a[MaxN],b[MaxN],c[MaxN+1];

        int an,bn,cn;

        while( cin >> sa >> sb )

        {

                memset(a,0,sizeof(a));

                s2n(sa, a, an);  // print(a,an);

                memset(b,0,sizeof(b));

           s2n(sb, b, bn);  // print(b,bn);

           memset(c,0,sizeof(c));

           badd(a,an, b,bn, c,cn);

           print(c,cn);

        }

        return 0;

}

/*

範例輸入：

123456789012345678901234567890 111111111111111111111111111111

999999999999999999999999999999 1

12345 876

123 456789

範例輸出 ：

234567900123456790012345679001

1000000000000000000000000000000

13221

456912

*/


大數相乘 ================

#include <iostream>

#include <cstring>

using namespace std;

const int MaxN = 500+2;      // 最多500位數相乘

void s2n (string xs, int x[], int& xn )        // 將大整數字串 xs 轉為 整數陣列 x[] , 長度 xn

{

        xn = xs.size();

        for(int i=xn-1,j=0;  i>=0;  --i,++j)          x[j] = xs[i]-'0';

}

void print (int x[], int xn )           // 將 整數陣列x[] 倒著印出

{

        for(int i=xn-1;  i>=0;  --i)     cout << x[i];

        cout << endl;               // 加換行，若不加需在 呼叫後處理

}

void bmul(int x[], int xn, int y[], int yn, int z[], int& zn)

{

        for(int i=0; i<xn; ++i)

          for(int j=0; j<yn; ++j)

            z[i+j] += x[i]*y[j];

//  進位

   zn = xn+yn;

   for(int k=0; k<zn; ++k)

   {

     if( z[k]>=10 )

     {

             z[k+1] += z[k]/10;

             z[k] %= 10;

     }

   }

   if(z[zn-1]==0) zn--;

}

int main(void)

{

        string sa,sb;

        int a[MaxN],b[MaxN], c[MaxN+MaxN];  // c為相乘後結果，位數加倍

        int an,bn,cn;

        cin >> sa >> sb;

        s2n(sa,a,an);   // print(a,an);

        s2n(sb,b,bn);   // print(b,bn);

        for(int i=an+bn; i>=0; --i) c[i]=0;

        bmul(a,an,b,bn, c,cn);

        print(c,cn);

        return 0;

}

/* 輸入

200000000000000000000 300000000000000000000 

123456789012345678901234567890 123456789012345678901234567890

123 5

99 99

輸出 =========

60000000000000000000000000000000000000000 

15241578753238836750495351562536198787501905199875019052100

615

9801

*/

求 n 階乘 ===================
 輸入一個 0<1<1000 的正整數， 列出一行 n!
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int MaxN = 2570; // 1000! = 4.02387260077093773543702433923e+2567

void print (int x[], int xn )
{
for(int i=xn-1;  i>=0;  --i)
  cout << x[i];
cout << endl;
}

void bmi(int x[], int& xn, int y)
{
for(int i=0; i<xn; ++i)
  x[i]*=y;     /// <<< 與 bmul 不同，不累加，故可以不用清為0
//  進位
//     double ceil (double x);
//      float ceil (float x);
//   long double ceil (long double x);
//  Round up value  :   Rounds x upward, returning the smallest integral value that is not less than x.
//   zn = xn;
      xn+=4;   //xn+=ceil(log(y));   //
//   for(int i=zn; i<xn; ++i) x[i]=0;   ///有可能進位的位數才需清為 0
   for(int k=0; k<xn; ++k)
   {
    if( x[k]>=10 )
    {
    x[k+1] += x[k]/10;
    x[k] %= 10;
    }
   }
   while( x[xn-1]==0 ) xn--;  //去前導 0 {確定位數}
}

int main(void)
{
string sa,sb;
int a[MaxN];  // n! 的陣列
int an;       // 位數
   int n,s;
cin >> n;
memset(a,0,sizeof(a));  // 清為 0
a[0]=1; an=1;  // 1! 放在 a[0], 長度為1
for( int y=2; y<=n; ++y )  // 從 2開始乘至 n
{
bmi(a,an, y );
}
print(a,an);

return 0;
}
/*
10
20
50
100
1000
------
3628800
2432902008176640000
30414093201713378043612608166064768844377641568960512000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
*/

Z2AY7M2練習-1

105正-F5P22 最大公約數計算    ✔

105正-F5P11 計算字數                ✔               

105正-F5P12 摩斯電碼

105正-F4P21 網段ID

105模-M5P11 質數

105模-M5P22 行、字數、字元數

105模-M5P41 尋找對稱字串

105模-M5P42 十進制轉二進制

105模-M5P21 前綴字串and後綴字串

補充大數 N! (0<N<1000)            ✔ 

內建函式整理： ======================

1．s.split(ds) '以 ds 為分隔字，將字串s分成多個資料，傳回陣列
   例： s="1,23,4" : dim dat() = s.split(",")
     會傳回dat為三個元素：dat(0)="1"、dat(1)="23"、dat(2)="4"
2．UBound(dat)：取得陣列dat的最大註標值傳回數值
   以上例：會傳回 2，就是dat的最大註標元素為dat(2)
3．Trim(s)：將字串 s 的最左及最右空白刪除傳回字串
4．Instr(s1,s2)：在字串s1中找看是否有s2，若沒有傳回 0 ，有則傳回位置
5．s.replace(s1,s2)：在字串s中找第1個s1有找到換成s2，傳回換好的字串

======================================



105正式P22:最大公約數計算================================

   Function P22(ByVal s As String) As Integer
        Dim dat() = s.Split(",") '以空白分割
        Dim g As Integer
        P22 = 1
        For j = 0 To UBound(dat) - 1   ' 兩兩求gcd，所有中 找最大
            For k = j + 1 To UBound(dat)
                g = gcd(dat(j), dat(k))
                If g > P22 Then P22 = g
            Next
        Next j
    End Function
    Function gcd(ByVal a As Integer, ByVal b As Integer) As Integer
        Dim r As Integer = a Mod b
        Do Until r = 0
            a = b
            b = r
            r = a Mod b
        Loop
        Return b
    End Function
105正式P11:計算字數================================
    Function P11(ByVal s As String) As Integer
        P11 = 0
        ttrim(s, "  ", " ") '呼叫 ttrim自訂副程式，將多個空格改為1個
        Dim dat() = s.Split(" ")
        Return dat.Length
    End Function

    Sub ttrim(ByRef s As String, ByVal a As String, ByVal b As String)
        s = Trim(s)  ' trim是內建函式，去首尾的空白
        Do While (InStr(s, "  ") > 0) '有兩個空白傳回值>0
            s = s.Replace("  ", " ")
        Loop

    End Sub

補充大數 N! (0<N<1000)=========================

Public Class Form1

    ' 建一個標籤 Label1，一個按鈕 Button1

    Const MaxN As Integer = 2600 ' 1000! 共2568 位數

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        Dim a(MaxN) As Integer

        Dim an As Integer = 1  ' 1!=1 ，一位數

        a(0) = 1

        Dim n As Integer = InputBox("輸入n 1~1000")

        For k = 2 To n

            bmuli(a, an, k)

        Next

        Label1.Text = printn(a, an) & vbNewLine

    End Sub

    Sub bmuli(ByVal a() As Integer, ByRef an As Integer, ByVal k As Integer)

        ' 大數 a 乘 整數 k

        For i = 0 To an - 1

            a(i) *= k

        Next

        an += 3

        For i = 0 To an - 1

            If a(i) >= 10 Then

                a(i + 1) += (a(i) \ 10)

                a(i) = a(i) Mod 10

            End If

        Next

        Do While an >= 0 AndAlso a(an) = 0

            an -= 1

        Loop

        an += 1

        If an = 0 Then an = 1

    End Sub

    Function printn(ByVal a() As Integer, ByVal an As Integer) As String

        ' 將 a 陣列倒轉列出 => 字串 ans 轉回 ans

        Dim ans = ""

        For i = an - 1 To 0 Step -1

            ans &= a(i)

        Next

        Return ans

    End Function

End Class

' 範例輸入

10

20

50

88

==============

'範範例輸出

3628800

2432902008176640000

30414093201713378043612608166064768844377641568960512000000000000

185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000