To P2 之 a010質因數分解

參考程式碼 ，最後有另一組建質數表的 genp程式
// a010
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 46340  // sqrt(2147483647) < 46341
using namespace std;
bool c[maxn+10];
vector <int> p;    // 2~46340之間的質數共有 4792個，p[4791]=46337 ,前46327後46349

// 以下 isp 為函式， 傳入 n 判斷是否為質數 
bool isp(int n)
{
  if(n<=maxn) return( !c[n] );
  int q = (int) sqrt(n);
  int k;
  for(k=0; k<p.size() && p[k]<=q ; ++k)
    if(n%p[k]==0) return false;
  return true;     
}
// 篩法
void sieve()
{
  int i,j,k;
  memset(c,0,sizeof(c));
  c[0]=c[1]=1;
  for(i=2;i<=maxn;++i)
  {
     if(c[i]==1) continue; //非質數
     p.push_back(i);  // i是質數，放入 p 中 
     //是質數的倍數 註記為非質數
     for(j=i+i; j<=maxn; j+=i)
       c[j]=1;                   
  }
  //  for(k=2; k<=100; ++k)  // 印出 2~100的質數 
//    if( !c[k] ) cout << k << endl;
//  cout << p.size() <<" " << p[p.size()-1] << endl;
  return ;
}

int main()
{
  sieve(); 

  int n;

  while( cin >> n )  
  {
     int i=0, f=0;
     bool lead=true;
     while( n>1 && i<p.size() )
     {
if(n%p[i]==0)
{
    n/=p[i];
   ++f;
}
else
{
           if(f>0)
   {
      if(lead) lead=false; else cout <<" * ";
      cout <<p[i];
              if(f>1) cout <<"^" <<f;
              f=0;
   }
   ++i;
}
     }
     if(n>1 || f>0)
     {
        if(lead) lead=false; else cout <<" * ";  // n>1 及 f>0 不同時
        if(f>0) cout <<p[i];
        if(f>1) cout <<"^" <<f;
        if(n>1) cout << n;
     }
     cout << endl;
  }
  return 0;
}
/*
範例輸入 ：
20
17
999997
288
614017530
92822
2147210123
範例輸出 ：
2^2 * 5
17
757 * 1321
2^5 * 3^2
2 * 3^3 * 5 * 7^2 * 46411
2 * 46411
46327 * 46349
*/

genp 建質數表-2

#include <iostream>

#include <cmath>

#include <vector>

#define MaxN 2147483647

using namespace std;

vector <int> p;

bool isp(int n)

{

   int i,ps=p.size();

   int qn=sqrt(n);

   if (  !((n %6==1)or(n%6==5))  ) return 0;

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

     if( !(n%p[i]) ) return 0;

   return 1;  

}

void gen_p(int n){

  int k,gap;

  int q=int(sqrt(float(n)));

//  cout<<n<<", sqrt="<<q<<endl;

  p.push_back(2);p.push_back(3);

  for(k=5,gap=2; k<=q; k+=gap)

   { gap=6-gap;

     if(isp(k)){

       // cout <<k<<"  ";

       p.push_back(k); }

   }

  // cout<<endl;

}

int main()

{

    int n;

    gen_p(MaxN);

    cout <<p.size()<<","<<p[p.size()-1]<<endl;

    cin>>n;

    cout <<n<<":"<<isp(n);

    return 0;

} 

商競104F-P42最小成本生成樹(VB參考)

這是依商業技藝競賽程式104年正式題第4題子題2稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料一列
每一列為一個圖形所有「邊」以空格隔開，「邊」由3個以逗號隔開的數字組成{2個節點及成本}
每組資料印出1個數字，算出圖形的最小成本生成樹的成本。

參考程式碼：

'最小成本生成樹 MST

Const MaxM As Integer = 20 '最多20邊

Const MaxN As Integer = 26 '最多26點

Dim eg(MaxM) As String '邊

Dim ct(MaxM) As Integer  '成本

Dim rt(MaxN) '此點的根

Dim ht(MaxN) '此點的高

Dim n As Integer '節點數

Dim m As Integer '邊數

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

 FileOpen(1, "in1.txt", OpenMode.Input)

 ' FileOpen(2, "in2.txt", OpenMode.Input)

 FileOpen(3, "out.txt", OpenMode.Output)

 For fn = 1 To 1 'in1,in2合成一個

    If fn = 2 Then PrintLine(3)

    Dim t As Short = LineInput(fn)

    For i = 1 To t

       Dim egs() = LineInput(fn).Split(" ")   '一列為一個樹，多個邊

       m = egs.Length  '邊數

       For j = 0 To m - 1

          eg(j) = Strings.Left(egs(j), 3)  '一個邊

          ct(j) = Val(Mid(egs(j), 5))  ' 這個邊的 成本

       Next

        Array.Sort(ct, eg, 0, m)

        Array.Clear(ht, 0, MaxN)

        For j = 0 To MaxN

             rt(j) = j

        Next

        Dim ans = 0

        For j = 0 To m - 1

          Dim x As Integer = Asc(Mid(eg(j), 1, 1)) - 65

          Dim y As Integer = Asc(Mid(eg(j), 3, 1)) - 65

          If same(x, y) Then Continue For

          ans += ct(j)  '不是同一 根 就將成本加入 ans

          uni(x, y) '將x,y合併

          Print(3, "+" & ct(j) & eg(j) & " ") '測試用列印

        Next

        PrintLine(3, "ans=" & ans)  '測試用列印

     Next i

  Next fn

  End

End Sub

 Function fdrt(ByVal x As Integer) As Integer  '找 x 的根

        If rt(x) = x Then Return x

        rt(x) = fdrt(rt(x))

        Return rt(x)

 End Function

 Function same(ByVal x As Integer, ByVal y As Integer)

        Return (fdrt(x) = fdrt(y))  ' x,y 的根是否相同

 End Function

 Sub uni(ByVal x As Integer, ByVal y As Integer)  '將 x樹 及 y樹 合成一樹

        x = fdrt(x) : y = fdrt(y)

        If x = y Then Return

        If ht(x) < ht(y) Then

            rt(x) = y

        Else

            rt(y) = x

            If ht(x) = ht(y) Then ht(x) += 1

        End If

 End Sub

'輸入 in1.txt 併 in2 

4

A,B,6 A,E,9 B,C,3 B,D,5 C,D,7 B,F,8 D,E,10 D,F,11 A,F,12 E,F,15

A,B,3 A,C,2 B,C,1 B,D,2 C,D,1 B,E,2 C,F,1 D,E,1 D,F,1 D,G,2 E,G,1 F,G,1

B,A,6 B,F,8 B,D,5 D,E,10 D,F,9 A,F,12 A,E,10 E,F,15

D,E,1 D,G,2 D,F,1 E,G,1 F,G,1

輸出：第1組 31 , 第2組 7 , 第3組 29 , 第4組 3

31

7

29

3   

參考：

    +3B,C +5B,D +6A,B +8B,F +9A,E ans=31

    +1C,D +1D,F +1D,E +1F,G +1B,C +2A,C ans=7

    +5B,D +6B,A +8B,F +10A,E ans=29

    +1E,G +1F,G +1D,F ans=3

商競104F-P42最小成本生成樹(CPP參考)

這是依商業技藝競賽程式104年正式題第4題子題2稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料一列
每一列為一個圖形所有「邊」以空格隔開，「邊」由3個以逗號隔開的數字組成{2個節點及成本}
每組資料印出1個數字，算出圖形的最小成本生成樹的成本。
參考程式碼：
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
const int MaxM = 20;  //最多 20 邊
const int MaxN = 26;  //最多 26 點
struct egs
{
int k;  // 成本
int a,b;  // a-b 相鄰
} eg[MaxM];
int rt[MaxN];  // 根
int ht[MaxN];  // 高
bool cmp(egs x, egs y)  //結構為 egs 的資料型別 x , y 比較大小(x<y傳回真)
{
return x.k<y.k;
}
int val(string t)  //字串數 轉為數值
{
  int k=t.size();
  int i,v=0;
  for(i=0; i<k; ++i)
    if(t[i]>='0' && t[i]<='9')
   v = v*10 + t[i]-'0';
  return v;
}
int n,m; // n 節點、m邊
int fdrt(int x) // 找 x 的根
{
if( rt[x] == x ) return x;
return ( rt[x] = fdrt(rt[x]) );
}
void uni(int x, int y) // x樹 及 y樹 合併
{
x=fdrt(x) ; y=fdrt(y);
if( x==y ) return;
if( ht[x] < ht[y] ) rt[x] = y;
else
{
rt[y] = x;
if(rt[x] == rt[y]) ht[x]++;
}
}
bool same(int x, int y)
{
return fdrt(x) == fdrt(y);
}
int main(void)
{
   int t,i,j;
   int x,y,k;
   string line,s;
   cin >> t; getline(cin,line);
   while( t-- )
   {
// init
n=0; m=0;
for(i=0; i<MaxN; ++i)
{
rt[i] = i;
ht[i] = 0;
}
getline(cin,line);
istringstream sin(line);
while( sin >> s )
{
x = s[0] -'A';  y = s[2] -'A';
k = val( s.substr(4) );
// cout << x <<'-' << y << ':' << k <<' ';  //
eg[m].a = x;  eg[m].b = y; eg[m].k = k;
m++;
}
// cout << endl;  //
sort(eg , eg+m, cmp);
// for(i=0; i<m; ++i)
//   cout << eg[i].k <<':' << eg[i].a << '-' << eg[i].b <<' ';
// cout << endl;
int ans=0;
for(i=0; i<m; ++i)
{
x = eg[i].a;  y = eg[i].b;  k = eg[i].k;
if( same(x,y) ) continue;
ans += k;
uni(x,y);   // x樹 及 y樹 合併
// cout << '+' <<k<<':'<<x<<'-'<<y<<'='<<ans<<' ';
}
// cout <<" ans=" << ans << endl;
   }
return 0;
}
/*範例輸入
4
A,B,6 A,E,9 B,C,3 B,D,5 C,D,7 B,F,8 D,E,10 D,F,11 A,F,12 E,F,15
A,B,3 A,C,2 B,C,1 B,D,2 C,D,1 B,E,2 C,F,1 D,E,1 D,F,1 D,G,2 E,G,1 F,G,1
B,A,6 B,F,8 B,D,5 D,E,10 D,F,9 A,F,12 A,E,10 E,F,15
D,E,1 D,G,2 D,F,1 E,G,1 F,G,1
範例輸出 ------
31
7
29
3
---參考
+3B,C +5B,D +6A,B +8B,F +9A,E ans=31
+1C,D +1D,F +1D,E +1F,G +1B,C +2A,C ans=7
+5B,D +6B,A +8B,F +10A,E ans=29
+1E,G +1F,G +1D,F ans=3
*/

商競104F-P41二搜+後巡(VB版參考)

這是依商業技藝競賽程式104年正式題第4題子題1稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料二列
每組的第1列一個數字x，每組第2列 x 個數字以逗號隔開
將讀入的 x 數字建成二元搜尋樹，然後依二元樹的後序拜訪 印出
參考程式碼：
 Dim dt(20) As Integer  '資料
 Dim chi(20, 1) As Integer '左、右子樹
 Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
    FileOpen(1, "in1.txt", OpenMode.Input)
   ' FileOpen(2, "in2.txt", OpenMode.Input) '本題只一 in1
    FileOpen(3, "out.txt", OpenMode.Output)
    For fn = 1 To 1 '本題只一 in1
       If fn > 1 Then PrintLine(3) '本題只一檔，若2檔，中間空一列
       Dim n As Short = LineInput(fn)  '每組第一列 N 組資料
       Do Until n = 0
           n -= 1
           Dim x As Short = LineInput(fn)  ' x 個節點
           For i = 0 To x - 1
               chi(i, 0) = -1 : chi(i, 1) = -1
           Next
           Dim id() = LineInput(fn).Split(",")
           dt(0) = id(0)
           For i = 1 To x - 1
               dt(i) = id(i)
               gbst(i, dt(i))
           Next
         ' For j = 0 To x - 1  '此段多印的 左樹、資料、右樹
         '     PrintLine(3, j & "  " & chi(j, 0) & ":" & dt(j) & ":" & chi(j, 1))
         ' Next
           po_t(chi(0, 0))
           po_t(chi(0, 1))
           PrintLine(3, dt(0) & "")
       Loop
    Next ' fn
   End
End Sub
Sub gbst(ByVal i, ByVal v)   '建二元搜尋樹
    Dim p As Integer = 0
    Dim dir As Integer  '0往左 或 1往右
    Do Until p = -1
       Dim pp As Integer = p
       If v < dt(p) Then  '往左
           dir = 0
           p = chi(p, 0)
       Else   '往右
           dir = 1
           p = chi(p, 1)
       End If
       If p = -1 Then
           chi(pp, dir) = i
           Return
       End If
    Loop
End Sub
Sub po_t(ByVal p As Integer) '後序列印
    If p = -1 Then Return
    po_t(chi(p, 0))
    po_t(chi(p, 1))
    Print(3, dt(p) & ",")

End Sub
/*範例輸入in1.txt
4
8
7,4,1,5,12,8,9,15
10
9,4,1,5,12,11,10,15,2,3
9
4,1,5,12,11,10,15,2,3
4
1,2,3,4
範例輸出out.txt
1,5,4,9,8,15,12,7
3,2,1,5,4,10,11,15,12,9
3,2,1,10,11,15,12,5,4
4,3,2,1
*/

商競104F-P41二搜+後巡(CPP版參考)

這是依商業技藝競賽程式104年正式題第4題子題1稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料二列
每組的第1列一個數字x，每組第2列 x 個數字以逗號隔開
將讀入的 x 數字建成二元搜尋樹，然後依二元樹的後序拜訪 印出
參考程式碼：
/*
104f-p41_bst-pos 將 n 個數字建二元搜尋樹，再以後序巡訪序印出
第一列 整數 t:代表有 t組資料{ 0<t<10 }， 接著每組2列
每組第1列為 整數 n:代表有 n 個數字 { 3<= n <= 20 } ， 每組第2列有 n 個以逗號隔開的整數 vi {  0 <= vi <=99 for i=1~n }
*/

#include <iostream>
using namespace std;
const int MaxN = 21; //本題最多20個節點
struct nds  // 每一點有 值dt , 左子、右子 chi[0],chi[1]
{
int dt;
int chi[2]; // -1代表 沒有子樹 chi[0]左子，chi[1]右子
} nds[MaxN]; //本題最多20個節點
// 函式 gbst 建二元搜尋樹 
void gbst( int i, int v )
{
int p = 0 , dir; // dir:0左、1右
while( p != -1 )  //找到  null 節點 ，再 break
{
int pp = p;
if( v < nds[p].dt )    //往左樹
{
dir = 0;
p=nds[p].chi[0];
}
else {  // v > nds[p].v  往右樹
dir = 1;
p=nds[p].chi[1];
}
if ( p == -1 ) //左或右為null ，找到，加入
{
nds[pp].chi[dir] = i;
return;
}
}
}

// post_order 後序拜訪：先印左樹、再印右樹、最後 才印節點本身
void po_st( int p )
{
   if( p == -1 ) return;
   po_st( nds[p].chi[0] );
   po_st( nds[p].chi[1] );
   cout << nds[p].dt << ',';
}

int main(void)
{
   int i, v,n,x;
   char c;
   cin >> n;
   while( n-- )
   {
cin >> x;
for(i=0;i<x;++i) nds[i].chi[0] = nds[i].chi[1] = -1;
cin >> v; nds[0].dt = v;
for(i=1; i<x; ++i)
{
cin >> c >> v;    // 數字間有一 逗號 先讀c 再讀 v
nds[i].dt = v;
gbst( i , v );  // 呼叫函式建左右樹的連結表
}
//for(i=0; i<n; ++i)   // 測試列印 建好表後的 左樹、值、右樹
//   cout << nds[i].chi[0] <<':' << 先nds[i].dt <<':' << nds[i].chi[1] << endl;
    po_st( nds[0].chi[0] );  //先印 左樹
    po_st( nds[0].chi[1] );  //再印 右樹
    cout << nds[0].dt << endl; //最後才印根節點
   }
   return 0;
}
/*範例輸入
4
8
7,4,1,5,12,8,9,15
10
9,4,1,5,12,11,10,15,2,3
9
4,1,5,12,11,10,15,2,3
4
1,2,3,4
範例輸出 ------
1,5,4,9,8,15,12,7
3,2,1,5,4,10,11,15,12,9
3,2,1,10,11,15,12,5,4
4,3,2,1
*/

商競103M-P31是否為樹(CPP版參考)

這是依商業技藝競賽程式103年模擬題第3題子題1稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料{0<n<10}，接著每組資料一列
每列是一個圖形的所有「邊」以空白隔開 ,每一個「邊」是由兩數字以逗號連接
判斷這個圖形是否為一棵樹，是印T否印F

參考程式碼：
/*
b517: 是否為樹-商競103 標籤 : dfs tree
這是 103年商業技藝競賽模擬題的 P31題，原題中對樹的描述就先省略了。
給一個圖形的邊的資訊，判斷是否為一棵樹？
輸入說明 ： 每組測資檔的第1列為一個數字 n ，代表以下有 n 列，每列為一個圖形的相鄰節點(邊)的資訊：
         每列中的所有邊皆由 i,j 表示，邊與邊之間以空格隔開， 0<=i,j <=80， i及j為相鄰的兩節點編號，以「,」連接i,j不含空格
輸出說明 ： 對於每一個圖形輸出一列，判斷其是否為一棵樹，若是則輸出 T 、否則輸出 F
*/
#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
const int MaxN = 80;  // 0~80
int val(string t)  //將字串的數字轉為數值
{
  int k=t.size();
  int i,v=0;
  for(i=0; i<k; ++i)
    if(t[i]>='0' && t[i]<='9')
   v = v*10 + t[i]-'0';
  return v;
}
bool adj[MaxN+5][MaxN+5] , nd[MaxN+5];
void dfs(int u)
{
nd[u] = false;   // 訪過的設為 false
for(int v=0; v<=MaxN; ++v)
{
if( adj[u][v]==true && nd[v]==true ) // 有相連且沒訪過
  dfs(v);
}
}
int main()
{
   int i,n;
   string line,s;
   cin >>n; getline(cin,line);
   while(n--)
   {
int vn=0 , en=0;  // node , edge 節點數、邊數
getline(cin,line);
istringstream  sin(line);  // 一整列轉成 串讀 
int st;
while( sin >> s) //以空格隔開 讀一個邊的字串 s
{
++en;
   int p=s.find(',');
   int x=val(s.substr(0,p)) , y=val(s.substr(p+1));
   adj[x][y] =  adj[y][x] = true;
   nd[x] = nd[y] = true;
   st = x;  // start node
}
      // 建好 adj 及 nd 兩個表後，以下判斷是否為樹
      for(i=0; i<=MaxN; ++i) 
   if(nd[i]) ++vn;  //計算節點數
      if( vn != en+1 ) { cout << "F" << endl; continue; } //節點數=邊數+1 ?
      dfs( st ); //從節點 st 開始 dfs ，有走過的 nd[ ]設為 false
      bool conn=true;
      for(i=0; i<=MaxN; ++i)
 if(nd[i])  { conn=false;  break; } //有某一節點沒訪過
      if(conn)  cout << "T" << endl;
      else cout << "F" << endl;
  }
  return 0;      
}
/*
範例輸入 ： 
4
6,8 5,3 5,2 6,4 5,6 1,2 2,0
8,1 1,3 6,2 8,10 7,5 1,4 7,8 7,6 8,0
3,8 6,8 6,4 5,3 5,6 8,2 2,0
1,0 4,3 1,2 
範例輸出:
T
T
F
F

*/