分治法；非等差數列

輸入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;

}