排列

output

0123
0132
0213
0231
0312
0321
1023
1032
1203
1230
1302
1320
2013
2031
2103
2130
2301
2310
3012
3021
3102
3120
3201
3210

code

#include <iostream>
#include <algorithm>
using namespace std;
int main () {
 int A[4];
 for(int i=0;i<4;i++)
 {
  for(int j=0;j<4;j++)
  {
   for(int k=0;k<4;k++)
   {
    for(int x=0;x<4;x++)
    {
     if(i==j||i==k||i==x||j==k||j==x||k==x)
     {
      continue;
     }
     else
     {
      cout<<i<<j<<k<<x<<endl;
     }
    }
   }
  }
 }
}

只算個數(final)

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int target; //目標值
int count=0;
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M]; //每一次抽中的球
 
 int *B=new int[N]; //讀進N顆球的數字
 for (int j=0;j<N;j++){
  cin >> B[j]; 
 }
 
 cin >> target;
 
 //產生所有可能重複排列，加以檢測
 for (int i=0;i<size;i++){
  
  int a=i;
  for (int j=0;j<M;j++){ //每一次抽中的球的序號
   A[j]= a%N ;
   a = a/N;
  }
 
  int amount=0;
  for (int j=0;j<M;j++){   
   amount+=B[A[M-j-1]];
  }
  
  if (amount==target){
   count++;   
  }
 }
 cout << count;
}

只算個數

a.out
16

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int target; //目標值
int count=0;
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M];
 
 int *B=new int[N]; //讀進N顆球的數字
 for (int j=0;j<N;j++){
  cin >> B[j]; 
 }
 
 cin >> target;
 
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   A[j]= a%N ;
   a = a/N;
  }
  int amount=0; 
  amount+=B[A[M-1]];
  for (int j=1;j<M;j++){
   
   amount+=B[A[M-j-1]];
  }
  
  if (amount==target){
   count++;   
  }
 }
 cout << count;
}

只有列出符合的

a.out

1+1+3+5=10
1+1+5+3=10
1+3+1+5=10
1+3+3+3=10
1+3+5+1=10
1+5+1+3=10
1+5+3+1=10
3+1+1+5=10
3+1+3+3=10
3+1+5+1=10
3+3+1+3=10
3+3+3+1=10
3+5+1+1=10
5+1+1+3=10
5+1+3+1=10
5+3+1+1=10

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int target; //目標值
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M];
 
 int *B=new int[N]; //讀進N顆球的數字
 for (int j=0;j<N;j++){
  cin >> B[j]; 
 }
 
 cin >> target;
 
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   A[j]= a%N ;
   a = a/N;
  }
  int amount=0; 
  amount+=B[A[M-1]];
  for (int j=1;j<M;j++){
   
   amount+=B[A[M-j-1]];
  }
  
  if (amount==target){
   cout << B[A[M-1]];
   for (int j=1;j<M;j++){
    cout << '+' << B[A[M-j-1]] ;   
   }
   cout << "=" << amount ;
   cout << endl;
  }
 }
}

N顆球抽M次球上有數字，求抽出的球上的數字的加總，加總數字是否為某個數字

a.in

3 4
1 3 5
10
a.out
1+1+1+1=4 N
1+1+1+3=6 N
1+1+1+5=8 N
1+1+3+1=6 N
1+1+3+3=8 N
1+1+3+5=10 Y
1+1+5+1=8 N
1+1+5+3=10 Y
1+1+5+5=12 N
1+3+1+1=6 N
1+3+1+3=8 N
1+3+1+5=10 Y
1+3+3+1=8 N
1+3+3+3=10 Y
1+3+3+5=12 N
1+3+5+1=10 Y
1+3+5+3=12 N
1+3+5+5=14 N
1+5+1+1=8 N
1+5+1+3=10 Y
1+5+1+5=12 N
1+5+3+1=10 Y
1+5+3+3=12 N
1+5+3+5=14 N
1+5+5+1=12 N
1+5+5+3=14 N
1+5+5+5=16 N
3+1+1+1=6 N
3+1+1+3=8 N
3+1+1+5=10 Y
3+1+3+1=8 N
3+1+3+3=10 Y
3+1+3+5=12 N
3+1+5+1=10 Y
3+1+5+3=12 N
3+1+5+5=14 N
3+3+1+1=8 N
3+3+1+3=10 Y
3+3+1+5=12 N
3+3+3+1=10 Y
3+3+3+3=12 N
3+3+3+5=14 N
3+3+5+1=12 N
3+3+5+3=14 N
3+3+5+5=16 N
3+5+1+1=10 Y
3+5+1+3=12 N
3+5+1+5=14 N
3+5+3+1=12 N
3+5+3+3=14 N
3+5+3+5=16 N
3+5+5+1=14 N
3+5+5+3=16 N
3+5+5+5=18 N
5+1+1+1=8 N
5+1+1+3=10 Y
5+1+1+5=12 N
5+1+3+1=10 Y
5+1+3+3=12 N
5+1+3+5=14 N
5+1+5+1=12 N
5+1+5+3=14 N
5+1+5+5=16 N
5+3+1+1=10 Y
5+3+1+3=12 N
5+3+1+5=14 N
5+3+3+1=12 N
5+3+3+3=14 N
5+3+3+5=16 N
5+3+5+1=14 N
5+3+5+3=16 N
5+3+5+5=18 N
5+5+1+1=12 N
5+5+1+3=14 N
5+5+1+5=16 N
5+5+3+1=14 N
5+5+3+3=16 N
5+5+3+5=18 N
5+5+5+1=16 N
5+5+5+3=18 N
5+5+5+5=20 N


#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int target; //目標值
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M];
 
 int *B=new int[N]; //讀進N顆球的數字
 for (int j=0;j<N;j++){
  cin >> B[j]; 
 }
 
 cin >> target;
 
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   A[j]= a%N ;
   a = a/N;
  }
  int amount=0;
  cout << B[A[M-1]];
  amount+=B[A[M-1]];
  for (int j=1;j<M;j++){
   cout << '+' << B[A[M-j-1]] ;
   amount+=B[A[M-j-1]];
  }
  cout << "=" << amount << " ";
  if (amount==target)
   cout << "Y";
  else
   cout << "N";
  cout << endl;
 }
}

N顆球抽M次球上有數字，求抽出的球上的數字的加總

a.in

3 4
1 3 5

a.out

1+1+1+1=4
1+1+1+3=6
1+1+1+5=8
1+1+3+1=6
1+1+3+3=8
1+1+3+5=10
1+1+5+1=8
1+1+5+3=10
1+1+5+5=12
1+3+1+1=6
1+3+1+3=8
1+3+1+5=10
1+3+3+1=8
1+3+3+3=10
1+3+3+5=12
1+3+5+1=10
1+3+5+3=12
1+3+5+5=14
1+5+1+1=8
1+5+1+3=10
1+5+1+5=12
1+5+3+1=10
1+5+3+3=12
1+5+3+5=14
1+5+5+1=12
1+5+5+3=14
1+5+5+5=16
3+1+1+1=6
3+1+1+3=8
3+1+1+5=10
3+1+3+1=8
3+1+3+3=10
3+1+3+5=12
3+1+5+1=10
3+1+5+3=12
3+1+5+5=14
3+3+1+1=8
3+3+1+3=10
3+3+1+5=12
3+3+3+1=10
3+3+3+3=12
3+3+3+5=14
3+3+5+1=12
3+3+5+3=14
3+3+5+5=16
3+5+1+1=10
3+5+1+3=12
3+5+1+5=14
3+5+3+1=12
3+5+3+3=14
3+5+3+5=16
3+5+5+1=14
3+5+5+3=16
3+5+5+5=18
5+1+1+1=8
5+1+1+3=10
5+1+1+5=12
5+1+3+1=10
5+1+3+3=12
5+1+3+5=14
5+1+5+1=12
5+1+5+3=14
5+1+5+5=16
5+3+1+1=10
5+3+1+3=12
5+3+1+5=14
5+3+3+1=12
5+3+3+3=14
5+3+3+5=16
5+3+5+1=14
5+3+5+3=16
5+3+5+5=18
5+5+1+1=12
5+5+1+3=14
5+5+1+5=16
5+5+3+1=14
5+5+3+3=16
5+5+3+5=18
5+5+5+1=16
5+5+5+3=18
5+5+5+5=20


#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M];
 
 int *B=new int[N]; //讀進N顆球的數字
 for (int j=0;j<N;j++){
  cin >> B[j]; 
 }
 
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   A[j]= a%N ;
   a = a/N;
  }
  int amount=0;
  cout << B[A[M-1]];
  amount+=B[A[M-1]];
  for (int j=1;j<M;j++){
   cout << '+' << B[A[M-j-1]] ;
   amount+=B[A[M-j-1]];
  }
  cout << "=" << amount << endl;
 }
}

N顆球抽M次球上有數字

球上有數字

a.in

3 4
1 3 5

a.out

1111
1113
1115
1131
1133
1135
1151
1153
1155
1311
1313
1315
1331
1333
1335
1351
1353
1355
1511
1513
1515
1531
1533
1535
1551
1553
1555
3111
3113
3115
3131
3133
3135
3151
3153
3155
3311
3313
3315
3331
3333
3335
3351
3353
3355
3511
3513
3515
3531
3533
3535
3551
3553
3555
5111
5113
5115
5131
5133
5135
5151
5153
5155
5311
5313
5315
5331
5333
5335
5351
5353
5355
5511
5513
5515
5531
5533
5535
5551
5553
5555

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M];
 
 int *B=new int[N]; //讀進N顆球的數字
 for (int j=0;j<N;j++){
  cin >> B[j]; 
 }
 
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   A[j]= a%N ;
   a = a/N;
  }
  for (int j=0;j<M;j++){
   cout << B[A[M-j-1]];
  }
  cout << endl;
 }
}

N顆球抽M次

a.in

3 4

a.out

0000
0001
0002
0010
0011
0012
0020
0021
0022
0100
0101
0102
0110
0111
0112
0120
0121
0122
0200
0201
0202
0210
0211
0212
0220
0221
0222
1000
1001
1002
1010
1011
1012
1020
1021
1022
1100
1101
1102
1110
1111
1112
1120
1121
1122
1200
1201
1202
1210
1211
1212
1220
1221
1222
2000
2001
2002
2010
2011
2012
2020
2021
2022
2100
2101
2102
2110
2111
2112
2120
2121
2122
2200
2201
2202
2210
2211
2212
2220
2221
2222

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw
int power(int n,int m){
 int result=1;
 for (int i=0;i<m;i++){result*=n;}
 return result;
}
int main () { 
 cin >> N >> M;
 int size=power(N,M);
 int *A=new int[M];
 for (int i=0;i<size;i++){
  int a=i;
  for (int j=0;j<M;j++){
   A[j]= a%N ;
   a = a/N;
  }
  for (int j=0;j<M;j++){
   cout << A[M-j-1];
  }
  cout << endl;
 }
}

重複排列, 袋中有 n 個不同的球，每次抽一顆，抽出後放回，抽m次，將每次抽出的球的編號記錄下來，總和是否為sum？共有幾種。

in

3 4 //3顆球 抽4次
1 3 5 //球上的數字
10 //抽出的球上面的數字的總和, 11 不可能

out

1 1 1 1 N //1+1+1+1=4, No
1 1 1 3 N
1 1 1 5 N
1 1 3 1 N
1 1 3 3 N
1 1 3 5 Y //1+1+3+5=10, Yes

a.in

3 4
1 3 5
10

a.out

1 1 1 1 N
1 1 1 3 N
1 1 1 5 N
1 1 3 1 N
1 1 3 3 N
1 1 3 5 Y
1 1 5 1 N
1 1 5 3 Y
1 1 5 5 N
1 3 1 1 N
1 3 1 3 N
1 3 1 5 Y
1 3 3 1 N
1 3 3 3 Y
1 3 3 5 N
1 3 5 1 Y
1 3 5 3 N
1 3 5 5 N
1 5 1 1 N
1 5 1 3 Y
1 5 1 5 N
1 5 3 1 Y
1 5 3 3 N
1 5 3 5 N
1 5 5 1 N
1 5 5 3 N
1 5 5 5 N
3 1 1 1 N
3 1 1 3 N
3 1 1 5 Y
3 1 3 1 N
3 1 3 3 Y
3 1 3 5 N
3 1 5 1 Y
3 1 5 3 N
3 1 5 5 N
3 3 1 1 N
3 3 1 3 Y
3 3 1 5 N
3 3 3 1 Y
3 3 3 3 N
3 3 3 5 N
3 3 5 1 N
3 3 5 3 N
3 3 5 5 N
3 5 1 1 Y
3 5 1 3 N
3 5 1 5 N
3 5 3 1 N
3 5 3 3 N
3 5 3 5 N
3 5 5 1 N
3 5 5 3 N
3 5 5 5 N
5 1 1 1 N
5 1 1 3 Y
5 1 1 5 N
5 1 3 1 Y
5 1 3 3 N
5 1 3 5 N
5 1 5 1 N
5 1 5 3 N
5 1 5 5 N
5 3 1 1 Y
5 3 1 3 N
5 3 1 5 N
5 3 3 1 N
5 3 3 3 N
5 3 3 5 N
5 3 5 1 N
5 3 5 3 N
5 3 5 5 N
5 5 1 1 N
5 5 1 3 N
5 5 1 5 N
5 5 3 1 N
5 5 3 3 N
5 5 3 5 N
5 5 5 1 N
5 5 5 3 N
5 5 5 5 N
16
code
#include <iostream>
#include <stack>
 
using namespace std;
 
int N,M; //#balls, #draw  
int main () { 
 int *A,target;  int amountofy=0;
 
 int  size=1;
 cin>>N>>M;
 A= new int [N];
 for(int i=0;i<N;i++)
 {
  cin>>A[i];
 }
 cin>>target;
 for(int i=0;i<M;i++)
 {
  size=size*N;
 }
 
 for(int i=0;i<size;i++ )
 {
  stack<int >S;int a=i;
  for(int j=0;j<M;j++){
   S.push (a%N);
   a=a/N;
  }
  int amount =0;
 
  for(int x=0;x<M;x++)
  {
   cout << A[S.top()] << ' ';
   amount+=A[S.top()];
   S.pop();
   
  }
  if (amount==target){ cout <<"Y";amountofy++;}
  else cout <<"N";
  cout<<endl;
 
 }
 cout<<amountofy;
}

應用(GJL版本)

p.in

5
2 3 5 7 9

p.out

99929

#include <iostream>
#include <cmath>
using namespace std;
int N,M; //#balls, #draw  
int main () { 
 int *A,N,*B;
 cin >> N;
 int size=(int)pow((float)N,(float)N);
 
 A=new int[N];
 B=new int[size];
 for(int i=0;i<N;i++)
 {
  cin>>A[i];
 
 }
 
 for (int i=0;i<size;i++){
  int a=i;
  int amount=0;
  for (int j=0;j<N;j++){
   amount=amount*10+A[a%N];
 
   //cout << A[a%N] << ' ';
   a =  a/N;
  }   
  B[i]=amount;
  //cout << endl;
 } 
 int max=0;
 for(int i=0;i<size;i++)
 { bool prime =true;
 for(int y=2;y<B[i];y++){
  if(B[i]%y==0){prime=false;break;}
 }
 
 if(prime==true){//cout<<B[i]<<endl;
 if(B[i]>max){max=B[i];}
 
 }
 }
 cout<<max;
}

應用

由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;

}