对sort的进一步操作
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
vector<int> vec;
vector<int>::iterator p;
int cc;
vec.clear();
while(cin>>cc)
vec.push_back(cc);
sort(vec.begin(), vec.end());
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
sort(vec.begin(), vec.end(), greater<int>());
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
return 0;
}
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
vector<int> vec;
vector<int>::iterator p;
int cc;
vec.clear();
while(cin>>cc)
vec.push_back(cc);
sort(vec.begin(), vec.end());
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
sort(vec.begin(), vec.end(), greater<int>());
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
return 0;
}
泛型算法之stable_sort
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
int str[8] = {2, 3, 1, 1, 45, 32, 1, 0};
stable_sort(str, str + 8);
for(int i = 0; i < 8; i++)
cout<<str[i]<<" ";
cout<<endl;
return 0;
}
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
int str[8] = {2, 3, 1, 1, 45, 32, 1, 0};
stable_sort(str, str + 8);
for(int i = 0; i < 8; i++)
cout<<str[i]<<" ";
cout<<endl;
return 0;
}
泛型算法之unique
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
int str[8] = {0, 1, 1, 2, 3, 2, 1, 1};
vector<int> vec(str, str + 8);
vector<int>::iterator p, q;
p = vec.begin();
q = unique(vec.begin(), vec.end());
while(p != q)
cout<<*p++<<" ";
cout<<endl;
sort(vec.begin(), vec.end());
p = vec.begin();
q = unique(vec.begin(), vec.end());
while(p != q)
cout<<*p++<<" ";
cout<<endl;
return 0;
}
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
int str[8] = {0, 1, 1, 2, 3, 2, 1, 1};
vector<int> vec(str, str + 8);
vector<int>::iterator p, q;
p = vec.begin();
q = unique(vec.begin(), vec.end());
while(p != q)
cout<<*p++<<" ";
cout<<endl;
sort(vec.begin(), vec.end());
p = vec.begin();
q = unique(vec.begin(), vec.end());
while(p != q)
cout<<*p++<<" ";
cout<<endl;
return 0;
}
unique()虽然去掉容器中的重复值，但是只去掉相邻的重复值。
为达到每次只出现单个字母一次的目的，需对其先排序。
unique()操作容器的长度并没有改变，每个独一无二的元素被放到从头开始的下一个自由槽中。
实际上结果为01231223,序列1223是算法的废弃部分，unique()返回一个iterator指向废弃部分的开始处，
典型情况下，这个iterator被传递给相关的容器操作erase()来删除无效元素。
为达到每次只出现单个字母一次的目的，需对其先排序。
unique()操作容器的长度并没有改变，每个独一无二的元素被放到从头开始的下一个自由槽中。
实际上结果为01231223,序列1223是算法的废弃部分，unique()返回一个iterator指向废弃部分的开始处，
典型情况下，这个iterator被传递给相关的容器操作erase()来删除无效元素。
泛型算法之copy,back_inserter
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
vector<int> v1, v2;
vector<int>::iterator p;
v1.clear(); v2.clear();
for(int i = 1; i <= 10; i++)
v1.push_back(i);
copy(v1.begin(), v1.end(), back_inserter(v2));
//copy算法把一对iterator当做二个参数，用其标记要拷贝的元素范围，
//第三个实参是一个iterator，标记要拷贝元素将被放置的起始位置
//back_inserter被称作iterator适配器;使元素被插入到作为实参的vector的尾部。
p = v2.begin();
while(p != v2.end())
cout<<*p++<<endl;
return 0;
}
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
vector<int> v1, v2;
vector<int>::iterator p;
v1.clear(); v2.clear();
for(int i = 1; i <= 10; i++)
v1.push_back(i);
copy(v1.begin(), v1.end(), back_inserter(v2));
//copy算法把一对iterator当做二个参数，用其标记要拷贝的元素范围，
//第三个实参是一个iterator，标记要拷贝元素将被放置的起始位置
//back_inserter被称作iterator适配器;使元素被插入到作为实参的vector的尾部。
p = v2.begin();
while(p != v2.end())
cout<<*p++<<endl;
return 0;
}
泛型算法之find
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
int str[10], cc = 1;
vector<int> ivec;
list<int> ilist;
ivec.clear();
ilist.clear();
for(int i = 0; i < N; i++)
{
str[i] = cc;
ivec.push_back(cc + 10);
ilist.push_back(cc + 20);
cc++;
}
while(cin>>cc)
{
if(find(str, str + N, cc) != str + N)
cout<<"在数组中找到"<<endl;
if(find(ivec.begin(), ivec.end(), cc) != ivec.end())
cout<<"在vector中找到"<<endl;
if(find(ilist.begin(), ilist.end(), cc) != ilist.end())
cout<<"在list中找到"<<endl;
}
return 0;
}
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
const int N = 10;
int main()
{
int str[10], cc = 1;
vector<int> ivec;
list<int> ilist;
ivec.clear();
ilist.clear();
for(int i = 0; i < N; i++)
{
str[i] = cc;
ivec.push_back(cc + 10);
ilist.push_back(cc + 20);
cc++;
}
while(cin>>cc)
{
if(find(str, str + N, cc) != str + N)
cout<<"在数组中找到"<<endl;
if(find(ivec.begin(), ivec.end(), cc) != ivec.end())
cout<<"在vector中找到"<<endl;
if(find(ilist.begin(), ilist.end(), cc) != ilist.end())
cout<<"在list中找到"<<endl;
}
return 0;
}
Word之虚拟文本功能
为排版专业工作者准备。
在word中输入: =rand(200,99),再敲回车
=rand(m,n) + 回车, 将产生m段，每段包含n个句子。m <= 200, n <= 99
The quick brown fox jumps over the lazy dog.（这是包含26个字母的最短英文句子）
那只敏捷的棕毛狐狸跃过那只懒狗。
map的三种插入操作
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, int> M;
M.clear();
/*用下标初始化*/
M[string("i1")] = 1;
/*用pair初始化*/
M.insert(pair<string, int>(string("i2"), 2));
/*直接用内置的value_type初始化*/
M.insert(map<string, int>::value_type ("i3", 3));
map<string, int>::iterator p = M.begin();
while(p != M.end())
{
cout<<"first: "<<p->first<<" secnd: "<<p->second<<endl;
p++;
}
return 0;
}
#include <algorithm>
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, int> M;
M.clear();
/*用下标初始化*/
M[string("i1")] = 1;
/*用pair初始化*/
M.insert(pair<string, int>(string("i2"), 2));
/*直接用内置的value_type初始化*/
M.insert(map<string, int>::value_type ("i3", 3));
map<string, int>::iterator p = M.begin();
while(p != M.end())
{
cout<<"first: "<<p->first<<" secnd: "<<p->second<<endl;
p++;
}
return 0;
}
对容器的一些操作
vector附初值vector<int> ivec(vec_size, 100);
list 附初值list<int> ilist(list_size, 11);
list类型的重新设置容器长度 ilist.resize(2 * ilist.size());
容器类型是支持一组关系操作符的，可以用来比较二个容器大小(<,>,=)。不过，对于能够定义的容器的类型有三个限制
<1>.元素类型必须支持等于操作符
<2>.元素类型必须支持小于操作符
<3>.元素类型必须支持一个缺省值。
迭代器(iterator)提供一种一般化的方法，对顺序或关联容器类型中的每个元素进行连续访问。
通过数组实现vector的初始化:
int cc[4] = {1, 2, 3, 4};
vector<int> ivec(cc, cc + 4);第二个指针指向的对象不包含在要被拷贝或遍历的元素之中。
任意位置插入元素:
ivec.insert(ivec.begin(), 100);
更加随机化的插法：
q = find(ivec.begin(), ivec.end(), 5);
ivec.insert(q, 99);
第一个参数是一个位置，第二个参数是将要被插入的值，这个值将被插入到有iterator指向的位置的前面。
在某个位置插入指定数量的元素:
ivec.insert(ivec.begin(), 10, -1);在begin()位置插入10个-1
向容器插入一段范围内的元素:
ivec.insert(ivec.begin(),cc, cc + 4);
泛型算法：把所有容器类型的公共操作抽取出来，形成一个通用算法集合，它能够被应用到全部容器类型以及内置数组类型上。
vector PK list
vector表示一段连续的内存区域，每个元素被顺序存储在这段内存中。对vector的随机访问效率很高，因为每次访问离vector起始处的位移都是固定的。但是，在任意位置，而不是vector的末尾插入/删除元素，其效率很低，需要把待插入/删除元素的右边的每个元素的复制一遍。
list表示非连续的内存区域，并通过一对指向首尾元素的指针双向链接起来，从而是允许向前和向后二个方向进行遍历的。在list的任意位置插入和删除元素的效率很高：指针必须被重新赋值，但不需拷贝元素来实现移动。另一方面，它对于随机访问效率不高：访问一个元素需要遍历中间元素。
选择顺序容器类型的一些准则：
<1>.如果我们需要随机访问一个容器，则vector要比list好的多。
<2>.如果我们已知要存储元素的个数，则vector比list要好。
<3>.如果我们需要的不只是二端插入和删除元素，则list好。
<4>.除非我们需要在容器首部插入和删除元素，否则vector比deque好。
一个需要动态增长的vector必须分配一定的内存以便保存新的序列，按顺序拷贝旧序列的元素以及释放旧的内存。为提高效率，实际上vector并不是随每个元素的插入而增长自己，而是当vector需要增长自身时，它实际分配的空间比当前所需的空间要多一些。故而对于小的对象，vector在实践中的效率比list高。
八皇后问题（递归+非递归）
一．问题描述
在8×8格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45°或135°的斜线）上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。请用递归与非递归两种方法写出求出八皇后问题的算法。
二．解题思路描述
一个正确的解应当是每一列，每一行，每一条斜线上均只有一个皇后。
对于递归算法，本人才有模拟的方式进行，而且，我觉得开辟一个二维数组更显而易见。首先，从空棋盘开始摆放，保证第m行m个皇后互不攻击，然后摆放第m+1个皇后。当然对于第m+1个皇后可能有多种摆放方法，由此，我必须一一枚举，采用回溯策略是可行且合乎逻辑的。
而对于非递归算法，我只是借助于书本上一个递归改为非递归的框架，依次搭建而已。
在此过程中，我采用一维数组，一位对于八皇后问题，每一行不可能存在二个及二个以上的皇后，board[i]表示第i行棋盘摆放的位置为第board[i]列。递归方法借助于系统提供的栈，而我非递归算法的实现，仅仅是自己构造一个栈而已。
递归解法
#include <iostream>
#include <cstdio>
#include <sys/timeb.h>
using namespace std;
const int MAX_SIZE = 100;
enum flag {blank ='X',queen = 1};
char Chess[MAX_SIZE][MAX_SIZE];//棋盘图
int n;//解决n皇后问题
int total;//用于计摆放方式
void Init()
{//对棋牌进行初始化
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
Chess[i][j] = blank;
total = 0;//初始时有零中摆放方式
}
bool Judge(int r,int c)
{//判断(r,c)位置是否可放置
int i,j;
for(i = r + 1; i < n; i++)
if(Chess[i][c] == queen)
return false;//说明c列上已有一皇后
for(i = c + 1; i < n; i++)
if(Chess[r][i] == queen)
return false;//说明r行上已有一皇后
for(i = r + 1, j = c + 1; (i < n) && (j < n); i++, j++)
if(Chess[i][j] == queen)
return false;//45度斜线上已有一皇后
for(i = r + 1, j = c - 1; (i <n) && (j >= 0); i++, j--)
if(Chess[i][j] == queen)
return false;//135度斜线上已有一皇后
return true;//排除四种情况后，说明(r,c)点可放置皇后
}
void Backtrack(int k,int cnt)
{//回溯算法主程序
if(k < 0 || cnt == n)//棋牌摆放完毕 or 以摆满n后
{
if(cnt == n)
{
printf("No.%d:\n",++total);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
printf(" %c ",Chess[i][j]);
putchar('\n');
}
putchar('\n');
}
}
else
{
int r = k / n, c = k % n;
if(Judge(r,c))
{//可放置一皇后
Chess[r][c] = queen;
Backtrack(k-1,cnt+1);
Chess[r][c] = blank;
}
Backtrack(k-1,cnt);
}
}
int main()
{//此为主函数
timeb t1,t2;
long kk;
cout<<"输入皇后个数:";
while(cin>>n)
{
Init();
ftime(&t1);
Backtrack(n*n-1,0);
ftime(&t2);
cout<<"计算"<<n<<"后问题总共可有"<<total<<"种摆法!"<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}
#include <cstdio>
#include <sys/timeb.h>
using namespace std;
const int MAX_SIZE = 100;
enum flag {blank ='X',queen = 1};
char Chess[MAX_SIZE][MAX_SIZE];//棋盘图
int n;//解决n皇后问题
int total;//用于计摆放方式
void Init()
{//对棋牌进行初始化
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
Chess[i][j] = blank;
total = 0;//初始时有零中摆放方式
}
bool Judge(int r,int c)
{//判断(r,c)位置是否可放置
int i,j;
for(i = r + 1; i < n; i++)
if(Chess[i][c] == queen)
return false;//说明c列上已有一皇后
for(i = c + 1; i < n; i++)
if(Chess[r][i] == queen)
return false;//说明r行上已有一皇后
for(i = r + 1, j = c + 1; (i < n) && (j < n); i++, j++)
if(Chess[i][j] == queen)
return false;//45度斜线上已有一皇后
for(i = r + 1, j = c - 1; (i <n) && (j >= 0); i++, j--)
if(Chess[i][j] == queen)
return false;//135度斜线上已有一皇后
return true;//排除四种情况后，说明(r,c)点可放置皇后
}
void Backtrack(int k,int cnt)
{//回溯算法主程序
if(k < 0 || cnt == n)//棋牌摆放完毕 or 以摆满n后
{
if(cnt == n)
{
printf("No.%d:\n",++total);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
printf(" %c ",Chess[i][j]);
putchar('\n');
}
putchar('\n');
}
}
else
{
int r = k / n, c = k % n;
if(Judge(r,c))
{//可放置一皇后
Chess[r][c] = queen;
Backtrack(k-1,cnt+1);
Chess[r][c] = blank;
}
Backtrack(k-1,cnt);
}
}
int main()
{//此为主函数
timeb t1,t2;
long kk;
cout<<"输入皇后个数:";
while(cin>>n)
{
Init();
ftime(&t1);
Backtrack(n*n-1,0);
ftime(&t2);
cout<<"计算"<<n<<"后问题总共可有"<<total<<"种摆法!"<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}
非递归解法
#include <iostream>
#include <sys/timeb.h>
#define N 100
using namespace std;
int board[N];
int n,sum;
void init()
{
for(int i = 1; i <= n; i++)
board[i] = 0;
}
void display()
{
int i,j;
cout<<"No."<<sum<<endl;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(board[i] == j)
cout<<"Q ";
else
cout<<"X ";
cout<<endl;
}
cout<<endl;
}
bool canPut(int k)
{
for(int i = 1; i < k; i++)
if((abs(k - i) == abs(board[k] - board[i])) || board[i] == board[k])
return false;//1.是否在同一斜线;2.是否位于同一列
return true;
}
void Backtrack()
{
board[1] = 0;
int k = 1;
while(k > 0)
{
board[k]++;
while((board[k] <= n) && !(canPut(k)))
board[k] += 1;
if(board[k] <= n)
if(k == n)
{
sum++;
display();
}
else
{
k++;
board[k] = 0;
}
else
k--;
}
}
int main()
{
timeb t1,t2;
long kk;
cout<<"输入皇后个数:";
while(cin>>n)
{
init();
sum = 0;
ftime(&t1);
Backtrack();
ftime(&t2);
cout<<"总共排列方式为:"<<sum<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}
#include <sys/timeb.h>
#define N 100
using namespace std;
int board[N];
int n,sum;
void init()
{
for(int i = 1; i <= n; i++)
board[i] = 0;
}
void display()
{
int i,j;
cout<<"No."<<sum<<endl;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(board[i] == j)
cout<<"Q ";
else
cout<<"X ";
cout<<endl;
}
cout<<endl;
}
bool canPut(int k)
{
for(int i = 1; i < k; i++)
if((abs(k - i) == abs(board[k] - board[i])) || board[i] == board[k])
return false;//1.是否在同一斜线;2.是否位于同一列
return true;
}
void Backtrack()
{
board[1] = 0;
int k = 1;
while(k > 0)
{
board[k]++;
while((board[k] <= n) && !(canPut(k)))
board[k] += 1;
if(board[k] <= n)
if(k == n)
{
sum++;
display();
}
else
{
k++;
board[k] = 0;
}
else
k--;
}
}
int main()
{
timeb t1,t2;
long kk;
cout<<"输入皇后个数:";
while(cin>>n)
{
init();
sum = 0;
ftime(&t1);
Backtrack();
ftime(&t2);
cout<<"总共排列方式为:"<<sum<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}