應用

由N個數所組成的數中，求最大的質數
範例
p.in

2
2 3

p.out

2 2 22 0 
3 2 32 0 
2 3 23 1 
3 3 33 0 
max:23

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
bool IsPrime(int num)
{
 if(num<=1)
  return false;
 for(int i=2; i<=sqrt(num*1.0); i++)
 {
  if(num%i==0)
   return false;
 }
 return true;
}
 
int main () { 
 int *A,*B;
 int max=0;
 cin >> N;
 A=new int[N];
 B=new int[N];
 for (int i=0;i<N;i++) cin >>A[i];
 int size=(int)pow((float)N,(float)N);
 for (int i=0;i<size;i++){
  int a=i;
 
  for (int j=0;j<N;j++){
   B[j]=A[a%N];
   a = a/N;
  } 
  for (int j=0;j<N;j++){
   cout << B[j] << ' ';   
  } 
  int b=0;
  for (int j=0;j<N;j++){
   b = b*10+B[j];   
  } 
  cout << b << ' ';
  bool p =IsPrime(b); 
  cout << p << ' ';
  if (p&&b>max) max=b;
  cout << endl;
 }
 cout << "max:" << max << endl;
}

n顆不同的球，抽m次，每次都放回，列出所有可能(由小而大)

#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
int N,M; //#balls, #draw
int main () { 
 cin >> N >> M;
 int size=(int)pow((float)N,(float)M);
 for (int i=0;i<size;i++){
  int a=i;
  stack<int> s;
  for (int j=0;j<M;j++){
   s.push(a%N);
   a = a/N;
  }
  while(!s.empty()){
   cout << s.top() << ' ';
   s.pop();
  }
  cout << endl;
 }
}

---

3 2

---

0 0 
0 1 
0 2 
1 0 
1 1 
1 2 
2 0 
2 1 
2 2 

n顆不同的球，抽m次，每次都放回，列出所有可能(不介意是否由大而小的話

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int main () { 
 cin >> N >> M;
 int size=(int)pow((float)N,(float)M);
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   cout << a%N << ' ';
   a = a/N;
  }  
  cout << endl;
 }
}

---

3 2

---

0 0 
1 0 
2 0 
0 1 
1 1 
2 1 
0 2 
1 2 
2 2 

n顆不同的球，抽m次，每次都放回，列出所有可能(更精簡一點的版本)

#include <iostream>
using namespace std;
int N,M; //#balls, #draw
void draw(int n,int m, int*a){ 
 for (int i=0;i<n;i++){
  a[M-m]=i;
  if (m==1){
   for (int j=0;j<M;j++)
    cout << a[j] << ' ';
   cout << endl;
  }
  else
   draw(n,m-1,a);
 } 
}
int main () { 
 cin >> N >> M;
 int *a = new int[M];
 draw(N,M,a); 
}

n顆不同的球，抽m次，每次都放回，列出所有可能

#include <iostream> 
#include <string>
using namespace std;
int N,M; //#balls, #draw
void draw(int n,int m, int*a){
 if (m==0){
  for (int j=0;j<M;j++)
   cout << a[j] << ' ';
  cout << endl;
 }
 else{
  for (int i=0;i<n;i++){
   a[M-m]=i;
   draw(n,m-1,a);
  }
 }
}
int main () { 
 cin >> N >> M;
 int *a = new int[M];
 draw(N,M,a); 
}

n顆不同的球，抽m次，每次都放回，列出所有可能(找找看什麼地方錯了？)

#include <iostream> 
#include <string>
using namespace std;
int N,M; //#balls, #draw
void draw(int n,int m, int*a){
 for (int i=0;i<n;i++){
  if (m==0){
   for (int j=0;j<M;j++)
    cout << a[j] << ' ';
   cout << endl;
  }
  else{
   a[M-m]=i;
   draw(n,m-1,a);
  }
 }
}
int main () { 
 cin >> N >> M;
 int *a = new int[M];
 draw(N,M,a); 
}

分治法；非等差數列

輸入n，請構造出一組1~n的排列，滿足任意選擇其中三個數，按照原本的順序排列，均不會形成等差數列。

n=8

3 4 2 1 7 8 5 6

來源：p14

http://www.csie.ntu.edu.tw/~sprout/11.%20Divide_Conquer.pptx

#include <iostream>

#include <queue>

using namespace std;

int main(){

      int n;

      cin >>n;

      int m = n/3-1;

      if (n%3!=0) m++;

      queue<int> p;

      queue<int> q1;

      queue<int> q2;

      p.push(2);p.push(3),p.push(1);

      for (int i=0;i<m;i++){

           // q1=2*p-1

           // q2=2*p

           while(!p.empty()){

                 int a = p.front();

                 q1.push(a*2-1);

                 q2.push(a*2);        

                 p.pop();

           }

           // p = q1+q2

           while(!q1.empty()){

                 p.push(q1.front());

                 q1.pop();

           }

           while(!q2.empty()){

                 p.push(q2.front());

                 q2.pop();

           }

      }

      while(!p.empty()){

                 int a =  p.front(); p.pop();

                 if (a<=n) cout << a << " ";

           }

     

      system("pause");

      return 0;

}